---
title: Iterative Estimates for Eigenvalues
module: Eigenvalues and Eigenvectors
moduleNumber: 5
lessonNumber: 7
order: 507
summary: >
  When only a numerical eigenvalue is needed, iteration is preferred over the
  characteristic polynomial. The power method repeatedly multiplies by A to
  converge on the dominant eigenvalue and its eigenvector; the Rayleigh quotient
  sharpens the estimate for symmetric matrices; and the inverse power method
  targets any eigenvalue near a known guess.
topics: [Eigenvalues and Eigenvectors]
sources:
  - book: Lay
    ref: "§5.8 Iterative Estimates for Eigenvalues"
---

In applications, eigenvalues are rarely needed to full precision, and the characteristic
polynomial is the wrong tool for computing them: no finite formula solves a general
polynomial of degree $5$ or more, and forming then rooting the polynomial is
numerically unstable. Iterative methods avoid it, producing accurate approximations from
repeated matrix-vector products. The power method and its relatives below also motivate
the
[numerical eigenvalue algorithms](/linear-algebra/numerical-linear-algebra/numerical-eigenvalues-and-svd).

## The dominant eigenvalue

Assume $A$ is diagonalizable with a basis of eigenvectors $v_1, \dots, v_n$ and a
**strictly dominant** eigenvalue, meaning

$$
\vert\lambda_1\vert > \vert\lambda_2\vert \geq \vert\lambda_3\vert \geq \cdots
\geq \vert\lambda_n\vert.
$$

Write a starting vector as $x = c_1 v_1 + \cdots + c_n v_n$ with $c_1 \neq 0$. Then

$$
A^k x = c_1 (\lambda_1)^k v_1 + c_2 (\lambda_2)^k v_2 + \cdots + c_n (\lambda_n)^k v_n.
$$

Dividing by $(\lambda_1)^k$ isolates the dominant term:

$$
\frac{1}{(\lambda_1)^k} A^k x
= c_1 v_1 + c_2 \Big(\tfrac{\lambda_2}{\lambda_1}\Big)^k v_2 + \cdots
+ c_n \Big(\tfrac{\lambda_n}{\lambda_1}\Big)^k v_n.
$$

Every ratio $\lambda_j/\lambda_1$ has magnitude below $1$, so its powers vanish. Hence

$$
\frac{1}{(\lambda_1)^k} A^k x \;\longrightarrow\; c_1 v_1
\qquad \text{as } k \to \infty.
$$

The vectors $A^k x$ line up with the dominant eigenvector: the direction of $A^k x$
converges to the eigenspace of $\lambda_1$.

$$
% caption: Successive iterates $x, Ax, A^2 x, \dots$ swing toward the dominant
% eigenspace; each multiplication by $A$ suppresses the subdominant component.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (-0.3,0) -- (4.6,0) node[right, black!70] {$x_1$};
  \draw[->, black] (0,-0.3) -- (0,3.0) node[above, black!70] {$x_2$};
  \draw[acc!45, thick] (0,0) -- (4.2,2.8);
  \node[acc] at (3.6,2.75) {eigenspace $v_1$};
  \draw[->, black, thick] (0,0) -- (0.5,2.0) node[left] {$x$};
  \draw[->, black, thick] (0,0) -- (1.3,1.9);
  \draw[->, black, thick] (0,0) -- (2.3,1.85);
  \draw[->, acc, very thick] (0,0) -- (3.4,2.3) node[right, acc] {$A^k x$};
\end{tikzpicture}
$$

## The algorithm

The scaling factor $(\lambda_1)^k$ is unknown, so instead each iterate is rescaled so
its largest entry is $1$. The largest entry of $A x_k$ then converges to $\lambda_1$,
because $A x_k \approx \lambda_1 x_k$ once $x_k$ is close to an eigenvector.

```algorithm
caption: $\textsc{PowerMethod}(A, x_0)$ — estimate the dominant eigenvalue
require x_0 has largest entry equal to 1
for k = 0, 1, 2, ... do
  y <- A x_k
  mu <- an entry of y with the largest absolute value   // eigenvalue estimate
  x_{k+1} <- (1 / mu) y                                  // rescale largest entry to 1
until mu and x_k stop changing
return (mu, x_k)   // dominant eigenvalue and its eigenvector
```

> **Worked example.** Apply the power method to
> $A = \begin{bmatrix} 6 & 5 \\ 1 & 2 \end{bmatrix}$ starting from $x_0 = (0, 1)$.
>
> The first step computes $A x_0 = (5, 2)$, whose largest entry is $\mu_0 = 5$; scaling
> by $1/5$ gives $x_1 = (1, 0.4)$. Iterating produces the trace below.

| $k$ | $x_k$ | $A x_k$ | $\mu_k$ |
| --- | --- | --- | --- |
| $0$ | $(0,\, 1)$ | $(5,\, 2)$ | $5$ |
| $1$ | $(1,\, 0.4)$ | $(8,\, 1.8)$ | $8$ |
| $2$ | $(1,\, 0.225)$ | $(7.125,\, 1.45)$ | $7.125$ |
| $3$ | $(1,\, 0.2035)$ | $(7.0175,\, 1.407)$ | $7.0175$ |
| $4$ | $(1,\, 0.2005)$ | $(7.0025,\, 1.401)$ | $7.0025$ |
| $5$ | $(1,\, 0.20007)$ | $(7.00036,\, 1.40014)$ | $7.00036$ |

The estimates $\mu_k \to 7$ and $x_k \to (1, 0.2)$, and indeed
$A(1, 0.2)^\top = (7, 1.4)^\top = 7(1, 0.2)^\top$: the dominant eigenvalue is $7$ with
eigenvector $(1, 0.2)$.

## Rate of convergence

The leftover error in using a scaled $A^k x$ for $c_1 v_1$ is dominated by the term
$c_2 (\lambda_2 / \lambda_1)^k v_2$, so the convergence is geometric with ratio
$\vert\lambda_2 / \lambda_1\vert$.

> **Convergence rate.** The power method converges linearly with rate
> $\vert\lambda_2 / \lambda_1\vert$: the error shrinks by roughly that factor each
> iteration. Convergence is fast when the dominant eigenvalue is well separated
> ($\vert\lambda_2 / \lambda_1\vert$ small) and slow when $\vert\lambda_2\vert$ is
> close to $\vert\lambda_1\vert$.

In the worked run $\lambda_2 = 1$ and $\lambda_1 = 7$, so the ratio is $1/7$ and the
estimates gained roughly one digit per step.

$$
% caption: Error against iteration for two ratios; a small $|\lambda_2/\lambda_1| = 1/7$
% (steep line) converges far faster than a ratio near $0.95$ (shallow line).
\begin{tikzpicture}[>=stealth, scale=1.0, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \definecolor{red}{HTML}{B0413E}
  \draw[->, black] (0,0) -- (5.2,0) node[right, black!70] {iteration $k$};
  \draw[->, black] (0,0) -- (0,3.4) node[above, black!70] {error (log)};
  % fast: steep decay
  \draw[acc, very thick] (0.3,3.1) -- (4.8,0.3);
  \node[acc, anchor=west] at (3.0,1.9) {small ratio: fast};
  % slow: shallow decay
  \draw[red, very thick] (0.3,3.1) -- (4.8,2.0);
  \node[red, anchor=west] at (2.6,2.95) {ratio near 1: slow};
\end{tikzpicture}
$$

When $\vert\lambda_2/\lambda_1\vert$ is near $1$, the plain power method is too slow and
other approaches are preferred.

## The Rayleigh quotient

The largest-entry estimate $\mu_k$ is crude. A better eigenvalue estimate from an
approximate eigenvector uses the **Rayleigh quotient**. If $Ax = \lambda x$, then
$x^\top A x = \lambda (x^\top x)$, so

$$
R(x) = \frac{x^\top A x}{x^\top x}
$$

equals $\lambda$ exactly for an eigenvector, and is close to $\lambda$ when $x$ is close
to an eigenvector.

> **Rayleigh quotient accuracy.** For a **symmetric** matrix ($A^\top = A$), the
> Rayleigh quotient $R(x_k)$ has roughly twice as many correct digits as the
> largest-entry scale factor $\mu_k$ from the same iterate. Each power-method step then
> yields a markedly sharper eigenvalue estimate.

$$
% caption: From the same iterate the Rayleigh quotient carries about twice the correct
% digits of the largest-entry estimate for a symmetric matrix.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (0,0) -- (0,3.5) node[above, black!70] {correct digits};
  \draw[black] (0,0) -- (5.6,0);
  \foreach \k/\x/\mh/\rh in {1/0.7/0.8/1.6, 2/2.5/1.4/2.8, 3/4.3/1.9/3.1} {
    \fill[black] (\x,0) rectangle (\x+0.5,\mh);
    \fill[acc] (\x+0.55,0) rectangle (\x+1.05,\rh);
    \node[black] at (\x+0.5,-0.32) {$k=\k$};
  }
  \fill[black] (0.5,3.2) rectangle (0.85,3.4);
  \node[black, anchor=west] at (0.95,3.3) {largest-entry};
  \fill[acc] (3.1,3.2) rectangle (3.45,3.4);
  \node[acc, anchor=west] at (3.55,3.3) {Rayleigh $R(x_k)$};
\end{tikzpicture}
$$

This doubling is why symmetric problems — the setting of the
[Spectral Theorem](/linear-algebra/symmetric-quadratic-svd/diagonalizing-symmetric-matrices) —
are especially amenable to iteration.

## The inverse power method

The power method finds only the dominant eigenvalue. To target **any** eigenvalue $\lambda$,
given a rough estimate $\alpha$ near it, apply the power method to

$$
B = (A - \alpha I)^{-1}.
$$

If the eigenvalues of $A$ are $\lambda_1, \dots, \lambda_n$, the eigenvalues of $B$ are
$1/(\lambda_i - \alpha)$, with the **same** eigenvectors. When $\alpha$ is close to a
particular $\lambda_i$, the value $1/(\lambda_i - \alpha)$ is huge — strictly dominant
in $B$ — so the power method on $B$ homes in on that eigenvector rapidly.

$$
% caption: Shifting by $\alpha$ near an eigenvalue makes $1/(\lambda_i - \alpha)$
% dominate; the reciprocal blows up the eigenvalue nearest the shift.
\begin{tikzpicture}[>=stealth, scale=1.0, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \definecolor{red}{HTML}{B0413E}
  \draw[->, black] (-0.4,0) -- (5.4,0) node[right, black!70] {eigenvalues of $A$};
  \foreach \x/\lab in {0.6/{}, 2.0/{}, 4.7/{}} \fill[black] (\x,0) circle (2pt);
  \draw[red, thick, dashed] (2.35,-0.35) -- (2.35,0.9);
  \node[red, anchor=south] at (2.35,0.9) {shift point};
  \fill[red] (2.0,0) circle (2.6pt) node[below, red] {nearest};
  \draw[->, acc, thick] (2.0,-0.75) .. controls (3.0,-1.3) .. (4.6,-0.9);
  \node[acc, anchor=west] at (4.5,-0.9) {becomes dominant in $B$};
\end{tikzpicture}
$$

In practice $(A - \alpha I)^{-1}$ is never formed. Instead each step solves a linear
system, and the eigenvalue of $A$ is recovered from the estimate for $B$.

```algorithm
caption: $\textsc{InversePowerMethod}(A, \alpha, x_0)$ — estimate an eigenvalue near $\alpha$
require x_0 has largest entry equal to 1
for k = 0, 1, 2, ... do
  solve (A - alpha I) y = x_k for y      // reuse one LU factorization each step
  mu <- an entry of y with the largest absolute value
  lambda <- alpha + 1 / mu               // eigenvalue estimate for A
  x_{k+1} <- (1 / mu) y
until lambda and x_k stop changing
return (lambda, x_k)
```

Because the same matrix $A - \alpha I$ is solved against every step, one LU
factorization is computed once and reused. If no estimate of the smallest eigenvalue is
available, taking $\alpha = 0$ (so $B = A^{-1}$) targets the eigenvalue nearest zero.

> **Worked example.** Estimate the smallest eigenvalue of
> $$
> A = \begin{bmatrix} 10 & -8 & -4 \\ -8 & 13 & 4 \\ -4 & 5 & 4 \end{bmatrix}
> $$
> given rough eigenvalue estimates $21$, $3.3$, $1.9$.
>
> Take $\alpha = 1.9$, close to the smallest estimate. Then $1/(\lambda_i - \alpha)$ is
> largest for the eigenvalue near $1.9$, so the inverse power method on
> $(A - 1.9 I)^{-1}$ converges in a handful of steps to that eigenvalue, exactly $2$.

## The methods in context

| Method | Finds | Needs | Convergence rate |
| --- | --- | --- | --- |
| Power method | dominant eigenvalue $\lambda_1$ | a strictly dominant eigenvalue | $\vert\lambda_2/\lambda_1\vert$ |
| Rayleigh quotient | sharper $\lambda$ from an approximate eigenvector | (best for symmetric $A$) | doubles the digits |
| Inverse power method | eigenvalue nearest $\alpha$ | a good initial guess $\alpha$ | $\vert(\lambda_i - \alpha)/(\lambda_j - \alpha)\vert$ |

These algorithms handle simple situations well. Production software instead uses the
**QR algorithm**, which generates a sequence of matrices all similar to $A$ that
converge to triangular form, reading off every eigenvalue at once. It underlies the
standard eigenvalue routines and is developed with the rest of the
[numerical eigenvalue problem](/linear-algebra/numerical-linear-algebra/numerical-eigenvalues-and-svd).[^lay58]

[^lay58]: **Lay**, _Linear Algebra and Its Applications_, 5th ed., §5.8 — Iterative Estimates for Eigenvalues: the power method for a strictly dominant eigenvalue and its $\vert\lambda_2/\lambda_1\vert$ convergence rate, the Rayleigh quotient $R(x) = x^\top A x / x^\top x$, and the inverse power method using $(A - \alpha I)^{-1}$ to target an eigenvalue near $\alpha$.