= Convergence criterion for a stationary iteration
{title2=$H^k\to0\iff\rho(H)<1$}
A <stationary iterative method for a linear system> converges to its specified <fixed point> for every initial <vector> if and only if its <iteration matrix> satisfies $\rho(H)<1$, where the <spectral radius> is the largest <modulus> of an <eigenvalue>.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Basic iterative methods: theorem following the spectral-radius lemmas, before the Jacobi update]{ref}
For a <diagonalizable matrix>, write $H=V\Lambda V^{-1}$. Then $H^k=V\Lambda^kV^{-1}$, so each <eigenvector> coefficient tends to zero exactly when its <eigenvalue> has <modulus> less than one. For a general <matrix>, the <Jordan normal form> gives the same result: a <Jordan block> $J=\lambda I+K$ with a <nilpotent matrix> $K$ of size $m$ satisfies
$$
J^k=\sum_{j=0}^{\min(k,m-1)}\binom{k}{j}\lambda^{k-j}K^j.
$$
If $0<|\lambda|<1$, every coefficient tends to zero because <exponential decay> beats any fixed <polynomial> in $k$; if $\lambda=0$, the block vanishes once $k\geq m$. Conversely, an <eigenvector> with $|\lambda|\geq1$ provides an initial error that cannot tend to zero. For a real <matrix> with complex <eigenvalues>, the same obstruction appears in the real <invariant subspace> spanned by the real and imaginary parts of an <eigenvector>.
The words "every initial <vector>" matter. For example, $H=\operatorname{diag}(3/2,1/2)$ fails the criterion, but $e^{(0)}=(0,1)^T$ still tends to zero. Here a generic initial error has a nonzero first coordinate and diverges; the exceptional errors lie on the second coordinate axis. With $H=\operatorname{diag}(-1,1/2)$, generic errors oscillate rather than diverge in <norm>, while the same exceptional axis still converges. Both are valid <matrix splittings> with $M=I$ and $A=I-H$. In general the convergent errors form the <direct sum> of the <generalized eigenspaces> for $|\lambda|<1$; if $\rho(H)\geq1$, this is a proper <linear subspace>.
A small <spectral radius> describes eventual convergence, but does not imply that the <Euclidean norm> of the error decreases on every step for a <non-normal matrix>. An <operator norm> bound $\|H\|<1$ does give the stepwise estimate $\|e^{(k)}\|\leq\|H\|^k\|e^{(0)}\|$. For a real <symmetric matrix>, the <matrix 2-norm> equals its <spectral radius>, making this particularly direct.
Back to article page
