# How to improve this double-shift QR algorithm for non-symmetric matrices?

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:

(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:

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.

• 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? – Brian Borchers Aug 4 '16 at 19:07
• @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. – Micrified Aug 4 '16 at 19:22
• It's pure luck that the upper left 2x2 block worked out the way it did. – Brian Borchers Aug 4 '16 at 21:34
• Thank you. I didn't realize this. It's very helpful. If you can write it as an answer I could accept it. – Micrified Aug 5 '16 at 7:29

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$.