Trefethen and Bau, Numerical Linear Algebra, p. 208 states that Rayleigh quotient iteration (combining Rayleigh quotient estimate for eigenvalues and inverse power iteration) converges cubically
…the convergence is ultimately cubic in the sense that if
$\lambda_J$ is an eigenvalue of $A$ and $v^{(0)}$ is sufficiently
close to the eigenvector $q_J$,
then $$\|v^{(k+1)} – (\pm q_J)\| = O(\|v^{(k)} – (\pm q_J)\|^3)$$ and $$|\lambda^{(k+1)} – \lambda_J| =
> O(|\lambda^{(k)} – \lambda_J|^3)$$ as $k \rightarrow \infty$.
Their argument is as follows. Suppose that convergence occurs, and that
$\|v^{(k)} – q_J\| \leq \epsilon$ for some small $\epsilon$.
Then the Rayleigh quotient estimation for an eigenvalue gives an eigenvalue
estimate $\lambda^{(k)}$ with $|\lambda^{(k)} – \lambda_J| = O(\epsilon^2)$.
Then apply the proof of the inverse power iteration for one step to obtain $v^{(k+1)}$ from $v^{(k)}$ and $\lambda^{(k)}$, so that
$$\|v^{(k+1)} – q_J \|= O(|\lambda^{(k)}-\lambda_J| \|v^{(k)} – q_J\|) = O(\epsilon^3)$$
with the constants in the big-Oh symbols uniform in sufficiently small neighborhoods.
I don't see the left most equality above, nor why the constants are uniform.
It seems that all power iteration gives is
$$O(|\lambda^{(k)}-\lambda_J|/|\lambda^{(k)}-\lambda_K|)$$
where $\lambda_K$ is the second closest eigenvalue.
Best Answer
Here's a high level explanation brushing some analysis under the rug. Let's rewrite Theorem 27.2 as $$ \|v^{(k+1)}-(\pm q_J)\| = O\left( \left|\frac{\mu-\lambda_J}{\mu-\lambda_K} \right|^{k+1} \right) = O\left( \left|\frac{\mu-\lambda_J}{\mu-\lambda_K} \right|^{k} \left|\frac{\mu-\lambda_J}{\mu-\lambda_K} \right| \right) = O\left(\|v^{(k)}-(\pm q_J)\| \ \left|\frac{\mu-\lambda_J}{\mu-\lambda_K} \right| \right)$$
For the Rayleigh quotient iteration, the $ \mu $ in the expression above is replaced with $ \lambda^{(k)} $. The key to understanding the rest of the argument is that for $ j \neq J $, $ |\lambda^{(k)}-\lambda_j|$ is approximately constant for $ v^{(k)} $ near $ q_J $. This follows because the eigenvectors are stationary points of the Rayleigh quotient. In particular, $|\lambda^{(k)}-\lambda_K|$ is approximately a constant and can be absorbed into the $O$.
Combining these observations gives the result: $$ \|v^{(k+1)}-(\pm q_J)\| = O(\|v^{(k)}-(\pm q_J)\| |\lambda^{(k)}-\lambda_J|)$$
A formal proof of the cubic convergence of the Rayleigh quotient iteration can be found in Applied Numerical Linear Algebra by Demmel.