Eigenvalue Algorithms

Eigenvalue algorithms compute the eigenvalues and eigenvectors of a matrix iteratively, since for matrices larger than four-by-four no finite formula can exist.

Definition

An eigenvalue algorithm is an iterative numerical procedure for approximating the eigenvalues and, optionally, the eigenvectors of a matrix, since the eigenvalues are roots of the characteristic polynomial and generally cannot be found in finitely many arithmetic operations.

Scope

This topic covers the power and inverse iterations, reduction to Hessenberg or tridiagonal form, the QR algorithm with shifts, and specialized methods for the symmetric eigenvalue problem, along with the perturbation theory that governs the sensitivity of computed eigenvalues.

Core questions

• Why must general eigenvalue computation be iterative rather than direct?
• How does the shifted QR algorithm converge to the Schur form, and why is preliminary reduction to Hessenberg form essential for efficiency?
• What makes the symmetric eigenvalue problem better conditioned and amenable to specialized algorithms?
• How sensitive are eigenvalues to perturbations, and how does this depend on non-normality of the matrix?

Key theories

The QR algorithm

Repeatedly factoring a matrix as QR and recombining as RQ, with well-chosen shifts and a preliminary Hessenberg reduction, drives the matrix toward upper-triangular (Schur) form whose diagonal holds the eigenvalues; it is the standard method for the dense eigenvalue problem.

Power and inverse iteration

Repeated multiplication by the matrix converges to the dominant eigenvector, while inverse iteration with a shift targets the eigenvalue nearest the shift; these underlie both classical methods and modern eigenvector refinement.

Eigenvalue perturbation theory

The Bauer-Fike theorem and related results bound how far eigenvalues move under perturbations; for symmetric (normal) matrices eigenvalues are perfectly conditioned, whereas for highly non-normal matrices they can be extremely sensitive.

Mechanisms

A dense matrix is first reduced by orthogonal similarity transformations to upper Hessenberg form (tridiagonal in the symmetric case), which preserves eigenvalues while making each QR step cheap. The shifted QR iteration then deflates converged eigenvalues one or two at a time from the bottom of the matrix. For symmetric problems, divide-and-conquer and MRRR algorithms exploit structure to compute eigenvalues and eigenvectors accurately and in parallel.

Clinical relevance

Eigenvalue computations determine vibrational modes and natural frequencies in structural and mechanical engineering, stability of dynamical systems and control loops, energy levels in quantum chemistry and physics, and the spectral methods behind graph partitioning, PageRank, and principal component analysis.

History

The QR algorithm was introduced independently by John Francis and Vera Kublanovskaya around 1961 and, with the addition of shifts and Hessenberg reduction, became the dominant method for the dense eigenvalue problem; Wilkinson's analysis established its reliability and the perturbation theory that explains its accuracy.

Key figures

• James H. Wilkinson
• John G. F. Francis
• Vera Kublanovskaya
• Beresford Parlett

Seminal works

• trefethen1997
• golub2013
• wilkinson1965

Frequently asked questions

Why can't eigenvalues be computed by a direct formula like a linear solve?

Eigenvalues are roots of the characteristic polynomial, and by Abel's theorem polynomials of degree five or higher have no general radical formula, so eigenvalue computation for matrices larger than four-by-four must be iterative.

Are eigenvalues always well-conditioned?

For symmetric and other normal matrices eigenvalues are perfectly conditioned, but for strongly non-normal matrices they can be highly sensitive to perturbations, which is why the spectrum alone may not capture the behaviour of such matrices.