The QR Algorithm

The QR algorithm computes all eigenvalues of a matrix by repeated QR factorization, accelerated by Hessenberg reduction and shifts.

Iterating with orthogonal factorizations

The QR algorithm is the standard method for the full eigenvalue spectrum of a dense matrix. It factors the matrix as A = Q R, with Q orthogonal and R upper triangular, then forms the next iterate A' = R Q. This similarity transformation preserves eigenvalues while driving the matrix toward upper-triangular (Schur) form, exposing the eigenvalues on the diagonal.

Why it converges

Each QR step is implicitly related to power iteration on all invariant subspaces at once. Off-diagonal entries shrink geometrically at rates set by ratios of eigenvalues. Left alone this can be slow, so the practical algorithm adds two accelerations that make it fast and reliable.

Hessenberg reduction and shifts

• Hessenberg reduction first transforms the matrix to upper-Hessenberg form (one subdiagonal) with orthogonal similarities, cutting each QR step from O(n^3) to O(n^2).
• Shifts apply the algorithm to A - mu I with a well-chosen mu near an eigenvalue, accelerating convergence to cubic and letting eigenvalues be deflated one at a time.
• Wilkinson and double shifts handle complex eigenvalues of real matrices without complex arithmetic.

import numpy as np
def qr_algorithm(A, iters=500):
    Ak = A.astype(float).copy()
    for _ in range(iters):
        Q, R = np.linalg.qr(Ak)
        Ak = R @ Q
    return np.diag(Ak)   # eigenvalues (real symmetric case)

Reliability

The shifted QR algorithm with Hessenberg reduction is backward stable and is the engine behind eig routines in LAPACK and every major numerical library. For symmetric matrices it specializes to a tridiagonal QR that is especially fast and accurate. For very large sparse matrices, Krylov methods replace it since forming dense Q is infeasible.

Dense eigen-solvers of this kind analyze mode structure in reduced models supporting breeder Hyperion stability studies.