The QR Algorithm for Eigenvalues
The standard dense eigenvalue method: repeatedly factor a matrix into orthogonal times triangular, then reverse the product.
The basic iteration
The QR algorithm computes all eigenvalues of a dense matrix. Each step factors the current matrix A into an orthogonal matrix Q times an upper-triangular matrix R (a QR factorization), then forms the new matrix as R times Q. This new matrix is orthogonally similar to the old one, so it has the same eigenvalues, and under mild conditions the iterates converge to an upper-triangular (or block-triangular) form whose diagonal reveals the eigenvalues.
Why it works
The QR iteration is a disguised simultaneous power iteration: it drives all invariant subspaces to converge at once, with the eigenvalues emerging in order of magnitude along the diagonal. This connection to the power method explains both its convergence and its rate.
Making it practical
- First reduce A to upper-Hessenberg form (or tridiagonal, if symmetric) by orthogonal transformations; this is a one-time cost that makes each QR step cheap
- Apply shifts (Wilkinson shift) to accelerate convergence dramatically, often achieving cubic convergence per eigenvalue
- Deflate converged eigenvalues by splitting off rows and columns, shrinking the active problem
- Use the implicit double-shift (Francis) step to handle complex conjugate eigenvalue pairs in real arithmetic without complex numbers
The workhorse of dense linear algebra
With Hessenberg reduction, shifts, and deflation, the shifted QR algorithm is the method behind essentially every dense eigenvalue routine in LAPACK. It is used for small-to-moderate dense matrices; for large sparse matrices where only a few eigenvalues are needed, Lanczos and Arnoldi are preferred instead. It also underlies the singular value decomposition, which applies a QR-type iteration to a bidiagonal form.