the QR algorithm

The QR algorithm is the workhorse that computes ALL the eigenvalues of a dense matrix, and it is one of the most beautiful surprises in numerical mathematics. The bare idea is almost too simple to believe: factor the matrix as A = Q R (orthogonal Q times upper-triangular R, via QR factorization), then multiply the factors back together in the swapped order to form A_1 = R Q. Repeat. Astonishingly, this sequence of matrices marches toward upper-triangular form, and the eigenvalues appear on the diagonal.

Why does swapping the factors do anything useful? Note A_1 = R Q = Q^T (Q R) Q = Q^T A Q, a similarity transformation — so A_1 has exactly the same eigenvalues as A, just expressed in a rotated basis. Each iteration is one such orthogonal change of basis, and the magic is that these particular rotations gradually expose the eigenvalues: subdiagonal entries shrink to zero and the matrix becomes (block) triangular, whose diagonal entries are the eigenvalues. The deep reason is that the QR algorithm is secretly running the power method (and inverse iteration) on every eigenvector at once, in an orthogonalized form — the largest eigenvalue settles into the top-left, the smallest into the bottom-right.

Three engineering touches make it practical, and named together they form the algorithm actually used in LAPACK. First, reduce A to Hessenberg form (tridiagonal if symmetric) once up front so each QR step costs O(n^2) instead of O(n^3). Second, use SHIFTS: work on A - sigma I instead of A, choosing sigma near an eigenvalue (the Rayleigh-quotient or Wilkinson shift) to make the relevant subdiagonal entry collapse quadratically or cubically fast. Third, DEFLATE: once a subdiagonal entry is negligibly small, split off that eigenvalue and shrink the active matrix. With shifts and deflation the cost is about O(n^3) total to find every eigenvalue, and because every step is an orthogonal similarity, the whole process is backward stable.