Méthode du pivot de Gauss

Pour résoudre un système système d'équations linéaires, on cherche à se ramener à un système plus simple que l'on sait résoudre : un système triangulaire (méthode du pivot de Gauss) ou un système diagonal (méthode de Gauss-Jordan). Pour cela on transforme un système en un système équivalent obtenu par :

• échange éventuel de deux lignes,
• multiplication d'une ligne par un nombre non nul,
• addition d'une ligne à une autre ligne.

Mise en place de l'algorithme sur un exemple

Soit à résoudre le système suivant de trois équations à trois inconnues

$ \left\{ \begin{array}{rrrrrrrr} x_0 & +& 2x_1& + & 2x_2& = & 2 &L_0\\ x_0 & +& 3x_1& - & 2 x_2 & = & -1&L_1\\ 3x_0 & +& 5x_1 & + & 8x_2 & = & 8 &L_2\end{array} \right.$

Mise sous forme triangulaire

On définit les matrices $ \left( \begin{array}{rrr} a_{00} & a_{01} & a_{02}\\ a_{10} & a_{11} & a_{12}\\ a_{20} & a_{21} & a_{22}\end{array} \right) = \left( \begin{array}{rrr} 1 & 2 & 2\\ 1 & 3 & -2\\ 3 & 5 & 8 \end{array} \right)$ et $ \left( \begin{array}{r} y_0 \\ y_1 \\ y_2 \end{array} \right) = \left( \begin{array}{r} 2 \\ -1 \\ 8 \end{array} \right)$.

Le premier pivot est $a_{00} = 1 $. On supprime l'inconnue $x_0$ de $L_1$ et $L_2$ en utilisant la transformation :

• $L_1 \leftarrow L_1 - \frac{a_{10}}{a_{00}} \cdot L_0$ où $\frac{a_{10}}{a_{00}}$ = 1,
• $L_2 \leftarrow L_2 - \frac{a_{20}}{a_{00}} \cdot L_0$ où $\frac{a_{20}}{a_{00}}$ = 1.

On a :

$ \left\{ \begin{array}{rrrrrrrl} x_0 & +& 2x_1& + & 2x_2 &= & 2 & L_0\\ & & x_1& - & 4x_2 &= &-3 & L_1 \leftarrow L_1 - 1 \cdot L_0\\ & & -x_1& + & 2x_2 &= &2 & L_2 \leftarrow L_2 - 3 \cdot L_0\end{array} \right.$

On a maintenant les matrices $ \left( \begin{array}{rrr} a_{00} & a_{01} & a_{02}\\ a_{10} & a_{11} & a_{12}\\ a_{20} & a_{21} & a_{22}\end{array} \right) = \left( \begin{array}{rrr} 1 & 2 & 2\\ 0 & 1 & -4\\ 0 & -1 & 2\end{array} \right)$ et $ \left( \begin{array}{r} y_0 \\ y_1 \\ y_2 \end{array} \right) = \left( \begin{array}{r} 2 \\ -3 \\ 2 \end{array} \right)$.

Le second pivot est $a_{11} = 1 $.

On supprime l'inconnue $x_1$ de $L_2$ en utilisant la transformation :

• $L_2 \leftarrow L_2 - \frac{a_{21}}{a_{11}} \cdot L_1$ où $\frac{a_{21}}{a_{11}}$ = -1.

Ce qui donne, cette fois-ci...

$ \left\{ \begin{array}{rrrrrrrl} x_0 & +& 2x_1& + & 2x_2 &= & 2 & L_0 \\ & & x_1& - & 4x_2 &= &-3 & L_1 \\ & & & & -2x_2 &= &-1 & L_2 \leftarrow L_2 + 1 \cdot L_1 \end{array} \right.$

On a maintenant les matrices $ \left( \begin{array}{rrr} a_{00} & a_{01} & a_{02}\\ a_{10} & a_{11} & a_{12}\\ a_{20} & a_{21} & a_{22}\end{array} \right) = \left( \begin{array}{rrr} 1 & 2 & 2\\ 0 & 1 & -4\\ 0 & 0 & -2\end{array} \right)$ et $ \left( \begin{array}{r} y_0 \\ y_1 \\ y_2 \end{array} \right) = \left( \begin{array}{r} 2 \\ -3 \\ -1 \end{array} \right)$.

Remonter en substituant

Une fois la valeur de $x_2$ obtenue, il reste à remonter l'information pour obtenir les valeurs des variables $x_1$ puis $x_0$. Pour cela on effectue successivment

• $x_2 = \frac{y_2}{a_{22}} = \frac{1}{2}$
• $x_1 = \frac{y_1 - a_{12} \cdot x_2}{a_{11}} = \frac{-3 + 4 \cdot 1/2}{1} = -1$
• $x_0 = \frac{y_0 - (a_{02} \cdot x_2 + a_{01} \cdot x_1) }{a_{00}} = \frac{2 - (2 \cdot -1 + 2 \cdot 1/2) }{1} = 3$

L'unique solution est $ \left( \begin{array}{r} x_0 \\ x_1 \\ x_2 \end{array} \right) = \left( \begin{array}{r} 3 \\ -1 \\ 1/2 \end{array} \right)$.

Travaux pratiques

Pour définir les matrices on effectue comme suit :

  import numpy as np
  A = np.matrix([ [1,2,2],[1,3,-2],[3,5,8] ])
  Y = np.matrix([ [2],[-1],[8] ])

Application directe de la méthode

1. Construire la fonction transvection(A,Y,k,i,c) qui modifie A et Y pour effectuer l'instruction Lk <- Lk - c . Li ; solution;
2. Appeler trois fois la fonction précédente avec les bons paramètres pour obtenir le système triangulaire issu de l'étape de triangularisation ci-dessus ;
3. Construire la fonction triangularise(A,Y) qui transforme un système défini par A et Y en un système équivalent triangulaire ; solution;
4. Construire la fonction remonte(A,Y) qui donne la solution d'un système triangulaire défini par A et Y ;
5. Construire la fonction pivotDeGauss(A,Y) qui donne la solution d'un système défini par A et Y.
6. Retrouver les résultats de l'exemple ci-dessus.

Généralisation de la méthode

On considère $ \left\{ \begin{array}{rrrrrrrr} 2x_0 & +& 2x_1& - & 3x_2& = & 2 &L_0\\ -2x_0 & -& x_1& - & 3 x_2 & = & -5&L_1\\ 6x_0 & +& 4x_1 & + & 4x_2 & = & 16 &L_2\end{array} \right.$

$ \left\{ \begin{array}{rrrrrrrr} 3x_0 & -& 5x_1& + & 4x_2& = & -4 &L_0\\ -6x_0 & +& 10x_1& - & 3 x_2 & = & 23&L_1\\ 3x_0 & -& 8x_1 & + & 6x_2 & = & -4 &L_2\end{array} \right.$

1. Evaluer le code sur les deux systèmes précédents. Constater une erreur quant aux choix du pivot ;
2. Corriger le code en
   1. construisant la fonction intervertit(A,Y,i,j) qui intervertit les lignes i et j du système défini par A et Y ;
   2. corrigeant la triangularise(A,Y) : à chaque étape $i$, on cherche l'indice $j$, $ i \le j \le n-1$ tel que $|a_{ji}|$ est maximal et on intervertit $L_i$ et $L_j$ pour chosir le bon pivot.

Des erreurs d'arrondi

1. Evaluer le code sur le système suivant et résoudre le problème à la main. Que constate-t-on ?

$ \left\{ \begin{array}{rrrrrrrr} x_0 & +& \frac{1}{4}x_1& + & x_2& = & 0 &L_0\\ x_0 & +& \frac{1}{3}x_1& + & 2 x_2 & = & 0&L_1\\ & & x_1 & + & 12x_2 & = & 1 &L_2\end{array} \right.$

De "mauvais" systèmes

1. Résoudre le système défini par les matrices $A$ et $Y$ :

$ A= \left(\begin{array}{cccc}10 & 7 & 8 & 7 \\7 & 5 & 6 & 5 \\9 & 6 & 10& 9 \\ 7 & 5 & 9 & 10 \end{array} \right)$ et $Y = \left( \begin{array}{c} 21 \\ 12 \\ 22 \\ 20 \end{array} \right)$.

1. $Y$ est mesuré physiquement ; résoudre le systèmes avec le nouvel $Y$ défini par :

$Y = \left( \begin{array}{c} 21,1 \\ 11,9 \\ 22,1 \\ 19,9 \end{array} \right)$.

1. Mesurer l'erreur sur $Y$ et l'erreur sur le résultat de la résolution. Que constate-t-on ? On parle de matrice mal conditionnée.

Résolution avec numpy

On montre comment faire pour résoudre numériquement un système linéaire, en utilisant numpy.

  import numpy as np
  A = np.matrix([ [1.,0.25,1.],[1.,1./3,2.],[0.,1.,12.] ])
  Y = np.matrix([ [0.],[0.],[1.] ])
  X=np.linalg.solve(A,Y)
  print X
  [[ -7.50599938e+14]
   [  4.50359963e+15]
   [ -3.75299969e+14]]

Le résultat est encore faux dû aux erreurs d'arrondis.

Méthode de Gauss-Jordan

Présentation

C'est une variante de la méthode du pivot de Gauss : à la l'étape $i$, on combine toutes les lignes (sauf la ligne i) avec la ligne $i$ (au lieu de ne le faire que pour les lignes d'indice supérieurs à $i$). L'intéret est que cela fait apparaître des 0 sur toute la colonne sauf au niveau du pivot $a_{ii}^i$

Exemple

Soit à résoudre le système de trois équations à trois inconnues suivant :

$ \left\{ \begin{array}{rrrrrrrl} 2x_0 & +& x_1& - & 4x_2& = & 8 &L_0\\ 3x_0 & +& 3x_1& - & 5x_2 & = & 14&L_1\\ 4x_0 & +& 5x_1 & - & 2x_2 & = & 16 &L_2\end{array} \right.$

1. on choisit comme premier pivot le nombre $a_{00} = 2 $
2. on normalise la ligne $L_0$ en la divisant par 2 et on obtient $L'_0$
3. on applique les transformations suivantes pour les autres lignes :
   • $L'_1 \leftarrow L_1 -3 \cdot L'_0$
   • $L'_2 \leftarrow L_2 -2 \cdot L'_0$

On trouve alors...

$ \left\{ \begin{array}{rrrrrrrl} x_0 & +& 1/2x_1& - & 2x_2 &= & 4 & L'_0 \leftarrow L_0/2\\ & & 3/2 \cdot x_1& + & x_2 &= &2 & L'_1 \leftarrow L_1 -3 \cdot L'_0\\ & & 3x_1& + & 6x_2 &= &0 & L'_2 \leftarrow L_2 -4 \cdot L'_0 \end{array}\right.$

1. on choisit comme second pivot le nombre $a_{11} = 3/2 $
2. on normalise la ligne $L'_1$ en la multipliant par 2/3 et on obtient $L"_1$
3. on applique les transformations suivantes pour les autres lignes :
   • $L"_0 \leftarrow L'_0 -1/2 \cdot L"_1$
   • $L"_2 \leftarrow L'_2 -3 \cdot L"_1$

Cela donne :

$ \left\{ \begin{array}{rrrrrrrl} x_0 & & & & -7/3 \cdot x_2 &= & 10/3 & L"_0 \leftarrow L'_0 -1/2 \cdot L"_1 \\ & & x_1& + & 4/3 \cdot x_2 &= &4/3 & L"_1 \leftarrow 2/3 \cdot L'_1 \\ & & & & 4x_2 &= &-4 & L"_2 \leftarrow L'_2 -3 \cdot L"_1 \end{array}\right.$

1. on choisit enfin comme troisième pivot le nombre $a_{22} = 4 $
2. on normalise la ligne $L"_2$ en la divisant par 4 et on obtient $L_2^{3}$
3. on applique les transformations suivantes pour les autres lignes :
   • $L_0^{3} \leftarrow L"_0 + 7/3 \cdot L_1^{3}$
   • $L_1^{3} \leftarrow L"_1 - 2/3 \cdot L_1^{3}$

D'où, finalement,

$ \left\{ \begin{array}{rrrrrrrl} x_0 & & & & & = & 1 & L_0^{3} \leftarrow L"_0 + 7/3 \cdot L_1^{3}\\ & & x_1& & &= &2 & L_1^{3} \leftarrow L"_1 - 2/3 \cdot L_1^{3} \\ & & & & x_2 &= &-1 & L_2^{3} \leftarrow L"_2/4 \cdot L"_1 \end{array}\right.$

et on trouve directement les racines sur la 4^ème colonne.

Algorithme

On a le pseudo algorithme suivant :

  pour i = 1 à n 
    recherche du pivot (non nul) sur la ligne p, p >= i 
    échange éventuel des lignes i et p -> le pivot est Aii
    division de la ligne Li par Aii pour obtenir L'i
    pour k = 1 à n sauf i
      L'k = L_k - Aki .L'i

Les solutions sont dans la colonne $n+1$.

Travaux Pratiques.

• Implanter l'algorithme de Gauss-Jordan et s'assurer de son fonctionnement sur les exemples du TP.
• Résoudre avec l'algorithme implanté les deux systèmes équivalents

$\left(\begin{array}{cc}10^{-01} & 1 \\ 1 & 1 \end{array}\right) \cdot \left(\begin{array}{c}x_0 \\x_1 \end{array}\right)=\left(\begin{array}{c} 1 \\2 \end{array}\right)$ et $\left(\begin{array}{cc}1 & 1 \\ 10^{-01} & 1 \end{array}\right) \cdot \left(\begin{array}{c}x_0 \\x_1 \end{array}\right)=\left(\begin{array}{c} 1 \\2 \end{array}\right)$.