Power Iteration

Power iteration (also known as the power method) is an iterative algorithm for finding the dominant eigenvalue and eigenvector of a matrix. It is one of the simplest eigenvalue algorithms and forms the foundation for more advanced methods like Arnoldi and Lanczos iteration.

Basic Power Iteration

Given a matrix $A$, the power iteration method finds the eigenvector corresponding to the eigenvalue with the largest absolute value. The algorithm iteratively computes:

where ${\mathbf{v}}_k$ is normalized at each step. The corresponding eigenvalue is estimated as:

Algorithm

1. Start with a random vector ${\mathbf{v}}_0$ (not orthogonal to the dominant eigenvector)
2. For $k=1,2,\dots$:
   • Compute ${\mathbf{w}}_k=A{\mathbf{v}}_{k-1}$
   • Normalize: ${\mathbf{v}}_k=\frac{{\mathbf{w}}_k}{\Vert {\mathbf{w}}_k\Vert }$
   • Estimate eigenvalue: ${\lambda }_k={\mathbf{v}}_k^{T}A{\mathbf{v}}_k$
   • Check for convergence

Convergence

The method converges to the eigenvector corresponding to the eigenvalue with the largest absolute value, provided that:

• The initial vector has a nonzero component in the direction of the dominant eigenvector
• The dominant eigenvalue is unique (no other eigenvalue has the same absolute value)

The convergence rate depends on the ratio $|{\lambda }_2|/|{\lambda }_1|$, where ${\lambda }_1$ is the dominant eigenvalue and ${\lambda }_2$ is the second largest.

Applications

• Finding the largest eigenvalue and eigenvector of large sparse matrices
• PageRank algorithm
• Principal Component Analysis (PCA)
• Foundation for more advanced methods (Arnoldi, Lanczos)