Sufficient Convergence Condition for Gauss–Jacobi

Summary

Strict diagonal dominance of $A$ is a practical sufficient condition for Jacobi (and often Gauss–Seidel) convergence. The sharp criterion for any stationary iteration $x^{(k+1)}=T{x}^{(k)}+c$ is $\rho (T)<1$ .

Prerequisites

• Gauss-Jacobi Method
• Matrix norms and eigenvalues (spectral radius)

Problem Type

Decide whether Jacobi iteration for $Ax=b$ is guaranteed to converge.

Method Definition

Jacobi matrix: with $A=D+L+U$ ,

Spectral radius criterion (necessary and sufficient). The iteration converges for every $x^{(0)}$ if and only if

Norm criterion (sufficient). If $\parallel T_J\parallel <1$ for some subordinate matrix norm, then $\rho (T_J)<1$ , so the method converges.^[1]

Strict diagonal dominance (sufficient). If

then $\parallel T_J{\parallel }_{\mathrm{\infty }}<1$ , hence Jacobi converges.

Assumptions / Requirements

• $a_{ii}\ne 0$ so $D^{-1}$ exists
• Dominance is strict for the simple $\mathrm{\infty }$ -norm argument above

Worked Example 1 (borderline dominance)

Row 1: $|2|=|1|+|-1|$ (not strict). Rows 2–3 are strictly dominant. Dominance test is inconclusive; one must inspect $\rho (T_J)$ (or run the iteration carefully).

Worked Example 2 (strict dominance)

Each row satisfies $|a_{ii}|>\sum _{j\ne i}|a_{ij}|$ , so Jacobi converges for every start.

Error / Accuracy

Even when convergence is guaranteed, monitor $\parallel x^{(k+1)}-x^{(k)}\parallel$ and $\parallel b-A{x}^{(k)}\parallel$ .

Common Failure Modes

• Treating weak dominance ( $|a_{ii}|\ge \sum _{j\ne i}|a_{ij}|$ ) as an automatic guarantee
• Confusing sufficient conditions with necessary ones
• Applying a Jacobi bound unchanged to Gauss–Seidel without using $T_{GS}$

Connections

• Gauss-Jacobi Method, Gauss-Seidel Method
• Iterative Methods
• Numerical Methods/Linear Systems/Solving Linear Systems

References