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.

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 _{2}/\lambda _{1})^{k}}$ where ${\displaystyle k}$ is the number of iterations, and ${\displaystyle \lambda _{1}}$ and ${\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.