Voir la source de Élimination de Gauss-Jordan

{{voir homonymes|Pivot}}
En [[mathématiques]], plus précisément en [[algèbre linéaire]], l''''élimination de Gauss-Jordan''', est un [[algorithme]] pour déterminer les solutions d'un [[système d'équations linéaires]]. Cette méthode permet aussi de déterminer le [[Rang (mathématiques)|rang]] d'une [[Matrice (mathématiques)|matrice]] et de calculer l'[[inverse d'une matrice]] (carrée) inversible. Lorsqu'on applique l'élimination de Gauss à une matrice, on obtient sa forme [[Matrice échelonnée|échelonnée réduite]].

La méthode est nommée ainsi en hommage à [[Carl Friedrich Gauss]] et [[Wilhelm Jordan (géodésien)|Wilhelm Jordan]].

== Histoire ==

Cette méthode est connue des [[Mathématiques chinoises|mathématiciens chinois]] depuis au moins le {{Ier siècle}} de notre ère. Elle est référencée dans le livre chinois ''Jiuzhang suanshu'' (''[[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.

En Europe, cette méthode a été découverte et présentée sous forme moderne au {{XIXe siècle}}. En 1810, [[Carl Friedrich Gauss]] présente sa [[méthode des moindres carrés]] dans un livre étudiant le mouvement de l'astéroïde [[(2) Pallas|Pallas]]<ref>{{harvnb|Gauss|1810}}.</ref>. Dans l'article 13 de ce livre, il décrit une méthode générale de résolution de système d'équations linéaires qui constitue l'essentiel de la méthode du pivot. En 1888, [[Wilhelm Jordan (géodésien)|Wilhelm Jordan]] publie un livre de [[géodésie]] précisant comment utiliser cette méthode et adoptant une notation un peu différente<ref>{{harvnb|Jordan|1888}}.</ref>. C'est grâce à ce dernier livre que cette méthode se diffusa dans tout l'Occident<ref>{{harvnb|Althoen|McLaughlin|1987}}.</ref>. Elle est aujourd'hui connue sous le nom d'''élimination de Gauss-Jordan'' ou ''méthode du pivot de Gauss''.

== Algorithme ==

=== Opérations ===

L'algorithme de Gauss-Jordan produit la [[matrice échelonnée]] réduite d'une matrice à l'aide d'[[Opération élémentaire|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 (mathématiques)|scalaire]] non nul ;
* '''Ajout''' du multiple d'une ligne à une autre ligne.

=== Pseudocode ===

Soit une matrice A de dimensions ''n'' × ''m'' ;

L'[[Algorithmique|algorithme]] de Gauss-Jordan est le suivant<ref>Adapté de {{harvnb|Beezer|2014|p=30}}.</ref> :

   '''Gauss-Jordan'''
      r = 0                                       ''(r est l'indice de ligne du dernier pivot trouvé)''
      '''Pour''' j '''de''' 1 '''jusqu'à''' m                       ''(j décrit tous les indices de colonnes)''
      |   '''Rechercher''' max(|A[i,j]|, r+1 ≤ i ≤ n). '''Noter''' k l'indice de ligne du maximum
      |                                           ''(A[k,j] est le pivot)''
      |   '''Si''' A[k,j]≠0 '''alors'''                       (''A[k,j] désigne la valeur de la ligne k et de la colonne j)''
      |   |   r=r+1                               ''(r désigne l'indice de la future ligne servant de pivot)''
      |   |   '''Diviser''' la ligne k par A[k,j]       ''(On normalise la ligne de pivot de façon que le pivot prenne la valeur 1)''
      |   |   '''Si''' k≠r '''alors'''
      |   |       |   '''Échanger''' les lignes k et r  ''(On place la ligne du pivot en position r)''
      |   |   '''Fin Si'''
      |   |   '''Pour''' i '''de''' 1 '''jusqu'à''' n               ''(On simplifie les autres lignes)''
      |   |   |   '''Si''' i≠r '''alors'''
      |   |   |   |   '''Soustraire''' à la ligne i la ligne r multipliée par A[i,j] ''(de façon à annuler A[i,j])''
      |   |   |   '''Fin Si'''
      |   |   '''Fin Pour'''
      |   '''Fin Si'''
      '''Fin Pour'''
   '''Fin Gauss-Jordan'''


'''Exemple.'''

On part de la matrice
: <math>\mathrm{A} = \begin{pmatrix}
   2 & -1 & 0 \\
   -1 & 2 & -1 \\
   0 & -1 & 2
\end{pmatrix}</math>
Il s'agit d'une matrice réelle, donc le module d'un coefficient est sa [[valeur absolue]].

* Première [[itération]], ''j'' = 1 (et ''r'' = 0) :
** étape 1.1 : on cherche dans la première colonne de la matrice la valeur maximale des valeurs absolues des coefficients. Elle vaut  2, située en (1, 1), de sorte que ''k'' = 1,
** étape 1.2.1 : ''r'' = 1,
** étape 1.2.2 : ''r'' = ''k'', il n'y a pas d'échange,
** étape 1.2.3 : on divise la ligne 1 par A(1, 1) = 2, soit <math>\begin{pmatrix} 1 & -1/2 & 0 \end{pmatrix}</math>,
** étape 1.2.4 :
*** ligne ''i'' = 2, on a A(2, 1) = -1 ; on calcule<br /> <math>\begin{pmatrix} -1 & 2 & -1 \end{pmatrix} - (-1) \times \begin{pmatrix} 1 & -1/2 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 3/2 & -1 \end{pmatrix}</math>,
*** ligne ''i'' = 3, on a A(3, 1) = 0, la ligne n'est donc pas modifiée,
** la matrice est alors<br /><math>\mathrm{A}' = \begin{pmatrix}
   1 & -1/2 & 0 \\
   0 & 3/2 & -1 \\
   0 & -1 & 2
\end{pmatrix}</math> ;
* deuxième itération, ''j'' = 2 (et ''r'' = 1) :
** étape 2.1 : on cherche dans les lignes 2 à 3 de la deuxième colonne la valeur maximale en valeur absolue. Il s'agit de 3/2, situé en (2, 2),
** étape 2.2.1 : ''r'' = 2,
** étape 2.2.2 : ''r'' = ''k'', il n'y a pas d'échange.
** étape 2.2.3 : on divise la ligne 2 par A'(2, 2) = 3/2, soit <math>\begin{pmatrix} 0 & 1 & -2/3 \end{pmatrix}</math>,
** étape 2.2.4 :
*** ligne ''i'' = 1, on a A'(1, 2) = -1/2 ; on calcule <br /> <math>\begin{pmatrix} 1 & -1/2 & 0 \end{pmatrix} - (-1/2) \times \begin{pmatrix} 0 & 1 & -2/3 \end{pmatrix} = \begin{pmatrix} 1 & 0 & -1/3 \end{pmatrix}</math>,
*** ligne ''i'' = 3, on a A'(3, 2) = -1 ; on calcule<br /> <math>\begin{pmatrix} 0 & -1 & 2 \end{pmatrix} - (-1) \times \begin{pmatrix} 0 & 1 & -2/3 \end{pmatrix} = \begin{pmatrix} 0 & 0 & 4/3 \end{pmatrix}</math>,
** la matrice est alors<br /><math>\mathrm{A}'' = \begin{pmatrix}
   1 & 0 & -1/3 \\
   0 & 1 & -2/3 \\
   0 & 0 & 4/3
\end{pmatrix}</math> ;
* troisième itération, ''j'' = 3 (et ''r'' = 2) :
** étape 3.1 : le pivot de la troisième colonne, troisième ligne est 4/3. Donc ''k'' = 3
** étape 3.2.1 : ''r'' = k,
** étape 3.2.2 : il n'y a aucune ligne à permuter,
** étape 3.2.3 : on divise la ligne 3 par A<nowiki>''</nowiki>(3, 3) = 4/3, elle devient <math>\begin{pmatrix} 0 & 0 & 1 \end{pmatrix}</math>
** étape 3.2.4 :
*** ligne ''i'' = 1, on a A<nowiki>''</nowiki>(1, 3) = -1/3. La dernière étape annule ce coefficient.
*** ligne ''i'' = 2, on a A<nowiki>''</nowiki>(2, 3) = -2/3. La dernière étape annule ce coefficient.
** la matrice est alors<br /><math>\mathrm{A}''' = \begin{pmatrix}
   1 & 0 & 0 \\
   0 & 1 & 0 \\
   0 & 0 & 1
\end{pmatrix}</math> qui est réduite échelonnée.

=== Stabilité numérique ===

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<ref>Voir par exemple les commentaires de {{LascauxThéodor1}}, {{p.|228}}.</ref>.

=== Complexité algorithmique ===

La [[complexité en temps|complexité algorithmique asymptotique]] de l'élimination de Gauss est ''O''(''n''{{3}}) ([[Comparaison asymptotique#Notations de Landau, notations de Hardy, notation de Vinogradov|notations de Landau]]) : ''n''×''n'' est la taille de la matrice et le nombre d'instructions à réaliser est proportionnel à ''n''{{3}}.
Cet algorithme peut être utilisé sur un ordinateur pour des systèmes avec des milliers d'inconnues et d'équations<ref name="Edelman">{{article|auteur=Alan Edelman|titre=The first annual large dense linear systems survey|périodique=The SIGNUM Newsletter|numéro=26 |pages=6-12|url= https://math.mit.edu/~edelman/publications/first_annual.pdf|date=octobre 1991}} ; {{article|auteur=Alan Edelman|titre=Large dense numerical linear algebra in 1993: The parallel computing influence|périodique=Int. J. Supercomputer appl.|volume=7|numéro=2 |pages=113-128|date=1993}}.</ref>{{,}}<ref>La [https://math.nist.gov/MatrixMarket/collections/hb.html collection de matrices creuses inversibles de Harwell-Boeing] est très connue des développeurs de codes de calcul. Elle a fait l'objet de plusieurs publications, par ex. {{article|auteur1=I. Duff|auteur2=R. Grimes|auteur3=J. Lewis |titre=Sparse Matrix Test Problems |périodique=ACM Trans. Math. Softw.|volume=15|numéro=1 |pages=1-14|doi=10.1145/62038.62043|date=mars 1989}}</ref>. Cependant, l'[[algorithme de Strassen]], qui est en ''O''(''n''{{exp|2,807}}) a une meilleure complexité algorithmique asymptotique.

La complexité algorithmique du pivot de Gauss reste ''O''(''n''{{3}}) quand la matrice est creuse.
En effet, prenons une matrice ''n''×''n'' dont seulement ''k'' ''n'' entrées sont non nulles mais dont 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 ==

L'élimination de Gauss-Jordan peut être utilisée pour inverser une [[Matrice (mathématiques)|matrice]] [[Matrice carrée|carrée]] si celle-ci est [[matrice inversible|inversible]]. Pour cela, on crée une matrice à ''n'' lignes et 2''n'' colonnes en bordant la matrice A par la [[matrice identité]] I<sub>''n''</sub>, ce qui génère une {{Lien|matrice augmentée|trad = Augmented matrix}} notée {{math|[ A {{!}} I ]}}. Si la matrice d'entrée est inversible, on applique l'algorithme de Gauss-Jordan à la matrice augmentée. La matrice finale est de la forme {{math|[ I {{!}} A{{-1}} ]}} et contient l'inverse de la matrice initiale dans sa section de droite.

=== Exemple ===

Admettons la matrice suivante:
:<math> \mathrm{A} =
\left( \begin{array}{rrr}
2 & -1 & 0 \\
-1 & 2 & -1 \\
0 & -1 & 2
\end{array} \right)
</math>

Pour trouver l'inverse de cette matrice, il faut générer la matrice augmentée {{math|[ A {{!}} I ]}} comme suit:
:<math> [ \mathrm{A} | \mathrm{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)
</math>

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

:<math> [ \mathrm{I} | \mathrm{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)
</math>

{{démonstration
 | 1=Comme précédemment, le premier pivot est sur la première ligne. À l'étape 2.2.3, la première ligne devient
: <math>\left ( \begin{array}{rrr|rrr} 1 & -1/2 & 0 & 1/2 & 0 & 0 \end{array} \right )</math>
L'étape 2.2.4 devient : 
* ligne i = 2, on a A(2, 1) = -1 ; on calcule <br /><math>
( \begin{array}{rrr|rrr} -1 & 2 & -1 & 0 & 1 & 0 \end{array} ) - (-1) \times ( \begin{array}{rrr|rrr}  1 & -1/2 & 0 & 1/2 & 0 & 0 \end{array} ) = ( \begin{array}{rrr|rrr} 0 & 3/2 & -1 & 1/2 & 1 & 0 \end{array} )</math> ;
* ligne i = 3, on a A(3, 1) = 0, la ligne n'est pas modifiée.
On a donc
:<math> 
\left( \begin{array}{rrr|rrr}
1 & -1/2 & 0 & 1/2 & 0 & 0 \\
0 & 3/2 & -1 & 1/2 & 1 & 0\\
0 & -1 & 2 & 0 & 0 & 1
\end{array} \right)
</math>

Pour la deuxième itération, on permute les lignes 2 et 3, et on divise la nouvelle ligne 2 par 2, soit à l'étape 2.2.3 :
:<math> 
\left( \begin{array}{rrr|rrr}
1 & -1/2 & 0 & 1/2 & 0 & 0 \\
0 & -1/2 & 1 & 0 & 0 & 1/2 \\
0 & 3/2 & -1 & 1/2 & 1 & 0
\end{array} \right)
</math>
À l'étape 2.2.4 :
* ligne i = 1, on a A(1, 3) = 0, la ligne n'est pas modifiée ;
* ligne i = 3, on a A(3, 3) = -1 ; on calcule<br /><math>
( \begin{array}{rrr|rrr} 0 & 3/2 & -1 & 1/2 & 1 & 0 \end{array} ) - (-1) \times ( \begin{array}{rrr|rrr}  0 & -1/2 & 1 & 0 & 0 & 1/2 \end{array} ) = ( \begin{array}{rrr|rrr} 0 & 1 & 0 & 1/2 & 1 & 1/2 \end{array} )</math> ;
On a donc
:<math> 
\left( \begin{array}{rrr|rrr}
1 & -1/2 & 0 & 1/2 & 0 & 0 \\
0 & -1/2 & 1 & 0 & 0 & 1/2 \\
0 & 1 & 0 & 1/2 & 1 & 1/2
\end{array} \right)
</math>

Pour la troisième itération, on divise la ligne 3 par 1, la matrice est inchangée à l'étape 2.2.3.

À l'étape 2.2.4 :
* ligne i = 1, on a A(1, 2) = -1/2 ; on calcule<br /><math>
( \begin{array}{rrr|rrr} 1 & -1/2 & 0 & 1/2 & 0 & 0 \end{array} ) - (-1/2) \times ( \begin{array}{rrr|rrr}  0 & 1 & 0 & 1/2 & 1 & 1/2 \end{array} ) = ( \begin{array}{rrr|rrr} 1 & 0 & 0 & 3/4 & 1/2 & 1/4 \end{array} )</math> ;
* ligne i = 2, on a A(2, 2) = -1/2 ; on calcule<br /><math>
( \begin{array}{rrr|rrr} 0 & -1/2 & 1 & 0 & 0 & 1/2 \end{array} ) - (-1/2) \times ( \begin{array}{rrr|rrr} 0 & 1 & 0 & 1/2 & 1 & 1/2 \end{array} ) = ( \begin{array}{rrr|rrr} 0 & 0 & 1 & 1/4 & 1/2 & 3/4 \end{array} )</math> ;
On a donc
:<math> 
\left( \begin{array}{rrr|rrr}
1 & 0 & 0 & 3/4 & 1/2 & 1/4 \\
0 & 0 & 1 & 1/4 & 1/2 & 3/4 \\
0 & 1 & 0 & 1/2 & 1 & 1/2
\end{array} \right)
</math>.

Une dernière permutation des lignes 2 et 3 nous donne
:<math> 
\left( \begin{array}{rrr|rrr}
1 & 0 & 0 & 3/4 & 1/2 & 1/4 \\
0 & 1 & 0 & 1/2 & 1 & 1/2 \\
0 & 0 & 1 & 1/4 & 1/2 & 3/4
\end{array} \right)
</math>.
}}

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.

=== Cas général ===
Effectuer une opération élémentaire ''O'' sur les ''n'' lignes d'une matrice revient à la multiplier à gauche par la [[Matrice élémentaire#Propriétés|matrice élémentaire (inversible)]] ''G{{ind|s}}'' := ''O''([[Matrice identité|{{math|I{{ind|''n''}}}}]]).

En notant ''O''{{ind|1}}, …, ''O{{ind|s}}'' les opérations élémentaires que l'on effectue sur ''A'', et ''G{{ind|s}} = O{{ind|s}}''({{math|I{{ind|''n''}}}}) les matrices élémentaires associées, on aboutit donc, dans la section de gauche, à la matrice

<math>\mathrm{I}_n=(O_s\circ\ldots\circ O_1)(A)=G_s\ldots G_1A</math>

et dans celle de droite, à la matrice

<math>B=(O_s\circ\ldots\circ O_1)(\mathrm{I}_n)=G_s\ldots G_1.</math>

Ainsi, ''B'' est inversible et ''BA'' = {{math|I{{ind|''n''}}}}, donc ''B''{{-1}} = ''A'' et ''A''{{-1}} = ''B''.

== Résolution d'un [[système d'équations linéaires]] ==

L'élimination de Gauss-Jordan peut résoudre un système d'équations AX = B, où A est une matrice ''n'' × ''m'' de rang ''r'', B est un vecteur fixé, et X le vecteur inconnu.  On crée un tableau à ''n'' lignes et ''m'' + 1 colonnes en bordant la matrice A par le vecteur B. On réduit la matrice sous forme échelonnée réduite.

Si les pivots de la matrice échelonnée réduite associée à (A|B) sont situés uniquement dans les ''m'' premières colonnes (ce qui est toujours le cas si ''r'' = ''n''&thinsp;) et ont pour indice de colonnes ''k''<sub>1</sub>, …, ''k<sub>r&thinsp;</sub>'', alors la dernière colonne fournit une solution particulière, obtenue en prenant tous ses termes nuls sauf ceux situés à la ligne d'indice ''k<sub>i</sub>'' et à qui on donne la valeur du terme situé à la ligne ''i'' de la dernière colonne, ''i'' variant de 1 à ''r''.

On obtient la solution générale du système en ajoutant à cette solution particulière un élément quelconque du noyau de A. Celle-ci s'obtient en donnant des valeurs quelconques aux coefficients de X situés à un indice de ligne autre que les ''k<sub>i</sub>'', et en déterminant les coefficients situés aux lignes d'indice ''k<sub>i</sub>'' de façon à satisfaire le système (ce qui est facile compte tenu de la forme échelonnée de la matrice).

Si le dernier pivot de la matrice échelonnée réduite associée à (A|B) se situe dans la dernière colonne, alors il n'y a pas de solution.

Si la matrice A est carrée inversible (autrement dit, le système est de Cramer), alors on obtient dans la dernière colonne l'unique solution X du système.

Variante : dans l'algorithme précédent, si on se borne à obtenir une matrice échelonnée (non réduite), on obtient une matrice triangulaire supérieure. Il ne reste plus qu'à « remonter » pour retrouver les valeurs des coefficients de X.

{{Boîte déroulante/début|titre=Exemple 1 (détaillé)}}

Soit le système d'équations linéaires :
:<math>
\left\{\begin{array}{*{7}{c}} 
x &-& y &+& 2z &=& 5 \\
3x &+& 2y &+&z &=& 10 \\
2x &-& 3y &-& 2z &=& -10 \\
\end{array}\right.
</math>

On établit la matrice correspondante :
:<math>
\left(\begin{array}{ccc|c}
1 &  -1 & 2 &  5 \\
 & & & \\
3 & 2 & 1 &  10 \\
 & & & \\
2 & -3 & -2 & -10
\end{array}\right)
</math>

On commence par la colonne 1. Le pivot est le maximum en valeur absolue entre 1, 3 et 2, soit 3 :
:<math>
\left(\begin{array}{ccc|c}
1 &  -1 & 2 &  5 \\
 & & & \\
(3) & 2 & 1 &  10 \\
 & & & \\
2 & -3 & -2 & -10
\end{array}\right)
</math>

Comme ce pivot n'est pas nul, on divise la ligne où il se trouve (c'est-à-dire la ligne 2) par le pivot :
:<math>
\left(\begin{array}{ccc|c}
1 &  -1 & 2 &  5 \\
 & & & \\
(1) & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \\
 & & & \\
2 & -3 & -2 & -10
\end{array}\right)
</math>

On échange les lignes 1 et 2 :
:<math>
\left(\begin{array}{ccc|c}
(1) & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \\
 & & & \\
1 &  -1 & 2 &  5 \\
 & & & \\
2 & -3 & -2 & -10
\end{array}\right)
</math>

On analyse maintenant les lignes autres que celle du pivot. Ligne 2, on a A(2, 1) = 1. On calcule
:<math>\begin{pmatrix} 1 & -1 & 2 & 5 \end{pmatrix} - (1) \times \begin{pmatrix} 1 & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \end{pmatrix} = \begin{pmatrix} 0 & - \frac{5}{3} & \frac{5}{3} & \frac{5}{3} \end{pmatrix}</math>

Ligne 3, on a A(3, 1) = 2. On calcule
:<math>\begin{pmatrix} 2 & -3 & -2 & -10 \end{pmatrix} - (2) \times \begin{pmatrix} 1 & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \end{pmatrix} = \begin{pmatrix} 0 & - \frac{13}{3} & - \frac{8}{3} & - \frac{50}{3} \end{pmatrix}</math>

On remplace les lignes 2 et 3 ainsi calculées :
:<math>
\left(\begin{array}{ccc|c}
(1) & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \\
 & & & \\
0 & - \frac{5}{3} & \frac{5}{3} & \frac{5}{3} \\
 & & & \\
0 & - \frac{13}{3} & - \frac{8}{3} & - \frac{50}{3}
\end{array}\right)
</math>

On passe à la colonne 2. Le pivot est le maximum en valeur absolue entre <math>- \frac{5}{3}</math> et <math>- \frac{13}{3}</math>, soit <math>- \frac{13}{3}</math> :
:<math>
\left(\begin{array}{ccc|c}
1 & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \\
 & & & \\
0 & - \frac{5}{3} & \frac{5}{3} & \frac{5}{3} \\
 & & & \\
0 & \left(- \frac{13}{3}\right) & - \frac{8}{3} & - \frac{50}{3}
\end{array}\right)
</math>

Comme ce pivot n'est pas nul, on divise la ligne où il se trouve (c'est-à-dire la ligne 3) par le pivot :
:<math>
\left(\begin{array}{ccc|c}
1 & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \\
 & & & \\
0 & - \frac{5}{3} & \frac{5}{3} & \frac{5}{3} \\
 & & & \\
0 & (1) & \frac{8}{13} & \frac{50}{13}
\end{array}\right)
</math>

On échange les lignes 2 et 3 :
:<math>
\left(\begin{array}{ccc|c}
1 & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \\
 & & & \\
0 & (1) & \frac{8}{13} & \frac{50}{13} \\
 & & & \\
0 & - \frac{5}{3} & \frac{5}{3} & \frac{5}{3}
\end{array}\right)
</math>

On analyse maintenant les lignes autres que celle du pivot. Ligne 1, on a A(1, 2) = <math>\frac{2}{3}</math>. On calcule
:<math>\begin{pmatrix} 1 & \frac{2}{3} & \frac{1}{3} & \frac{10}{3} \end{pmatrix} - \left(\textstyle\frac{2}{3}\right) \times \begin{pmatrix} 0 & 1 & \frac{8}{13} & \frac{50}{13} \end{pmatrix} = \begin{pmatrix} 1 & 0 & - \frac{1}{13} & \frac{10}{13} \end{pmatrix}</math>

Ligne 3, on a A(3, 2) = <math>- \frac{5}{3}</math>. On calcule
:<math>\begin{pmatrix} 0 & - \frac{5}{3} & \frac{5}{3} & \frac{5}{3} \end{pmatrix} - \left(- \textstyle\frac{5}{3}\right) \times \begin{pmatrix} 0 & 1 & \frac{8}{13} & \frac{50}{13} \end{pmatrix} = \begin{pmatrix} 0 & 0 & \frac{35}{13} & \frac{105}{13} \end{pmatrix}</math>

On remplace les lignes 1 et 3 ainsi calculées :
:<math>
\left(\begin{array}{ccc|c}
1 & 0 & - \frac{1}{13} & \frac{10}{13} \\
 & & & \\
0 & (1) & \frac{8}{13} & \frac{50}{13} \\
 & & & \\
0 & 0 & \frac{35}{13} & \frac{105}{13}
\end{array}\right)
</math>

On passe à la colonne 3. Le pivot est <math>\frac{35}{13}</math> :
:<math>
\left(\begin{array}{ccc|c}
1 & 0 & - \frac{1}{13} & \frac{10}{13} \\
 & & & \\
0 & 1 & \frac{8}{13} & \frac{50}{13} \\
 & & & \\
0 & 0 & \left(\frac{35}{13}\right) & \frac{105}{13}
\end{array}\right)
</math>

Comme ce pivot n'est pas nul, on divise la ligne où il se trouve (c'est-à-dire la ligne 3) par le pivot :
:<math>
\left(\begin{array}{ccc|c}
1 & 0 & - \frac{1}{13} & \frac{10}{13} \\
 & & & \\
0 & 1 & \frac{8}{13} & \frac{50}{13} \\
 & & & \\
0 & 0 & (1) & 3
\end{array}\right)
</math>

Comme ce pivot est déjà ligne 3, on n'a pas besoin d'échanger de lignes.

On analyse maintenant les lignes autres que celle du pivot. Ligne 1, on a A(1, 3) = <math>- \frac{1}{13}</math>. On calcule
:<math>\begin{pmatrix} 1 & 0 & - \frac{1}{13} & \frac{10}{13} \end{pmatrix} - \left(- \textstyle\frac{1}{13}\right) \times \begin{pmatrix} 0 & 0 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 0 & 0 & 1 \end{pmatrix}</math>

Ligne 2, on a A(2, 3) = <math>\frac{8}{13}</math>. On calcule
:<math>\begin{pmatrix} 0 & 1 & \frac{8}{13} & \frac{50}{13} \end{pmatrix} - \left(\textstyle\frac{8}{13}\right) \times \begin{pmatrix} 0 & 0 & 1 & 3 \end{pmatrix} = \begin{pmatrix} 0 & 1 & 0 & 2 \end{pmatrix}</math>

On remplace les lignes 1 et 2 ainsi calculées :
:<math>
\left(\begin{array}{ccc|c}
1 & 0 & 0 & 1 \\
 & & & \\
0 & 1 & 0 & 2 \\
 & & & \\
0 & 0 & 1 & 3
\end{array}\right)
</math>

Toutes les colonnes à gauche de la barre verticale ont été traitées. Nous sommes en présence d'une matrice échelonnée réduite, avec la matrice identité d'un côté et la valeur des variables de l'autre. La solution du système d'équations est donc :
:<math>
\left\{\begin{array} {ccc}
x &=& 1 \\
y &=& 2 \\
z &=& 3 \\
\end{array}\right.
</math>
{{Boîte déroulante/fin}}

{{Boîte déroulante/début|titre=Exemple 2}}

Soit le système d'équations linéaires :
:<math>
\left\{\begin{array}{*{11}{c}} 
x_1  &+& 2x_2 &+& 2x_3 &-& 3x_4 &+& 2x_5 &=& 3 \\
2x_1 &+& 4x_2 &+& x_3  & &      &-& 5x_5 &=& -6 \\
4x_1 &+& 8x_2 &+& 5x_3 &-& 6x_4 &-& x_5  &=& 0 \\
-x_1 &-& 2x_2 &-& x_3  &+& x_4  &+& x_5  &=&1
\end{array}\right.
</math>

La matrice échelonnée réduite associée à 
:<math>
\left(\begin{array}{ccccc|c} 
1  & 2  & 2  & -3 & 2  & 3 \\
2  & 4  & 1  & 0  & -5 & -6 \\
4  & 8  & 5  & -6 & -1 & 0 \\
-1 & -2 & -1 &  1 & 1  & 1
\end{array}\right)
</math>
est 
:<math>
\left(\begin{array}{ccccc|c} 
1  & 2 & 0 & 1  & -4 & -5 \\
0  & 0 & 1 & -2 &  3 & 4 \\
0  & 0 & 0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right)
</math>.

Les pivots sont situés aux colonnes d'indice 1 et 3. Une solution particulière est donc : <math>x_1 = -5, x_3 = 4, x_2 = x_4 = x_5 = 0</math>, ce qui correspond au vecteur :
:<math>
\left(\begin{array} {ccc}
-5 \\
0 \\
4 \\
0 \\
0 
\end{array}\right)
</math>
{{Boîte déroulante/fin}}

{{Boîte déroulante/début|titre=Exemple 3}}

Soit le système d'équations linéaires :
:<math>
\left\{\begin{array}{*{11}{c}} 
x_1  &+& 2x_2 &+& 2x_3 &-& 3x_4 &+& 2x_5 &=& 3 \\
2x_1 &+& 4x_2 &+& x_3  & &      &-& 5x_5 &=& -6 \\
4x_1 &+& 8x_2 &+& 5x_3 &-& 6x_4 &-& x_5  &=& 0 \\
-x_1 &-& 2x_2 &-& x_3  &+& x_4  &+& x_5  &=&2
\end{array}\right.
</math>

La matrice échelonnée réduite associée à 
:<math>
\left(\begin{array}{ccccc|c} 
1  &  2 & 2  & -3 &  2 & 3 \\
2  &  4 & 1  & 0  & -5 & -6 \\
4  &  8 & 5  & -6 & -1 & 0 \\
-1 & -2 & -1 & 1  &  1 & 2
\end{array}\right)
</math>
est 
:<math>
\left(\begin{array}{ccccc|c} 
1  & 2 & 0 & 1  & -4 & 0 \\
0  & 0 & 1 & -2 &  3 & 0 \\
0  & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0
\end{array}\right)
</math>.

Il n'y a pas de solution.
{{Boîte déroulante/fin}}

== Déterminant ==
{{section à recycler|date=novembre 2014}}
Cet algorithme permet également de calculer le [[Déterminant (mathématiques)#Déterminant d'une matrice|déterminant d'une matrice]] :

<math>\det(A)=(-1)^p. \prod_{j \mathop =1}^{n}(A[k,j])</math>

avec ''p'' le nombre de permutations de lignes, et <math>A[k,j]</math> le pivot noté à l'étape ''j'' de l'algorithme.

Si l'un des pivots est nul, alors le déterminant de la matrice est nul et celle-ci n'est pas inversible.

;Exemple

On part de la matrice
: <math>\mathrm{A} = \begin{pmatrix}
   2 & -1 & 0 \\
   0 & -1 & 2 \\
   -1 & 2 & -1
\end{pmatrix}</math>
Il s'agit d'une matrice réelle, donc le module d'un coefficient est sa valeur absolue.

On recherche le pivot dans la colonne 1 :
:<math>\begin{pmatrix}
   (2) & -1 & 0 \\
   0 & -1 & 2 \\
   -1 & 2 & -1
\end{pmatrix}</math>

On divise la ligne 1 par 2 de sorte que l'on obtienne un 1 sur la diagonale :
:<math>\begin{pmatrix}
   1 & -1/2 & 0 \\
   0 & -1 & 2 \\
   -1 & 2 & -1
\end{pmatrix}</math>

On modifie les lignes 2 et 3 par combinaisons linéaires avec la ligne 1 de sorte que l'on obtienne des zéros dans la première colonne (hors diagonale) :
:<math>\begin{pmatrix}
   1 & -1/2 & 0 \\
   0 & -1 & 2 \\
   0 & 3/2 & -1
\end{pmatrix}</math>

On recherche le pivot dans la colonne 2 :
:<math>\begin{pmatrix}
   1 & -1/2 & 0 \\
   0 & -1 & 2 \\
   0 & (3/2) & -1
\end{pmatrix}</math>

On échange les lignes 2 et 3 :
:<math>\begin{pmatrix}
   1 & -1/2 & 0 \\
   0 & (3/2) & -1 \\
   0 & -1 & 2
\end{pmatrix}</math>

On divise la ligne 2 par (3/2) de sorte que l'on obtienne 1 sur la diagonale :
:<math>\begin{pmatrix}
   1 & -1/2 & 0 \\
   0 & 1 & -2/3 \\
   0 & -1 & 2
\end{pmatrix}</math>

On modifie les lignes 1 et 3 par combinaisons linéaires avec la ligne 2 de sorte que l'on obtienne des zéros dans la deuxième colonne (hors diagonale) :
:<math>\begin{pmatrix}
   1 & 0 & -1/3 \\
   0 & 1 & -2/3 \\
   0 & 0 & 4/3
\end{pmatrix}</math>

On recherche le pivot dans la colonne 3 :
:<math>\begin{pmatrix}
   1 & 0 & -1/3 \\
   0 & 1 & -2/3 \\
   0 & 0 & (4/3)
\end{pmatrix}</math>

On divise la ligne 3 par (4/3) de sorte que l'on obtienne 1 sur la diagonale :
:<math>\begin{pmatrix}
   1 & 0 & -1/3 \\
   0 & 1 & -2/3 \\
   0 & 0 & 1
\end{pmatrix}</math>

On modifie les lignes 1 et 2 par combinaisons linéaires avec la ligne 3 de sorte que l'on obtienne des zéros dans la troisième colonne (hors diagonale), la matrice est alors :
:<math>\begin{pmatrix}
   1 & 0 & 0 \\
   0 & 1 & 0 \\
   0 & 0 & 1
\end{pmatrix}</math>
qui est réduite échelonnée.

Le déterminant de la matrice vaut donc <math>(-1)^1 \times 2 \times \frac32 \times \frac43=-4</math>.

== Notes ==
{{Références}}

== Références ==

*{{Article
 | prénom1 = Steven C.
 | nom1 = Althoen
 | prénom2 = Renate
 | nom2 = McLaughlin
 | titre = Gauss-Jordan Reduction: A Brief History
 | lien périodique = American Mathematical Monthly
 | revue = Amer. Math. Month.
 | volume = 94
 | année = 1987
 | pages = 130-142
}}.

*{{Ouvrage
 | prénom = Robert A.
 | nom = Beezer
 | url = http://linear.ups.edu/download/fcla-3.30-tablet.pdf
 | titre = A First Course in Linear Algebra
 | éditeur = University of Puget Sound
 | version = 3.30
 | année = 2014
}}.

*{{Ouvrage
 | prénom = Carl Friedrich
 | nom = Gauss
 | titre = Disquisitio de elementis ellipticis Palladis
 | année = 1810
}}.

*{{Ouvrage
 | prénom = Wilhelm
 | nom = Jordan
 | titre = Handbuch der Vermessungskunde
 | volume = 1
 | édition = 3e rév.
 | année = 1888
 | éditeur = Metzler
}}.

*{{Ouvrage
 |auteur=[[Joseph-Louis Lagrange]]
 | titre = Mélanges de Turin
 | année = 1759
}}.

== Articles connexes ==
* [[Théorème des facteurs invariants#Échelonnement des matrices à coefficients dans un anneau euclidien|Algorithme d'échelonnement dans un anneau euclidien]]
* [[Décomposition LU]]
* [[Décomposition QR]]
* [[Élimination de Fourier-Motzkin]], généralisation de la méthode aux systèmes d'inégalités linéaires
* [[Factorisation de Cholesky]]

== Lien externe ==
[http://www.math-linux.com/spip.php?article38 Méthode du pivot de Gauss] sur math-linux.com

{{Autres projets|wiktionary=élimination de Gauss-Jordan}} 

{{Palette|Gauss|Algèbre linéaire}}
{{Portail|algèbre|informatique théorique}}

[[Catégorie:Matrice]]
[[Catégorie:Analyse numérique matricielle]]
[[Catégorie:Carl Friedrich Gauss]]