488 Chapter 11.Eigensystems The first row of Q is found as follows.Equation (11.6.10)shows that Q is the orthogonal matrix that triangularizes the real matrix M.Any real matrix can be triangularized by premultiplying it by a sequence of Householder matrices P1 (acting on the first column),P2(acting on the second column),...,Pn-1.Thus Q=Pn-1...P2.P1,and the first row of Q is the first row of P1 since Pi is an (i-1)x(i-1)identity matrix in the top left-hand corner.We now must find Q satisfying (11.6.14)whose first row is that of P. The Householder matrix P1 is determined by the first column of M.Since As is upper Hessenberg,equation (11.6.9)shows that the first column of M has the form pi,q1,r1,0,...,0],where p1=a11-a11(kg+kg+1)+kkg+1+a12a21 91=a21(a11+a22-kg-kg+1) (11.6.15) Cam T1=a21a32 RECIPES Hence P1=1-2w1·w (11.6.16) o Press. where wi has only its first 3 elements nonzero(cf.equation 11.2.5).The matrix P1.A.Pf is therefore upper Hessenberg with 3 extra elements: Programs ×1 XXXXXX × IENTIFIC X 6 P1·A1P= × (11.6.17) 千 19200 COMPUTING (ISBN This matrix can be restored to upper Hessenberg form without affecting the first row 10-621 by a sequence of Householder similarity transformations.The first such Householder matrix,P2,acts on elements 2,3,and 4 in the first column,annihilating elements Fuurggoglrion 43106 3 and 4.This produces a matrix of the same form as(11.6.17),with the 3 extra elements appearing one column over: (outside XX XX ×1 North Software. XX + + + 女 (11.6.18) × ××」 Proceeding in this way up to Pn-1,we see that at each stage the Householder matrix Pr has a vector wr that is nonzero only in elements r,r+1,and r+2. These elements are determined by the elements r,r+1,and r+2 in the(r-1)st488 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). The first row of Q is found as follows. Equation (11.6.10) shows that Q is the orthogonal matrix that triangularizes the real matrix M. Any real matrix can be triangularized by premultiplying it by a sequence of Householder matrices P 1 (acting on the first column), P2 (acting on the second column), ... , Pn−1. Thus Q = Pn−1 ··· P2 · P1, and the first row of Q is the first row of P1 since Pi is an (i − 1) × (i − 1) identity matrix in the top left-hand corner. We now must find Q satisfying (11.6.14) whose first row is that of P1. The Householder matrix P1 is determined by the first column of M. Since As is upper Hessenberg, equation (11.6.9) shows that the first column of M has the form [p1, q1, r1, 0, ..., 0]T , where p1 = a2 11 − a11(ks + ks+1) + ksks+1 + a12a21 q1 = a21(a11 + a22 − ks − ks+1) r1 = a21a32 (11.6.15) Hence P1 = 1 − 2w1 · wT 1 (11.6.16) where w1 has only its first 3 elements nonzero (cf. equation 11.2.5). The matrix P1 · As · PT 1 is therefore upper Hessenberg with 3 extra elements: P1 · A1 · PT 1 =          ××××××× ××××××× x ×××××× x x ××××× ×××× ××× × ×          (11.6.17) This matrix can be restored to upper Hessenberg form without affecting the first row by a sequence of Householder similarity transformations. The first such Householder matrix, P2, acts on elements 2, 3, and 4 in the first column, annihilating elements 3 and 4. This produces a matrix of the same form as (11.6.17), with the 3 extra elements appearing one column over:          ××××××× ××××××× ×××××× x ××××× x x ×××× ××× × ×          (11.6.18) Proceeding in this way up to Pn−1, we see that at each stage the Householder matrix Pr has a vector wr that is nonzero only in elements r, r + 1, and r + 2. These elements are determined by the elements r, r + 1, and r + 2 in the (r − 1)st