Méthode de Gauss-Seidel

La méthode de Gauss-Seidel est une méthode itérative pour résoudre les systèmes linéaires $Ax=b$, où $A$ est une matrice carrée d'ordre $n$ et $x,b$ sont des vecteurs de $\mathbb R^n.$ Elle consiste en la manipulation suivante : on écrit $A$ sous la forme $A=D-L-U$, où $D$ est une matrice diagonale, $-L$ est une matrice triangulaire inférieure ($L$ pour Lower), et $-U$ est une matrice triangulaire supérieure ($U$ pour Upper). On peut alors transformer le système en $$Ax=b\iff (D-L)x-Ux=b\iff x=(D-L)^{-1}Ux+(D-L)^{-1}b.$$ On définit ensuite une suite de vecteurs $(x^k)$ en choisissant un vecteur $x^0\in\mathbb R^n$ et par la formule de récurrence $$x^{k+1}=(D-L)^{-1}Ux^k+(D-L)^{-1}b.$$ On espère que la suite $(x^k)_k$ converge vers une solution de $Ax=b.$ Sous de bonnes hypothèses concernant la matrice $A$, c'est effectivement le cas.

Cette méthode appelle plusieurs commentaires. Le premier est qu'on peut se demander pourquoi on a besoin d'une méthode qui donne une solution approchée à une équation, alors qu'on dispose d'un algorithme (le pivot de Gauss) qui donne en un temps raisonnable (de l'ordre de $n^3$ opérations) une solution exacte. Il se trouve que le pivot de Gauss est numériquement instable. Les erreurs de calcul de l'ordinateur s'accumulent et font que la solution que l'on calcule est parfois très éloignée de la solution exacte. La convergence de la méthode de Gauss-Seidel est fondée sur le théorème du point fixe, et cette méthode est plus stable numériquement.

Ensuite, il faut vérifier que la suite $(x^k)$ est facilement calculable. Mais comme $(D-L)$ est une matrice triangulaire inférieure, elle n'est pas du tout difficile à inverser, et on a la formule suivante pour calculer $x^{k+1}$ : $$x_{i}^{k+1}=\frac 1{a_{i,i}}\left(b_i-\sum_{j=1}^{i-1}a_{i,j}x_j^{k+1}-\sum_{j=i+1}^n a_{i,j}x_j^k\right).$$ Cette formule montre que la méthode de Gauss-Seidel est une amélioration de la méthode de Jacobi. Dans la méthode de Jacobi, la relation de récurrence est : $$x_{i}^{k+1}=\frac 1{a_{i,i}}\left(b_i-\sum_{j=1}^{i-1}a_{i,j}x_j^{k}-\sum_{j=i+1}^n a_{i,j}x_j^k\right).$$ L'avantage de la méthode de Gauss-Seidel est que, pour calculer $x_i^{k+1}$, on utilise les valeurs déjà calculées de $x_j^{k+1}$, pour $j<i$, au lieu de $x_j^k$ comme dans la méthode de Jacobi.

La méthode de Gauss-Seidel est un cas particulier des méthodes de relaxation.