L'essentiel à connaître
Jacobi, Gauss-Seidel et SOR résolvent $Ax=b$ en construisant une suite de vecteurs $x^{(0)}, x^{(1)}, x^{(2)}, \dots$ censée tendre vers la solution : on isole $x_i$ dans la $i$-ième équation, puis on remplace les autres inconnues par des valeurs déjà connues. Jacobi prend toutes ces valeurs dans l'itéré précédent $x^{(k)}$ ; Gauss-Seidel utilise tout de suite les composantes qu'il vient de recalculer. Exemple : si la première équation est $3x_1+x_2=5$, les deux méthodes posent $x_1^{(k+1)}=\frac{5-x_2^{(k)}}{3}$ ; ensuite, pour $x_2$, Jacobi garde $x_1^{(k)}$ quand Gauss-Seidel prend déjà $x_1^{(k+1)}$.
Formule : on écrit $A=D-E-F$, où $D$ est la diagonale de $A$, $-E$ sa partie strictement inférieure et $-F$ sa partie strictement supérieure.
Jacobi : $x_i^{(k+1)}=\frac{1}{a_{ii}}\Big(b_i-\sum_{j\neq i}a_{ij}x_j^{(k)}\Big)$, soit $Dx^{(k+1)}=(E+F)x^{(k)}+b$, de matrice d'itération $J=D^{-1}(E+F)$.
Gauss-Seidel : $x_i^{(k+1)}=\frac{1}{a_{ii}}\Big(b_i-\sum_{j<i}a_{ij}x_j^{(k+1)}-\sum_{j>i}a_{ij}x_j^{(k)}\Big)$, soit $(D-E)x^{(k+1)}=Fx^{(k)}+b$, de matrice d'itération $\mathcal{L}_1=(D-E)^{-1}F$.
SOR (sur-relaxation successive) : $x_i^{(k+1)}=\omega\,\tilde{x}_i^{(k+1)}+(1-\omega)\,x_i^{(k)}$, où $\tilde{x}_i^{(k+1)}$ est la valeur donnée par la formule de Gauss-Seidel ; sa matrice d'itération se note $\mathcal{L}_\omega$, et $\omega=1$ redonne Gauss-Seidel.
Chaque méthode s'écrit $x^{(k+1)}=Bx^{(k)}+c$, où $B$ est sa matrice d'itération, et l'erreur vérifie $e^{(k)}=B^ke^{(0)}$. Elle converge pour tout $x^{(0)}$ si et seulement si $\rho(B)<1$, le rayon spectral $\rho(B)$ étant le plus grand module des valeurs propres de $B$. Une norme subordonnée (induite par une norme de vecteurs) $\|B\|<1$ suffit, puisque $\rho(B)\le\|B\|$, mais elle n'est pas nécessaire. À la longue, l'erreur est multipliée par environ $\rho(B)$ à chaque itération.
Règle : si $A$ est à diagonale strictement dominante, c'est-à-dire $|a_{ii}|>\sum_{j\neq i}|a_{ij}|$ sur chaque ligne $i$, Jacobi et Gauss-Seidel convergent quel que soit $x^{(0)}$ (UTC, MT09, proposition IV.1.2). Si $A$ est symétrique définie positive ($A^T=A$ et $x^TAx>0$ pour $x\neq0$), Gauss-Seidel converge, SOR converge si et seulement si $0<\omega<2$, mais Jacobi peut diverger (cours de R. Herbin, théorème 1.34 et remarque 1.35). Pour toute matrice de taille $n$, $\det\mathcal{L}_\omega=(1-\omega)^n$, donc $\rho(\mathcal{L}_\omega)\ge|1-\omega|$ : SOR ne peut converger que si $0<\omega<2$.
Pour une matrice tridiagonale (coefficients nuls hors de la diagonale et de ses deux voisines), $\rho(\mathcal{L}_1)=\rho(J)^2$ : à la longue, une itération de Gauss-Seidel réduit l'erreur autant que deux de Jacobi (même cours, théorème 1.36).
À retenir : si $A$ est tridiagonale, que les valeurs propres de $J$ sont réelles et que $\rho(J)<1$, le meilleur paramètre de SOR est $\omega_0=\frac{2}{1+\sqrt{1-\rho(J)^2}}$, et alors $\rho(\mathcal{L}_{\omega_0})=\omega_0-1$.
Quiz : teste tes connaissances
Les questions montent en difficulté, et les trois dernières sont les plus piégeuses.
Question 1 : Que fait une méthode itérative comme Jacobi pour résoudre $Ax=b$ ?
Réponse : B. On part d'un vecteur $x^{(0)}$ et on calcule $x^{(1)}, x^{(2)}, \dots$ jusqu'à la précision voulue. A est le piège : c'est le propre d'une méthode directe, comme l'élimination de Gauss décrite en C.
Question 2 : Dans un système de trois équations à coefficients tous non nuls, avec quelles valeurs Jacobi calcule-t-il $x_2^{(k+1)}$ ?
Réponse : D. Jacobi n'utilise que l'itéré précédent, et $x_2^{(k)}$ n'intervient pas puisqu'on isole $x_2$. A est le piège : c'est Gauss-Seidel, qui reprend aussitôt $x_1^{(k+1)}$.
Question 3 : Quelle formule est celle de Gauss-Seidel ?
Réponse : A. Les $x_j$ d'indice $j<i$ sont déjà recalculés à l'itération $k+1$, donc on les prend. B est le piège : il inverse les deux sommes, alors que les $x_j$ d'indice $j>i$ ne sont pas encore recalculés. C est Jacobi, et D oublie de diviser par $a_{ii}$.
Question 4 : Pour quelle valeur de $\omega$ la méthode SOR redonne-t-elle exactement Gauss-Seidel ?
Réponse : C. Avec $\omega=1$, le terme $(1-\omega)\,x_i^{(k)}$ disparaît et il reste la valeur de Gauss-Seidel. A est le piège : avec $\omega=0$, on aurait $x^{(k+1)}=x^{(k)}$, et la suite ne bougerait plus.
Question 5 : Avec $A=D-E-F$, quelle écriture est celle de Gauss-Seidel ?
Réponse : A. Les composantes déjà recalculées sont celles d'indice $j<i$ : la partie inférieure $-E$ reste à gauche avec la diagonale. D est le piège : $Ax=b$ s'écrit $(D-E)x-Fx=b$, donc $-F$ passe à droite en devenant $+F$. C est Jacobi.
Question 6 : Une méthode s'écrit $x^{(k+1)}=Bx^{(k)}+c$. Quelle condition est nécessaire et suffisante pour qu'elle converge quel que soit $x^{(0)}$ ?
Réponse : B. L'erreur vaut $B^ke^{(0)}$, qui tend vers $0$ pour tout départ exactement quand $\rho(B)<1$. A est le piège : cette condition suffit mais n'est pas nécessaire, car $B=\begin{pmatrix}0&2\\0&0\end{pmatrix}$ a $\rho(B)=0$ et $\|B\|_\infty=2$.
Question 7 : On résout $4x_1-x_2=2$ et $-x_1+4x_2=7$ en partant de $x^{(0)}=(1\,;\,1)$. Que vaut $x^{(1)}$ avec Jacobi ?
Réponse : A. $x_1^{(1)}=\frac{2+x_2^{(0)}}{4}=\frac{3}{4}$ et $x_2^{(1)}=\frac{7+x_1^{(0)}}{4}=2$. B est le piège : en passant de l'autre côté, $-x_2$ devient $+x_2$. D est Gauss-Seidel, et C oublie de diviser par $4$.
Question 8 : Même système, même départ $x^{(0)}=(1\,;\,1)$. Que vaut $x^{(1)}$ avec Gauss-Seidel ?
Réponse : D. $x_1^{(1)}=\frac{3}{4}$ comme avec Jacobi, puis on l'utilise aussitôt : $x_2^{(1)}=\frac{7+3/4}{4}=\frac{31}{16}$. A est le piège : il garde $x_1^{(0)}=1$, c'est Jacobi. B vient de l'erreur de signe, C de l'oubli de la division.
Question 9 : Laquelle de ces matrices est à diagonale strictement dominante ?
Réponse : C. Ligne par ligne, $|-4|=4>3$ et $3>2$. D est le piège : on compare des valeurs absolues, et $|-3|=3>2$. A n'a qu'une égalité sur la première ligne, et B ne domine que par colonnes.
Question 10 : $A$ est à diagonale strictement dominante. Que peux-tu affirmer ?
Réponse : B. La stricte dominance diagonale suffit pour les deux méthodes, quel que soit le départ. D est le piège : ici, la convergence ne dépend pas de $x^{(0)}$, puisqu'elle ne tient qu'à $\rho(B)$.
Question 11 : $A$ est tridiagonale et Jacobi demande environ $200$ itérations. Combien en faut-il à Gauss-Seidel pour la même précision ?
Réponse : C. Ici $\rho(\mathcal{L}_1)=\rho(J)^2$ : à la longue, une itération de Gauss-Seidel réduit l'erreur autant que deux de Jacobi, donc il en faut deux fois moins. D est le piège : $14\approx\sqrt{200}$, mais c'est le rayon spectral qui est au carré, pas le nombre d'itérations.
Question 12 : $A=\begin{pmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{pmatrix}$, et la matrice $\begin{pmatrix}0&1&0\\1&0&1\\0&1&0\end{pmatrix}$ a pour valeurs propres $0$ et $\pm\sqrt{2}$. Que vaut $\rho(\mathcal{L}_1)$ ?
Réponse : A. Ici $D=2I$, donc $J=D^{-1}(E+F)$ vaut la moitié de cette matrice et $\rho(J)=\frac{\sqrt{2}}{2}$. Comme $A$ est tridiagonale, $\rho(\mathcal{L}_1)=\rho(J)^2=\frac{1}{2}$. B est le piège : il s'arrête à $\rho(J)$. C oublie le facteur $\frac{1}{2}$ et ferait croire que Gauss-Seidel diverge.
Question 13 : Avec la matrice de la question 12, que vaut le paramètre optimal $\omega_0$ de SOR ?
Réponse : B. La formule prend $\rho(J)=\frac{\sqrt{2}}{2}$ : $\omega_0=\frac{2}{1+\sqrt{1-1/2}}=4-2\sqrt{2}\approx1{,}17$, et $\rho(\mathcal{L}_{\omega_0})=\omega_0-1\approx0{,}17$ contre $0{,}5$ pour Gauss-Seidel. A est le piège : il met $\rho(\mathcal{L}_1)$ à la place de $\rho(J)$. C oublie le carré, D la racine.
Question 14 : $A=\begin{pmatrix}1&a&a\\a&1&a\\a&a&1\end{pmatrix}$ avec $a=\frac{3}{4}$ est symétrique définie positive, et la matrice $\begin{pmatrix}0&1&1\\1&0&1\\1&1&0\end{pmatrix}$ a pour valeurs propres $2$ et $-1$. Que font Jacobi et Gauss-Seidel ?
Réponse : C. Une matrice symétrique définie positive garantit Gauss-Seidel. Mais ici $D=I$, donc $J=-\frac{3}{4}$ fois cette matrice, de valeurs propres $-\frac{3}{2}$ et $\frac{3}{4}$ : $\rho(J)=\frac{3}{2}>1$. A est le piège : pour Jacobi, être symétrique définie positive ne suffit pas.
Question 15 : $A$ est symétrique définie positive et SOR converge bien avec $\omega=1{,}5$. Tu essaies $\omega=2{,}2$ pour aller encore plus vite. Que se passe-t-il ?
Réponse : D. Pour toute matrice, $\det\mathcal{L}_\omega=(1-\omega)^n$, donc $\rho(\mathcal{L}_\omega)\ge|1-\omega|=1{,}2>1$. B est le piège : une matrice symétrique définie positive garantit SOR seulement pour $0<\omega<2$.
Sources
Raphaèle Herbin, Cours d'analyse numérique, licence de mathématiques, université Aix-Marseille 1, 2008 : partie 1.5, théorèmes 1.26, 1.34 et 1.36, remarque 1.35, exercice 30.
Équipe de mathématiques appliquées de l'UTC, MT09, Analyse numérique élémentaire, chapitre 4, 2007 : propositions IV.1.2 et IV.1.3.