The QR Algorithm

The The Power Method finds one eigenvalue at a time. The QR algorithm, the method behind standard eigenvalue routines, finds all of them at once. It uses the QR factorization over and over: $$A_0 = A,\qquad A_k = Q_kR_k\ \ (\text{factor}),\qquad A_{k+1} = R_kQ_k\ \ (\text{multiply in reverse order}).$$

Key idea

Each $A_{k+1} = Q_k^{T}A_kQ_k$ is similar to $A$, so it has the same eigenvalues. When the eigenvalues have different sizes, $A_k$ approaches an upper triangular matrix, and its diagonal approaches the eigenvalues, largest in size first. The entry below the diagonal in position $(i + 1, i)$ shrinks by about $\left|\frac{\lambda_{i+1}}{\lambda_i}\right|$ each step.

Why it works

From $A_k = Q_kR_k$ we get $R_k = Q_k^{T}A_k$, so $A_{k+1} = R_kQ_k = Q_k^{T}A_kQ_k$, and $Q_k^{T} = Q_k^{-1}$: a similarity. Why the triangle appears: the product $Q_0Q_1 \cdots Q_{k-1}$ is what you get from running the power method on a whole set of vectors at once, keeping them orthonormal. Its first column turns toward the dominant eigenvector, exactly as in the power method, which pushes the first column of $A_k$ toward $(\lambda_1, 0, \ldots, 0)$; the later columns follow with the next eigenvalues.

Worked example: One step

Take one step from $A_0 = \begin{bmatrix} 3 & 1 \\ 4 & 2 \end{bmatrix}$.

The first column $(3, 4)$ has length $5$: $\mathbf{q}_1 = (0.6, 0.8)$, and $\mathbf{q}_2 = (-0.8, 0.6)$.
$R_0 = Q_0^{T}A_0 = \begin{bmatrix} 5 & 2.2 \\ 0 & 0.4 \end{bmatrix}$.
Multiply in reverse order, $A_1 = R_0Q_0$. Row 1: $5(0.6) + 2.2(0.8) = 4.76$ and $5(-0.8) + 2.2(0.6) = -2.68$. Row 2: $0.4(0.8) = 0.32$ and $0.4(0.6) = 0.24$.
So $A_1 = \begin{bmatrix} 4.76 & -2.68 \\ 0.32 & 0.24 \end{bmatrix}$. Check: the trace is still $5$. The entry below the diagonal fell from $4$ to $0.32$.

Answer: $\begin{bmatrix} 4.76 & -2.68 \\ 0.32 & 0.24 \end{bmatrix}$

Worked example: Watching it converge

Continue the same example. How fast does the lower-left entry shrink?

$A_2$ has lower-left entry $0.0281$, $A_3$ has $0.00268$, $A_4$ has $0.000257$: about $\frac{1}{10}$ each step.
The eigenvalues are $\frac{5 \pm \sqrt{17}}{2} \approx 4.5616$ and $0.4384$, and $\frac{0.4384}{4.5616} \approx 0.096$. That is the predicted rate.
Meanwhile the diagonal of $A_4$ is $(4.5617, 0.4383)$: the eigenvalues, to about four digits.

Answer: by about $0.096$ per step

Worked example: Multiplying in the wrong order

What happens if each step forms $Q_kR_k$ instead of $R_kQ_k$?

$Q_kR_k$ is the factorization of $A_k$ itself, so the "new" matrix is $A_k$ again (up to round-off).
Nothing changes, step after step. The reversal of the order is the entire method.

Answer: nothing happens

The QR algorithm on a 3 × 3 symmetric matrix. Entries below the diagonal shrink at rates set by ratios of eigenvalues, and the diagonal settles on the eigenvalues.

Production codes add three ideas. They first reduce $A$ to Hessenberg form (zeros below the first subdiagonal), which makes each QR step cost $O(n^{2})$ instead of $O(n^{3})$. They use shifts, factoring $A_k - s_kI$ with $s_k$ near an eigenvalue, which turns the slow ratio into a tiny one, just as in Inverse and Shifted Power Methods. And they deflate: once a subdiagonal entry is negligible, the problem splits into smaller ones. All eigenvalues of an $n \times n$ matrix then cost roughly $10n^{3}$ operations.

Common mistake

Multiplying the factors back in the same order, $Q_kR_k$, which just gives $A_k$ again. The step is "factor, then multiply in reverse": $A_{k+1} = R_kQ_k$. Check: the new matrix should differ from the old one but keep the same trace and determinant.

The QR Algorithm

Practice

Builds on

Leads to

Sources and further reading