Power Iteration

Power Iteration

Power iteration finds the dominant eigenvalue (largest in magnitude) and its eigenvector by repeated matrix-vector multiplication:

$\mathbf{v}_{0} = \text{random unit vector}, \qquad \mathbf{v}_{k+1} = \frac{A\mathbf{v}_{k}}{\|A\mathbf{v}_{k}\|}, \qquad \lambda = \mathbf{v}^T A \mathbf{v} \; (\text{Rayleigh quotient})$

Why It Works

Expand $\mathbf{v}_{0}$ in the eigenbasis: $\mathbf{v}_{0} = \sum_i c_i \mathbf{u}_{i}$. After $k$ multiplications:

$A^k \mathbf{v}_{0} = \sum_i c_i \lambda_i^k \mathbf{u}_{i} \approx c_1 \lambda_1^k \mathbf{u}_{1} \quad (\text{since } |\lambda_1| > |\lambda_2| \geq \ldots)$

The dominant component grows fastest and eventually dominates.

Convergence

The rate is $|\lambda_2 / \lambda_1|$. If the second eigenvalue is small relative to the first, convergence is fast.

Example

$A = \begin{pmatrix} 4 & 1 \\ 2 & 3 \end{pmatrix}, \quad \text{eigenvalues: } 5, 2, \quad \text{dominant eigenvector: } [0.7071,\ 0.7071]$

Your Task

Implement power_iteration(A, iterations=100) returning (eigenvalue, eigenvector).