Eigenvalues and Power Method
Eigenvalues and eigenvectors are central in linear algebra, physics, mechanics, and data analysis. Computing them is a rich subject, with methods ranging from simple iteration to sophisticated spectral algorithms. This chapter introduces the main techniques used in numerical practice.
Definitions
For a square matrix A, a nonzero vector v satisfying Av = λv is an eigenvector with eigenvalue λ. Eigenvalues are roots of the characteristic polynomial det(A − λI) = 0. An n × n matrix has exactly n eigenvalues (counting multiplicities), though they may be complex even for real matrices.
Applications
Eigenvalues describe natural frequencies of vibrating structures, stability of dynamical systems, and principal components in statistics. PageRank uses the dominant eigenvector of a stochastic matrix; quantum mechanics builds on eigenvalue problems. Any serious numerical toolkit must solve them efficiently.
Characteristic Polynomial
Directly finding roots of det(A − λI) is feasible only for small matrices. The polynomial's roots are extremely ill-conditioned with respect to the polynomial's coefficients, so this approach is avoided in modern software. Algorithms operate on A directly.
Power Method
The power method finds the dominant eigenvalue and its eigenvector. Starting with a random vector v(0), the iteration v(k+1) = Av(k) / ‖Av(k)‖ converges to the eigenvector of the largest-magnitude eigenvalue, provided it is unique and v(0) has a component in that direction. The corresponding eigenvalue is recovered from the Rayleigh quotient λ ≈ vTAv / vTv.
Inverse and Shifted Power Methods
The inverse power method applies the power method to A-1, yielding the smallest eigenvalue. Combined with a shift A − μI, it finds the eigenvalue closest to μ. This shift-and-invert strategy underlies many advanced algorithms and is especially useful when approximate eigenvalues are already known.
Deflation
After finding the dominant eigenpair, deflation subtracts its rank-one contribution to make the next eigenvalue dominant, so the power method can find it. Deflation is simple but numerically delicate; errors accumulate as more eigenvalues are extracted.
Jacobi Method
For symmetric matrices, Jacobi's method performs successive plane rotations to reduce off-diagonal elements toward zero. The diagonal elements then approach the eigenvalues. Jacobi's is highly parallelizable and delivers excellent accuracy, but it is slower than modern alternatives for large matrices.
QR Algorithm
The QR algorithm iteratively factors A = QR and forms A' = RQ. Under mild conditions, A' approaches upper triangular form with eigenvalues on the diagonal. With shifts and deflation, QR is the standard method for dense eigenvalue problems. For large sparse matrices, Lanczos, Arnoldi, and Krylov-subspace methods are preferred.
Stability and Condition Numbers
Eigenvalues of symmetric matrices are well-conditioned; they change little under small perturbations. Non-symmetric and especially defective matrices can have eigenvalues that are very sensitive. The pseudospectrum is a useful tool for analyzing stability of eigenvalues to perturbations.
Summary
Eigenvalue computation ranges from the simple power method to the sophisticated QR algorithm. Modern software delivers high accuracy for problems of enormous size, making spectral techniques a staple of scientific and engineering computation.