Maîtrise la Résolution Numérique de Systèmes Linéaires

Correction :

L'objectif est de réécrire chaque équation du système de manière à isoler la variable $x_i$ correspondante sur le membre de gauche. Pour le système donné :

Étape 1 : Réécrire la première équation pour isoler $x_1$.

De $4x_1 - x_2 = 3$, on obtient $4x_1 = x_2 + 3$, donc $x_1 = \frac{1}{4}x_2 + \frac{3}{4}$.

Étape 2 : Réécrire la deuxième équation pour isoler $x_2$.

De $-x_1 + 4x_2 - x_3 = 2$, on obtient $4x_2 = x_1 + x_3 + 2$, donc $x_2 = \frac{1}{4}x_1 + \frac{1}{4}x_3 + \frac{2}{4} = \frac{1}{4}x_1 + \frac{1}{4}x_3 + \frac{1}{2}$.

Étape 3 : Réécrire la troisième équation pour isoler $x_3$.

De $-x_2 + 4x_3 = 3$, on obtient $4x_3 = x_2 + 3$, donc $x_3 = \frac{1}{4}x_2 + \frac{3}{4}$.

Étape 4 : Assembler les équations sous la forme $x = Tx + c$.

En regroupant les termes, on obtient le système sous forme matricielle :

$$ \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 0 & \frac{1}{4} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & \frac{1}{4} & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} + \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix} $$

Ainsi, on a $T = \begin{pmatrix} 0 & \frac{1}{4} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & \frac{1}{4} & 0 \end{pmatrix}$ et $c = \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix}$.

Point méthode : Pour obtenir la forme $x = Tx + c$, il faut s'assurer que le coefficient diagonal de chaque ligne soit non nul pour pouvoir diviser par celui-ci.

Correction :

La formule de mise à jour pour la méthode de Jacobi est $x^{(k+1)} = Tx^{(k)} + c$. On part de $x^{(0)} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}$.

Étape 1 : Appliquer la formule pour $k=0$.

$x^{(1)} = Tx^{(0)} + c$

Étape 2 : Calculer le produit matriciel $Tx^{(0)}$.

$$ Tx^{(0)} = \begin{pmatrix} 0 & \frac{1}{4} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & \frac{1}{4} & 0 \end{pmatrix} \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \times 0 + \frac{1}{4} \times 0 + 0 \times 0 \\ \frac{1}{4} \times 0 + 0 \times 0 + \frac{1}{4} \times 0 \\ 0 \times 0 + \frac{1}{4} \times 0 + 0 \times 0 \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} $$

Étape 3 : Ajouter le vecteur $c$.

$$ x^{(1)} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} + \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix} = \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix} $$

Correction :

On applique la formule pour $k=1$ : $x^{(2)} = Tx^{(1)} + c$. On utilise $x^{(1)} = \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix}$.

Étape 1 : Calculer le produit matriciel $Tx^{(1)}$.

$$ Tx^{(1)} = \begin{pmatrix} 0 & \frac{1}{4} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & \frac{1}{4} & 0 \end{pmatrix} \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix} = \begin{pmatrix} 0 \times \frac{3}{4} + \frac{1}{4} \times \frac{1}{2} + 0 \times \frac{3}{4} \\ \frac{1}{4} \times \frac{3}{4} + 0 \times \frac{1}{2} + \frac{1}{4} \times \frac{3}{4} \\ 0 \times \frac{3}{4} + \frac{1}{4} \times \frac{1}{2} + 0 \times \frac{3}{4} \end{pmatrix} = \begin{pmatrix} \frac{1}{8} \\ \frac{3}{16} + \frac{3}{16} \\ \frac{1}{8} \end{pmatrix} = \begin{pmatrix} \frac{1}{8} \\ \frac{6}{16} \\ \frac{1}{8} \end{pmatrix} = \begin{pmatrix} \frac{1}{8} \\ \frac{3}{8} \\ \frac{1}{8} \end{pmatrix} $$

Étape 2 : Ajouter le vecteur $c$.

$$ x^{(2)} = \begin{pmatrix} \frac{1}{8} \\ \frac{3}{8} \\ \frac{1}{8} \end{pmatrix} + \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix} = \begin{pmatrix} \frac{1}{8} + \frac{6}{8} \\ \frac{3}{8} + \frac{4}{8} \\ \frac{1}{8} + \frac{6}{8} \end{pmatrix} = \begin{pmatrix} \frac{7}{8} \\ \frac{7}{8} \\ \frac{7}{8} \end{pmatrix} $$

Astuce : On peut remarquer que les composantes de $x^{(2)}$ sont de plus en plus proches de la solution exacte, qui est dans ce cas $\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}$. Vérifions : $4(1) - 1 = 3$, $-1 + 4(1) - 1 = 2$, $-1 + 4(1) = 3$. C'est correct.

Correction :

La méthode de Gauss-Seidel met à jour les composantes de $x^{(k+1)}$ séquentiellement en utilisant les valeurs les plus récentes disponibles. La formule générale peut s'écrire sous forme matricielle, mais il est souvent plus clair de l'écrire composante par composante.

Pour le système $x = Tx + c$, avec $T = \begin{pmatrix} 0 & t_{12} & t_{13} \\ t_{21} & 0 & t_{23} \\ t_{31} & t_{32} & 0 \end{pmatrix}$ et $c = \begin{pmatrix} c_1 \\ c_2 \\ c_3 \end{pmatrix}$, les mises à jour sont :

$x_1^{(k+1)} = t_{12}x_2^{(k)} + t_{13}x_3^{(k)} + c_1$

$x_2^{(k+1)} = t_{21}x_1^{(k+1)} + t_{23}x_3^{(k)} + c_2$ (note l'utilisation de $x_1^{(k+1)}$)

$x_3^{(k+1)} = t_{31}x_1^{(k+1)} + t_{32}x_2^{(k+1)} + c_3$ (note l'utilisation de $x_1^{(k+1)}$ et $x_2^{(k+1)}$)

Dans notre cas, $T = \begin{pmatrix} 0 & \frac{1}{4} & 0 \\ \frac{1}{4} & 0 & \frac{1}{4} \\ 0 & \frac{1}{4} & 0 \end{pmatrix}$ et $c = \begin{pmatrix} \frac{3}{4} \\ \frac{1}{2} \\ \frac{3}{4} \end{pmatrix}$.

Étape 1 : Calculer $x_1^{(1)}$.

$x_1^{(1)} = t_{12}x_2^{(0)} + t_{13}x_3^{(0)} + c_1 = \frac{1}{4}(0) + 0(0) + \frac{3}{4} = \frac{3}{4}$.

On a donc $x^{(1)} = \begin{pmatrix} \frac{3}{4} \\ ? \\ ? \end{pmatrix}$.

Étape 2 : Calculer $x_2^{(1)}$.

$x_2^{(1)} = t_{21}x_1^{(1)} + t_{23}x_3^{(0)} + c_2 = \frac{1}{4}\left(\frac{3}{4}\right) + \frac{1}{4}(0) + \frac{1}{2} = \frac{3}{16} + \frac{1}{2} = \frac{3}{16} + \frac{8}{16} = \frac{11}{16}$.

On a donc $x^{(1)} = \begin{pmatrix} \frac{3}{4} \\ \frac{11}{16} \\ ? \end{pmatrix}$.

Étape 3 : Calculer $x_3^{(1)}$.

$x_3^{(1)} = t_{31}x_1^{(1)} + t_{32}x_2^{(1)} + c_3 = 0\left(\frac{3}{4}\right) + \frac{1}{4}\left(\frac{11}{16}\right) + \frac{3}{4} = \frac{11}{64} + \frac{3}{4} = \frac{11}{64} + \frac{48}{64} = \frac{59}{64}$.

Point méthode : La différence clé avec Jacobi est l'utilisation des valeurs les plus récentes. Ici, pour calculer $x_2^{(1)}$, on utilise $x_1^{(1)}$ qui vient d'être calculé, et pour $x_3^{(1)}$, on utilise $x_1^{(1)}$ et $x_2^{(1)}$.

Correction :

Une matrice $A = (a_{ij})$ est dite à diagonale strictement dominante si pour tout $i$, $|a_{ii}| > \sum_{j \neq i} |a_{ij}|$.

a) Vérification de la diagonale dominante :

Pour la ligne 1 : $|a_{11}| = |2| = 2$. La somme des valeurs absolues des autres éléments de la ligne est $|a_{12}| = |-1| = 1$. On a $2 > 1$. La condition est vérifiée pour la ligne 1.

Pour la ligne 2 : $|a_{22}| = |2| = 2$. La somme des valeurs absolues des autres éléments de la ligne est $|a_{21}| = |-1| = 1$. On a $2 > 1$. La condition est vérifiée pour la ligne 2.

b) Condition de convergence :

Puisque la matrice $A$ est à diagonale strictement dominante, un critère suffisant pour la convergence des méthodes de Jacobi et de Gauss-Seidel est que la norme spectrale de la matrice d'itération $T$ soit strictement inférieure à 1 ($\rho(T) < 1$).

Pour la méthode de Jacobi, la matrice $T$ s'obtient en remplaçant chaque élément $a_{ij}$ par $-\frac{a_{ij}}{a_{ii}}$ pour $i \neq j$, et par 0 pour $i=j$. Pour notre matrice $A$, la matrice $T$ associée à la méthode de Jacobi est :

$$ T_J = \begin{pmatrix} 0 & -\frac{-1}{2} \\ -\frac{-1}{2} & 0 \end{pmatrix} = \begin{pmatrix} 0 & \frac{1}{2} \\ \frac{1}{2} & 0 \end{pmatrix} $$

La norme spectrale $\rho(T_J)$ est le maximum des valeurs absolues des valeurs propres de $T_J$. Les valeurs propres $\lambda$ sont solutions de $\det(T_J - \lambda I) = 0$.

$\det \begin{pmatrix} -\lambda & \frac{1}{2} \\ \frac{1}{2} & -\lambda \end{pmatrix} = (-\lambda)(-\lambda) - (\frac{1}{2})(\frac{1}{2}) = \lambda^2 - \frac{1}{4} = 0$.

Donc $\lambda^2 = \frac{1}{4}$, ce qui donne $\lambda = \pm \frac{1}{2}$.

La norme spectrale est $\rho(T_J) = \max(|\frac{1}{2}|, |-\frac{1}{2}|) = \frac{1}{2}$.

Point méthode : La diagonale dominante est une condition suffisante mais non nécessaire. Si elle n'est pas satisfaite, la méthode peut quand même converger.

Correction :

La matrice d'itération $T_G$ pour la méthode de Gauss-Seidel est obtenue par la relation $(D - L)x^{(k+1)} = Ux^{(k)} + b$, où $A = D - L - U$ est la décomposition de $A$ en partie diagonale ($D$), triangulaire inférieure stricte ($L$) et triangulaire supérieure stricte ($U$).

Pour $A = \begin{pmatrix} 2 & -1 \\ -1 & 2 \end{pmatrix}$, on a $D = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}$, $L = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}$, et $U = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$.

a) Calcul de la matrice $T_G$ :

La relation de récurrence est $x^{(k+1)} = (D-L)^{-1}Ux^{(k)} + (D-L)^{-1}b$. Donc $T_G = (D-L)^{-1}U$ et $c_G = (D-L)^{-1}b$.

$D - L = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} - \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ -1 & 2 \end{pmatrix}$.

Calculons l'inverse de $D-L$ :

$$ (D-L)^{-1} = \frac{1}{\det(D-L)} \begin{pmatrix} 2 & 0 \\ 1 & 2 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 2 & 0 \\ 1 & 2 \end{pmatrix} = \begin{pmatrix} \frac{1}{2} & 0 \\ \frac{1}{4} & \frac{1}{2} \end{pmatrix} $$

Maintenant, calculons $T_G = (D-L)^{-1}U$ :

$$ T_G = \begin{pmatrix} \frac{1}{2} & 0 \\ \frac{1}{4} & \frac{1}{2} \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} = \begin{pmatrix} \frac{1}{2}(0) + 0(0) & \frac{1}{2}(1) + 0(0) \\ \frac{1}{4}(0) + \frac{1}{2}(0) & \frac{1}{4}(1) + \frac{1}{2}(0) \end{pmatrix} = \begin{pmatrix} 0 & \frac{1}{2} \\ 0 & \frac{1}{4} \end{pmatrix} $$

b) Calcul de la norme spectrale de $T_G$ :

Les valeurs propres de $T_G$ sont les solutions de $\det(T_G - \lambda I) = 0$.

$\det \begin{pmatrix} -\lambda & \frac{1}{2} \\ 0 & \frac{1}{4} - \lambda \end{pmatrix} = (-\lambda)(\frac{1}{4} - \lambda) - (\frac{1}{2})(0) = -\lambda(\frac{1}{4} - \lambda) = 0$.

Les valeurs propres sont donc $\lambda = 0$ et $\lambda = \frac{1}{4}$.

La norme spectrale est $\rho(T_G) = \max(|0|, |\frac{1}{4}|) = \frac{1}{4}$.

Comparaison : Dans ce cas, $\rho(T_J) = \frac{1}{2}$ et $\rho(T_G) = \frac{1}{4}$. La méthode de Gauss-Seidel converge plus rapidement car sa norme spectrale est plus petite.

Correction :

a) Formulation $x = Tx + c$ :

De la première ligne : $10x_1 = x_2 - 2x_3 + 6 \implies x_1 = \frac{1}{10}x_2 - \frac{2}{10}x_3 + \frac{6}{10}$.

De la deuxième ligne : $10x_2 = -x_1 + x_3 + 25 \implies x_2 = -\frac{1}{10}x_1 + \frac{1}{10}x_3 + \frac{25}{10}$.

De la troisième ligne : $12x_3 = -1.5x_1 + x_2 - 6 \implies x_3 = -\frac{1.5}{12}x_1 + \frac{1}{12}x_2 - \frac{6}{12} = -\frac{1}{8}x_1 + \frac{1}{12}x_2 - \frac{1}{2}$.

En notation matricielle :

$$ T = \begin{pmatrix} 0 & \frac{1}{10} & -\frac{2}{10} \\ -\frac{1}{10} & 0 & \frac{1}{10} \\ -\frac{1}{8} & \frac{1}{12} & 0 \end{pmatrix}, \quad c = \begin{pmatrix} \frac{6}{10} \\ \frac{25}{10} \\ -\frac{1}{2} \end{pmatrix} $$

b) Vérification de la diagonale dominante :

Ligne 1 : $|10| = 10$. $|-1| + |2| = 3$. $10 > 3$. (OK)

Ligne 2 : $|10| = 10$. $|1| + |-1| = 2$. $10 > 2$. (OK)

Ligne 3 : $|12| = 12$. $|1.5| + |-1| = 2.5$. $12 > 2.5$. (OK)

La matrice $A$ est bien à diagonale strictement dominante.

c) Première itération $x^{(1)}$ :

$x^{(1)} = Tx^{(0)} + c = T \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} + c = c$.

Correction :

On utilise les équations obtenues en isolant $x_1, x_2, x_3$ :

$x_1 = 0.1x_2 - 0.2x_3 + 0.6$

$x_2 = -0.1x_1 + 0.1x_3 + 2.5$

$x_3 = -0.125x_1 + 0.0833x_2 - 0.5$

Étape 1 : Calcul de $x_1^{(1)}$.

On utilise $x^{(0)} = \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}$.

$x_1^{(1)} = 0.1(0) - 0.2(0) + 0.6 = 0.6$.

: $x^{(1)} = \begin{pmatrix} 0.6 \\ ? \\ ? \end{pmatrix}$.

Étape 2 : Calcul de $x_2^{(1)}$.

On utilise $x_1^{(1)} = 0.6$ et $x_3^{(0)} = 0$.

$x_2^{(1)} = -0.1(0.6) + 0.1(0) + 2.5 = -0.06 + 2.5 = 2.44$.

: $x^{(1)} = \begin{pmatrix} 0.6 \\ 2.44 \\ ? \end{pmatrix}$.

Étape 3 : Calcul de $x_3^{(1)}$.

On utilise $x_1^{(1)} = 0.6$ et $x_2^{(1)} = 2.44$.

$x_3^{(1)} = -0.125(0.6) + 0.0833(2.44) - 0.5$

$x_3^{(1)} = -0.075 + 0.203132 - 0.5 \approx -0.371868$.

Comparaison : Pour $x^{(1)}$ avec Jacobi, on avait $\begin{pmatrix} 0.6 \\ 2.5 \\ -0.5 \end{pmatrix}$. Gauss-Seidel donne une première approximation différente, potentiellement plus proche de la solution.

Correction :

La matrice $T$ est une simplification de la matrice $T$ de Jacobi calculée à l'exercice 7, avec des valeurs arrondies pour $1/12$. La matrice exacte est $T = \begin{pmatrix} 0 & \frac{1}{10} & -\frac{2}{10} \\ -\frac{1}{10} & 0 & \frac{1}{10} \\ -\frac{1}{8} & \frac{1}{12} & 0 \end{pmatrix}$.

a) Calcul de la norme $L_1$ de $T$ :

Colonne 1 : $|0| + |-\frac{1}{10}| + |-\frac{1}{8}| = 0 + 0.1 + 0.125 = 0.225$.

Colonne 2 : $|\frac{1}{10}| + |0| + |\frac{1}{12}| = 0.1 + 0 + 0.0833. = 0.1833.

Colonne 3 : $|-\frac{2}{10}| + |\frac{1}{10}| + |0| = 0.2 + 0.1 + 0 = 0.3$.

La norme $L_1$ est le maximum de ces sommes : $||T||_1 = 0.3$.

b) Calcul de la norme $L_\infty$ de $T$ :

Ligne 1 : $|0| + |\frac{1}{10}| + |-\frac{2}{10}| = 0 + 0.1 + 0.2 = 0.3$.

Ligne 2 : $|-\frac{1}{10}| + |0| + |\frac{1}{10}| = 0.1 + 0 + 0.1 = 0.2$.

Ligne 3 : $|-\frac{1}{8}| + |\frac{1}{12}| + |0| = 0.125 + 0.0833. = 0.2083.

La norme $L_\infty$ est le maximum de ces sommes : $||T||_\infty = 0.3$.

c) Conclusion sur la convergence :

Le critère de convergence par la norme stipule que si une norme matricielle quelconque de la matrice d'itération $T$ est strictement inférieure à 1, alors la méthode itérative converge.

Dans ce cas, nous avons calculé $||T||_1 = 0.3$ et $||T||_\infty = 0.3$. Les deux normes sont inférieures à 1.

Point méthode : La norme spectrale est le rayon le plus petit pour lequel la convergence est garantie. Cependant, si une norme matricielle quelconque est inférieure à 1, la méthode converge. Les normes $L_1$ et $L_\infty$ sont souvent plus faciles à calculer que la norme spectrale.

Correction :

Analysons les propriétés de la matrice $A$ et leur impact sur le choix de la méthode itérative.

Propriétés de A :

1. Grand système creux : Les méthodes directes (comme l'élimination de Gauss) peuvent devenir coûteuses en mémoire et en temps de calcul pour de très grands systèmes creux à cause du "remplissage" (fill-in). Les méthodes itératives sont généralement préférables car elles ne nécessitent pas de stocker la matrice factorisée et leur coût par itération est proportionnel au nombre d'éléments non nuls de $A$.
2. Symétrique définie positive (SDP) : Cette propriété est très importante. Elle garantit que la méthode de Gauss-Seidel converge et, plus important, elle permet l'utilisation de méthodes plus avancées comme le gradient conjugué (CG). La méthode de Jacobi et Gauss-Seidel convergent toujours si la matrice est SDP et à diagonale dominante, mais CG converge généralement plus rapidement.
3. Diagonale dominante : Comme vu précédemment, cela garantit la convergence des méthodes de Jacobi et de Gauss-Seidel.

Comparaison des méthodes :

• Jacobi : Facile à paralléliser car chaque itération est indépendante. Moins rapide que Gauss-Seidel en général.
• Gauss-Seidel : Généralement plus rapide que Jacobi car il utilise les informations mises à jour immédiatement. Difficilement parallélisable car les mises à jour sont séquentielles.
• Gradient Conjugué (CG) : Cette méthode est particulièrement adaptée aux systèmes SDP. Elle a une convergence garantie et souvent très rapide, surtout si les valeurs propres de $A$ sont bien groupées. Elle nécessite de pouvoir calculer des produits matrice-vecteur ($Ax$).

Recommandation :

Étant donné que la matrice $A$ est symétrique définie positive, la méthode la plus appropriée et la plus efficace serait le Gradient Conjugué (CG).

Justification :

• La propriété SDP est la condition principale pour l'application de CG.
• CG converge généralement beaucoup plus rapidement que Jacobi ou Gauss-Seidel pour les matrices SDP.
• CG est bien adapté aux matrices creuses car il repose sur le calcul de $Ax^{(k)}$.
• La diagonale dominante renforce la garantie de convergence, mais CG fonctionne même si elle n'est pas strictement satisfaite, tant que la matrice est SDP.

Si la parallélisation était une contrainte majeure et que CG n'était pas envisageable, Gauss-Seidel serait un bon choix pour sa rapidité relative par rapport à Jacobi, bien que sa parallélisation soit limitée. Jacobi serait alors l'option la plus simple à paralléliser.

Point méthode : Comprendre les propriétés de la matrice du système ($A$) est crucial pour choisir l'algorithme de résolution numérique le plus adapté. Les méthodes itératives comme CG, Jacobi, et Gauss-Seidel ont des domaines d'application et des performances qui dépendent de ces propriétés.