QR Algorithm

The QR algorithm is one of the most elegant and powerful methods in numerical linear algebra for computing eigenvalues of matrices. The algorithm’s beauty lies in its simplicity and theoretical depth: through iterative QR decompositions, it converges to a triangular (or diagonal for symmetric matrices) form, revealing the eigenvalues along the diagonal.

1 Algorithm Overview

The basic QR iteration proceeds as follows:

  1. Start with a matrix A_0 = A
  2. For k = 0, 1, 2, \ldots :
    • Compute QR decomposition: A_k = Q_kR_k
    • Form next iterate: A_{k+1} = R_kQ_k

For symmetric matrices, this process converges to a diagonal matrix containing the eigenvalues. For general matrices, it converges to an upper triangular (Schur) form, where the diagonal elements are still the eigenvalues. The animation below was inspired by the Gabriel Peyré post.

The visualization above demonstrates how the QR algorithm gradually transforms a symmetric matrix into diagonal form, with the off-diagonal elements converging to zero. The convergence rate depends on the separation of eigenvalues - better separated eigenvalues typically lead to faster convergence.

2 Implementation

Code

3 Key Properties

  1. Preservation of Eigenvalues: Each iteration Aₖ₊₁ = RₖQₖ is similar to Aₖ, thus preserving eigenvalues
  2. Convergence: For symmetric matrices, the algorithm converges to a diagonal matrix
  3. Numerical Stability: The use of orthogonal transformations ensures good numerical properties

The QR algorithm forms the basis of modern eigenvalue computations and is implemented in most numerical linear algebra libraries. While the basic version shown here is elegant, practical implementations use various enhancements like shifts and deflation to improve efficiency.