Shift-and-invert is a spectral transformation: it turns \(A\) into \((A - \sigma I)^{-1}\), remapping the eigenvalues while leaving the eigenvectors untouched. Applying the power method to that transformed operator is called inverse iteration, and it converges faster the closer the shift \(\sigma\) sits to the true eigenvalue. So why keep \(\sigma\) fixed?

The idea behind Rayleigh Quotient Iteration is to update the shift at every iteration, replacing it with your current best estimate of the eigenvalue. That estimate is the Rayleigh quotient.

The Rayleigh quotient

For a unit vector \(x\), the Rayleigh quotient is

\[\rho(x) = \frac{x^{*} A x}{x^{*} x} = x^{*} A x \quad (\text{when } \lvert x \rvert = 1)\]
  • If \(x\) is exactly an eigenvector, then \(Ax = \lambda x\) and \(\rho(x) = x^{*}\lambda x = \lambda\) returns the eigenvalue exactly.
  • If \(x\) is only an approximate eigenvector, \(\rho(x)\) is the value of \(\lambda\) that minimizes the residual \(\lvert Ax - \lambda x \rvert\) in the least-squares sense. In other words, it is the scalar that makes \(Ax\) look most like \(\lambda x\).

The algorithm

It is exactly inverse iteration, but with the shift refreshed from the Rayleigh quotient at each step:

  • Start with a unit vector \(x_0\), and set \(\sigma_0 = \rho(x_0) = x_0^{*} A x_0\).
  • Solve \((A - \sigma_k I)\, w_{k+1} = x_k\) for \(w_{k+1}\).
  • Normalize: \(x_{k+1} = w_{k+1} / \lvert w_{k+1} \rvert\).
  • Update the shift: \(\sigma_{k+1} = \rho(x_{k+1}) = x_{k+1}^{*} A x_{k+1}\).
  • Repeat until the residual \(\lvert A x_k - \sigma_k x_k \rvert\) is tiny.

The eigenpair you converge to is \((\sigma_k, x_k)\).

What’s different from inverse iteration

The price for the extra speed is that the matrix changes every step, so it must be re-factored each time instead of being factored once and reused.

  Inverse iteration (fixed shift) Rayleigh quotient iteration
Shift \(\sigma\) fixed updated every step
Matrix factored once, reused re-factored every step (since \(A-\sigma_k I\) changes)
Convergence linear cubic (symmetric) / quadratic (general)
Target eigenvalue the one near fixed \(\sigma\) whichever \(x_0\) leans toward

The animation below illustrates the iteration process.