472 Chapter 11. Eigensystems Now choose the vector x for the second Householder matrix to be the bottom n-2 elements of the second column,and from it construct 10 0 0 01 0 0 P2三 00 (11.2.9) (m-2)P2 0 0 The identity block in the upper left corner insures that the tridiagonalization achieved .com or in the first step will not be spoiled by this one,while the (n-2)-dimensional Householder matrix(-2)P2 creates one additional row and column ofthe tridiagonal output.Clearly,a sequence of n-2 such transformations will reduce the matrix A to tridiagonal form. Instead of actually carrying out the matrix multiplications in P.A.P,we 彩 compute a vector ⊙ 2 p (11.2.10) Then 三9 Press. A.P=A(1-")=A-pu7 Program 9 A'=P.A.P=A-p.uT-u.pT+2Ku.uT where the scalar K is defined by CIENTIFIC 6 ur·p K= 2H (11.2.11) If we write q≡p-Ku (11.2.12) COMPUTING (ISBN 1992 then we have A'=A-q.uT-u.qT (11.2.13) 、君0m Numerical 10621 This is the computationally useful formula. 43106 Following [2],the routine for Householder reduction given below actually starts in the nth column of A,not the first as in the explanation above.In detail,the equations are as follows:At stage m (m =1,2,...,n-2)the vector u has the form uT=[a1,02,,ai,i-2,ai,i-1±VG,0,,0] (11.2.14) Here i≡n-m+1=n,n-1,…,3 (11.2.15) and the quantity o(2 in our earlier notation)is 0=(a)2+…+(a.-1)2 (11.2.16) We choose the sign of a in (11.2.14)to be the same as the sign of ai.-1 to lessen roundoff error.472 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). Now choose the vector x for the second Householder matrix to be the bottom n − 2 elements of the second column, and from it construct P2 ≡          1 0 0 ··· 0 0 1 0 ··· 0 0 0 . . . . . . (n−2)P2 0 0          (11.2.9) The identity block in the upper left corner insures that the tridiagonalization achieved in the first step will not be spoiled by this one, while the (n − 2)-dimensional Householder matrix (n−2)P2 creates one additional row and column of the tridiagonal output. Clearly, a sequence of n − 2 such transformations will reduce the matrix A to tridiagonal form. Instead of actually carrying out the matrix multiplications in P · A · P, we compute a vector p ≡ A · u H (11.2.10) Then A · P = A · (1 − u · uT H ) = A − p · uT A = P · A · P = A − p · uT − u · pT + 2Ku · uT where the scalar K is defined by K = uT · p 2H (11.2.11) If we write q ≡ p − Ku (11.2.12) then we have A = A − q · uT − u · qT (11.2.13) This is the computationally useful formula. Following [2], the routine for Householder reduction given below actually starts in the nth column of A, not the first as in the explanation above. In detail, the equations are as follows: At stage m (m = 1, 2,...,n−2) the vector u has the form uT = [ai1, ai2,...,ai,i−2, ai,i−1 ± √σ, 0,..., 0] (11.2.14) Here i ≡ n − m +1= n, n − 1,..., 3 (11.2.15) and the quantity σ (|x| 2 in our earlier notation) is σ = (ai1) 2 + ··· + (ai,i−1) 2 (11.2.16) We choose the sign of σ in (11.2.14) to be the same as the sign of a i,i−1 to lessen roundoff error.