11.6 The QR Algorithm for Real Hessenberg Matrices 489 column of the current matrix.Note that the preliminary matrix P1 has the same structure as P2,...,Pn-1. The result is that Pn-1…P2P1·AgP.P…Pt-1=H (11.6.19) where H is upper Hessenberg.Thus =Q=Pn-1…P2·P1 (11.6.20 and As+2=H (11.6.21) The shifts of origin at each stage are taken to be the eigenvalues of the 2 x 2 matrix in the bottom right-hand corner of the current As.This gives ksks+2 an-1,n-1+ann (11.6.22) ksks+1 an-1,n-1ann -an-1,nan,n-1 RECIPES è Substituting (11.6.22)in (11.6.15),we get Press. p1=a21{[(ann-a11)(an-1,n-1-a11)-an-1,nan,n-1]/a21+a12} q1=a21[a22-a11-(ann-a11）-(an-1,n-1-a11] T1=a21a32 (11.6.23) We have judiciously grouped terms to reduce possible roundoff when there are IENTIFIC( small off-diagonal elements.Since only the ratios of elements are relevant for a Householder transformation,we can omit the factor a21 from(11.6.23). In summary,to carry out a double OR step we construct the Householder matrices Pr,r=1,...,n-1.For Pi we use p1,g,and ri given by (11.6.23).For the remaining matrices,pr,r,and rr are determined by the (r,r-1),(r+1,r-1), and (r+2,r-1)elements of the current matrix.The number of arithmetic 10621 operations can be reduced by writing the nonzero elements of the 2w.wT part of the Householder matrix in the form 43106 (p±s)/(±s) (outside 2w.w q/(±s) 1 q/(p±s)r/(p±s)] (11.6.24) 腿 r/（土s】 where s2=p2+g2+r2 (11.6.25) (We have simply divided each element by a piece of the normalizing factor;cf. the equations in $11.2.) If we proceed in this way,convergence is usually very fast.There are two possible ways of terminating the iteration for an eigenvalue.First,if an.n-1 becomes "negligible,"then ann is an eigenvalue.We can then delete the nth row and column11.6 The QR Algorithm for Real Hessenberg Matrices 489 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). column of the current matrix. Note that the preliminary matrix P1 has the same structure as P2,..., Pn−1. The result is that Pn−1 ··· P2 · P1 · As · PT 1 · PT 2 ··· PT n−1 = H (11.6.19) where H is upper Hessenberg. Thus Q = Q = Pn−1 ··· P2 · P1 (11.6.20) and As+2 = H (11.6.21) The shifts of origin at each stage are taken to be the eigenvalues of the 2 × 2 matrix in the bottom right-hand corner of the current A s. This gives ks + ks+2 = an−1,n−1 + ann ksks+1 = an−1,n−1ann − an−1,nan,n−1 (11.6.22) Substituting (11.6.22) in (11.6.15), we get p1 = a21 {[(ann − a11)(an−1,n−1 − a11) − an−1,nan,n−1]/a21 + a12} q1 = a21[a22 − a11 − (ann − a11) − (an−1,n−1 − a11)] r1 = a21a32 (11.6.23) We have judiciously grouped terms to reduce possible roundoff when there are small off-diagonal elements. Since only the ratios of elements are relevant for a Householder transformation, we can omit the factor a 21 from (11.6.23). In summary, to carry out a double QR step we construct the Householder matrices Pr, r = 1,...,n − 1. For P1 we use p1, q1, and r1 given by (11.6.23). For the remaining matrices, pr, qr, and rr are determined by the (r, r −1), (r + 1, r−1), and (r + 2, r − 1) elements of the current matrix. The number of arithmetic operations can be reduced by writing the nonzero elements of the 2w · w T part of the Householder matrix in the form 2w · wT =   (p ± s)/(±s) q/(±s) r/(±s)   · [ 1 q/(p ± s) r/(p ± s)] (11.6.24) where s2 = p2 + q2 + r2 (11.6.25) (We have simply divided each element by a piece of the normalizing factor; cf. the equations in §11.2.) If we proceed in this way, convergence is usually very fast. There are two possible ways of terminating the iteration for an eigenvalue. First, if a n,n−1 becomes “negligible,” then ann is an eigenvalue. We can then delete the nth row and column