Rayleigh quotient iteration

Remarks

Write $x_k = \cos\theta_k \, v + \sin\theta_k \, w$ with $w$ a unit vector orthogonal to $v$. For symmetric $A$ the Rayleigh quotient is stationary at eigenvectors, so $\abs{\mu_k - \lambda} \le \norm{A - \lambda I} \sin^2\theta_k = O(\theta_k^2)$. Let the gap be the distance from $\mu_k$ to the other eigenvalues. One step of inverse iteration with shift $\mu_k$ multiplies the ratio of the $w$-component to the $v$-component by at most $\abs{\mu_k - \lambda}/\mathrm{gap}$. So $\tan\theta_{k+1} \le O(\theta_k^2) \tan\theta_k$, which is cubic.

Example: for $A = \mathrm{diag}(1, 3)$ and $x_k = (\cos\theta, \sin\theta)$, one finds $\mu_k = 1 + 2\sin^2\theta$ and $\tan\theta_{k+1} = \tan^3\theta_k$ exactly. Symmetry is needed for cubic convergence: for a general matrix with a simple eigenvalue the Rayleigh quotient error is only $O(\theta_k)$, and the local convergence is quadratic. Which eigenvector the iteration finds depends on $x_0$ in a complicated way, so the method is used to refine a good approximation rather than to locate eigenvalues from scratch.

Going deeper

For a student

Each step costs a fresh factorization of $A - \mu_k I$, unlike inverse iteration with a fixed shift, but very few steps are needed. The cubic rate comes from two facts. The Rayleigh quotient is a second-order accurate eigenvalue estimate for symmetric matrices, and inverse iteration converges at a rate proportional to the shift error. The shifted QR algorithm with Rayleigh quotient shifts is closely related, and this explains its fast convergence on symmetric matrices.