The Power Method

Finding eigenvalues from the characteristic polynomial is hopeless for large matrices: the roots of a high-degree polynomial are badly conditioned. The simplest practical method only multiplies by $A$. Start from a vector $\mathbf{x}_0$ and repeat: $$\mathbf{y} = A\mathbf{x}_k,\qquad \mu_{k+1} = \text{the entry of }\mathbf{y}\text{ largest in size},\qquad \mathbf{x}_{k+1} = \frac{\mathbf{y}}{\mu_{k+1}}.$$ Scaling keeps the numbers from overflowing; it makes $\lVert\mathbf{x}_{k+1}\rVert_\infty = 1$ (see Vector and Matrix Norms).

Key idea

If $A$ has a dominant eigenvalue, $|\lambda_1| > |\lambda_2| \ge \cdots$, and $\mathbf{x}_0$ has some component along its eigenvector $\mathbf{v}_1$, then $\mathbf{x}_k$ turns toward $\mathbf{v}_1$ and $\mu_k \to \lambda_1$. The error shrinks by about $\left|\frac{\lambda_2}{\lambda_1}\right|$ each step.

Why it works

Write $\mathbf{x}_0 = c_1\mathbf{v}_1 + c_2\mathbf{v}_2 + \cdots + c_n\mathbf{v}_n$ (for a diagonalizable $A$). Then $$A^{k}\mathbf{x}_0 = \lambda_1^{k}\left(c_1\mathbf{v}_1 + c_2\left(\tfrac{\lambda_2}{\lambda_1}\right)^{k}\mathbf{v}_2 + \cdots + c_n\left(\tfrac{\lambda_n}{\lambda_1}\right)^{k}\mathbf{v}_n\right).$$ Every ratio has size less than 1, so every term but the first dies out, the slowest one like $\left|\frac{\lambda_2}{\lambda_1}\right|^{k}$. Scaling only changes the length, not the direction, so $\mathbf{x}_k$ lines up with $\mathbf{v}_1$, and then $A\mathbf{x}_k \approx \lambda_1\mathbf{x}_k$ makes the scale factor approach $\lambda_1$.

Worked example: Three steps by hand

Run the power method on $A = \begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ from $\mathbf{x}_0 = (1, 0)$. (Its eigenvalues are $3$ and $1$.)

$A\mathbf{x}_0 = (2, 1)$: $\mu_1 = 2$, $\mathbf{x}_1 = (1, 0.5)$.
$A\mathbf{x}_1 = (2.5, 2)$: $\mu_2 = 2.5$, $\mathbf{x}_2 = (1, 0.8)$.
$A\mathbf{x}_2 = (2.8, 2.6)$: $\mu_3 = 2.8$, $\mathbf{x}_3 \approx (1, 0.929)$.
Heading to $\lambda_1 = 3$ and $\mathbf{v}_1 = (1, 1)$; the error in $\mu$ goes $1, 0.5, 0.2$, then $0.071, 0.024$: shrinking by about $\frac{1}{3}$ each step.

Answer: $\mu_3 = 2.8$, $\mathbf{x}_3 \approx (1, 0.929)$

Worked example: How many steps?

About how many steps reduce the error by a factor of $10^{6}$ when $\left|\frac{\lambda_2}{\lambda_1}\right| = 0.9$? When it is $\frac{1}{3}$?

Solve $0.9^{k} = 10^{-6}$: $k = \frac{6}{\log_{10}(1/0.9)} \approx 131$ steps.
With ratio $\frac{1}{3}$: $k = \frac{6}{\log_{10}3} \approx 13$ steps.
When the top two eigenvalues are close in size, the power method crawls.

Answer: about $131$ and about $13$

Worked example: Two eigenvalues of the same size

Run the power method on $A = \begin{bmatrix} 0 & 2 \\ 2 & 0 \end{bmatrix}$ (eigenvalues $2$ and $-2$) from $\mathbf{x}_0 = (1, 0.5)$.

$A\mathbf{x}_0 = (1, 2)$: $\mathbf{x}_1 = (0.5, 1)$.
$A\mathbf{x}_1 = (2, 1)$: $\mathbf{x}_2 = (1, 0.5) = \mathbf{x}_0$.
The iterates bounce between two vectors forever. With $\lambda_2 = -\lambda_1$ the ratio has size exactly $1$, and the $\mathbf{v}_2$ part never fades; it just flips sign each step.

Answer: no convergence

Each iterate drawn as a direction (scaled so its largest entry is 1), with the eigenvector lines dashed. The table lists the scale factors μ.

For a symmetric matrix, a better estimate of $\lambda_1$ from the same vector is the Rayleigh quotient $\frac{\mathbf{x}^{T}A\mathbf{x}}{\mathbf{x}^{T}\mathbf{x}}$: its error shrinks like $\left|\frac{\lambda_2}{\lambda_1}\right|^{2k}$, twice as many digits. For $\mathbf{x}_2 = (1, 0.8)$ above it gives $2.976$, already closer than $\mu_4 \approx 2.929$. Search engines once ranked web pages with a power method on a matrix of links.

Common mistake

Expecting convergence when the two largest eigenvalues have the same size, such as $2$ and $-2$, or a complex pair $a \pm bi$. Then no term dominates and the iterates never settle. Check: if the scale factors or vectors keep repeating a pattern instead of settling, look for a tie in size. (The method also fails if $\mathbf{x}_0$ has no $\mathbf{v}_1$ part, though round-off usually adds one.)

The Power Method

Practice

Builds on

Leads to

Sources and further reading