Méthode de Gauss-Seidel

Principe de construction

La méthode de Gauss-Seidel est une méthode itérative de résolution de système linéaire de la forme

Pour cela, on utilise une suite $x^{(k)}$ qui converge vers un point fixe

, solution du système d’équations linéaires. On cherche à construire l’algorithme pour $x^{(0)}$ donné, la suite $x^{(k+1)}=F(x^{(k)})$ avec $k \in \mathbf{N}$ .

où M est une matrice inversible.

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

où

est une fonction affine.

Algorithme

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

Si est solution de alors $x = M^{-1}Nx+M^{-1}b$

Erreur

Soit $e^{(k)}$ le vecteur erreur

$e^{(k+1)}=x^{(k+1)}-x^{(k)}=M^{-1}N(x^{(k)}-x^{(k-1)})=M^{-1}Ne^{(k)}$
On pose $B = M^{-1}N$ , ce qui donne

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

Convergence

L’algorithme converge si $\lim_{k \to \infty} \| e^{(k)} \| = 0 \Leftrightarrow \lim_{k \to \infty} \| B^k \| = 0$ (matrice nulle).

Théorème : Une condition nécessaire et suffisante pour que $\lim_{k \to \infty} \| B^k \| = 0$ est que le rayon spectral de vérifie

$\rho(B)<1,$

on rappelle que $\rho(B) = \max_{i = 1,\ldots,n} |\lambda_i|$ où $\lambda_1,\ldots,\lambda_n$ sont les valeurs propres de

Théorème : si est à diagonale strictement dominante

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

alors pour tout

la méthode de Gauss-Seidel converge vers la solution

du système

On décompose la matrice A de la façon suivante :

avec

la diagonale

la partie en dessous de la diagonale

la partie au dessus.

Dans la méthode de Gauss-Seidel, on choisit et (dans la méthode de Jacobi, et ).

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

on a alors :

$x^{(k+1)}_i = \displaystyle\frac{b_i - \displaystyle\sum_{j=1}^{i-1} a_{ij} x^{(k+1)}_j - \displaystyle\sum_{j=i+1}^{n} a_{ij} x^{(k)}_j }{a_{ii}}$

Test d’arrêt

Pour le test d’arrêt, on utilise le vecteur résidu $r^{(k)}=b-Ax^{(k)}$ , ce qui donne, pour une précision donnée $\epsilon$ :

$\frac{\|r^{(k)} \|}{\|b\|}=\frac{\|b-Ax^{(k)} \|}{\|b\|} < \epsilon$

Méthode de Gauss-Seidel

Mots-clés:

Principe de construction

Algorithme

Erreur

Convergence

Méthode de Gauss-Seidel

Test d’arrêt

Rubriques

Dans la même rubrique

Mots-clés