In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix A {\displaystyle A} , the algorithm will produce a number λ {\displaystyle \lambda } , which is the greatest (in absolute value) eigenvalue of A {\displaystyle A} , and a nonzero vector v {\displaystyle v} , which is a corresponding eigenvector of λ {\displaystyle \lambda } , that is, A v = λ v {\displaystyle Av=\lambda v} . The algorithm is also known as the Von Mises iteration. Power iteration is a very simple algorithm, but it may converge slowly. The most time-consuming operation of the algorithm is the multiplication of matrix A {\displaystyle A} by a vector, so it is effective for a very large sparse matrix with appropriate implementation. The speed of convergence is like ( λ 2 / λ 1 ) k {\displaystyle (\lambda _{2}/\lambda _{1})^{k}} where k {\displaystyle k} is the number of iterations, and λ 1 {\displaystyle \lambda _{1}} and λ 2 {\displaystyle \lambda _{2}} 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
The power iteration algorithm starts with a vector b 0 {\displaystyle b_{0}} , which may be an approximation to the dominant eigenvector or a random vector. The method is described by the recurrence relation
b k + 1 = A b k ‖ A b k ‖ {\displaystyle b_{k+1}={\frac {Ab_{k}}{\lVert Ab_{k}\rVert }}}
So, at every iteration, the vector b k {\displaystyle b_{k}} is multiplied by the matrix A {\displaystyle A} and normalized. If we assume A {\displaystyle A} has an eigenvalue that is strictly greater in magnitude than its other eigenvalues, i.e.,
| λ 1 | > | λ 2 | ≥ … ≥ | λ n | ≥ 0 {\displaystyle \left\vert \lambda _{1}\right\vert >\left\vert \lambda _{2}\right\vert \geq \ldots \geq \left\vert \lambda _{n}\right\vert \geq 0}
and the starting vector b 0 {\displaystyle b_{0}} has a nonzero component in the direction of an eigenvector associated with the dominant eigenvalue, then a subsequence ( b k ) {\displaystyle \left(b_{k}\right)} converges to an eigenvector associated with the dominant eigenvalue. Without the two assumptions above, the sequence ( b k ) {\displaystyle \left(b_{k}\right)} does not necessarily converge. In this sequence,
… excerpt ends here. Continue reading the full article.
