Rayleigh quotient iteration
Rayleigh quotient iteration is an iterative method, that is, it must be repeated until it converges to an answer (this is true for all eigenvalue algorithms). Fortunately, very rapid convergence is guaranteed and no more than a few iterations are needed in practice. The Rayleigh quotient iteration algorithm converges cubically for Hermitian or symmetric matrices, given an initial vector that is sufficiently close to an eigenvector of the matrix that is being analyzed.
The algorithm is very similar to inverse iteration, but replaces the estimated eigenvalue at the end of each iteration with the Rayleigh quotient. Begin by choosing some value as an initial eigenvalue guess for the Hermitian matrix . An initial vector must also be supplied as initial eigenvector guess.
Calculate the next approximation of the eigenvector by
where is the identity matrix, and set the next approximation of the eigenvalue to the Rayleigh quotient of the current iteration equal to
To compute more than one eigenvalue, the algorithm can be combined with a deflation technique.
Consider the matrix
for which the exact eigenvalues are , and , with corresponding eigenvectors
- , and .
(where is the golden ratio).
The largest eigenvalue is and corresponds to any eigenvector proportional to
We begin with an initial eigenvalue guess of
Then, the first iteration yields
the second iteration,
and the third,
from which the cubic convergence is evident.
The following is a simple implementation of the algorithm in Octave.
function x = rayleigh(A,epsilon,mu,x) x = x / norm(x); y = (A-mu*eye(rows(A))) \ x; lambda = y'*x; mu = mu + 1 / lambda err = norm(y-lambda*x) / norm(y) while err > epsilon x = y / norm(y); y = (A-mu*eye(rows(A))) \ x; lambda = y'*x; mu = mu + 1 / lambda err = norm(y-lambda*x) / norm(y) end end
- Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra, Society for Industrial and Applied Mathematics, 1997. ISBN 0-89871-361-7.
- Rainer Kress, "Numerical Analysis", Springer, 1991. ISBN 0-387-98408-9