Re: convergence of QR-algorithm

From: Jeremy Watts (jwatts1970_at_hotmail.com)
Date: 03/22/05 

Date: Tue, 22 Mar 2005 05:59:12 GMT

"Bill Shortall" <pecos@cminet.net> wrote in message
news:d1nan8027pp@enews3.newsguy.com...
> 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.

Bill, yes I'm doing all of that., alongside using a shift that is the
element in the bottom right hand corner of the matrix of the current matrix
being worked upon.

 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.

I had a look at Francis's method and likely think it would be slower than
the one I'm using as it involves more calculation at each iteration. Unless
of course it involves fewer iterations. But my scheme isnt bad and usually
finds an eigenvalue after less than 10 iterations.

What I've done now is to use QR with shifts, and check for convergence in
the top or bottom of the diagonal (bottom invariably converges first but not
always), and then deflate the matrix as I explained in my original post. If
for a matrix which does not fully converge, then of the ones I have tested,
it does seem the case that the final two eigenvalues are left in this 2x2
block that does not converge.

So I have got my program to use Cramers rule on this block to retrieve the
final two and then use inverse iteration to hone them down completely. The
only problem I can see with this is if two bulges ever develop in a matrix -
one say near the top of the diagonal and the other at the bottom. In this
case convergence could never occur. Do you think this could ever happen?

Also would you say that using eigenvalues of the last 2x2 block as shifts
would be faster than my current scheme which simply uses the last element of
the diagonal?

thanks
>
> 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
>>
>>
>> >
>>
>>
>
>

Relevant Pages

  • Re: convergence of QR-algorithm
    ... >Bill, yes I'm doing all of that., alongside using a shift that is the ... In either case the bottom two elements below the diagonal should ... >the one I'm using as it involves more calculation at each iteration. ... >case convergence could never occur. ...
    (sci.math.num-analysis)
  • Re: Loop ? again
    ... Then move whats left of g:i to the bottom of a:c>then sort a:c. ... To fill these empty rows I need to shift whatever ... Dim dlr, slr As Long ...
    (microsoft.public.excel.misc)
  • Re: Loop ? again
    ... bottom of columns. ... To fill these empty rows I need to shift whatever ... the need to shift rows up in to fill those empty spaces. ... Dim dlr, slr As Long ...
    (microsoft.public.excel.misc)
  • Re: Loop ? again
    ... bottom of columns. ... the need to shift rows up in to fill those empty spaces. ... Dim dlr, slr As Long ... I would also like to sort the entries by oldest date first. ...
    (microsoft.public.excel.misc)
  • Re: Einstein interpretation of gravitational redshift is misleading
    ... As the receiver is moving relatively to the source, ... observe a blue shift due to the Doppler effect, ... mine shaft. ... Nu2 is the frequency of the signal received at the bottom. ...
    (sci.physics.relativity)