Gauss–Seidel method

Remarks

The error satisfies $e_{k+1} = G e_k$ with $G = -L_*^{-1} U$, and convergence for all starts means that the spectral radius of $G$ is less than $1$. In case 1, an eigenvector argument bounds each eigenvalue $\lambda$ of $G$ by $\abs{\lambda} \le \max_i \frac{\sum_{j > i} \abs{a_{ij}}}{\abs{a_{ii}} - \sum_{j < i} \abs{a_{ij}}} < 1$. In case 2, the energy $\norm{e}_A^2 = e^T A e$ strictly decreases along the iteration, by a computation with $L_*^T + L_* - A = D$, where $D$ is the positive diagonal of $A$. Example: for $A$ with rows $(2, 1)$ and $(1, 2)$ and $b = (3, 3)$, starting at $0$ gives $(1.5, 0.75)$, then $(1.125, 0.9375)$, tending to $(1, 1)$. The error is multiplied by $1/4$ at each step, the square of the Jacobi factor $1/2$. Without the hypotheses the method can diverge: for $A$ with rows $(1, 2)$ and $(2, 1)$, which is symmetric but indefinite, $G$ has spectral radius $4$.

Going deeper

For a student

In matrix form Gauss–Seidel is the iterative method of the splitting $A = M - N$ with $M = L_*$, so each step is a forward substitution. For symmetric positive definite $A$ it is a coordinate-wise minimization of the energy $\frac12 x^T A x - b^T x$. Its sweeps depend on the order of the unknowns, which makes it harder to parallelize than Jacobi. Successive over-relaxation adds a weight to each update and can converge much faster.