Niveau : supérieur, du facile au difficile. Durée estimée : 1 h 30. 10 exercices avec corrections détaillées.
Rappel des notions clés
Une méthode itérative remplace la résolution de $Ax = b$ par une suite $x^{(k+1)} = Tx^{(k)} + c$ qui converge vers la solution. Avec Jacobi, tu isoles l'inconnue $x_i$ dans l'équation $i$ et tu calcules toutes les nouvelles composantes avec les anciennes : pour $4x_1 - x_2 = 3$ et $-x_1 + 4x_2 = 3$, cela donne $x_1^{(k+1)} = \frac{3 + x_2^{(k)}}{4}$ et $x_2^{(k+1)} = \frac{3 + x_1^{(k)}}{4}$. Gauss-Seidel fait le même calcul, mais réutilise chaque nouvelle composante dès qu'elle est connue : $x_2^{(k+1)} = \frac{3 + x_1^{(k+1)}}{4}$.
Avec $A = D - E - F$ ($D$ partie diagonale de $A$, $-E$ partie strictement sous la diagonale, $-F$ partie strictement au-dessus), Jacobi a pour matrice d'itération $T_J = D^{-1}(E+F)$ et Gauss-Seidel $T_{GS} = (D-E)^{-1}F$. La méthode converge pour tout départ si et seulement si le rayon spectral $\rho(T)$, plus grand module des valeurs propres de $T$, vérifie $\rho(T) < 1$, comme le démontre le cours de licence de R. Herbin. En général, l'erreur finit par être multipliée par environ $\rho(T)$ à chaque itération.
Le pivot de Gauss, méthode directe, donne la solution en un nombre fini d'opérations. Avec le pivot partiel, tu prends comme pivot, à chaque étape, le coefficient de plus grand module de la colonne, sur la diagonale ou en dessous, quitte à échanger deux lignes : un pivot minuscule ferait grossir les erreurs d'arrondi. Le conditionnement $\mathrm{cond}(A)$ mesure combien une petite erreur sur les données peut grossir sur la solution.
Formules à retenir :
- Norme infinie : $\|v\|_\infty = \max_i |v_i|$ et $\|T\|_\infty = \max_i \sum_j |t_{ij}|$.
- Erreur $e^{(k)} = x^{(k)} - x$ : $e^{(k)} = T^k e^{(0)}$, donc $\|e^{(k)}\|_\infty \le \|T\|_\infty^k\,\|e^{(0)}\|_\infty$.
- Si $|a_{ii}| > \sum_{j \neq i} |a_{ij}|$ pour tout $i$ (diagonale strictement dominante), Jacobi et Gauss-Seidel convergent.
- Si $A$ est tridiagonale (coefficients nuls hors de la diagonale et de ses deux voisines), sans zéro sur la diagonale : $\rho(T_{GS}) = \rho(T_J)^2$ (cours de L3 de l'université de Nantes).
- $\mathrm{cond}(A) = \|A\|\,\|A^{-1}\|$ et, pour une solution approchée $\tilde{x}$ : $\dfrac{\|x - \tilde{x}\|}{\|x\|} \le \mathrm{cond}(A)\,\dfrac{\|b - A\tilde{x}\|}{\|b\|}$.
Piège classique : la diagonale strictement dominante est une condition suffisante, pas nécessaire. Si elle manque, ne conclus rien sans calculer $\rho(T)$. Et l'ordre des équations compte : en échanger deux change $D$, donc $T_J$, et peut faire converger une méthode qui divergeait.
Exercices : niveau facile
Exercice 1 : On considère le système $Ax = b$ avec
$$A = \begin{pmatrix} 4 & -1 & 0 \\ -1 & 4 & -1 \\ 0 & -1 & 4 \end{pmatrix}, \quad b = \begin{pmatrix} 3 \\ 2 \\ 3 \end{pmatrix}.$$
Écris les formules de Jacobi composante par composante, puis donne $T_J$ et $c$ tels que $x^{(k+1)} = T_J x^{(k)} + c$.
Correction :
On isole $x_i$ dans l'équation $i$ en divisant par $a_{ii} = 4$ :
$$x_1^{(k+1)} = \frac{3 + x_2^{(k)}}{4}, \quad x_2^{(k+1)} = \frac{2 + x_1^{(k)} + x_3^{(k)}}{4}, \quad x_3^{(k+1)} = \frac{3 + x_2^{(k)}}{4}.$$
D'où $T_J = \frac{1}{4}\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$ et $c = \begin{pmatrix} 3/4 \\ 1/2 \\ 3/4 \end{pmatrix}$.
L'erreur à éviter : garder le signe de $a_{ij}$. En changeant de membre, $-1$ devient $+1$.
Exercice 2 : Pour le système de l'exercice 1, pars de $x^{(0)} = (0\,;\,0\,;\,0)$ et calcule $x^{(1)}$ puis $x^{(2)}$ par Jacobi. Vérifie que la solution exacte est $x = (1\,;\,1\,;\,1)$, puis calcule l'erreur $\|x^{(2)} - x\|_\infty$.
Correction :
On n'utilise que les valeurs de l'itération précédente.
$x^{(1)} = c = (3/4\,;\,1/2\,;\,3/4)$, puis $x_1^{(2)} = \frac{3 + 1/2}{4} = \frac{7}{8}$, $x_2^{(2)} = \frac{2 + 3/4 + 3/4}{4} = \frac{7}{8}$ et $x_3^{(2)} = \frac{7}{8}$.
Vérification : $4 - 1 = 3$, $-1 + 4 - 1 = 2$ et $-1 + 4 = 3$.
$x^{(2)} = (7/8\,;\,7/8\,;\,7/8)$ et $\|x^{(2)} - x\|_\infty = 1/8$.
Exercice 3 : Même système, même départ. Calcule $x^{(1)}$ par Gauss-Seidel, puis compare son erreur $\|x^{(1)} - x\|_\infty$ à celle du $x^{(1)}$ de Jacobi.
Correction :
On calcule les composantes dans l'ordre, en réutilisant aussitôt chaque nouvelle valeur.
$x_1^{(1)} = \frac{3}{4}$, puis $x_2^{(1)} = \frac{2 + 3/4 + 0}{4} = \frac{11}{16}$, puis $x_3^{(1)} = \frac{3 + 11/16}{4} = \frac{59}{64}$.
Écarts à la solution : $\frac{1}{4}$, $\frac{5}{16}$ et $\frac{5}{64}$, contre $\frac{1}{4}$, $\frac{1}{2}$ et $\frac{1}{4}$ pour Jacobi.
$x^{(1)} = (3/4\,;\,11/16\,;\,59/64)$, d'erreur $5/16 \approx 0{,}31$ contre $1/2$ pour Jacobi.
L'erreur à éviter : calculer $x_2^{(1)}$ avec $x_1^{(0)}$, ce qui redonne Jacobi.
Exercices : niveau moyen
Exercice 4 : Soit $A = \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}$. Justifie que Jacobi converge pour tout système $Ax = b$, puis calcule $\rho(T_J)$ et dis ce qu'il indique sur la vitesse.
Correction :
On vérifie la dominance diagonale, puis on cherche les valeurs propres de $T_J$.
Sur chaque ligne, $|2| > |-1|$ : $A$ est à diagonale strictement dominante, donc Jacobi converge.
$T_J = \begin{pmatrix} 0 & 1/2 \\ 1/2 & 0 \end{pmatrix}$ et $\det(T_J - \lambda I) = \lambda^2 - \frac{1}{4}$, nul pour $\lambda = \pm\frac{1}{2}$.
$\rho(T_J) = 1/2$ : l'erreur est divisée par 2 environ à chaque itération.
Exercice 5 : Avec la même matrice, calcule $T_{GS} = (D-E)^{-1}F$ et son rayon spectral. Combien d'itérations de Jacobi vaut une itération de Gauss-Seidel ?
Correction :
On inverse la matrice triangulaire $D - E$, puis on multiplie par $F$.
$D - E = \begin{pmatrix} 2 & 0 \\ -1 & 2 \end{pmatrix}$, $(D-E)^{-1} = \begin{pmatrix} 1/2 & 0 \\ 1/4 & 1/2 \end{pmatrix}$ et $F = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$.
$T_{GS} = \begin{pmatrix} 0 & 1/2 \\ 0 & 1/4 \end{pmatrix}$ est triangulaire : ses valeurs propres sont $0$ et $1/4$.
$\rho(T_{GS}) = 1/4 = \rho(T_J)^2$ : une itération de Gauss-Seidel vaut deux itérations de Jacobi.
Exercice 6 : Soit $A = \begin{pmatrix} 10 & -1 & 2 \\ 1 & 10 & -1 \\ 1{,}5 & -1 & 12 \end{pmatrix}$. Calcule $T_J$ et $\|T_J\|_\infty$. Combien d'itérations de Jacobi garantissent, quel que soit le départ, une erreur $\|e^{(k)}\|_\infty$ divisée au moins par $10^6$ ?
Correction :
On divise chaque ligne par son coefficient diagonal en changeant le signe des autres, puis on majore l'erreur par $\|T_J\|_\infty^k\,\|e^{(0)}\|_\infty$.
$$T_J = \begin{pmatrix} 0 & 0{,}1 & -0{,}2 \\ -0{,}1 & 0 & 0{,}1 \\ -0{,}125 & 1/12 & 0 \end{pmatrix}$$
Sommes des valeurs absolues par ligne : $0{,}3$, $0{,}2$ et $0{,}125 + 1/12 \approx 0{,}208$, donc $\|T_J\|_\infty = 0{,}3$.
Il faut $(0{,}3)^k \le 10^{-6}$, soit $k \ge \frac{6}{\log_{10}(10/3)} \approx 11{,}5$. En effet, $(0{,}3)^{11} \approx 1{,}8 \times 10^{-6}$ et $(0{,}3)^{12} \approx 5{,}3 \times 10^{-7}$.
$\|T_J\|_\infty = 0{,}3$ : 12 itérations suffisent.
Exercice 7 : On résout par Jacobi le système $x_1 + 3x_2 = 7$, $4x_1 + x_2 = 6$, écrit dans cet ordre.
a) Pars de $x^{(0)} = (0\,;\,0)$ et calcule $x^{(1)}$, $x^{(2)}$ et $x^{(3)}$. Que constates-tu ?
b) Échange les deux équations. Que peux-tu conclure ? Donne la solution.
Correction :
La convergence de Jacobi dépend de la diagonale, donc de l'ordre des équations.
a) $x_1^{(k+1)} = 7 - 3x_2^{(k)}$ et $x_2^{(k+1)} = 6 - 4x_1^{(k)}$ donnent $x^{(1)} = (7\,;\,6)$, $x^{(2)} = (-11\,;\,-22)$ et $x^{(3)} = (73\,;\,50)$. Les itérés explosent : $T_J = \begin{pmatrix} 0 & -3 \\ -4 & 0 \end{pmatrix}$ a pour rayon spectral $\sqrt{12} \approx 3{,}46 > 1$, la méthode diverge.
b) Dans l'ordre $4x_1 + x_2 = 6$, $x_1 + 3x_2 = 7$, on a $4 > 1$ et $3 > 1$ : diagonale strictement dominante, Jacobi converge. La solution est $(1\,;\,2)$, car $4 + 2 = 6$ et $1 + 6 = 7$.
La solution $(1\,;\,2)$ ne change pas, mais Jacobi diverge dans un ordre et converge dans l'autre.
Exercices : niveau difficile
Exercice 8 : On résout $\begin{cases} 0{,}0001\,x_1 + x_2 = 1 \\ x_1 + x_2 = 2 \end{cases}$ par le pivot de Gauss, en arrondissant chaque résultat à 3 chiffres significatifs.
a) Élimine $x_1$ en gardant $0{,}0001$ comme pivot.
b) Recommence avec le pivot partiel.
c) Compare à la solution exacte et explique l'écart.
Correction :
On élimine, puis on remonte, en arrondissant à chaque opération.
a) $L_2 \leftarrow L_2 - 10\,000\,L_1$ donne $-9\,999\,x_2 = -9\,998$, arrondi en $-1{,}00 \times 10^4\,x_2 = -1{,}00 \times 10^4$, donc $x_2 = 1{,}00$. Puis $0{,}0001\,x_1 = 1 - 1{,}00 = 0$, donc $x_1 = 0$.
b) Le plus grand coefficient de la colonne 1 est $1$ : on échange les lignes. $L_2 \leftarrow L_2 - 0{,}0001\,L_1$ donne $0{,}9999\,x_2 = 0{,}9998$, arrondi en $1{,}00\,x_2 = 1{,}00$, donc $x_2 = 1{,}00$ et $x_1 = 2 - 1{,}00 = 1{,}00$.
c) La solution exacte est $x_1 = \frac{1}{0{,}9999} \approx 1{,}0001$ et $x_2 = \frac{0{,}9998}{0{,}9999} \approx 0{,}9999$.
Sans pivot partiel, $x_1 = 0$ au lieu de $1$ (100 % d'erreur) ; avec, $(1{,}00\,;\,1{,}00)$, juste à 3 chiffres.
Le multiplicateur $10\,000$ a noyé la deuxième équation dans les arrondis : c'est ce que le pivot partiel évite.
Exercice 9 : Soit $A = \begin{pmatrix} 1 & 1 \\ 1 & 1{,}0001 \end{pmatrix}$ et $b = \begin{pmatrix} 2 \\ 2{,}0001 \end{pmatrix}$, de solution exacte $x = (1\,;\,1)$. Un programme renvoie $\tilde{x} = (2\,;\,0)$.
a) Calcule le résidu $r = b - A\tilde{x}$ et l'erreur $x - \tilde{x}$, en norme infinie.
b) Calcule $\mathrm{cond}_\infty(A)$ et explique pourquoi un petit résidu ne suffit pas pour arrêter le calcul.
Correction :
On compare résidu et erreur, puis on les relie par le conditionnement.
a) $A\tilde{x} = (2\,;\,2)$, donc $r = (0\,;\,0{,}0001)$ et $\|r\|_\infty = 10^{-4}$. Mais $x - \tilde{x} = (-1\,;\,1)$, donc $\|x - \tilde{x}\|_\infty = 1$ : 100 % d'erreur relative.
b) $\det A = 0{,}0001$, d'où $A^{-1} = \begin{pmatrix} 10\,001 & -10\,000 \\ -10\,000 & 10\,000 \end{pmatrix}$. Avec $\|A\|_\infty = 2{,}0001$ et $\|A^{-1}\|_\infty = 20\,001$, on obtient $\mathrm{cond}_\infty(A) \approx 4 \times 10^4$.
L'inégalité du rappel autorise alors une erreur relative jusqu'à $4 \times 10^4 \times \frac{10^{-4}}{2{,}0001} \approx 2$ : un résidu de $10^{-4}$ peut cacher 100 % d'erreur.
$\|r\|_\infty = 10^{-4}$, erreur relative de 100 %, $\mathrm{cond}_\infty(A) \approx 4 \times 10^4$.
Un petit résidu ne prouve une solution juste que si $\mathrm{cond}(A)$ est modéré.
Exercice 10 : Une barre de 1 m a ses extrémités maintenues à 20 °C et 100 °C. Sa température d'équilibre $u$ vérifie $u'' = 0$. Avec trois points intérieurs équidistants, les différences finies (on remplace $u''(x_i)$ par $\frac{u_{i-1} - 2u_i + u_{i+1}}{h^2}$) donnent, en degrés Celsius, le système $Au = b$ avec
$$A = \begin{pmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{pmatrix}, \quad b = \begin{pmatrix} 20 \\ 0 \\ 100 \end{pmatrix}.$$
a) $A$ est-elle à diagonale strictement dominante ? Peut-on en conclure que Jacobi diverge ?
b) Calcule $\rho(T_J)$, puis $\rho(T_{GS})$.
c) Estime le nombre d'itérations de chaque méthode pour diviser l'erreur par $10^6$.
Correction :
On calcule les rayons spectraux, puis on applique la règle des matrices tridiagonales.
a) Ligne 2 : $|2| = |-1| + |-1|$, l'inégalité n'est pas stricte. Mais ce critère n'est que suffisant : on ne peut rien conclure.
b) $T_J = \frac{1}{2}\begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$. La matrice entre parenthèses a pour polynôme caractéristique $-\lambda(\lambda^2 - 2)$, donc pour valeurs propres $0$ et $\pm\sqrt{2}$. Ainsi $\rho(T_J) = \frac{\sqrt{2}}{2} \approx 0{,}707 < 1$ : Jacobi converge. Comme $A$ est tridiagonale, $\rho(T_{GS}) = \rho(T_J)^2 = \frac{1}{2}$.
c) Il faut $\left(\frac{\sqrt{2}}{2}\right)^k = 2^{-k/2} \le 10^{-6}$, soit $k \ge 12\log_2 10 \approx 39{,}9$ ; et $2^{-k} \le 10^{-6}$, soit $k \ge 6\log_2 10 \approx 19{,}9$.
Environ 40 itérations pour Jacobi, 20 pour Gauss-Seidel.
La solution, $u = (40\,;\,60\,;\,80)$ en °C, se vérifie directement dans le système.
Bilan et conseils
Ce qu'il faut retenir : une méthode itérative converge si et seulement si $\rho(T) < 1$, la diagonale strictement dominante n'étant qu'une condition suffisante. Pour une matrice tridiagonale, une itération de Gauss-Seidel vaut deux itérations de Jacobi. En méthode directe, utilise le pivot partiel, et ne juge pas une solution sur son seul résidu quand $\mathrm{cond}(A)$ est grand.
Sources
- Raphaèle Herbin, Cours d'analyse numérique, licence de mathématiques, université Aix-Marseille 1, version du 19 octobre 2008 (chapitre 1 : pivot partiel, conditionnement, Jacobi et Gauss-Seidel).
- Résolution des systèmes linéaires, méthodes itératives, notes de cours de L3, université de Nantes (diagonale strictement dominante, matrices tridiagonales).