Power iteration

In mathematics, power iteration (also known as the power method) is an eigenvalue algorithm: given a diagonalizable matrix ${\displaystyle A}$, the algorithm will produce a number ${\displaystyle \lambda }$, which is the greatest (in absolute value) eigenvalue of ${\displaystyle A}$, and a nonzero vector ${\displaystyle v}$, which is a corresponding eigenvector of ${\displaystyle \lambda }$, that is, ${\displaystyle Av=\lambda v}$. The algorithm is also known as the Von Mises iteration.^[1]

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 ${\displaystyle A}$ by a vector, so it is effective for a very large sparse matrix with appropriate implementation. The speed of convergence is like ${\displaystyle (\lambda _{1}/\lambda _{2})^{k}}$(see a later section). In words, convergence is exponential with base being the spectral gap.