Potency method

The power method , vector iteration or Von Mises iteration (after Richard von Mises ) is a numerical method for calculating the greatest eigenvalue and the associated eigenvector of a matrix . The name comes from the fact that matrix powers are formed, so matrix-vector products are essential . The method is therefore particularly suitable for thinly populated matrices . The subspace iteration is a direct generalization for the calculation of several eigenvalues ​​with the greatest magnitude of sparse matrices . ${\displaystyle A^{k}x}$

The power method can be interpreted as a non-optimal Krylow subspace method , which only uses the last calculated vector to approximate the eigenvalue. In terms of the speed of convergence, the power method is inferior to the other Krylow space methods, such as the method of Lanczos or the method of Arnoldi . In return, the power method does better in terms of stability analysis.

The algorithm

motivation

From the stochastic derived, there is the following naive approach to eigenvalue calculation: Considering a stochastic starting vector and a spaltenstochastische matrix , then the probability distribution of a is Markov chain at the time exactly . If they now converge to a vector , then and we have found a stationary distribution independent of the initial state and thus also an eigenvector with eigenvalue 1. So it is formal that matrix powers were formed. This procedure can now be generalized for any matrices. ${\displaystyle v_{0}}$ ${\displaystyle S}$ ${\displaystyle t}$ ${\displaystyle v_{t}=Sv_{t-1}}$ ${\displaystyle v_{t}}$ ${\displaystyle v}$ ${\displaystyle Sv=v}$ ${\displaystyle v=\lim _{i\rightarrow \infty }S^{i}v_{0}}$

General algorithm

A square matrix and a start vector are given . In each iteration step, the matrix is applied to the current approximation and then normalized . ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle r_{0}\in \mathbb {C} ^{n}}$ ${\displaystyle Ar_{0}\neq 0}$ ${\displaystyle A}$ ${\displaystyle r_{k}}$

${\displaystyle r_{k+1}={\frac {Ar_{k}}{\Vert Ar_{k}\Vert }}}$

or in closed form

${\displaystyle r_{k+1}={\frac {A^{k+1}r_{0}}{\Vert A^{k+1}r_{0}\Vert }}}$

The vectors converge against an eigenvector to the eigenvalue with the greatest magnitude , provided that this eigenvalue is semi-simple and all other eigenvalues ​​have a really smaller amount. So there is an index so that for the eigenvalues and . Here is the geometric (and algebraic) multiplicity of the eigenvalue . ${\displaystyle r_{k}}$ ${\displaystyle d}$ ${\displaystyle \lambda _{1}=\ldots =\lambda _{d}}$ ${\displaystyle |\lambda _{d}|>|\lambda _{d+1}|\geq \ldots \geq |\lambda _{n}|}$ ${\displaystyle d}$ ${\displaystyle \lambda _{1}}$

The approximated eigenvalue belonging to the vector can be calculated in two ways: ${\displaystyle r_{k}}$

1. If one forms the scalars (the so-called Rayleigh quotient ), then converges against . This follows directly from the convergence of against an eigenvector. ${\displaystyle \theta _{k}={\frac {\langle r_{k},\,Ar_{k}\rangle }{\langle r_{k},\,r_{k}\rangle }}={\frac {\langle r_{k},\,r_{k+1}\rangle }{\Vert r_{k}\Vert _{2}^{2}}}}$ ${\displaystyle \theta _{k}}$ ${\displaystyle \lambda _{1}}$ ${\displaystyle r_{k}}$
2. If one is not interested in the sign of the eigenvalue, a simple approach is available: Since converging to an eigenvector and normalizing to 1 in each step, converges to (regardless of the norm used). ${\displaystyle r_{k}}$ ${\displaystyle \Vert Ar_{k}\Vert }$ ${\displaystyle |\lambda _{1}|}$

Proof of Convergence

We give a proof here under the assumption that the matrix is diagonalizable. The proof for the non-diagonalizable case runs analogously. ${\displaystyle A}$

OBdA let the eigenvalues ​​be arranged as above. Let be the base change matrix to the matrix . Then where is a diagonal matrix, which contains the eigenvalues, by assumption. Let now be a basis of eigenvectors (the column vectors of ) and a starting vector with ${\displaystyle V}$ ${\displaystyle A}$ ${\displaystyle A^{k}=VD^{k}V^{-1}}$ ${\displaystyle D}$ ${\displaystyle v_{1},\ldots ,v_{n}}$ ${\displaystyle V}$ ${\displaystyle r_{0}}$

${\displaystyle r_{0}=\sum _{i=1}^{n}\beta _{i}v_{i}\quad {\text{mit}}\;\beta _{1}v_{1}+\ldots +\beta _{d}v_{d}\neq 0}$

Then

${\displaystyle \displaystyle {\begin{aligned}A^{k}r_{0}&=VD^{k}V^{-1}r_{0}\\&=VD^{k}(\beta _{1}e_{1}+\ldots +\beta _{n}e_{n})\\&=\lambda _{1}^{k}V\left(\beta _{1}e_{1}+\ldots +\beta _{d}e_{d}+\sum _{i=d+1}^{n}\left({\frac {\lambda _{i}}{\lambda _{1}}}\right)^{k}e_{i}\right)\\&=\lambda _{1}^{k}\left(\beta _{1}v_{1}+\ldots +\beta _{d}v_{d}+\underbrace {\sum _{i=d+1}^{n}\left({\frac {\lambda _{i}}{\lambda _{1}}}\right)^{k}v_{i}} _{\to 0{\text{ für }}k\to \infty }\right)\end{aligned}}}$

Since the prerequisite is that . Because of ${\displaystyle {\tfrac {|\lambda _{i}|}{|\lambda _{1}|}}<1\;{\text{für}}\;i\geq d+1}$

${\displaystyle \lim _{k\to \infty }\lambda _{1}^{k}={\begin{cases}\pm \infty &\;{\text{für}}\;|\lambda _{1}|>1\\0&\;{\text{für}}\;|\lambda _{1}|<1\end{cases}}}$

the vector is normalized to 1 in each step. The condition given above for the start vector means that it must have a non-zero component in the direction of the eigenvector. However, this is usually not restrictive, as this condition often arises by itself in practice due to rounding errors.

Convergence speed

Convergence speed of the power method for the matrices A (blue) and B (green). It is plotted against the number of iteration steps. ${\displaystyle \Vert r_{k}-e\Vert _{\infty }}$

Under the frequent severe condition that the eigenvalue is easy magnitude simple and well-separated, both the eigenvalue approximations converge as well as the eigenvector approximation linearly with the speed of convergence , wherein the eigenvalues are adopted in magnitude falling sorted . According to Perron-Frobenius' theorem, this requirement is fulfilled for matrices with positive entries. Furthermore, Jordan blocks have an influence on the speed of convergence. Consider the matrices as an example ${\displaystyle |\lambda _{2}|/|\lambda _{1}|}$ ${\displaystyle |\lambda _{1}|>|\lambda _{2}|\geq \ldots \geq |\lambda _{n}|}$

${\displaystyle A={\begin{pmatrix}1&0&0&0\\0&0.8&0&0\\0&0&0.8&0\\0&0&0&0.8\end{pmatrix}}\quad {\text{mit}}\quad A^{n}={\begin{pmatrix}1&0&0&0\\0&0.8^{n}&0&0\\0&0&0.8^{n}&0\\0&0&0&0.8^{n}\end{pmatrix}}}$

and

${\displaystyle B={\begin{pmatrix}1&0&0&0\\0&0.8&1&0\\0&0&0.8&1\\0&0&0&0.8\end{pmatrix}}\quad {\text{mit}}\quad B^{n}={\begin{pmatrix}1&0&0&0\\0&0.8^{n}&n\cdot 0.8^{n-1}&{\tfrac {n(n-1)}{2}}\cdot 0.8^{n-2}\\0&0&0.8^{n}&n\cdot 0.8^{n-1}\\0&0&0&0.8^{n}\end{pmatrix}}}$

Both have the eigenvector for the greatest eigenvalue and the separation of the eigenvalues ​​is . Using the maximum norm and the start vector , the matrix converges with a linear convergence speed, while the matrix only delivers a usable result after approx. 60 iteration steps (see figure). ${\displaystyle e=(1,0,0,0)^{T}}$ ${\displaystyle \lambda _{1}=1}$ ${\displaystyle |\lambda _{2}/\lambda _{1}|=0.8}$ ${\displaystyle \|x\|_{\infty }:=\max(|x_{1}|,\ldots ,|x_{n}|)}$ ${\displaystyle r_{0}=(1,1,1,1)^{T}}$ ${\displaystyle A}$ ${\displaystyle B}$

use

Since to calculate the equilibrium state of large Markov chains only the eigenvector for the greatest eigenvalue has to be determined, the power method can be used for this, as already described in the section “Motivation”. In particular, the normalization in each calculation step can be dispensed with here, since the matrix under consideration is stochastic and thus contains the norm of the absolute value of the stochastic vector. An example of this is the calculation of the PageRanks of a large directed graph as the largest eigenvector of the Google matrix . In particular, the eigenvalues ​​of the Google matrix are well separated so that a poor speed of convergence can be excluded.

variants

Once an eigenvalue has been calculated, the procedure can be applied to the matrix in order to determine another pair of eigenvalues ​​and eigenvectors. Here V is the Kronecker product of the eigenvector for the respective eigenvalue with itself. It is assumed that A is unitarily diagonalizable. receives all eigenvalues ​​of A with the exception of ( ). ${\displaystyle \lambda }$ ${\displaystyle A-\lambda V}$ ${\displaystyle \lambda }$ ${\displaystyle A-\lambda V}$ ${\displaystyle \lambda }$ ${\displaystyle \lambda =0}$

In addition, there is the inverse iteration , in which the method is applied to by solving systems of linear equations in each step. ${\displaystyle (A-\lambda I)^{-1}}$

Compare with other cryogenic space procedures

The potency method is very similar to the other Krylow space procedures. The typical components of the more complex procedures can be found again, such as the normalization of the constructed basis vectors, the expansion of the Krylow space and the calculation of (elements of) projections in the last step.

literature

• Hans R. Schwarz, Norbert Köckler: Numerical Mathematics. 5th edition. Teubner, Stuttgart 2004, ISBN 3-519-42960-8 .
• Peter Knabner , Wolf Barth : Lineare Algebra . Basics and applications (=  Springer textbook ). Springer, Berlin 2012, ISBN 978-3-642-32185-6 .
• Josef Stoer, Roland Bulirsch : Numerical Mathematics 2nd 5th edition. Springer, Berlin / Heidelberg / New York 2005, ISBN 978-3-540-23777-8 .

Individual evidence

1. ↑ R. von Mises and H. Pollaczek-Geiringer, Practical Methods of Equation Resolution, ZAMM - Journal for Applied Mathematics and Mechanics 9, 152-164 (1929)
2. ^ JH Wilkinson, The Algebraic Eigenvalue Problem , Oxford University Press (1965)
3. ^ The Second Eigenvalue of the Google Matrix . Stanford University website. Retrieved August 30, 2013.