Convergence Tests for Jacobi and Gauss-Seidel

From an Iteration to an Error Recurrence

Jacobi and Gauss-Seidel are stationary iterative methods: each step applies the same matrix to the current estimate, then adds a fixed vector. Whether the estimates approach the solution is therefore controlled by repeated powers of that matrix. The spectral radius gives an exact convergence test, while strict diagonal dominance gives a convenient sufficient condition that can be checked directly from the coefficients.

Let \(\mathbf{A}\in\mathbb{R}^{n\times n}\) be nonsingular, and consider \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Write \(\mathbf{A}=\mathbf{D}+\mathbf{L}+\mathbf{U}\), where \(\mathbf{D}\) is diagonal, \(\mathbf{L}\) contains the entries below the diagonal, and \(\mathbf{U}\) contains those above it. Assume every diagonal entry of \(\mathbf{A}\) is nonzero, so \(\mathbf{D}\) and the lower triangular matrix \(\mathbf{D}+\mathbf{L}\) are invertible.

For either method, write the update as \(\mathbf{x}^{(k+1)}=\mathbf{T}\mathbf{x}^{(k)}+\mathbf{c}\). A fixed point \(\mathbf{x}\) satisfies \(\mathbf{x}=\mathbf{T}\mathbf{x}+\mathbf{c}\). For Jacobi, multiplying this equation by \(\mathbf{D}\) gives \(\mathbf{D}\mathbf{x}=-(\mathbf{L}+\mathbf{U})\mathbf{x}+\mathbf{b}\), hence \(\mathbf{A}\mathbf{x}=\mathbf{b}\). For Gauss-Seidel, multiplication by \(\mathbf{D}+\mathbf{L}\) gives \((\mathbf{D}+\mathbf{L})\mathbf{x}=-\mathbf{U}\mathbf{x}+\mathbf{b}\), again equivalent to \(\mathbf{A}\mathbf{x}=\mathbf{b}\). Thus the exact solution is the fixed point for both methods.

Let \(\mathbf{x}\) be that solution and define the error by \(\mathbf{e}^{(k)}=\mathbf{x}^{(k)}-\mathbf{x}\). Subtracting the fixed-point equation from the iteration gives the central recurrence:

The error tends to zero for every starting vector exactly when every initial error is driven to zero by powers of \(\mathbf{T}\). The spectral radius captures this property.

Proof. First, \(\mathbf{T}^k\to\mathbf{O}\) implies that every eigenvalue has absolute value less than \(1\). If \(\lambda\) is an eigenvalue with nonzero complex eigenvector \(\mathbf{v}\), then \(\mathbf{T}^k\mathbf{v}=\lambda^k\mathbf{v}\). If \(|\lambda|\ge1\), this sequence does not tend to zero, contradicting \(\mathbf{T}^k\to\mathbf{O}\).

Conversely, suppose every eigenvalue has absolute value less than \(1\). Use the standard Jordan canonical form over \(\mathbb{C}\), whose construction is proved in the later treatment of Jordan form: \(\mathbf{T}=\mathbf{P}\mathbf{J}\mathbf{P}^{-1}\), with \(\mathbf{J}\) a block diagonal matrix of Jordan blocks. A block of size \(m\) has the form \(\mathbf{J}_{\lambda}=\lambda\mathbf{I}+\mathbf{N}\), where \(\mathbf{N}^m=\mathbf{O}\). For \(\lambda\ne0\), the binomial formula gives $$ \mathbf{J}_{\lambda}^{\,k} =\sum_{r=0}^{m-1}\binom{k}{r}\lambda^{k-r}\mathbf{N}^{r}, $$ where terms with \(r>k\) are zero. Each scalar coefficient tends to zero: a fixed-degree polynomial in \(k\) multiplied by \(|\lambda|^k\) tends to zero when \(|\lambda|<1\). If \(\lambda=0\), the block is \(\mathbf{N}\), whose powers are zero for \(k\ge m\). Hence every block power tends to zero, so \(\mathbf{J}^k\to\mathbf{O}\) and \(\mathbf{T}^k=\mathbf{P}\mathbf{J}^k\mathbf{P}^{-1}\to\mathbf{O}\). Finally, \(\mathbf{e}^{(k)}=\mathbf{T}^k\mathbf{e}^{(0)}\) shows convergence for every initial error. Conversely, convergence for every real initial error forces \(\mathbf{T}^k\to\mathbf{O}\), since applying the powers to each standard basis vector makes every column tend to zero. The two implications prove the criterion. \(\square\)

Worked Convergence Tests

Strict Diagonal Dominance as a Sufficient Test

Proof. First, strict row diagonal dominance implies that \(\mathbf{A}\) is nonsingular. If \(\mathbf{A}\mathbf{z}=\mathbf{0}\) for a nonzero vector \(\mathbf{z}\), choose \(i\) with \(|z_i|=\|\mathbf{z}\|_{\infty}>0\). The \(i\)-th equation would imply $$ |a_{ii}|\|\mathbf{z}\|_{\infty} \le \sum_{j\ne i}|a_{ij}||z_j| \le \left(\sum_{j\ne i}|a_{ij}|\right)\|\mathbf{z}\|_{\infty} <|a_{ii}|\|\mathbf{z}\|_{\infty}, $$ a contradiction. Thus the homogeneous system has only the zero solution, and the square matrix is nonsingular.

For Jacobi, the absolute row sum of its iteration matrix in row \(i\) is \(\sum_{j\ne i}|a_{ij}|/|a_{ii}|<1\). There are finitely many rows, so their maximum is some \(q<1\). Hence \(\|\mathbf{T}_{J}\|_{\infty}\le q<1\), and \(\|\mathbf{T}_{J}^{\,k}\|_{\infty}\le q^k\to0\).

For Gauss-Seidel, let \(\mathbf{y}=\mathbf{T}_{GS}\mathbf{x}\). Its component equations are $$ a_{ii}y_i=-\sum_{j<i}a_{ij}y_j-\sum_{j>i}a_{ij}x_j. $$ Suppose \(\mathbf{x}\ne\mathbf{0}\) and \(\|\mathbf{y}\|_{\infty}\ge\|\mathbf{x}\|_{\infty}\). Choose an index \(i\) with \(|y_i|=\|\mathbf{y}\|_{\infty}\). Then $$ |a_{ii}|\|\mathbf{y}\|_{\infty} \le \left(\sum_{j<i}|a_{ij}|\right)\|\mathbf{y}\|_{\infty} +\left(\sum_{j>i}|a_{ij}|\right)\|\mathbf{x}\|_{\infty} \le \left(\sum_{j\ne i}|a_{ij}|\right)\|\mathbf{y}\|_{\infty} <|a_{ii}|\|\mathbf{y}\|_{\infty}, $$ which is impossible. Thus \(\|\mathbf{T}_{GS}\mathbf{x}\|_{\infty}<\|\mathbf{x}\|_{\infty}\) for every nonzero real \(\mathbf{x}\). The unit sphere in \(\mathbb{R}^n\) is compact, and \(\mathbf{x}\mapsto\|\mathbf{T}_{GS}\mathbf{x}\|_{\infty}\) is continuous. Its maximum on that sphere is therefore some \(q<1\); scaling gives \(\|\mathbf{T}_{GS}\mathbf{x}\|_{\infty}\le q\|\mathbf{x}\|_{\infty}\) for every \(\mathbf{x}\). Consequently its powers tend to zero. The spectral-radius criterion now proves convergence of both methods for every starting vector. \(\square\)

Common Mistake: Treating a Sufficient Condition as Necessary

A common error is to see that strict diagonal dominance fails and conclude that an iteration must diverge. The second worked example is a concrete counterexample to that reasoning: its first row satisfies \(1<2\), so the matrix is not strictly diagonally dominant, but the Jacobi eigenvalues have absolute value \(1/\sqrt{2}<1\), and Gauss-Seidel has spectral radius \(1/2<1\). The correction is to treat diagonal dominance as a convenient sufficient test. When it fails, compute or otherwise bound the spectral radius instead.

Another pitfall is to check only that one update looks close to the solution. Convergence concerns every later power of the iteration matrix, not a single step or a small residual at one iterate. The recurrence \(\mathbf{e}^{(k)}=\mathbf{T}^k\mathbf{e}^{(0)}\) explains why the spectral-radius test addresses the long-term behavior.