Rayleigh quotient iteration

Rayleigh quotient iteration is an eigenvalue algorithm which extends the idea of the inverse iteration by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates.

Rayleigh quotient iteration is an iterative method, that is, it delivers a sequence of approximate solutions that converges to a true solution in the limit (this is true for all algorithms that compute eigenvalues: since eigenvalues can be irrational numbers, there can be no general method for computing them in a finite number of steps). Fortunately, very rapid convergence is guaranteed and no more than a few iterations are needed in practice to obtain a reasonable approximation. 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.

Algorithm

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.

Note that for very small problems it is beneficial to replace the matrix inverse with the adjugate, which will yield the same iteration because it's equal to the inverse up to an irrelevant scale (the inverse of the determinant, specifically). The adjugate is easier to compute explicitly than the inverse (though the inverse is easier to apply to a vector for problems that aren't small), and is more numerically sound because it remains well defined as the eigenvalue converges.

Example

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.

Octave Implementation

The following is a simple implementation of the algorithm in Octave.

function x = rayleigh(A, epsilon, mu, x)
  x = x / norm(x);
  % the backslash operator in Octave is equivalent to taking the inverse
  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

See also

• Power iteration
• Inverse iteration

References

• 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