Power Iteration

Definition Let $A \in \mathbb{F}^{n \times n}$, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$, and let $x_0 \in \mathbb{F}^n$ be nonzero. Power iteration repeats, for $k = 0, 1, 2, \dots$,

If some $y_{k+1} = 0$, the iteration stops, because normalization is undefined. The zero image is a result in its own right, since it shows that $x_k$ lies in $\ker A$, and a new start is needed to explore other directions. As long as no zero appears, each $x_k$ with $k \ge 1$ is a positive multiple of $A^k x_0$, so

The usual eigenvalue estimate is the Rayleigh quotient $\theta_k = x_k^{*}Ax_k / (x_k^{*}x_k)$, which equals $x_k^{*}Ax_k$ for every $k \ge 1$, and for $k = 0$ too when the start is a unit vector. Convergence is a statement about lines, not about vectors. A negative or nonreal dominant eigenvalue contributes a sign or a complex factor of modulus $1$ to the iterates at every step, so the right comparison is between the line $\operatorname{span}(x_k)$ and an eigenvector line, or between $x_k$ and a target after that phase is removed. Here and below a tuple such as $(1, 1)$ stands for a column vector.

Definition Let $A \in \mathbb{F}^{n \times n}$, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$, and count its eigenvalues in $\mathbb{C}$ with algebraic multiplicity. An eigenvalue $\lambda_1$ is dominant if it has algebraic multiplicity one and $\lvert \lambda_1 \rvert > \lvert \lambda \rvert$ for every other eigenvalue $\lambda$ of $A$. Power iteration also needs $\lambda_1 \ne 0$, which is automatic when $n \ge 2$. A dominant eigenvalue has a one-dimensional eigenspace, the dominant eigenvector line $\operatorname{span}(v_1)$. When $n \ge 2$, listing the eigenvalues as $\lambda_1, \lambda_2, \dots, \lambda_n$ with $\lvert \lambda_2 \rvert \ge \cdots \ge \lvert \lambda_n \rvert$, dominance means $\lvert \lambda_1 \rvert > \lvert \lambda_2 \rvert$, and the ratio

controls the speed of power iteration. If $A$ is real and has a dominant eigenvalue, that eigenvalue is real and has a real eigenvector, because the nonreal eigenvalues of a real matrix come in conjugate pairs of equal modulus. The word dominant is sometimes used loosely for any eigenvalue of largest modulus, but the convergence theorem below needs the strict version.

Definition Let $A \in \mathbb{C}^{n \times n}$ be diagonalizable, a real matrix being viewed as complex, with an eigenbasis $v_1, \dots, v_n$ of $\mathbb{C}^n$ and $Av_j = \lambda_j v_j$. Suppose $\lambda_1$ is dominant and nonzero, so $\lvert \lambda_j \rvert < \lvert \lambda_1 \rvert$ for $j \ge 2$, and let $\rho = \max_{j \ge 2} \lvert \lambda_j \rvert / \lvert \lambda_1 \rvert < 1$, or $\rho = 0$ when $n = 1$. Write the start as $x_0 = c_1v_1 + \cdots + c_nv_n$ and suppose $c_1 \ne 0$. Then no iterate is zero, and

where $S = \sum_{j \ge 2} \lvert c_j \rvert \lVert v_j \rVert_2$. Consequently, for every $k \ge 1$ with $\rho^k S < \lvert c_1 \rvert \lVert v_1 \rVert_2$,

which tends to $0$ like $\rho^k$. The phase-corrected iterates $(\lvert \lambda_1 \rvert / \lambda_1)^k x_k$ converge to the unit vector $c_1v_1 / \lVert c_1v_1 \rVert_2$, and the Rayleigh quotients $\theta_k$ converge to $\lambda_1$.

For the proof, expand $A^k x_0 = \sum_j c_j \lambda_j^k v_j$ and divide by $\lambda_1^k$. The remainder is $e_k = \sum_{j \ge 2} c_j (\lambda_j/\lambda_1)^k v_j$, and each ratio has modulus at most $\rho$, which gives the bound on $e_k$. The $v_1$ coordinate of $A^k x_0$ is $c_1\lambda_1^k \ne 0$, so $A^k x_0 \ne 0$. With $z_k = c_1v_1 + e_k$ we have, for $k \ge 1$, $x_k = (\lambda_1/\lvert \lambda_1 \rvert)^k z_k / \lVert z_k \rVert_2$. The distance from $z_k$ to the line is at most $\lVert e_k \rVert_2$, and the reverse triangle inequality gives $\lVert z_k \rVert_2 \ge \lvert c_1 \rvert \lVert v_1 \rVert_2 - \lVert e_k \rVert_2$, which proves the distance bound. Since $z_k \to c_1v_1 \ne 0$, the norms converge to the positive number $\lVert c_1v_1 \rVert_2$, so $z_k / \lVert z_k \rVert_2$ converges to $c_1v_1 / \lVert c_1v_1 \rVert_2$. That unit vector is an eigenvector for $\lambda_1$, and the Rayleigh quotient is continuous and unchanged by the phase factor, so $\theta_k \to \lambda_1$.

The constant $S / (\lvert c_1 \rvert \lVert v_1 \rVert_2)$ depends on the start and on the eigenbasis. When the eigenvectors are nearly dependent, an ordinary starting vector can have very large coefficients, so a long transient can come before the rate $\rho^k$ is visible. The theorem says nothing about defective matrices. The matrix $B$ with rows $(1/2, 10)$ and $(0, 1/2)$ has only the eigenvalue $1/2$, yet $Be_2 = (10, 1/2)$ has norm above $10$. With $N_0 = e_1e_2^{\mathsf{T}}$, which satisfies $N_0^2 = 0$, one has $B = \tfrac{1}{2}(I + 20N_0)$ and

So $B^k e_2 = 2^{-k}(20k, 1)$, whose direction approaches $\operatorname{span}(e_1)$ only like $1/(20k)$, not geometrically.

Definition In the convergence theorem the start must satisfy $c_1 \ne 0$, where $c_1$ is the coordinate of $x_0$ along $v_1$ in the eigenbasis expansion $x_0 = c_1v_1 + \cdots + c_nv_n$. Equivalently, $x_0 \notin \operatorname{span}(v_2, \dots, v_n)$. With $V = [v_1 \ \cdots \ v_n]$ the coordinate is the first entry of $V^{-1}x_0$. It can also be computed from a left eigenvector $w_1 \ne 0$ with $w_1^{*}A = \lambda_1 w_1^{*}$. For $j \ge 2$ the identity $\lambda_1 w_1^{*}v_j = w_1^{*}Av_j = \lambda_j w_1^{*}v_j$ with $\lambda_j \ne \lambda_1$ forces $w_1^{*}v_j = 0$, and then $w_1^{*}v_1 \ne 0$, since $w_1^{*}$ cannot vanish on a whole basis. Hence

and the condition reads $w_1^{*}x_0 \ne 0$. In general this is not the condition $v_1^{*}x_0 \ne 0$, a nonzero inner product with the dominant eigenvector. The two agree when $A$ is normal, because then the eigenbasis can be chosen orthonormal and $c_1 = v_1^{*}x_0$ for a unit vector $v_1$. If $c_1 = 0$, then in exact arithmetic the dominant component stays zero forever, and the iteration behaves as if $\lambda_1$ were absent. A random start whose distribution has a density, such as one with independent normal entries, satisfies $c_1 \ne 0$ with probability one, because $\operatorname{span}(v_2, \dots, v_n)$ is a proper subspace.

Definition Let $A \in \mathbb{F}^{n \times n}$, where $\mathbb{F}$ is $\mathbb{R}$ or $\mathbb{C}$. The top of its spectrum has equal-modulus eigenvalues when two eigenvalues, counted with algebraic multiplicity, share the largest modulus, $\lvert \lambda_1 \rvert = \lvert \lambda_2 \rvert \ge \lvert \lambda_j \rvert$ for all $j$. Then the decay argument gives nothing, because it needs $\lvert \lambda_2 \rvert < \lvert \lambda_1 \rvert$. Two cases differ.

If $\lambda_2 \ne \lambda_1$, as for $\lambda$ and $-\lambda$ or for a conjugate pair of a real matrix, the ratio $\lambda_2/\lambda_1 = e^{i\varphi}$ has modulus $1$ but is not $1$. Suppose $A$ is diagonalizable, these two simple eigenvalues are the only ones of largest modulus, and $c_1, c_2 \ne 0$. Then $A^k x_0 / \lambda_1^k$ equals $c_1v_1 + e^{ik\varphi}c_2v_2$ plus terms that tend to zero, and since $e^{ik\varphi}$ does not converge, the lines $\operatorname{span}(x_k)$ do not converge. A real matrix whose largest eigenvalues form a nonreal conjugate pair has no real eigenvector for them, so real iterates cannot settle on one.

If the only eigenvalue of largest modulus is a repeated eigenvalue $\lambda_1 \ne 0$ and $A$ is diagonalizable, the eigenspace of $\lambda_1$ has dimension at least two. The iterates converge to the line through the part of the eigenbasis expansion of $x_0$ that lies in this eigenspace, provided that part is nonzero. So a line is found, but the start decides which one. A defective repeated eigenvalue falls outside the theorem altogether.

Definition Let $A \in \mathbb{C}^{n \times n}$, let $v \in \mathbb{C}^n$ be a unit vector, $\lVert v \rVert_2 = 1$, and let $\theta \in \mathbb{C}$. The eigenpair residual of $(\theta, v)$ is

It is zero exactly when $(\theta, v)$ is an eigenpair of $A$. In general $(\theta, v)$ is an exact eigenpair of the nearby matrix $A - rv^{*}$, since $(A - rv^{*})v = Av - r = \theta v$, and $\lVert rv^{*} \rVert_2 = \lVert r \rVert_2$, so the residual norm is a backward error. For a fixed $v$ the residual is smallest when $\theta$ is the Rayleigh quotient $v^{*}Av$, because $Av - (v^{*}Av)v$ is orthogonal to $v$ and

The residual bound for normal matrices turns a small residual into eigenvalue information. If $A$ is normal, $A^{*}A = AA^{*}$, with eigenvalues $\lambda_1, \dots, \lambda_n$, then for every unit vector $v$ and every $\theta \in \mathbb{C}$

For the proof, the spectral theorem gives an orthonormal eigenbasis $q_1, \dots, q_n$ of $\mathbb{C}^n$. Write $v = \sum_j c_jq_j$ with $\sum_j \lvert c_j \rvert^2 = 1$. Then $r = \sum_j (\lambda_j - \theta)c_jq_j$, so

The bound places some eigenvalue in the closed disk of radius $\lVert r \rVert_2$ around $\theta$. It does not say which eigenvalue, and when eigenvalues are close together it does not say that $v$ is near a particular eigenvector. Real symmetric and Hermitian matrices are normal, so the bound applies to them. For a diagonalizable $A = V\Lambda V^{-1}$ the same idea gives $\min_j \lvert \lambda_j - \theta \rvert \le \kappa_2(V)\lVert r \rVert_2$, because $v = V(\Lambda - \theta I)^{-1}V^{-1}r$ when $\theta$ is not an eigenvalue, and the condition number of the eigenvector matrix can be large.