Rayleigh quotient iteration is an eigenvalue algorithm

Eigenvalue algorithm

In linear algebra, one of the most important problems is designing efficient and stable algorithms for finding the eigenvalues of a matrix. These eigenvalue algorithms may also find eigenvectors.-Characteristic polynomial:...

 which extends the idea of the inverse iteration

Inverse iteration

In numerical analysis, inverse iteration is an iterative eigenvalue algorithm. It allows to find an approximateeigenvector when an approximation to a corresponding eigenvalue is already known....

 by using the Rayleigh quotient to obtain increasingly accurate eigenvalue estimates.

Rayleigh quotient iteration is an iterative method

Iterative method

In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...

, that is, it must be repeated until it converges

Limit of a sequence

The limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...

 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

Rate of convergence

In numerical analysis, the speed at which a convergent sequence approaches its limit is called the rate of convergence. Although strictly speaking, a limit does not give information about any finite first part of the sequence, this concept is of practical importance if we deal with a sequence of...

 for Hermitian or symmetric matrices, given an initial vector that is sufficiently close to an eigenvector of the matrix

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

 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.

Example

Take the matrix





with the largest eigenvalue and corresponding eigenvector of,





We begin with an initial eigenvalue guess of and eigenvector 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

GNU Octave

GNU Octave is a high-level language, primarily intended for numerical computations. It provides a convenient command-line interface for solving linear and nonlinear problems numerically, and for performing other numerical experiments using a language that is mostly compatible with MATLAB...

.


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
error = norm(y-lambda*x) / norm(y)
while error > epsilon
x = y / norm(y);
y = (A-mu*eye(rows(A))) \ x;
lambda = y'*x;
mu = mu + 1 / lambda
error = norm(y-lambda*x) / norm(y)
end
end