The Rayleigh iteration method is an iterative algorithm for calculating eigenvalues and vectors , which complements the idea of the inverse power method by iteratively calculating the current approximation to the eigenvalue using the Rayleigh relation .
The Rayleigh method has a very high convergence rate and often it takes only a few iterations to obtain a solution. For symmetric and Hermitian matrices with sufficiently well chosen initial values, the convergence is cubic . However, the execution time of each iteration is usually proportional to the cube of the matrix size, while for the inverse power and power methods it is quadratic.
Algorithm
As in the inverse power method, we set some initial approximation to the eigenvalue of the matrix and initial vector , which can be either random or known approximation to its own vector. Next, iteratively compute new approximations to the eigenvector according to the formula
where unit matrix .
At the end of the iteration, we calculate the following approximation to the eigenvalue using the Rayleigh relation:
Software implementation example
The following is an example implementation in GNU Octave .
function x = rayleigh ( A, epsilon, mu, x )
x = x / norm ( x );
% the backslash operator in Octave solves a linear system
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
Links
- Lloyd N. Trefethen and David Bau, III, Numerical Linear Algebra , Society for Industrial and Applied Mathematics, 1997 ..
- Rainer Kress, "Numerical Analysis", Springer, 1991.