Voir la source de Méthode de Gauss-Seidel

La '''méthode de Gauss-Seidel''' est une [[méthode itérative]] de résolution d'un [[système d'équations linéaires|système linéaire]] (de dimension finie) de la forme <math>Ax = b</math>, ce qui signifie qu'elle génère une suite qui converge vers une solution de cette équation, lorsque celle-ci en a une et lorsque des conditions de convergence sont satisfaites (par exemple lorsque <math>A</math> est symétrique [[Matrice définie positive|définie positive]]). L'algorithme suppose que la diagonale de <math>A</math> est formée d'éléments non nuls.

La méthode se décline en une version « par blocs ».

Le principe de la méthode peut s'étendre à la résolution de systèmes d'équations non linéaires et à l'[[Optimisation (mathématiques)|optimisation]], mais avec des conditions d'efficacité moins claires. En optimisation, l'utilité de cette approche dépendra beaucoup de la structure du problème. Le principe gauss-seidelien permet aussi d'interpréter d'autres algorithmes.

Il est nommé d'après [[Carl Friedrich Gauss]] et [[Philipp Ludwig von Seidel]], qui l'ont développé et appliqué pour le calcul d'angles en [[géodésie]]<ref>{{article |lang=en |titre=Iterative solution of linear systems in the 20th century |auteur1=Yousef Saada |auteur2=Henk A. van der Vorst  |périodique=Journal of Computational and Applied Mathematics |volume=123 |année=2000 |pages=1–33 |doi=10.1016/S0377-0427(00)00412-X |lire en ligne=https://pdf.sciencedirectassets.com/271610/1-s2.0-S0377042700X01112/1-s2.0-S037704270000412X/main.pdf?X-Amz-Security-Token=IQoJb3JpZ2luX2VjEIP%2F%2F%2F%2F%2F%2F%2F%2F%2F%2FwEaCXVzLWVhc3QtMSJHMEUCIAzkfgL%2Babx5wtxJF7nBwObaLtg%2BSbhEtPu5ego9aIMAAiEAwcK1Io07%2BN5fm1SGB38bpEq%2F%2F1dMocz2Ld1lOQpQ4q4qsgUILBAFGgwwNTkwMDM1NDY4NjUiDCnjRZIcC7hZFl%2BM6yqPBX9tSdOSZNF2fFCulua0r%2FPNDxJ8gh6kdC3FY0qIY4i%2BAdFT98egDb8PM35OLC2mkELPLUykw5NHdOXQdGhvW096chHs0m%2BG46LqRqpRrSqY%2FV4Qi7y0WVjBzgJRwE0ODlccsaurxo4YZo280Knp%2Fvmg1SOMbwlZAiknV2tn69VFPmLXEp1%2FAZJzI9Et%2BKKHLqm%2BEiRH6RfxtPAAauKhIL1NVVFoUhSvBNIYTRhIJ5UelNUWnDYRO25nyV3AduAN1mbGaYbVZCbf%2Bb16JYVLg4mxjpj75JAT1to%2Blddxga3dV0RN0PiFSiIBsn5VeRA7DlWC5v8l%2BoEjn5Zpt9uk3EwLWBYtNaKfWlGcUE3cKXBoH7AnPYb73mC%2Fxd8y2t7mfbusarJDYEoK1ICguxZFgUEBY5ijKve2e5kXDP0a1I6Fp2jWxAcbWM3ATglmCFIJMIHS8afCLDWAidA6nNlVLcKOik0mYQ15nLI3YO%2F0pZDWQFZHf8A7AUVKVaa3uz57sBki3R2MtwTZhLSlFM7yiLh4RV2XVi%2BEYymGwNXdLvi5cTdL1K37dt7Zv%2Bxc8giB%2FNtuxVagM0nmWHQHrHQ21A6Xv%2Fi09Wy7Ex53CSu2aDwVVlUA%2FA22THP5yJvfCFfDbCEL5zXm%2BGiko4CJQc7OFOwzKy2GujBu1hlAKXSzw3oNXS%2FvFmyFf6YvucAdRBc5YqwQjj38ZgEMk7PxR1HnCwZ5p24irad8QNl%2BH3qQMkLaa3kpDzL8APlApV79GryoLr5Dnt5xB4MaUoF0vRKodeRPXNBXCgsKWoo956Ui35UoYKlQ0e63rvTeFY2K7m96zbf5x2H7ghCWxhQo4OYuD8A1DD%2BHaKys0qSVWJ08%2FWow9a2zpgY6sQF8HSCgS1Prx5RmGQyW%2FKtir%2Fw1%2BcGmBPTuYaq8PFOM1x5feH7FsOqmgFhb9Ll%2BPIt9tCcNE0msqkzfQu0FB3debI0oW4Wov2tmqYY0BubVvACFqTzcG33sPuUIKLUtc4OIUljLSj4LkMs%2BZuPbGCXXfRXn%2FI4LZ6n4blytrl7cNBFO2maLnK1duLUa30o2e5h3m0BU%2F7s08pM28qIJHwBvlPmZDgJD3mzasrhnW%2FFDZ3E%3D&X-Amz-Algorithm=AWS4-HMAC-SHA256&X-Amz-Date=20230804T121615Z&X-Amz-SignedHeaders=host&X-Amz-Expires=300&X-Amz-Credential=ASIAQ3PHCVTYQ7UQAHVK%2F20230804%2Fus-east-1%2Fs3%2Faws4_request&X-Amz-Signature=68bcec6af823049270bb4449ba660b9137f5c69ea2814b41e2217ccd4ba88780&hash=312c491f6839acd90c485d4beb337143defc1c6219ae1ab74220be3970571cb9&host=68042c943591013ac2b2430a89b270f6af2c76d8dfd086a07176afe7c76c2c61&pii=S037704270000412X&tid=spdf-be465bce-99e6-47f6-a5f0-45cbd74f2ab9&sid=8063bf8a1a0f924f634939327a8e36a12743gxrqb&type=client&tsoh=d3d3LnNjaWVuY2VkaXJlY3QuY29t&ua=1c1459045353030600020c&rr=7f16bafdca0641fc&cc=fr}}</ref>{{,}}<ref>{{ouvrage |lang=de |auteur1=Carl Friedrich Gauss |année=1973 |titre=Werke |volume=II |éditeur=Königlichen Gesellschaft der Wissenschaften zu Göttingen}} Réédité par Georg Olms Verlag, Hildesheim, 436-447.</ref>.

== L'algorithme ==

=== Principe ===

Soit

<center><math>
Ax=b
</math></center>

le système linéaire à résoudre, que l'on suppose écrit sous forme matricielle avec <math>A\in\R^{n\times n}</math> et <math>b\in\R^n</math>, ce qui signifie que l'on cherche <math>x\in\R^n</math> tel que le produit matriciel <math>Ax</math> soit égal à <math>b</math>.

On note <math>a_{ij}</math> les éléments de <math>A</math> et <math>b_i</math> ceux de <math>b</math> :

<center><math>
A=\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
a_{n1} & a_{n2} & \cdots & a_{nn}
\end{pmatrix}
\qquad\mbox{et}\qquad
b = \begin{pmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{pmatrix}.
</math></center>

La méthode de Gauss-Seidel résout le système linéaire <math>Ax=b</math> de manière [[Méthode itérative|itérative]], ce qui veut dire qu'elle génère une suite de vecteurs <math>x^k\in\R^n</math>, pour <math>k=0,1,2,\dots</math>. On interrompt le calcul de la suite lorsque l'[[Méthode itérative|itéré]] courant, disons <math>x^k</math>, est jugé suffisamment proche d'une solution, par exemple parce que le ''résidu'' <math>Ax^k-b</math> est petit.

Soit <math>x^{k}=(x^{k}_1, \ldots, x^{k}_n)\in\R^n</math> l'itéré courant. L'itéré suivant <math>x^{k+1}=(x^{k+1}_1, \ldots, x^{k+1}_n)\in\R^n</math> se calcule en <math>n</math> étapes, comme suit.

* {{souligner|Étape 1}}. Si l'on suppose que <math>a_{11}\ne0</math> et connaissant <math>(x^{k}_2, \ldots, x^{k}_n)</math>, on peut calculer <math>x^{k+1}_1</math> au moyen de la première équation du système linéaire <math>Ax=b</math>. De manière plus précise, <math>x^{k+1}_1</math> est pris comme solution de<center>{{Saut|10px}}<math>a_{11}\underline{x^{k+1}_1}+a_{12}x^{k}_2+\cdots+a_{1n}x^{k}_n=b_1,</math>{{Saut|10px}}</center>ce qui est possible si <math>a_{11}\ne0</math>.
* {{souligner|Étape 2}}. Si l'on suppose que <math>a_{22}\ne0</math> et connaissant <math>(x^{k+1}_1, x^{k}_3, \ldots, x^{k}_n)</math>, on peut calculer <math>x^{k+1}_2</math> au moyen de la deuxième équation du système linéaire <math>Ax=b</math>. De manière plus précise, <math>x^{k+1}_2</math> est pris comme solution de<center>{{Saut|10px}}<math>a_{21}x^{k+1}_1+a_{22}\underline{x^{k+1}_2}+a_{23}x^{k}_3+\cdots+a_{2n}x^{k}_n=b_2,</math>{{Saut|10px}}</center>ce qui est possible si <math>a_{22}\ne0</math>.
* {{souligner|Étape <math>i\in[\![1,n]\!]</math>}} (cas général). Si l'on suppose que <math>a_{ii}\ne0</math> et connaissant <math>(x^{k+1}_1, \ldots, x^{k+1}_{i-1}, x^{k}_{i+1}, \ldots, x^{k}_n)</math>, on peut calculer <math>x^{k+1}_i</math> au moyen de la <math>i</math>-ième équation du système linéaire <math>Ax=b</math>. De manière plus précise, <math>x^{k+1}_i</math> est pris comme solution de<center>{{Saut|10px}}<math>a_{i1}x^{k+1}_1+\cdots+a_{i,i-1}x^{k+1}_{i-1}+a_{ii}\underline{x^{k+1}_i}+a_{i,i+1}x^{k}_{i+1}+\cdots+a_{in}x^{k}_n=b_i,</math>{{Saut|10px}}</center>ce qui est possible si <math>a_{ii}\ne0</math>.

En résumé, pourvu que les éléments diagonaux de <math>A</math> soient non nuls, on calcule les composantes <math>x^{k+1}_i</math> de <math>x^{k+1}</math> de manière séquentielle pour <math>i=1,\ldots,n</math> par

{{Bloc emphase|bord=1px solid;|espacement=1.5ex|<math>x^{k+1}_i = \frac{1}{a_{ii}}\left(b_i - \sum_{j=1}^{i-1} a_{ij} x^{k+1}_j - \sum_{j=i+1}^n a_{ij} x^{k}_j\right).</math>}}

La formule fait intervenir les éléments <math>x^{k+1}_j</math> (<math>j=1,\dots,i-1</math>) calculés dans les étapes précédentes.

=== Expression matricielle ===

L'expression matricielle de l'algorithme suppose que la matrice <math>A</math> se sépare comme suit

<center><math>
A=L+D+U,
</math></center>

où <math>D</math> est la partie [[Matrice diagonale|diagonale]] de <math>A</math>, <math>L</math> (pour ''lower'') sa partie [[Matrice triangulaire|triangulaire]] inférieure stricte et <math>U</math> (pour ''upper'') sa partie triangulaire supérieure stricte.

Une [[itération]] de la méthode de Gauss-Seidel, celle passant de <math>x^k</math> à <math>x^{k+1}</math>, consiste alors à résoudre le système triangulaire inférieur

{{Bloc emphase|bord=1px solid;|espacement=1.5ex|<math>(L+D)x^{k+1} = b-U x^k,</math>}}

de « haut en bas », c'est-à-dire en déterminant successivement <math>x^{k+1}_1</math>, <math>x^{k+1}_2</math>, ..., <math>x^{k+1}_n</math>.

=== Convergence ===

La formule de mise à jour des itérés dans la méthode de Gauss-Seidel montre que ceux-ci sont des [[Application contractante#Approximations successives|approximations successives]] pour le calcul d'un [[point fixe]] de l'application

<center><math>
x\mapsto(L+D)^{-1}(b-Ux).
</math></center>

Les propriétés de convergence de la méthode vont donc dépendre du [[Spectre d'un opérateur linéaire|spectre]] de la matrice <math>(L+D)^{-1}U</math>.

On sait que la méthode de Gauss-Seidel converge, quels que soient le vecteur <math>b</math> et le point initial <math>x^0</math>, dans les situations suivantes :
* si la matrice <math>A</math> est symétrique [[Matrice définie positive|définie positive]]<ref>Voir par exemple, P. G. Ciarlet (1982), théorème 5.3.2.</ref> ;
* si A est [[Matrice à diagonale dominante|à diagonale strictement dominante]].

=== Discussion ===

Un seul vecteur <math>v\in\R^n</math> suffit pour mémoriser les itérés successifs : à l'étape <math>i</math>, il suffit de mémoriser les éléments déjà calculés de <math>x^{k+1}</math>, à savoir <math>x^{k+1}_j</math> pour <math>j=1,\ldots,i-1</math>, dans <math>v_{1:i-1}</math> et les éléments de <math>x^k</math> encore utiles, à savoir <math>x^k_j</math> pour <math>j=i+1,\ldots,n</math>, dans <math>v_{i+1:n}</math>. Cette faible exigence en espace mémoire peut être un atout dans certaines circonstances.

Contrairement à la [[méthode de Jacobi]], l'algorithme est essentiellement séquentiel et n'est donc pas adapté au calcul parallèle.

== Généralisations ==

=== Méthode par blocs ===

La version par blocs de la méthode de Gauss-Seidel procède de manière similaire à la méthode élément par élément, mais en remplaçant l'utilisation des éléments de <math>A</math> par des sous-matrices de <math>A</math>, appelées ici des ''blocs''.

On suppose que l'ensemble des indices <math>[\![1,n]\!]</math> est partitionné en <math>p</math> sous-intervalles (non vides et deux-à-deux disjoints) :

<center><math>
[\![1,n]\!]=I_1\cup I_2\cup\cdots\cup I_p.
</math></center>

La matrice <math>A</math> et le vecteur <math>b</math> sont alors dissocié comme suit

<center><math>
A=\begin{pmatrix}
A_{I_1I_1} & A_{I_1I_2} & \cdots & A_{I_1I_p} \\
A_{I_2I_1} & A_{I_2I_2} & \cdots & A_{I_2I_p} \\
\vdots     & \vdots     & \ddots & \vdots \\
A_{I_pI_1} & A_{I_pI_2} & \cdots & A_{I_pI_p}
\end{pmatrix}
\qquad\mbox{et}\qquad
b = \begin{pmatrix} b_{I_1} \\ b_{I_2} \\ \vdots \\ b_{I_p} \end{pmatrix},
</math></center>

où <math>A_{IJ}</math> est la sous-matrice de <math>A</math> obtenue en sélectionnant les éléments avec indices de ligne dans <math>I</math> et indices de colonnes dans <math>J</math>, tandis que <math>b_I</math> est le sous-vecteur de <math>b</math> obtenu en sélectionnant les éléments avec indices dans <math>I</math>.

''La méthode de Gauss-Seidel par blocs suppose que les sous-matrices principales <math>A_{I_iI_i}</math>, avec <math>i\in[\![1,p]\!]</math>, sont inversibles.''

Une itération de la méthode de Gauss-Seidel ''par blocs'', celle passant de <math>x^k</math> à <math>x^{k+1}</math>, s'écrit de la même manière que la méthode élément par élément, à savoir

{{Bloc emphase|bord=1px solid;|espacement=1.5ex|<math>(L+D)x^{k+1} = b-U x^k,</math>}}

mais avec des définitions différentes de <math>L</math>, <math>D</math> et <math>U</math> :

<center><math>
L=\begin{pmatrix}
0          & \cdots & \cdots         & 0      \\
A_{I_2I_1} & \ddots &                & \vdots \\
\vdots     & \ddots & \ddots         & \vdots \\
A_{I_pI_1} & \cdots & A_{I_pI_{p-1}} & 0
\end{pmatrix},
\quad
D=\begin{pmatrix}
A_{I_1I_1} & 0          & \cdots & 0         \\
0          & A_{I_2I_2} & \ddots & \vdots    \\
\vdots     & \ddots     & \ddots & 0         \\
0          & \cdots     & 0      & A_{I_pI_p}
\end{pmatrix}
\quad\mbox{et}\quad
U=A-L-D.
</math></center>

La résolution du système triangulaire par blocs ci-dessus, se fait également de « haut en bas », c'est-à-dire en déterminant successivement <math>x^{k+1}_{I_1}</math>, <math>x^{k+1}_{I_2}</math>, ..., <math>x^{k+1}_{I_p}</math>.

=== Systèmes d'équations non linéaires ===

Le principe de la méthode de Gauss-Seidel peut également s'appliquer à la résolution d'un système d'équations non linéaires <math>F(x)=0</math>, où <math>F:\R^n\to\R^n</math>. Ce système s'écrit donc sous la forme de <math>n</math> équations non linéaires à <math>n</math> inconnues :

<center><math>
\left\{\begin{array}{l}
F_1(x_1,x_2,\ldots,x_n)=0\\
F_2(x_1,x_2,\ldots,x_n)=0\\
\cdots\\
F_n(x_1,x_2,\ldots,x_n)=0.
\end{array}\right.
</math></center>

La méthode de Gauss-Seidel résout ce système de manière itérative, en générant donc une suite de vecteurs <math>x^k\in\R^n</math>, pour <math>k=0,1,2,\dots</math>. On interrompt le calcul de la suite lorsque l'itéré courant, disons <math>x^k</math>, est jugé suffisamment proche d'une solution, par exemple parce que le ''résidu'' <math>F(x^k)</math> est petit.

Soit <math>x^{k}=(x^{k}_1, \ldots, x^{k}_n)\in\R^n</math> l'itéré courant. L'itéré suivant <math>x^{k+1}=(x^{k+1}_1, \ldots, x^{k+1}_n)\in\R^n</math> se calcule en <math>n</math> étapes, comme suit.

* {{souligner|Étape 1}}. Connaissant <math>(x^{k}_2, \ldots, x^{k}_n)</math>, on calcule <math>x^{k+1}_1</math> comme solution de l'équation non linéaire (elle est supposée exister) :<center>{{Saut|10px}}<math>F_1(\underline{x^{k+1}_1}, x^{k}_2, \ldots, x^{k}_n)=0.</math>{{Saut|10px}}</center>

* {{souligner|Étape 2}}. Connaissant <math>(x^{k+1}_1, x^{k}_3, \ldots, x^{k}_n)</math>, on calcule <math>x^{k+1}_2</math> comme solution de l'équation non linéaire (elle est supposée exister) :<center>{{Saut|10px}}<math>F_2(x^{k+1}_1, \underline{x^{k+1}_2}, x^{k}_3, \ldots, x^{k}_n)=0.</math>{{Saut|10px}}</center>

* {{souligner|Étape <math>i\in[\![1,n]\!]</math>}} (cas général). Connaissant <math>(x^{k+1}_1,\ldots,x^{k+1}_{i-1}, x^{k}_{i+1}, \ldots, x^{k}_n)</math>, on calcule <math>x^{k+1}_i</math> comme solution de l'équation non linéaire (elle est supposée exister) :<center>{{Saut|10px}}<math>F_i(x^{k+1}_1, \ldots, x^{k+1}_{i-1}, \underline{x^{k+1}_i}, x^{k}_{i+1}, \ldots, x^{k}_n)=0.</math>{{Saut|10px}}</center>

La version ''par blocs'' se définit facilement en considérant des groupes d'équations et d'inconnues, au lieu de considérer, comme ci-dessus, équation et inconnue une par une.

=== Optimisation ===

Le principe de la méthode de Gauss-Seidel décrit dans la section précédente s'applique naturellement au problème d'[[Optimisation (mathématiques)|optimisation]] non linéaire

<center><math>
\inf_{x\in X}\;f(x),
</math></center>

dans lequel on  minimise une fonction <math>f:\R^n\to\R</math> sur un sous-ensemble <math>X</math> de <math>\R^n</math>. Nous présentons directement ci-dessous la version « par blocs », qui est la plus utile lorsque le nombre <math>p</math> de blocs est faible (souvent <math>p=2</math>). La méthode de Gauss-Seidel perd en effet de sa pertinence lorsque <math>p</math> est grand, par manque d'efficacité dans ce cas. La version « élément par élément » peut être vue comme un cas particulier de la version par blocs, obtenue en prenant <math>n</math> blocs de cardinal 1.

On suppose donc que l'ensemble des indices est ''[[Partition (mathématiques)|partitionné]]'' en <math>p</math> blocs,

<center><math>
[\![1,n]\!]=I_1\cup I_2\cup\cdots\cup I_p,
</math></center>

et que l'ensemble admissible est un [[produit cartésien]] de <math>p</math> ensembles,

<center><math>
X=X_1\times X_2\times\cdots\times X_p,
</math></center>

où chaque <math>X_i</math> est un ''[[Ensemble convexe|convexe]]'' de <math>\R^{|I_i|}</math>. La variable <math>x\in\R^n</math> se décomposera comme suit

<center><math>
x=(x_{I_1},x_{I_2},\ldots,x_{I_p}).
</math></center>

Lorsque <math>f</math> est différentiable et que <math>X=\R^n</math>, on pourrait obtenir une méthode de Gauss-Seidel en appliquant la méthode de la [[#Systèmes d'équations non linéaires|section précédente]] à la [[Conditions d'optimalité (dimension finie)#Conditions du premier ordre sans contrainte|condition d'optimalité]] du premier ordre de ce problème d'optimisation sans contrainte, à savoir

<center><math>
\nabla f(x)=0,
</math></center>

qui est un système de <math>n</math> équations non linéaires à <math>n</math> inconnues <math>x=(x_1,\ldots,x_n)</math>. Mais on peut préférer, comme ci-dessous, rester dans le domaine de l'optimisation en minimisant <math>f</math> séquentiellement, bloc par bloc. Cette option a l'avantage de pouvoir prendre en compte des contraintes, c'est-à-dire de restreindre les variables à l'ensemble admissible <math>X</math>.

La ''méthode de Gauss-Seidel''<ref>Cette méthode est appelée ''méthode de relaxation'' par Glowinski, Lions et Trémolières (1976), mais cette appellation est utilisée pour beaucoup trop d'algorithmes pour qu'elle soit suffisamment discriminante.</ref> résout le problème d'optimisation ci-dessus de manière itérative, en générant donc une suite <math>\{x^k\}\subset\R^n</math>. L'algorithme passe d'un itéré <math>x^k</math> au suivant <math>x^{k+1}</math> en minimisant <math>f</math> un bloc de variables à la fois, en séquence. On interrompt le calcul de la suite lorsque l'itéré courant, disons <math>x^k</math>, est jugé suffisamment proche d'une solution, par exemple parce que la norme du [[gradient projeté]] <math>\|g^{\rm\scriptscriptstyle P}(x^k)\|</math> est jugée suffisamment petite.

{{Théorème|Algorithme de Gauss-Seidel en optimisation|Une itération
passe de l'itéré courant <math>x^k\in X</math> à l'itéré suivant
<math>x^{k+1}\in X</math> en <math>p</math> étapes successives, indicées
par <math>i=1,\ldots,p</math> :
<center><math>
x^{k+1}_{I_i}\in\operatorname{arg\,min}_{x_{I_i}\in X_i}\,
f(x^{k+1}_{I_1},\ldots, x^{k+1}_{I_{i-1}}, x_{I_i},x^k_{I_{i+1}}, \ldots, x^k_{I_p}).
</math></center>}}

La version ''élément par élément'' se définit facilement en considérant des blocs <math>I_i</math> de cardinal 1 et en minimisant <math>f</math> composante par composante.

Le résultat suivant montre la convergence de la méthode de Gauss-Seidel lorsque <math>f</math> est de classe <math>C^1</math>, coercive et strictement convexe<ref>Résultat qui semble dû à Glowinski, Lions et Trémolières (1976), théorème 1.2, page 66.</ref>.

{{Théorème|Convergence de l'algorithme de Gauss-Seidel en optimisation|Si, pour chaque <math>i\in[\![1,p]\!]</math>, <math>X_i</math> est un convexe fermé non vide de <math>\R^{|I_i|}</math> et si <math>f</math> est [[Coercivité|coercive]] sur <math>X</math>, strictement convexe sur <math>X</math> et de classe <math>C^1</math> dans un voisinage de <math>X</math>, alors
* le problème ci-dessus a une unique solution <math>\bar{x}</math>,
* l'algorithme est bien défini et, quel que soit l'itéré initial <math>x^0\in X</math>, l'algorithme génère une suite <math>\{x^k\}\subset X</math> qui converge vers <math>\bar{x}</math>.}}

;Remarques

# Si l'on applique ce résultat au cas où <math>X=\R^n</math> et <math>f</math> est la fonction quadratique <math>x\mapsto \frac{1}{2} x^\top Ax-b^\top x</math>, on retrouve le résultat affirmant que la méthode de Gauss-Seidel par blocs pour résoudre le système linéaire <math>Ax=b</math> converge, quels que soient le vecteur <math>b</math> et le point initial, pourvu que <math>A</math> soit définie positive.
# La méthode de Gauss-Seidel est un algorithme lent (il requiert beaucoup d'itérations), dont la mise en œuvre est coûteuse (chaque itération peut demander beaucoup de temps de calcul, selon les cas). Tel qu'il est présenté, il requiert en effet la minimisation ''exacte'' de <math>f</math> dans chaque problème intermédiaire et ces <math>p</math> minimisations doivent être réalisées à chaque itération. Son application est donc restreinte au cas où le nombre de blocs est petit.
# L'algorithme de Gauss-Seidel ne s'étend pas aisément à des ensembles admissibles plus complexes qu'un produit cartésien d'ensembles convexes. Par exemple si l'on cherche à minimiser composante par composante la fonction linéaire <math>f:\R^2\to\R: (x_1,x_2) \mapsto x_1+x_2</math> sur l'ensemble <math>X:=\{x\in\R^2_+:x_1x_2\geq1\}</math>, qui n'est pas le produit cartésien de deux intervalles, tout point de la frontière de <math>X</math> est bloquant (c'est-à-dire que l'algorithme ne peut y progresser), alors que seul le point <math>\bar{x}=(1,1)</math> est solution.
# En l'absence de convexité, la méthode de Gauss-Seidel ne converge pas nécessairement, même pour des fonctions de classe <math>C^\infty</math>. Powell (1973) a en effet construit plusieurs fonctions conduisant à la non-convergence de la méthode de Gauss-Seidel composante par composante, notamment une fonction <math>C^\infty</math> de trois variables pour laquelle les itérés générés ont un [[cycle limite]] formé de 6 points auxquels le gradient n'est pas nul.
# D'autres résultats de convergence sont donnés par Luo et Tseng (1992).
# La méthode est vraiment peu élégante<ref>{{Article|langue=de|auteur1=Johann. T. Lügenwert|titre=Die Innere Schreklichkeit Der Gauss-Seidel Methode|périodique=Mathematische Untersuchungen - Leipzig|date=1891|lire en ligne=|pages=24}}</ref>.

== Annexes ==

=== Notes ===

{{références|colonnes=2}}

=== Articles connexes ===

* [[Factorisation de Cholesky|Méthode de Cholesky]]
* [[Méthode de Jacobi]]
* [[Décomposition LU]]
* [[Décomposition QR]]
* [[Méthode de surrelaxation successive|Méthode de surrelaxation successive ou SOR]]

=== Liens externes ===

* [http://www.math-linux.com/spip.php?article36 Méthode de Gauss-Seidel] sur math-linux.com
* J. Ch. Gilbert, ''[http://www-rocq.inria.fr/~gilbert/ensta/optim.html Éléments d'Optimisation Différentiable — Théorie et Algorithmes]'', syllabus de cours à l'[[École nationale supérieure de techniques avancées|ENSTA ParisTech]], Paris.

=== Références ===

* {{ouvrage |auteur=P. G. Ciarlet |année=1982 |titre=Introduction à l’Analyse Numérique Matricielle et à l’Optimisation |éditeur=Masson |lieu=Paris}}.
* {{ouvrage |auteur1=R. Glowinski |auteur2=J.-L. Lions |auteur3=R. Trémolières |année=1976 |titre=Analyse Numérique des Inéquations Variationnelles - Tome 1 : Théorie Générale et Premières Applications - Tome 2 : Applications aux phénomènes stationnaires et d'évolution |éditeur=[[Éditions Dunod|Dunod]] |lieu=Paris}}.
* {{article |lang=en |auteur1=Z.-Q. Luo |auteur2=P. Tseng |année=1992 |titre=On the convergence of the coordinate descent method for convex differentiable minimization |périodique=Journal of Optimization Theory and Applications |volume=72 |pages=7–35}}.
* {{article |lang=en |auteur1=M. J. D. Powell |année=1973 |titre=On search directions for minimization algorithms |périodique=Mathematical Programming |volume=4 |pages=193–201}}.

{{Palette|Analyse Numérique|Gauss}}
{{Portail|analyse}}

[[Catégorie:Analyse numérique matricielle|Methode de Gauss-Seidel]]
[[Catégorie:Carl Friedrich Gauss|Methode de Gauss-Seidel]]