Franklin's Notes

Rayleigh quotient iteration

Rayleigh quotient iteration is an iterative method for computing eigenvalue-eigenvector pairs by combining techniques from both power iteration and inverse iteration . Because inverse iteration works best given a good initial approximation for the eigenvalue, and power iteration works best given a good initial approximation for the eigenvector, we can alternate between iterations of power iteration and inverse iteration to obtain successively better approximations of both an eigenvector and the corresponding eigenvalue in a way that the accuracy of each approximation compounds off of the accuracy of the other, resulting in blazing fast convergence (to quote professor Jacob Schroder).

The algorithm is as follows:

1. Let $v^{(0)}$ be an arbitrary unit vector
2. Let $\lambda^{(0)}=r(v^{(0)})$, where $r$ is the Rayleigh quotient
3. For $k=1,2,\cdots$
1. Solve $(A-\lambda^{(k-1)}I)w=v^{(k-1)}$ for $w$
2. Let $v^{(k)}=w/\lVert w\rVert$
3. Let $\lambda^{(k)}=r(v^{(k)})$

Using the fact that the Rayleigh quotient is a quadratic eigenvalue estimate, we have that Additionally, the error bound for a single step of inverse iteration tells us that and therefore, by combining these bounds, we have that and additionally In particular, if we start with an eigenvector estimate with error $\epsilon$, performing $K$ iterations of Rayleigh quotient iteration will result in an eigenvector estimate of error $\mathcal O(\epsilon^{3^K})$ and an eigenvalue estimate or error $\mathcal O(\epsilon^{2\cdot 3^K})$. This is indeed blazing fast!




back to home page