power & inverse iteration

The power method is the most elementary eigenvalue algorithm, and its idea is one line: keep multiplying a vector by A and normalizing. Start with almost any v_0, form v_{k+1} = A v_k / ||A v_k||. Write v_0 in the eigenvector basis; each multiplication by A scales the component along eigenvalue lambda_i by lambda_i, so the component with the largest |lambda| grows fastest and eventually dominates. The vector converges to the dominant eigenvector; the Rayleigh quotient v^T A v / v^T v converges to its eigenvalue.

Convergence is linear, governed by the ratio |lambda_2| / |lambda_1| of the second-largest to the largest eigenvalue. A big spectral gap means fast convergence; eigenvalues of nearly equal magnitude mean a painful crawl, and a complex-conjugate dominant pair stalls it entirely. The method gives you only one eigenpair — the dominant one — which is sometimes exactly what you want (Google's original PageRank is essentially a power iteration on the web's link matrix).

Inverse iteration flips the trick to target other eigenvalues. Apply the power method to (A - mu I)^-1 instead of A. The eigenvalues of that inverse are 1/(lambda_i - mu), so the eigenvalue of A closest to the shift mu becomes the dominant one of the inverse — and inverse iteration zooms in on it. Each step solves a linear system with A - mu I rather than multiplying; choose mu near a known approximate eigenvalue and convergence is fast.

Rayleigh quotient iteration takes this to its limit: after each inverse-iteration step, update the shift mu to the current Rayleigh quotient. The shift chases the eigenvalue, and convergence becomes cubic — roughly tripling the number of correct digits per step — for symmetric matrices. These shift-and-invert ideas are the conceptual seed of the shifted QR algorithm.