= Gauss-Seidel method
{c}
{wiki=Gauss–Seidel_method}
= Gauss-Seidel iteration
{c}
{synonym}
With $A=D+L+U$, the <Gauss-Seidel method> solves $(D+L)x^{(k+1)}=b-Ux^{(k)}$. It uses each newly computed coordinate immediately in the remaining <triangular solve>. It is <successive over-relaxation> with parameter one, and converges from every start when $A$ is a <symmetric positive-definite matrix>.
To solve a <linear system> $Ax=b$, split its <matrix> into the <diagonal matrix> $D$ and the strictly lower and upper parts $L,U$, retaining their actual signs. Every diagonal entry must be nonzero. A sweep updates coordinates in order:
$$
x_i^{(k+1)}=\frac{b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}}{a_{ii}}.
$$
The <Jacobi method> uses the old <vector> throughout; the <Gauss-Seidel method> reuses each fresh coordinate. Thus the update order is part of the method.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Gauss-Seidel: component loop, splitting and update-order remark, web lines 372–380]{ref}
The <matrix splitting> has $M=D+L$, $N=-U$, so its <iteration matrix> is
$$
H=-(D+L)^{-1}U,\qquad x^{(k+1)}=Hx^{(k)}+(D+L)^{-1}b.
$$
Compute the update by <forward substitution> with the <lower triangular matrix> $D+L$, rather than forming a <matrix inverse>. For a <sparse matrix>, a sweep only visits stored entries and can overwrite the working <vector>. Dependencies on fresh coordinates constrain parallel execution. This makes the <Gauss-Seidel method> an inexpensive solver component, including in a <multigrid method>.<Math 221, Matrix Computations, Fall 2009/Notes for Ma221 Lecture 21, Nov 10 2009>[Math 221, Matrix Computations, Fall 2009; Basic iterative methods, cheap splitting requirement; Gauss-Seidel loop and red-black ordering; opening list of solver building blocks]{ref}
Back to article page
