The Power Method

The simplest eigenvalue algorithm: repeatedly apply a matrix to a vector to converge onto the dominant eigenvector.

Repeated multiplication

The power method finds the eigenvalue of largest magnitude and its eigenvector. Start with a vector, multiply by the matrix, normalize, and repeat. Any starting vector is a combination of eigenvectors; each multiplication scales each component by its eigenvalue, so the component with the largest-magnitude eigenvalue grows to dominate all others. After many steps the iterate aligns with the dominant eigenvector.

Convergence rate

The error shrinks at a rate given by the ratio of the second-largest to the largest eigenvalue magnitude. When the top two eigenvalues are close, convergence is slow; when the dominant eigenvalue is well separated, it is fast. The eigenvalue estimate is recovered from the Rayleigh quotient x^T A x divided by x^T x at each step.

import numpy as np

def power_method(A, x0, iters=100):
    x = x0 / np.linalg.norm(x0)
    for _ in range(iters):
        y = A @ x
        x = y / np.linalg.norm(y)
    lam = x @ (A @ x)
    return lam, x

Variants

• Inverse iteration applies the power method to (A minus shift)^(-1), converging to the eigenvalue nearest the shift
• Rayleigh quotient iteration updates the shift each step to the current Rayleigh quotient, achieving cubic convergence near a simple eigenvalue
• Shifting can also be used to find the smallest eigenvalue or to accelerate separation

Where it appears

Despite its simplicity the power method is foundational. It is the engine behind PageRank, the core of the dominant-mode extraction in stability studies, and a building block inside more sophisticated schemes. The QR algorithm can be understood as a simultaneous power iteration on all eigenvectors at once, and Arnoldi generalizes it to extract many eigenvalues efficiently.