MATH 6610 Lecture 20 - The QR Algorithm with Shifts

Sep 21, 2026

Uploaded by Jiven

Lecture 20 focuses on eigenvalue computation using the QR algorithm, starting from the basic QR iteration for Hermitian matrices. It explains the QR step (A=QR then A←RQ), connects QR to simultaneous power iteration, and discusses convergence speed relative to power iteration. The lecture then develops links between QR iteration and inverse iteration, including an unshifted inverse iteration viewpoint. Finally, it motivates how shifting can enable a Rayleigh-iteration-like method and presents the shifted QR update rule.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages21

Reading Time53 min

AccessFree to download

Eigenvalue algorithms: The QR algorithm with shifts

The QR algorithm (Hermitian case)

QR algorithm and inverse iteration (I)

QR algorithm and inverse iteration (II)

The QR algorithm with shifts

L20-S00 Eigenvalue algorithms: The QR algorithm with shifts MATH 6610 Lecture 20 October 26, 2020 Trefethen & Bau: Lecture 29 L20-S01 The QR algorithm Assume A is Hermitian. The QR algorithm for computing eigenvalues: 1. Compute A 􀀐 QR, the QR decomposition of A 2. Replace A by the procedure A Ð RQ 3. Return to step 1 We've seen that this is just simultaneous power iteration. L20-S01 The QR algorithm Assume A is Hermitian. The QR algorithm for computing eigenvalues: 1. Compute A 􀀐 QR, the QR decomposition of A 2. Replace A by the procedure A Ð RQ 3. Return to step 1 We've seen that this is just simultaneous power iteration. which also means that it converges as “quickly” as power iteration. Can we instead develop a Rayleigh iteration type of algorithm? L20-S02 QR algorithm and inverse iteration, I (Unshifted) inverse iteration: power iteration on A􀀁1 . The QR algorithm performs power iteration. L20-S02 QR algorithm and inverse iteration, I (Unshifted) inverse iteration: power iteration on A􀀁1 . The QR algorithm performs power iteration. The QR algorithm also performs unshifted inverse iteration. L20-S02 QR algorithm and inverse iteration, I (Unshifted) inverse iteration: power iteration on A􀀁1 . The QR algorithm performs power iteration. The QR algorithm also performs unshifted inverse iteration. Recall: if QQkR is the QR factor computed at the kth iteration, then Ak 􀀐 QkRk ; Qk 􀀐 QQ1R QQR2 􀀄 􀀄 􀀄 QQkR ; and Rk is an upper-triangular matrix. L20-S03 QR algorithm and inverse iteration, II Let F be a permutation matrix that ﬂips a vector, i.e. , associated to the permutation map: t1; 2; : : : ; n 􀀁 1; nu ÝÑ tn; n 􀀁 1 ; : : : ; 2 ; 1u : Then: L20-S03 QR algorithm and inverse iteration, II Let F be a permutation matrix that ﬂips a vector, i.e. , associated to the permutation map: t1; 2; : : : ; n 􀀁 1; nu ÝÑ tn; n 􀀁 1 ; : : : ; 2 ; 1u : Then: A􀀁kF 􀀐 pQkF q 􀀀FRT F􀀈 ; which is a QR factorization of A􀀁kF. I.e. , the last column(s) of Qk (computed via the QR algorithm) are inverse iteration with starting vectors given by the ﬁrst columns of F. The QR algorithm with shifts L20-S04 We can almost perform Rayleigh iteration with QR procedures. We can perform inverse iteration; how to accomplish shifting? L20-S04 The QR algorithm with shifts We can almost perform Rayleigh iteration with QR procedures. We can perform inverse iteration; how to accomplish shifting? Before explaining the shift, we show the result: The QR algorithm with shifts. Set AQR0 􀀐 A and 􀀖0 􀀐 0. For k 􀀐 1 ; 2 ; : : : ; QQkRRQRk 􀀐 AQk1 􀀁 􀀖k􀀁1I AQkR 􀀐 RQRkQQkR 􀀀 􀀖k􀀁1I “Choose” 􀀖 k

FAQs

What are the basic steps of the QR algorithm for computing eigenvalues of a Hermitian matrix?

Compute the QR decomposition A=QR, then replace A by the product RQ and repeat the process on the updated matrix.

How does the QR algorithm relate to power iteration and convergence behavior?

For Hermitian A, the QR algorithm can be viewed as a form of simultaneous power iteration, so its convergence is comparable to power iteration in speed.

How is the QR algorithm connected to inverse iteration, and how can shifting be incorporated?

The QR algorithm also performs an unshifted inverse iteration viewpoint, and the lecture discusses how shifting is needed to achieve a Rayleigh-iteration-like algorithm via a shifted QR procedure.

Sep 21, 2026

Uploaded by Jiven