Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 37 ยท Optimization and Eigenvalues

The QR Algorithm for All Eigenvalues

Compute every eigenvalue of a matrix by repeated QR factorization. Learn Gram-Schmidt QR, shifts, Hessenberg reduction, Jacobi's method and the SVD link.

The power method finds one eigenvalue at a time and slowly. The standard way to compute all eigenvalues is the QR algorithm, developed in the late 1950s and often listed among the most influential algorithms of the twentieth century. It is what sits behind np.linalg.eig (through LAPACK).

The core is surprisingly short: factor the matrix as A = Q R, multiply the factors back in the reverse order, and repeat. The sequence converges to a triangular matrix with the eigenvalues on its diagonal.

QR factorization

Any real square matrix factors as A = Q R, where Q is orthogonal (Q^T Q = I, columns of unit length at right angles) and R is upper triangular. Orthogonal matrices preserve lengths and are perfectly conditioned, which is why QR is trusted numerically. Two ways to compute it:

  • Gram-Schmidt: orthogonalize columns one by one. Simple to code but loses orthogonality for ill-conditioned matrices (use the modified version).
  • Householder reflections: reflect the columns to zero below the diagonal. This is the stable method used by LAPACK and np.linalg.qr.
Python QR by modified Gram-Schmidt

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The basic QR iteration

Start with A0 = A. At step k: factor Ak = Qk Rk, then set A(k+1) = Rk Qk. Since A(k+1) = Qk^T Ak Qk, every iterate is similar to A, so it has the same eigenvalues. Under mild conditions the iterates approach an upper triangular matrix (diagonal for symmetric A), and the diagonal entries are the eigenvalues, typically sorted by decreasing magnitude. Intuitively the QR iteration performs power iteration on all columns at once.

flowchart LR
  A["Ak = Qk Rk<br/>(factor)"] --> B["A(k+1) = Rk Qk<br/>(multiply reversed)"]
  B --> C["Similar to Ak:<br/>same eigenvalues"]
  C --> A
Python Basic unshifted QR iteration

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The off-diagonal part shrinks steadily while the diagonal settles on the eigenvalues. The convergence is again governed by ratios of eigenvalues, so close eigenvalues converge slowly.

Shifts, deflation and Hessenberg form

Production algorithms speed this up in three ways:

  1. Hessenberg reduction: first transform A by similarity into upper Hessenberg form (zero below the first subdiagonal; tridiagonal if A is symmetric) in O(n^3). Each QR step then costs only O(n^2) (or O(n) for tridiagonal).
  2. Shifts: factor Ak - mu I and add mu I back. If the shift mu approximates an eigenvalue, the last row converges to it in very few steps (like the shifts in inverse iteration). The plain corner entry (Rayleigh shift) can stall on symmetric matrices whose eigenvalues are symmetric about it; the Wilkinson shift, the eigenvalue of the trailing 2 by 2 block closer to the corner entry, is the standard safe choice.
  3. Deflation: when the last subdiagonal entry is negligible, the bottom diagonal entry is an eigenvalue. Remove that row and column and continue with a smaller matrix.
Python QR with Wilkinson shifts and deflation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

About two or three iterations per eigenvalue suffice. (The code assumes real eigenvalues, so it applies to symmetric matrices. General real matrices can have complex pairs, which need a double-shift variant.)

Other tools for the eigenproblem

  • Jacobi's method for symmetric matrices applies plane rotations that zero one off-diagonal entry at a time. It is slower than QR but very accurate and easy to parallelize.
  • Lanczos / Arnoldi methods (SciPy eigsh, eigs) compute a few eigenvalues of huge sparse matrices from matrix-vector products only.
  • Singular value decomposition: A = U S V^T. Singular values are the square roots of eigenvalues of A^T A, and the SVD is the most reliable tool for rank, conditioning and least squares (see least squares).
Python SciPy: dense, sparse and the SVD

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Conditioning of eigenvalues

For symmetric matrices, eigenvalues are well conditioned: a perturbation of size epsilon moves them by at most epsilon. For non-symmetric matrices they can be extremely sensitive, and the eigenvectors may be nearly parallel. Always check the residual |A v - lambda v|, not just that the algorithm ran.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the basic QR iteration, how is A(k+1) formed from Ak = Qk Rk?

    Multiplying the factors in reverse order gives a matrix similar to Ak, so eigenvalues are preserved.
  2. 2. Why is reducing to Hessenberg form first worthwhile?

    Hessenberg form is preserved by QR steps and makes each factorization much cheaper.
  3. 3. What does deflation do?

    When the last subdiagonal entry is negligible, the corner diagonal entry is an eigenvalue and the problem shrinks.
  4. 4. Which SciPy function finds a few eigenvalues of a large sparse symmetric matrix?

    eigsh uses Lanczos iteration and needs only matrix-vector products.

Summary

  • QR factorization splits a matrix into an orthogonal Q and upper triangular R; Householder is the stable way.
  • The QR iteration Ak = Qk Rk, A(k+1) = Rk Qk preserves eigenvalues and converges to a triangular matrix.
  • Hessenberg reduction, shifts and deflation make it fast; this is the core of LAPACK's eigenvalue solvers.
  • Use Lanczos/Arnoldi for a few eigenvalues of huge sparse matrices, and the SVD for rank and conditioning.

Next: Project: a projectile with air drag