Re: convergence of QR-algorithm
From: Peter Spellucci (spellucci_at_fb04373.mathematik.tu-darmstadt.de)
Date: 03/22/05
- Next message: Torsten Hennig: "Re: Transforming expressions into ellipse normal form"
- Previous message: Peter Spellucci: "Re: Transforming expressions into ellipse normal form"
- In reply to: Jeremy Watts: "Re: convergence of QR-algorithm"
- Next in thread: hansm: "Re: convergence of QR-algorithm"
- Messages sorted by: [ date ] [ thread ]
Date: Tue, 22 Mar 2005 11:11:09 +0000 (UTC)
In article <QuO%d.13$it1.2@newsfe2-gui.ntli.net>,
"Jeremy Watts" <jwatts1970@hotmail.com> writes:
>
>"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?
>
nonconvergence of QR can occur if there are eigenvalues of same absolute value
which are different. ths is what hans did write already. this can occur without
shifts or after an unhappy shift. this is the reason why QR codes check for
convergence after a predefined number of steps and in case of nonconvergence
use "exception shifts" (which have nothing to do with your Rayleigh -Shift
or the Wilkinson shift. at least for symmetric matrices it is clear that the
Wilkinson shift based on the right lower 2 by 2 matrix is faster than the
Rayleigh -Shift.) since complex arithmetic has four times the cost of real
arithmetic, for real matrices the Francis double shift is indeed cheaper.
(if not special hardware is present which allows parallelization of the
multiplies in complex arithmetic)
but of course doing it all in complex arithmetic is simpler and also a random
complex shift will almost for sure break any set of eigenvalues of equal modulus and
hence enforce convergence.
hth
peter
>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
>>>
> >>
>>> >
>>>
>>>
>>
>>
>
>
- Next message: Torsten Hennig: "Re: Transforming expressions into ellipse normal form"
- Previous message: Peter Spellucci: "Re: Transforming expressions into ellipse normal form"
- In reply to: Jeremy Watts: "Re: convergence of QR-algorithm"
- Next in thread: hansm: "Re: convergence of QR-algorithm"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
