Re: convergence of QR-algorithm

From: Bill Shortall (pecos_at_cminet.net)
Date: 03/21/05 

Date: Mon, 21 Mar 2005 13:27:17 -0700

Hi Jeremy,
   I assume you are working with a general real non symmetric or non
hermitian matrix and have reduced it to
upper hessenburg form. Consider the
2x2 matrix in the lower right corner. calculate the eigenvalues of this. If
they are complex do a qr iteration twice using first one eigenvalue then
it's conjugate. as the shift If they are real use one after the other as a
shift. In either case the bottom two elements below the diagonal should
slowly disappear. Forget about what happens in the upper left corner--
defate from the bottomDo all calculations in complex form completely. Double
check your QR decomposition make sure everything works in complex. This way
is very slow but it is easier to understand than the francis method.

  regards...bill shortall .. pecos_place()

"Jeremy Watts" <jwatts1970@hotmail.com> wrote in message
news:Woj%d.32203$3A6.26295@newsfe1-gui.ntli.net...
>
> "hansm" <mittelmann@asu.edu> wrote in message
> news:1111341866.314472.120360@g14g2000cwa.googlegroups.com...
> > Hi,
> > I strongly suggest you consult a good boock on numerical algebra and
> > study the QR algorithm. Things are much more complicated. If you work
> > in real arithmetic for complex-conjugate eigenvalues only a 2x2 block
> > will converge. However, if you have real deficient eigenvalues then
> > even a larger block will only converge. To make QR work and also be
> > efficient you have to apply a variety of measures such as initial
> > reduction to Hessenberg form, single/double shifts etc.
> > Books are Demmel, Golub&VanLoan etc
> > Hans Mittelmann
>
> Hello Hans,
>
> Yes I am working with complex arithmetic, and also reducing the matrix to
> Hessenberg form as a first step. I also add a 'complex shift' to the
> diagonal of the matrix if it is real, as this seems to ensure that the
> complex eigenvalues appear if there are any.
>
>
> Jeremy
>
>
> >
>
>