Home > Mathematics > Linear Systems > Gauss-Seidel method

Gauss-Seidel method

Sunday 25 June 2006, by Nadir SOUALEM

All the versions of this article: [English] [français]

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

For this, we use a sequence $x^{(k)}$ which converges to the fixed point(solution) .
For $x^{(0)}$ given, we build a sequence $x^{(k)}$ such $x^{(k+1)}=F(x^{(k)})$ with $k \in \mathbf{N}$ .

where is an invertible matrix.

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

where is an affine function.

Algorithm

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

If is solution of 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}Ne^{(k)}$
We put $B = M^{-1}N$ , which gives

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

Convergence

The algorithm converges if $\lim_{k \to \infty} \| e^{(k)} \| = 0 \Leftrightarrow \lim_{k \to \infty} \| B^k \| = 0$ (null matrix).

Theorem: $\lim_{k \to \infty} \| B^k \| = 0$ if and only if the spectral radius of the matrix
checks:

$\rho(B)<1,$

we remind that $\rho(B) = \max_{i = 1,\ldots,n} |\lambda_i|$ where $\lambda_1,\ldots,\lambda_n$ represent the eigenvalues of .

Theorem: If A is strictly diagonally dominant,

$\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |},\forall i=1,\ldots,n$

then for all the Gauss-Seidel algorithm will converge to the solution of the system