Power iteration

The power method, power iteration or von Mises - iteration (after Richard von Mises ) is a numerical method for calculating the amount the largest eigenvalue and the corresponding eigenvector of a matrix. The name comes from the fact that matrix powers are formed of key expenditure are therefore matrix-vector products. Therefore, the method is particularly suitable for sparse matrices.

The power method can be interpreted as non- optimal Krylov subspace method that uses only the most recent calculated vector for Eigenwertnäherung. The power method is inferior to the other Krylov space methods such as the method of Lanczos or the method of Arnoldi on convergence speed. For the power method cuts in terms of stability analysis better.

The algorithm

Naive approach

Derived from the stochastic there is the following naive approach to eigenvalue calculation. Considering a stochastic initial vector and a spaltenstochastische matrix, then the probability distribution of a Markov chain at the time is accurate. Now, if that converge to a vector, it is and we have an independent on the initial state of equilibrium distribution and thus also an eigenvector with eigenvalue 1 found. Formally, is thus formed were matrix powers. This procedure can now be generalized for arbitrary matrices.

General algorithm

Given a square matrix and an initial vector. In each iteration step the current approximation is applied to the matrix and then normalized.

Or in a closed form

The vectors converge to an eigenvector to the largest eigenvalue amount, provided that this eigenvalue is semisimple and all other eigenvalues ​​have a really small amount. Thus, there exists an index, such that the eigenvalues. Here is the geometric ( and algebraic ) multiplicity of the eigenvalue.

The vector belonging to the approximate eigenvalue can be calculated in two ways:

Proof of convergence

We give here a proof under the assumption that the matrix is ​​diagonalizable. The proof of the nichtdiagonalisierbaren case is analogous.

O.B.d.A. are located above the eigenvalues ​​. Let V be the change of basis matrix to the matrix. Then being, by assumption, is a diagonal matrix containing the eigenvalues. Let now a basis of eigenvectors ( the column vectors of ) and a start vector with

Then

Applies Since according to the assumption that. because of

Is performed in one in each step, the normalization of the vector. The above condition on the starting vector stating that he must have a non- Ulla part in the direction of the eigenvector. However, this is usually not limiting, as this condition often results due to rounding errors in the practice of their own.

Convergence speed

Under the frequent strong assumption that the eigenvalue is simple, absolute value simple and well separated, converge both the eigenvalue approximations as well as the eigenvector approximations linearly with the speed of convergence, where the eigenvalues ​​are in absolute value assumed sorted by descending. This condition is, for example, by the theorem of Perron - Frobenius with matrices filled with positive entries. Further still Jordan blocks have an influence on the convergence rate. Consider this as an example, the matrices

And

Both have the eigenvector corresponding to the largest eigenvalue magnitude and the separation of the eigenvalues ​​. Using the maximum norm of the starting vector and the matrix converges with a linear speed of convergence, whereas the matrix after 60 iteration steps, provides a useful result (see figure).

Use

Since only the eigenvector must be determined to draw the largest eigenvalue for the calculation of the equilibrium state of large Markov chains, the potency of this method can be used, as explained in section " naive approach " has been described. In particular, here be dispensed with the normalization in each calculation step, since the considered matrix is stochastic and thus receives the amount of the standard stochastic vector. One example is the calculation of the PageRank of a large directed graph as the largest amount eigenvector of the Google matrix. Particularly in the case of the Google matrix, the eigenvalues ​​are well separated so that a poor convergence rate can be excluded.

Variants

If one has an intrinsic value calculated, one can apply the method to the matrix to determine another eigenvalue - eigenvector pair. Moreover, there is the inverse iteration in which the method is applied to, by systems of linear equations are solved in every step.

Comparisons with other Krylowraum process

The power method is very similar to the other Krylowraum method. It 's typical ingredients of the complex process again, such as the normalization of the basis vectors constructed, the expansion of Krylowraumes and the calculation of ( elements of ) projections in the last step.