Power iteration

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.