Rayleigh quotient iteration
/ RAY-lee /
Inverse iteration works best when your shift sigma is very close to the target eigenvalue. But what if you only have a rough guess? Here is the elegant idea: don't keep the shift fixed — update it every step using the best eigenvalue estimate you currently have. As the eigenvector estimate sharpens, your shift gets closer to the true eigenvalue, which makes the next inverse-iteration step even faster, which sharpens the estimate further. This feedback loop is Rayleigh quotient iteration, and it converges astonishingly fast.
Mechanically: given a unit vector v, the Rayleigh quotient r(v) = v^T A v / (v^T v) is the best single-number estimate of the eigenvalue associated with v (for a symmetric matrix it is exactly the eigenvalue when v is an eigenvector, and it minimizes ||A v - r v||). The algorithm repeats: compute sigma = v^T A v; solve (A - sigma I) w = v; set v = w / ||w||. Because the shift homes in on the eigenvalue as fast as the vector homes in on the eigenvector, the errors compound. For a symmetric matrix convergence is CUBIC: the number of correct digits roughly TRIPLES each step. From 1 digit to 3 to 9 to 27 — a handful of iterations gives machine precision.
Cubic convergence is dramatic but comes with honest caveats. You must solve a fresh linear system every step (the shift changes, so you cannot reuse one LU factorization), making each step costlier than fixed-shift inverse iteration. And because the shift can jump, the method is only locally convergent: from a poor starting vector it can converge to an eigenpair you did not intend, or wander. In practice RQI is used as the fast endgame — get into the neighborhood with the QR algorithm or a few power steps, then switch to RQI to polish an eigenpair to full accuracy in two or three iterations.
On A with rows (2, 1) and (1, 2), start at v = (1, 0). sigma = v^T A v = 2. Solve (A - 2I) w = v with A - 2I rows (0,1),(1,0): w = (0, 1) -> v = (0, 1). New sigma = 2 again here by symmetry; a slightly tilted start like (1, 0.1) instead converges in two or three steps to (0.707, 0.707) and sigma = 3 to full precision — the digit count tripling each step.
Updating the shift with the Rayleigh quotient each step gives cubic convergence for symmetric matrices.
Cubic convergence holds for symmetric (Hermitian) matrices; for general nonsymmetric matrices RQI converges quadratically, still very fast. The price is a new factorization every step, and convergence is only local — it can land on an unintended eigenpair, so it is a polisher, not a global search.