Gauss–Jacobi Method

Summary

Jacobi iteration updates every unknown from the previous full vector. It is simple to parallelize and converges when the iteration matrix has spectral radius less than one (strict diagonal dominance is a common sufficient test).

Prerequisites

• Iterative Methods
• Component form of $Ax=b$

Problem Type

Iteratively solve $Ax=b$ with $a_{ii}\ne 0$ .

Method Definition

Write $A=D+L+U$ with $D$ diagonal and $L,U$ strict lower/upper parts. Jacobi uses

or componentwise

Iteration matrix: $T_J=-D^{-1}(L+U)=I-D^{-1}A$ .^[1]

Assumptions / Requirements

• Nonzero diagonals
• Prefer a starting vector $x^{(0)}$ (often $0$ )

Algorithm

1. Choose $x^{(0)}$ , tolerance $\epsilon$ , max iterations.
2. For each $i$ , compute $x_i^{\text{new}}$ from all $x_j^{\text{old}}$ , $j\ne i$ .
3. Set $x^{\text{old}}\leftarrow x^{\text{new}}$ only after all $i$ are updated.
4. Stop on $\parallel x^{\text{new}}-x^{\text{old}}{\parallel }_{\mathrm{\infty }}<\epsilon$ or residual test.

Convergence

Converges for every start iff $\rho (T_J)<1$ . Strict diagonal dominance of $A$ is sufficient. See Sufficient Convergence Condition for Gauss-Jacobi.

Error / Accuracy

Use infinity-norm step and residual $\parallel b-Ax{\parallel }_{\mathrm{\infty }}$ .

Worked Example

With $x^{(0)}=(0,0)$ :

True solution: $(x_1,x_2)=(14/5,12/5)=(2.8,2.4)$ . Residual of iterates shrinks toward zero.

Common Failure Modes

• Zero diagonal entry
• Updating in place (that would be Gauss–Seidel)
• Expecting convergence without $\rho (T_J)<1$

Connections

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

References