11.7 Eigenvalues or Eigenvectors by Inverse Iteration 493 CITED REFERENCES AND FURTHER READING: Wilkinson,J.H.,and Reinsch,C.1971,Linear Algebra,vol.Il of Handbook for Automatic Com- putation (New York:Springer-Verlag).[1] Golub,G.H.,and Van Loan,C.F.1989,Matrix Computations,2nd ed.(Baltimore:Johns Hopkins University Press),87.5. 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] 11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration The basic idea behind inverse iteration is quite simple.Let y be the solution of the linear system (A-T1).y=b (11.7.1) 令 where b is a random vector and r is close to some eigenvalue A of A.Then the 需 solution y will be close to the eigenvector corresponding to A.The procedure can be iterated:Replace b by y and solve for a new y,which will be even closer to the true eigenvector. Program We can see why this works by expanding both y and b as linear combinations of the eigenvectors xj of A: 色 OF SCIENTIFIC( 61 y=b=∑Bx (11.7.2) Then (11.7.1)gives ∑a-Ts=∑ (11.7.3) Numerica 10.621 so that 、86六 43106 月 =-T (11.7.4) (outside and y-刀月当 (11.7.5) 入-T If r is close to An,say,then provided Bn is not accidentally too small,y will be approximately xn,up to a normalization.Moreover,each iteration of this procedure gives another power ofj-in the denominator of(11.7.5).Thus the convergence is rapid for well-separated eigenvalues. Suppose at the kth stage of iteration we are solving the equation (A-k1)·y=bk (11.7.6)11.7 Eigenvalues or Eigenvectors by Inverse Iteration 493 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). 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] Golub, G.H., and Van Loan, C.F. 1989, Matrix Computations, 2nd ed. (Baltimore: Johns Hopkins University Press), §7.5. 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] 11.7 Improving Eigenvalues and/or Finding Eigenvectors by Inverse Iteration The basic idea behind inverse iteration is quite simple. Let y be the solution of the linear system (A − τ1) · y = b (11.7.1) where b is a random vector and τ is close to some eigenvalue λ of A. Then the solution y will be close to the eigenvector corresponding to λ. The procedure can be iterated: Replace b by y and solve for a new y, which will be even closer to the true eigenvector. We can see why this works by expanding both y and b as linear combinations of the eigenvectors xj of A: y =  j αjxj b =  j βjxj (11.7.2) Then (11.7.1) gives  j αj (λj − τ)xj =  j βjxj (11.7.3) so that αj = βj λj − τ (11.7.4) and y =  j βjxj λj − τ (11.7.5) If τ is close to λn, say, then provided βn is not accidentally too small, y will be approximately xn, up to a normalization. Moreover, each iteration of this procedure gives another power of λj − τ in the denominator of (11.7.5). Thus the convergence is rapid for well-separated eigenvalues. Suppose at the kth stage of iteration we are solving the equation (A − τk1) · y = bk (11.7.6)