Power Iteration for the Dominant Eigenvalue

Repeatedly multiply a vector by a matrix and normalize to converge on its largest-magnitude eigenvalue and eigenvector.

The idea

Write any starting vector as a combination of eigenvectors. Each multiplication by A scales each component by its eigenvalue, so the component with the largest-magnitude eigenvalue grows fastest and eventually dominates. Normalizing each step keeps numbers bounded.

import numpy as np
A=np.array([[2.0,1.0],[1.0,3.0]])
v=np.array([1.0,0.0])
for i in range(50):
    w=A@v; v=w/np.linalg.norm(w)
lam=v@A@v                    # Rayleigh quotient
print('dominant eigenvalue:',round(lam,6))  # 3.618...
print('eigenvector:',np.round(v,4))

Convergence

The error shrinks by the ratio |lambda_2/lambda_1| each iteration, where lambda_1 and lambda_2 are the two largest eigenvalues by magnitude. A big gap means fast convergence; nearly equal top eigenvalues make it crawl. The eigenvalue estimate is read off with the Rayleigh quotient v^T A v.

Getting other eigenvalues

Inverse iteration applies power iteration to (A - mu I)^-1, which converges to the eigenvalue nearest a shift mu - useful for interior eigenvalues. Deflation removes the found eigenvector to expose the next one. Combining a shift that updates each step gives Rayleigh-quotient iteration, which converges cubically.

Where it is used

Power iteration is behind PageRank (the dominant eigenvector of a web-link matrix), the leading principal component of a covariance matrix, and the largest vibration mode of a structure. It needs only matrix-vector products, so it scales to enormous sparse matrices where full eigensolvers cannot run.