Gauss-Seidel method

We will study an iterative method for solving linear systems: the Gauss-Seidel method. The aim is to build a sequence of approximations that converges to the true solution.

Iterative method

The Gauss-Seidel method is an iterative method for solving linear systems such as

$$Ax=b$$

For this, we use a sequence $x^{(k)}$ which converges to the fixed point(solution) $x$.

For $x^{(0)}$ given, we build a sequence $x^{(k)}$such $x^{(k+1)}=F(x^{(k)})$ with $k\in \mathbf{N}$.

$A=M-N$ where $M$ is an invertible matrix.

$$\begin{array}{cccc}Ax=b\iff Mx=Nx+b\iff & x& =& M^{-1}Nx+M^{-1}b\\ & & =& F(x)\end{array}$$

where $F$ is an affine function.

Algorithm

$$\{\begin{array}{cc}{x}^{(0)}\text{ given}& ,\\ x^{(k+1)}=M^{-1}N{x}^{(k)}+M^{-1}b& \text{else}.\end{array}$$

If $x$ is solution of $Ax=b$ then $x=M^{-1}Nx+M^{-1}b$

Error

Let $e^{(k)}$ be the error vector

$$e^{(k+1)}=x^{(k+1)}-x^{(k)}=M^{-1}N(x^{(k)}-x^{(k-1)})=M^{-1}N{e}^{(k)}$$

We put $B=M^{-1}N$, which gives

$$e^{(k+1)}=B{e}^{(k)}=B^{(k+1)}{e}^{(0)}.$$

Convergence

The algorithm converges if $\underset{k\to \mathrm{\infty }}{lim}|e^{(k)}|=0\iff \underset{k\to \mathrm{\infty }}{lim}|B^k|=0$ (null matrix).

Theorem: $\underset{k\to \mathrm{\infty }}{lim}|B^k|=0$ if and only if the spectral radius of the matrix $B$ checks: $\rho (B)<1,$ we remind that $\rho (B)=\underset{i=1,\dots ,n}{max}|{\lambda }_i|$ where ${\lambda }_1,\dots ,{\lambda }_n$ represent the eigenvalues of $B$.

Theorem: If A is strictly diagonally dominant, $\left|a_{ii}\right|>\sum _{i\ne j}\left|a_{ij}\right|,\mathrm{\forall }i=1,\dots ,n$ then for all $x_0$ the Gauss-Seidel algorithm will converge to the solution $x$ of the system $Ax=b.$

Gauss-Seidel Method

We decompose $A$ in the following way :$A=D-E-F$ with

• $D$ the diagonal
• $-E$ the strictly lower triangular part of $A$
• $-F$ the strictly upper triangular part of $A$.

In the Gauss-Seidel method we choose $M=D-E$ and $N=F$ (in the Jacobi method, $M=D$ et $N=E+F$).

$$x^{(k+1)}=(D-E{)}^{-1}F{x}^{(k)}+(D-E{)}^{-1}b$$

We obtain

$$x_i^{(k+1)}={\displaystyle \frac{b_i-{\displaystyle \sum _{j=1}^{i-1}{a}_{ij}{x}_j^{(k+1)}-{\displaystyle \sum _{j=i+1}^n{a}_{ij}{x}_j^{(k)}}}}{a_{ii}}}$$

Stop criteria

For the stop criteria , we can use the residual vector, wich gives for a given precision $ϵ$ :

$${\displaystyle \frac{\parallel r^{(k)}\parallel }{\parallel b\parallel }}=\frac{\parallel b-A{x}^{(k)}\parallel }{\parallel b\parallel }<ϵ$$