The QR Algorithm

The QR algorithm is the workhorse of numerical eigenvalue computation. It computes all eigenvalues of a matrix simultaneously with guaranteed convergence and $O(n^3)$ cost (after reduction to Hessenberg form).

Basic QR Algorithm

Definition6.4QR Iteration

The basic QR algorithm produces a sequence of similar matrices: given $A_0 = A$ , compute the QR factorization $A_k = Q_k R_k$ and set $A_{k+1} = R_k Q_k = Q_k^T A_k Q_k$ . Since $A_{k+1}$ is unitarily similar to $A_k$ , all iterates share the same eigenvalues. Under mild conditions (distinct eigenvalue magnitudes), $A_k$ converges to upper triangular (or quasi-upper triangular in real arithmetic), with eigenvalues on the diagonal.

ExampleQR Algorithm on 2x2 Matrix

For $A = \begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix}$ : QR factorization gives $Q_0 = \frac{1}{\sqrt{5}}\begin{pmatrix} 1 & 2 \\ 2 & -1 \end{pmatrix}$ , $R_0 = \frac{1}{\sqrt{5}}\begin{pmatrix} 5 & 3 \\ 0 & -3 \end{pmatrix}$ (approximately). Then $A_1 = R_0 Q_0$ ; the off-diagonal entries shrink by a factor of $|\lambda_2/\lambda_1|^2 = 1/9$ per iteration. After a few iterations, $A_k \approx \begin{pmatrix} 3 & 0 \\ 0 & -1 \end{pmatrix}$ .

Shifted QR Algorithm

Definition6.5QR Algorithm with Shifts

The shifted QR algorithm uses $A_k - \sigma_k I = Q_k R_k$ , $A_{k+1} = R_k Q_k + \sigma_k I$ . The shift $\sigma_k$ accelerates convergence by targeting specific eigenvalues. The Wilkinson shift chooses $\sigma_k$ as the eigenvalue of the bottom-right $2 \times 2$ submatrix of $A_k$ that is closer to $a_{nn}^{(k)}$ . For symmetric matrices, the Wilkinson shift guarantees cubic convergence of the bottom-right entry to an eigenvalue.

RemarkImplicit QR and Hessenberg Form

Direct QR factorization costs $O(n^3)$ per step. Hessenberg reduction first transforms $A \to Q^T A Q = H$ (upper Hessenberg, $h_{ij} = 0$ for $i > j + 1$ ) in $O(n^3)$ operations using Householder reflectors. Each QR step on a Hessenberg matrix costs only $O(n^2)$ (using Givens rotations), and the result is again Hessenberg. The implicit QR algorithm (Francis algorithm) performs the shift without explicitly forming $A_k - \sigma_k I$ , using a "bulge chase" that maintains the Hessenberg structure.

Practical Implementation

Definition6.6Double Shift (Francis) QR Step

For real matrices with complex eigenvalues, the double-shift (Francis) QR step implicitly applies two shifts $\sigma, \bar{\sigma}$ (a complex conjugate pair) simultaneously, maintaining real arithmetic throughout. This is achieved by computing $M = (A - \sigma I)(A - \bar{\sigma} I)$ , taking only its first column, and performing a "bulge chase" with Householder reflectors to restore Hessenberg form.

ExampleConvergence Speed Comparison

For a $100 \times 100$ random symmetric matrix: unshifted QR requires $\sim 1000$ iterations to converge. With the Wilkinson shift: $\sim 2$ iterations per eigenvalue on average, for a total of $\sim 200$ iterations. Total cost: $O(n^3)$ for Hessenberg reduction plus $O(n^2)$ per eigenvalue extraction, giving an overall $O(n^3)$ algorithm.