Élimination de Gauss-Jordan

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir pivot.

En mathématiques, l'élimination de Gauss-Jordan, aussi appelée pivot de Gauss, nommée en hommage à Carl Friedrich Gauss et Wilhelm Jordan, est un algorithme de l'algèbre linéaire pour déterminer les solutions d'un système d'équations linéaires, pour déterminer le rang d'une matrice ou pour calculer l'inverse d'une matrice (carrée) inversible. Lorsqu'on applique l'élimination de Gauss sur une matrice, on obtient sa forme échelonnée réduite.

Histoire[modifier | modifier le code]

Cette méthode doit son nom aux mathématiciens Carl Friedrich Gauss et Wilhelm Jordan, mais elle est connue des Chinois depuis au moins le Ier siècle de notre ère. Elle est référencée dans l'important livre chinois Jiuzhang suanshu ou Les Neuf Chapitres sur l'art mathématique, dont elle constitue le huitième chapitre, sous le titre « Fang cheng » (la disposition rectangulaire). La méthode est présentée au moyen de dix-huit exercices. Dans son commentaire daté de 263, Liu Hui en attribue la paternité à Chang Ts'ang, chancelier de l'empereur de Chine au IIe siècle avant notre ère.

Algorithme[modifier | modifier le code]

Opérations[modifier | modifier le code]

L'algorithme de Gauss-Jordan produit la forme échelonnée réduite d'une matrice à l'aide d'opérations élémentaires sur les lignes. Trois types d'opérations élémentaires sont utilisées:

  • Échange de deux lignes;
  • Multiplication d'une ligne par un scalaire non-nul;
  • Ajout du multiple d'une ligne à une autre ligne.

Pseudocode[modifier | modifier le code]

Soit une matrice A de dimensions n \times m;

L'algorithme de Gauss-Jordan est le suivant :

  1. Pour dans toutes les lignes k de la matrice:
    1. Trouver la valeur maximale en module de la colonne k (appelée le pivot)
    2. Si la valeur maximale trouvée est égale à 0
      1. Erreur La matrice est singulière
    3. Permuter la ligne contenant la valeur maximale avec la ligne k
    4. Normaliser la ligne k
    5. Pour toutes les lignes i de la matrice sauf la ligne k:
      1. Soustraire la ligne k de i de façon à obtenir la valeur 0 à la colonne k

Voici son pseudocode:

 Soit une matrice A_{n, m}
 Pour k allant de 1 à n:
   i_{max}  = argmax (i = k ... m, abs(A_{i, k}))
   Si A_{i_{max}, k} = 0
     Erreur La matrice est singulière
   Permuter les lignes (k, i_{max})
   A_{k}  = A_{k} \cdot \frac{1}{A_{k, k}}
   Pour i allant de 1 à n et ik:
     A_{i} = A_{i} -  A_{i, k} \cdot A_{k}

La sortie de l'algorithme, soit la matrice A modifiée, représente la forme échelonnée réduite de la matrice A en entrée.

Stabilité numérique[modifier | modifier le code]

La première section de l'algorithme, soit l'échange de ligne avec la valeur de pivot la plus grande, a pour but d'améliorer la stabilité numérique de l'algorithme. Cette étape tente de minimiser les erreurs d'arrondis cumulatives causant de l'instabilité numérique. Cette stratégie permet en général de remédier à cette instabilité, même si on peut donner des contre-exemples[1]. La stabilité numérique de l'élimination de Gauss est optimale pour les systèmes d'équations sur un corps où les calculs sont par nature exacts, comme les corps finis.

Complexité algorithmique[modifier | modifier le code]

La complexité algorithmique asymptotique de l'élimination de Gauss est O(n3) (notations de Landau) : n×n c'est la taille de la matrice et le nombre d'instructions nécessaires est proportionnel à n3. Cet algorithme peut être utilisé sur un ordinateur pour des systèmes avec des milliers d'inconnues et d'équations[citation nécessaire]. Cependant, l'algorithme de Strassen, qui est en O(n2,807) a une meilleure complexité algorithmique asymptotique.

La complexité algorithmique du pivot de Gauss reste O(n3) quand la matrice est creuse. Effet, prenons une matrice n×n dont seulement k n entrées sont non nulles mais dans les entrées sont régulièrement réparties sur les lignes et les colonnes, alors au cours de l'algorithme du pivot de Gauss le nombre moyen de valeurs non nulles sur une ligne passera de k à 2k puis 3k jusqu'à n. On trouve donc que le nombre d'instructions est de l'ordre de n n (n-1)/2.

Calcul de l'inverse d'une matrice carrée[modifier | modifier le code]

L'élimination de Gauss-Jordan peut être utilisée pour inverser une matrice carrée, si elle est inversible. Pour cela, on crée une matrice à n lignes et 2n colonnes en bordant la matrice A par la matrice identité In., ce qui génère une matrice augmentée (en) notée [ A | I ]. Si la matrice d'entrée est inversible, appliquer l'algorithme de Gauss-Jordan sur la matrice augmentée la matrice finale sera de forme [ I | A−1 ] et contiendra l'inverse de la matrice initiale dans sa section de droite.

Exemple[modifier | modifier le code]

Admettons la matrice suivante:

 A =
\left( \begin{array}{rrr}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{array} \right)

Pour trouver l'inverse de cette matrice, il faut générer la matrice augmentée [ A | I ] comme suit:

 [ A | I ] = 
\left( \begin{array}{rrr|rrr}
2 & -1 & 0 & 1 & 0 & 0\\
-1 & 2 & -1 & 0 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right)

En appliquant l'algorithme de Gauss-Jordan, on obtient la matrice augmentée sous sa forme échelonnée réduite suivante:

 [ I | B ] = 
\left( \begin{array}{rrr|rrr}
1 & 0 & 0 & \frac{3}{4} & \frac{1}{2} & \frac{1}{4}\\[3pt]
0 & 1 & 0 & \frac{1}{2} & 1 & \frac{1}{2}\\[3pt]
0 & 0 & 1 & \frac{1}{4} & \frac{1}{2} & \frac{3}{4}
\end{array} \right)

La section gauche de la matrice est la matrice identité, ce qui démontre que A est inversible. La section 3x3 de droite, soit la matrice B, est l'inverse de A.

Résolution d'un système d'équations linéaires[modifier | modifier le code]

L'élimination de Gauss-Jordan peut résoudre un système d'équations A.X=B, où B est un vecteur fixé, et X le vecteur inconnu. On crée un tableau à n lignes et n+1 colonnes en bordant la matrice A par le vecteur B. On utilise le même algorithme que ci-dessus. On obtient à la fin une matrice identité, et dans la dernière colonne le vecteur X recherché.

Variante : dans l'algorithme précédent, si on n'exécute la boucle interne que pour i allant de k+1 à n, on obtient une matrice triangulaire supérieure. Il ne reste plus qu'à « remonter » pour retrouver les valeurs des coefficients de X.

Exemple[modifier | modifier le code]

Soit le système d'équations suivant :


\left\{\begin{array}{*{7}{c}} 
x &-& y &+& 2z &=& 5 \\
3x &+& 2y &+&z &=& 10 \\
2x &-& 3y &-& 2z &=& -10 \\
\end{array}\right.

On établit la matrice correspondante et on applique la première étape de Gauss-Jordan, le pivot est 1 :


\left(\begin{array}{ccc|c}
(1) &  -1 & 2 &  5 \\
3 & 2 & 1 &  10 \\
2 & -3 & -2 & -10
\end{array}\right)

On ajoute un multiple de la première ligne aux deux autres lignes pour obtenir des zéros (respectivement \scriptstyle-3\times l_1 et \scriptstyle-2\times l_1) ; le nouveau pivot est ensuite 5 :


\left(\begin{array}{ccc|c}
1 &  -1 & 2 &  5 \\
0 & (5) & -5 &  -5 \\
0 & -1 & -6 & -20
\end{array}\right)

La deuxième ligne est multipliée par 1/5 :


\left(\begin{array}{ccc|c}
1 &  -1 & 2 &  5 \\
0 & (1) & -1 &  -1 \\
0 & -1 & -6 &   -20
\end{array}\right)

On ajoute cette deuxième ligne à la troisième et à la première, le nouveau pivot est -7 :


\left(\begin{array}{ccc|c}
1 &  0 & 1 &  4 \\
0 & 1 & -1 &  -1 \\
0 & 0 & (-7) &   -21
\end{array}\right)

On divise la 3e ligne par -7 :


\left(\begin{array}{ccc|c}
1 &  0 & 1 &  4 \\
0 & 1 & -1 &  -1 \\
0 & 0 & (1) &  3
\end{array}\right)

On utilise la 3e ligne pour éliminer des coefficients dans la première et deuxième ligne. Nous sommes alors en présence d'une forme échelonnée réduite avec la matrice identité d'un côté et la valeur des variables de l'autre :


\left(\begin{array}{ccc|c}
1 &  0 & 0 &  1 \\
0 & 1 & 0 &  2 \\
0 & 0 & 1 &   3
\end{array}\right)

La solution du système est ainsi :


\left\{\begin{array} {ccc}
x &=& 1 \\
y &=& 2 \\
z &=& 3 \\
\end{array}\right.

Déterminant[modifier | modifier le code]

Cet algorithme permet également de calculer le déterminant d'une matrice : dans l'algorithme ci-dessus, c'est le produit des « \scriptstyle A_{i,k}^{k-1}\not=0 » qui sont choisis comme pivot à chaque itération. Si l'algorithme s'arrête parce qu'il n'y a plus de pivot non nul, alors la matrice n'est pas inversible, son déterminant est nul, mais on peut calculer son rang.

Le déterminant est aussi égal à:  \prod_{i \mathop =1}^{n}(a_{ii}^{n})^{i-n+1}

Note et référence[modifier | modifier le code]

  1. Voir par exemple les commentaires de Patrick Lascaux et Raymond Théodor, Analyse numérique matricielle appliquée à l'art de l'ingénieur, tome 1 : Méthodes directes [détail des éditions], p. 228.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]