Why the QR Algorithm Dominates Eigenvalue Computation

This article provides an overview of why the QR algorithm is the undisputed standard for computing all eigenvalues of medium-sized matrices in numerical mathematics. While textbook algebra teaches students to find eigenvalues by solving the characteristic polynomial, this approach fails catastrophically in real-world computing due to rounding errors. The QR algorithm solves this problem by combining unmatched numerical stability with high computational efficiency. By utilizing orthogonal transformations, pre-processing matrices into simpler forms, and applying mathematical shifts for rapid convergence, the QR algorithm reliably and quickly extracts all eigenvalues from dense matrices containing up to a few thousand rows and columns.

The Failure of the Characteristic Polynomial

To understand why the QR algorithm is necessary, one must first understand why the standard algebraic method fails. In linear algebra courses, eigenvalues are found by computing the determinant of a matrix to form a characteristic polynomial, and then finding the roots of that polynomial.

In numerical computing, this approach is unusable for two reasons:

  1. The Abel-Ruffini Theorem: It is mathematically impossible to find an exact algebraic formula for the roots of a general polynomial of degree five or higher. Any method for matrices larger than 4x4 must be iterative.
  2. Extreme Instability: Finding the roots of a polynomial is notoriously sensitive to tiny rounding errors. A microscopic error in the matrix conversion can lead to massive errors in the calculated eigenvalues, a phenomenon famously demonstrated by Wilkinson's polynomial.

The QR algorithm completely bypasses the characteristic polynomial, working directly on the matrix itself.

Unmatched Numerical Stability

The primary reason the QR algorithm is the standard method is its backward stability. The algorithm works by repeatedly applying a two-step process: factoring a matrix into an orthogonal matrix (\(Q\)) and an upper triangular matrix (\(R\)), and then multiplying them in reverse order (\(RQ\)).

This process is a "similarity transformation," meaning the new matrix has the exact same eigenvalues as the original matrix. Because the transformation uses orthogonal matrices, it does not amplify floating-point rounding errors. In numerical analysis, orthogonal transformations are the gold standard because they preserve the geometric lengths and angles of vectors, ensuring that the computed eigenvalues are the exact eigenvalues of a matrix that is only microscopically different from the original.

Efficiency via Hessenberg Reduction

In its raw form, the QR algorithm is actually too slow for practical use, requiring \(O(n^3)\) operations for just a single iteration. To make it viable for medium-sized matrices, the algorithm is always paired with a pre-processing step.

Before the QR iterations begin, the matrix is reduced to upper Hessenberg form (a matrix that has zeros everywhere below the first subdiagonal). If the original matrix is symmetric, it is reduced to an even simpler tridiagonal form.

The QR algorithm preserves this Hessenberg structure during its iterations. This simple pre-processing step reduces the computational cost of each QR iteration from \(O(n^3)\) down to \(O(n^2)\) (or \(O(n)\) for symmetric matrices). This lowers the total cost of finding all eigenvalues to a manageable \(O(n^3)\), making it fast enough to solve matrices of size 1000x1000 in a fraction of a second on modern hardware.

Rapid Convergence Through Shifting

A naive implementation of the QR algorithm can take hundreds of iterations to converge to a single eigenvalue. The modern standard uses the implicitly shifted QR algorithm, which accelerates this process dramatically.

By subtracting a carefully chosen value (a "shift") from the matrix diagonal before factoring, and adding it back afterward, the algorithm forces the bottom-right entry of the matrix to converge to an eigenvalue at a quadratic or even cubic rate. With cubic convergence, the number of correct digits in the answer roughly triples with every single step. Consequently, it typically takes only two or three iterations to isolate each eigenvalue.

Handling Complex Numbers in Real Arithmetic

A matrix made entirely of real numbers can still have complex eigenvalues. A naive algorithm would have to switch from real arithmetic to complex arithmetic to find them, which quadruples the cost of multiplication and doubles the memory requirements.

The standard QR algorithm uses the Francis double-shift strategy. Because complex eigenvalues of real matrices always come in conjugate pairs, this technique combines two complex shifts into a single step. The imaginary parts cancel out, allowing the QR algorithm to find complex eigenvalues while exclusively using fast, real-number arithmetic.

Why Specifically "Medium-Sized" Matrices?

The QR algorithm is the standard specifically for medium-sized matrices (roughly \(5 \le n \le 5000\)) because of how its memory and computation requirements scale:

  • Small Matrices (\(n \le 4\)): Analytical formulas exist for these sizes. It is faster to plug the numbers directly into a closed-form equation than to run an iterative algorithm.
  • Medium Matrices: These matrices fit easily into a computer's RAM and cache. The \(O(n^3)\) computational cost of the QR algorithm executes rapidly, and because it finds all eigenvalues reliably, it is the best tool for the job.
  • Large Matrices (\(n > 10,000\)): The QR algorithm modifies the entire matrix, destroying any sparsity (zeros) that might exist. For massive matrices, storing a dense matrix in memory becomes impossible, and \(O(n^3)\) operations take too long. For large matrices, mathematicians abandon the QR algorithm in favor of methods like the Lanczos or Arnoldi iterations, which only find a few specific eigenvalues without altering the original matrix.