} } if (i != m) { Interchange rows and columns. for (j=m-1;j | 486 Chapter 11. Eigensystems if i m Interchange rows and columns. for j m-1 j n j SWAP a i j a m j for j 1 j n j SWAP a j i a j m if x Carry out the elimination. for i m 1 i n i if y a i m-1 y x a i m-1 y for j m j n j a i j - y a m j for j 1 j n j a j m y a j i CITED REFERENCES AND FURTHER READING Wilkinson . and Reinsch C. 1971 Linear Algebra vol. II of Handbook forAutomatic Computation New York Springer-Verlag . 1 Smith . et al. 1976 Matrix Eigensystem Routines EISPACK Guide 2nd ed. vol. 6 of Lecture Notes in Computer Science New York Springer-Verlag . 2 Stoer J. and Bulirsch R. 1980 Introduction to NumericalAnalysis New York Springer-Verlag . 3 The QR Algorithm for Real Hessenberg Matrices Recall the following relations for the QR algorithm with shifts Qs As - ks1 Rs where Q is orthogonal and R is upper triangular and As i Rs Or ks1 Qs As OT The QR transformation preserves the upper Hessenberg form of the original matrix A Ai and the workload on such a matrix is O n2 per iteration as opposed to O n3 on a general matrix. As s 1 As converges to a form where the eigenvalues are either isolated on the diagonal or are eigenvalues of a 2 x 2 submatrix on the diagonal. As we pointed out in shifting is essential for rapid convergence. A key difference here is that a nonsymmetric real matrix can have complex eigenvalues. Sample page from NUMERICAL RECIPES IN C THE ART OF SCIENTIFIC COMPUTING ISBN 0-521-43108-5 The QR Algorithm for Real Hessenberg Matrices 487 This means that good choices for the shifts ks may be complex apparently necessitating complex arithmetic. Complex arithmetic can be avoided however by a clever trick. The trick depends on a result analogous to the lemma we used for implicit shifts in . The lemma we need here states that if B is a nonsingular matrix such that B Q Q H where Q is orthogonal and H is upper Hessenberg then Q and H are fully determined by the first column of Q. The determination is
