486 Chapter 11. Eigensystems if(1！=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]) 1f(x)[ Carry out the elimination for(1=m+1;1<=n;1+)[ 1f((y=a[1][m-1])1=0.0)C y /=xi a[i][m-1]=y; for (j=m;j<=n;j++) http://www.nr. readable files a[i][j]-=y*a[m][j]; for (j=1;j<=n;j++) a[j][回间]+ey*a[j][i]; .com or call granted for 19881992 2 222 (including this one) 111800-672 /Cambridge NUMERICAL RECIPES IN CITED REFERENCES AND FURTHER READING: (Nort Wilkinson,J.H.,and Reinsch,C.1971,Linear Algebra,vol.Il of Handbook for Automatic Com- America users to make one paper server computer, University Press. THE putation (New York:Springer-Verlag).[1] Smith,B.T.,et al.1976,Matrix Eigensystem Routines-EISPACK Guide,2nd ed.,vol.6 of ART Lecture Notes in Computer Science (New York:Springer-Verlag).[2] Stoer,J.,and Bulirsch,R.1980,Introduction to Numerical Analysis (New York:Springer-Verlag). 9 Programs 66.5.4.[3] OF SCIENTIFIC 11.6 The QR Algorithm for Real Hessenberg Matrices 1920 MPUTING (ISBN Recall the following relations for the QR algorithm with shifts: Numerical 1021 Q·(Ag-kI)=Rg (11.6.1) 43108 where Q is orthogonal and R is upper triangular,and (outside Recipes A+1=R。·Q+k1 North Software. (11.6.2) =Q。·A。·Q7 visit website The QR transformation preserves the upper Hessenberg form of the original matrix A =A1,and the workload on such a matrix is O(n2)per iteration as opposed to O(n3)on a general matrix.As s-oo,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 811.3,shifting is essential for rapid convergence.A key difference here is that a nonsymmetric real matrix can have complex eigenvalues.This486 Chapter 11. Eigensystems Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). } } 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]) != 0.0) { 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, J.H., and Reinsch, C. 1971, Linear Algebra, vol. II of Handbook for Automatic Com￾putation (New York: Springer-Verlag). [1] Smith, B.T., 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 Numerical Analysis (New York: Springer-Verlag), §6.5.4. [3] 11.6 The QR Algorithm for Real Hessenberg Matrices Recall the following relations for the QR algorithm with shifts: Qs · (As − ks1) = Rs (11.6.1) where Q is orthogonal and R is upper triangular, and As+1 = Rs · QT s + ks1 = Qs · As · QT s (11.6.2) The QR transformation preserves the upper Hessenberg form of the original matrix A ≡ A1, and the workload on such a matrix is O(n2) per iteration as opposed to O(n3) on a general matrix. As s → ∞, As converges to a form where the eigenvalues are either isolated on the diagonal or are eigenvalues of a 2×2 submatrix on the diagonal. As we pointed out in §11.3, shifting is essential for rapid convergence. A key difference here is that a nonsymmetric real matrix can have complex eigenvalues. This