11.6 The QR Algorithm for Real Hessenberg Matrices 487 means that good choices for the shifts s may be complex,apparently necessitating complex arithmetic. Complex arithmetic can be avoided.however,by a clever trick.The trick depends on a result analogous to the lemma we used for implicit shifts in $11.3.The lemma we need here states that if B is a nonsingular matrix such that B.Q=Q.H (11.6.3) where Q is orthogonal and H is upper Hessenberg,then Q and H are fully determined by the first column of Q.(The determination is unique if H has positive subdiagonal elements.)The lemma can be proved by induction analogously to the proof given for tridiagonal matrices in $11.3. The lemma is used in practice by taking two steps of the OR algorithm, 菲 either with two real shifts ks and k+1,or with complex conjugate values ks and s+1=k*.This gives a real matrix As+2,where 会 A+2=Q+1Q。A..QT.oT+1 (11.6.4) The Q's are determined by 9 Ag-k1=Q.R。 (11.6.5) As+1=Q。·A。·Q (11.6.6) As+1-ks+11=Qg+1·Rs+1 (11.6.7) Using (11.6.6),equation (11.6.7)can be rewritten A。-k+11=Qf.Q+1·Rg+1·Q。 (11.6.8) Hence,if we define M=(Ag-k+11)·(Ag-ks1) (11.6.9) equations (11.6.5)and (11.6.8)give Numer R=Q·M (11.6.10) where Q=Qs+1·Q (11.6.11) R=Rg+1·Rs (11.6.12) Equation (11.6.4)can be rewritten A。·Q=Q·A+2 (11.6.13) 品 Thus suppose we can somehow find an upper Hessenberg matrix H such that A。.0=o.H (11.6.14) where Qis orthogonal.Ifhas the same first column as QT(ie.,Qhas the same first row as Q),then Q=Q and As+2 =H.11.6 The QR Algorithm for Real Hessenberg Matrices 487 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). means that good choices for the shifts ks may be complex, apparently necessitating complex arithmetic. Complex arithmetic can be avoided, however, by a clever trick. The trick depends on a result analogous to the lemma we used for implicit shifts in §11.3. The lemma we need here states that if B is a nonsingular matrix such that B · Q = Q · H (11.6.3) where Q is orthogonal and H is upper Hessenberg, then Q and H are fully determined by the first column of Q. (The determination is unique if H has positive subdiagonal elements.) The lemma can be proved by induction analogously to the proof given for tridiagonal matrices in §11.3. The lemma is used in practice by taking two steps of the QR algorithm, either with two real shifts ks and ks+1, or with complex conjugate values ks and ks+1 = ks*. This gives a real matrix As+2, where As+2 = Qs+1 · Qs · As · QT s · QT s+1· (11.6.4) The Q’s are determined by As − ks1 = QT s · Rs (11.6.5) As+1 = Qs · As · QT s (11.6.6) As+1 − ks+11 = QT s+1 · Rs+1 (11.6.7) Using (11.6.6), equation (11.6.7) can be rewritten As − ks+11 = QT s · QT s+1 · Rs+1 · Qs (11.6.8) Hence, if we define M = (As − ks+11) · (As − ks1) (11.6.9) equations (11.6.5) and (11.6.8) give R = Q · M (11.6.10) where Q = Qs+1 · Qs (11.6.11) R = Rs+1 · Rs (11.6.12) Equation (11.6.4) can be rewritten As · QT = QT · As+2 (11.6.13) Thus suppose we can somehow find an upper Hessenberg matrix H such that As · QT = QT · H (11.6.14) where Q is orthogonal. If QT has the same first column as QT (i.e., Q has the same first row as Q), then Q = Q and As+2 = H