In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix, which is the greatest (in absolute value) eigenvalue, which is a corresponding eigenvector. The algorithm is also known as the Von Mises iteration.

by a vector, so it is effective for a very large sparse matrix are, respectively, the eigenvalue of largest absolute value and an eigenvalue of second-largest absolute value (see a later section). In other words, convergence is exponential with base being the spectral gap.

The method

, which may be an approximation to the dominant eigenvector or a random vector. The method is described by the recurrence relation

and normalized.

has an eigenvalue that is strictly greater in magnitude than its other eigenvalues, i.e.,

has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence converges to an eigenvector associated with the dominant eigenvalue.

does not necessarily converge. In this sequence,

1. ,

defined by

converges to the dominant eigenvalue (with Rayleigh quotient).

One may compute this with the following algorithm (shown in Python with NumPy):

converges to an associated eigenvector. Ideally, one should use the Rayleigh quotient in order to get the associated eigenvalue.

This algorithm is used to calculate the Google PageRank.

The method can also be used to calculate the spectral radius (the eigenvalue with the largest magnitude, for a square matrix) by computing the Rayleigh quotient

Analysis

be decomposed into its Jordan canonical form. Since generically can be written as a linear combination:

.

The computationally useful recurrence relation can be rewritten as:

is more amenable to the following analysis:

is less than 1 in magnitude, so

It follows that:

is large:

.

is diagonalizable, then the following proof yields the same result:

.

can be written:

with probability 1. Now,

On the other hand:

. The convergence is geometric, with ratio

Thus, the method converges slowly if there is an eigenvalue close in magnitude to the dominant eigenvalue.

Applications

Although the power iteration method approximates only one eigenvalue of a matrix, it remains useful for certain computational problems. For instance, Google uses it to calculate the PageRank of documents in their search engine, and Twitter uses it to show users recommendations of whom to follow. The power iteration method is especially suitable for sparse matrices, such as the web matrix, or as the matrix-free method that does not require storing the coefficient matrix. For non-symmetric matrices that are well-conditioned the power iteration method can outperform more complex Arnoldi iteration. For symmetric matrices, the power iteration method is rarely used, since its convergence speed can be easily increased without sacrificing the small cost per iteration; see, e.g., Lanczos iteration and LOBPCG.

Some of the more advanced eigenvalue algorithms can be understood as variations of the power iteration. For instance, the inverse iteration. This subspace is known as the Krylov subspace. It can be computed by Arnoldi iteration or Lanczos iteration. Gram iteration is a super-linear and deterministic method to compute the largest eigenpair.

See also

• Rayleigh quotient iteration

• Inverse iteration

References