= Gauss-Seidel convergence from diagonal dominance and positive definiteness
{c}
{title2=$\rho(H)<1$}
A <strictly diagonally dominant matrix> or a real <symmetric positive-definite matrix> guarantees convergence of the <Gauss-Seidel method> from every initial <vector>. These are sufficient conditions.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Theorem 1, strict row diagonal dominance, web lines 462–465; Theorem 3, positive-definite SOR and its ω = 1 specialization, web lines 490–493]{ref}
For <strict diagonal dominance>, put
$$
q=\max_i\frac{\sum_{j\ne i}|a_{ij}|}{|a_{ii}|}<1,\qquad E=\|e^{(k)}\|_\infty.
$$
Induct through a sweep. Old coordinates have absolute error at most $E$; previously updated coordinates have absolute error at most $qE\leq E$. The component update and the <triangle inequality> therefore bound the new error by $qE$. This proves $\|e^{(k+1)}\|_\infty\leq q\|e^{(k)}\|_\infty$, a <maximum norm> contraction.
For a <symmetric positive-definite matrix>, write $A=D+L+L^T$. The <Householder-John theorem> applies to $M=D+L$ and $N=-L^T$, because $M^T+N=D$ is a <positive-definite matrix>. Hence the <iteration matrix> has <spectral radius> less than one, which gives the <convergence criterion for a stationary iteration>.
There is also a geometric reason fresh updates help: the <Gauss-Seidel method> is exact <coordinate descent> on the <convex quadratic function>
$$
F(z)=\frac12z^TAz-b^Tz,\qquad F(z)-F(x_*)=\frac12(z-x_*)^TA(z-x_*).
$$
Holding the other coordinates fixed, minimizing in coordinate $i$ gives the corresponding row update. A change $\delta_i$ lowers $F$ by exactly $a_{ii}\delta_i^2/2$. Each fresh coordinate is therefore the minimizer for the current <vector>, and a complete sweep lowers the <quadratic form> error unless every coordinate already solves its row. This explains the method's beauty without implying monotone decrease in every <vector norm>.
Back to article page
