4
$\begingroup$

I've implemented a version of the double-shift QR algorithm featured in this report from ETH Zurich (Begins on page 77). The algorithm takes advantage of the Implicit Q theorem by applying an orthogonal-similarity transformation to our original matrix (in Hessenberg) form. This introduces a 'bulge' which we then chase out of the matrix by applying successive householder reflectors. The end goal is to covert the original matrix to real schur form (Although not truly, since complex eigenvalues form as blocks along the diagonal). The pseudocode for the algorithm is as follows:

enter image description here

(I've implemented this particular algorithm in C)

However, when trying to solve companion matrices to retrieve the eigenvalues, I find it often gets things wrong. Even their example results with a $6 \times 6$ couldn't solve for all the eigenvalues:

enter image description here

enter image description here

Compare this to my results, which have much the same mistake: 

5.000000 6.000000 0.390635 -1.005053 -7.905002 7.702966 
-6.000000 5.000000 -10.791799 -2.710116 -14.579765 -19.663045 
0.000000 0.000000 3.491643 -2.656106 -4.440683 9.373136 
0.000000 0.000000 3.843327 -1.491643 -10.829108 -5.067750 
0.000000 0.000000 -0.000000 0.000000 4.000000 4.922432 
-0.000000 -0.000000 0.000000 0.000000 0.000000 3.000000

Even smaller matrices pose problems (though they are close) with very low tolerances:

Input: (Eigenvalues are: 4, -3, 2, -1)

2.000000 13.000000 -14.000000 -24.000000 
1.000000 0.000000 0.000000 0.000000 
0.000000 1.000000 0.000000 0.000000 
0.000000 0.000000 1.000000 0.000000

Output:

2.968869 11.491388 21.498124 17.801229 
0.535591 -1.968869 -3.241184 -2.692433 
-0.000000 0.000000 2.000000 1.078408 
0.000000 -0.000000 -0.000000 -1.000000

Can someone suggest what sort of improvements can be made to obtain better results? I've tried implementing another algorithm I found, but it provided worse results. Even when I ran it as-is through Matlab instead of my own C-version of the software.

Improve this question
$\endgroup$
4
  • $\begingroup$ The 2x2 block of H(11) that you've circled in red has eigenvalues of 1+-2i as expected. What do you think is wrong with this? $\endgroup$
    – Brian Borchers
    Aug 4, 2016 at 19:07
  • $\begingroup$ @BrianBorchers You must excuse me since I'm really not used to this sort of thing, but I thought it would be like the 5 (+/-) 6i, where it would be shown as a: {{1, 2}, {-2,1}} block. I suppose I am expected to retrieve it from this 2x2 block by solving for the eigenvalues instead of reading it off. I feel quite stupid having not thought of solving for the eigenvalues of the 2x2. $\endgroup$
    – Micrified
    Aug 4, 2016 at 19:22
  • 1
    $\begingroup$ It's pure luck that the upper left 2x2 block worked out the way it did. $\endgroup$
    – Brian Borchers
    Aug 4, 2016 at 21:34
  • $\begingroup$ Thank you. I didn't realize this. It's very helpful. If you can write it as an answer I could accept it. $\endgroup$
    – Micrified
    Aug 5, 2016 at 7:29

1 Answer 1

Reset to default
3
$\begingroup$

The matrix given as H(11) in your question actually does have the expected eigenvalues of $1 \pm 2i$, $5 \pm 6i$, $3$, and $4$. In particular, the eigenvalues of the 2x2 block circled in red are $1 \pm 2i$.

It's a matter of pure luck that the 2x2 block in the upper left has the form that it does, making it obvious that its eigenvalues of $5 \pm 6i$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.