s La méthode du pivot de Gauss est une méthode pour transformer un système en

un autre système équivalent (ayant les mêmes solutions) qui est échelonné et est
donc facile à résoudre. Les opérations autorisées pour transformer ce système sont :
échange de deux lignes. multiplication d'une ligne par un nombre non nul.

Méthode de résolution de Gauss

1. changer l'ordre des équations ;
2. changer l'ordre des inconnues (dans toutes les équations à la fois) ;
3. multiplier une équation par un nombre non nul ;
4. conserver toutes les lignes sauf une et ajouter à cette dernière ligne une
combinaison des autres.

Élimination de Gauss-Jordan -
Définition
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 .

Calcul de l'inverse d'une matrice carrée par l'algorithme

de Gauss-Jordan
Inverser une matrice A carrée inversible d'ordre n, revient à résoudre
les n systèmes Af i = ei pour i allant de 1 à n. Pour cela, on crée
 un tableau à n lignes et 2n colonnes en bordant la matrice A par la matrice
identité In.

Ainsi, pour inverser la matrice A=(a i j) de format (n, n), on utilisera la matrice
augmentée suivante :

La transformation de Gauss-Jordan consiste à transformer ce système en un

système équivalent dont le bloc gauche est l'identité, c'est-à-dire qu'il faut
modifier la matrice (A | I) pour qu'elle devienne de la forme (I | A − 1) en
utilisant les propriétés de l'algorithme. On notera :

 la ligne i de la matrice A à l'itération k

 le scalaire a i j de la matrice A à l'itération k

L'algorithme de Gauss-Jordan est le suivant :

Pour k allant de 1 à n

Si il existe une ligne telle que

échanger cette ligne i et la ligne k :

Pour i allant de 1 à n et

Sinon A n'est pas inversible, abandonner (on sait ici que le rang de la
matrice est k − 1).

Après l'étape k de l'algorithme, la colonne k a tous ces coefficients nuls sauf

un : celui de la diagonale , qui vaut 1.

Variante : on peut aussi chercher le coefficient le plus grand (en

valeur absolue) avant d'échanger les lignes. Cela améliore la stabilité de
l'algorithme. De même on peut aussi faire des échanges sur les colonnes
pour trouver une coefficient plus grand, mais il faut garder la trace de ces
permutations.

Avec l'inverse de la matrice A, peut résoudre les équations de la

forme A.X = B, où B est un vecteur fixé, et X l'inconnue. Mais il existe aussi
une autre présentation.
Résolution d'un système d'équations linéaires par
l'algorithme de Gauss-Jordan
On veut résoudre un système d'équations A.X = B, où B est un vecteur fixé,
et X le vesteur 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
Soit le système d'équations suivant :

On établit la matrice correspondante et on applique la première étape de

Gauss-Jordan, le pivot est 1 :

On ajoute un multiple de la première ligne aux deux autres lignes pour

obtenir des zéros (respectivement et ); le nouveau pivot
est ensuite 5 :

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

On ajoute cette deuxième ligne à la troisième et à la première, le nouveau

pivot est -7 :
On divise la 3ème ligne par -7 :

On utilise la 3ème 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 dans
l'autre :

La solution du système est ainsi :

Déterminant
Cet algorithme permet aussi de calculer le déterminant d'une matrice : dans
l'algorithme ci-dessus, c'est le produit des " " 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 sont rang.

Qu'est ce que la méthode du pivot de Gauss ?

L'algorithme d'élimination gaussienne (appellée méthode du pivot de Gauss ou
Gauss-Jordan) permet de trouver les solutions d'un système d'équations linéaires,
et de déterminer l'inverse d'une matrice.
L'algorithme travaille sur les lignes de la matrice, en échangeant ou multipliant les
lignes entre elles (à un facteur près).
A chaque étape, l'algorithme a pour but d'introduire dans la matrice, sur les
éléments en dehors de la diagonale, des valeurs nulles.
Comment calculer les solutions d'un système d'équations
linéaires avec Gauss ?
 A partir d'un système d'équations linéaires, la première étape est de convertir les

Exemple :⎧⎪⎨⎪⎩x−y+2z=53x+2y+z=102x−3y−2z=−10{𝑥−𝑦+2𝑧=53𝑥+2
équations en une matrice.

𝑦+𝑧=102𝑥−3𝑦−2𝑧=−10peut s'écrire sous forme

de multiplication matricielle :⎛⎜⎝1−123212−3−2⎞⎟⎠.⎛⎜⎝xyz⎞⎟⎠=⎛⎜⎝510−1

augmentée)⎛⎜
0⎞⎟⎠(1−123212−3−2).(𝑥𝑦𝑧)=(510−10)ce qui correspond à la matrice (appelée

⎜⎝1−125321102−3−2−10⎞⎟

⎟⎠(1−125321102−3−2−10)
Puis, pour chaque élément en dehors de la diagonale non nul, réaliser un calcul
adéquat en additionnant ou soustrayant les autres lignes afin que l'élément devienne
0.

1 soit nul :⎛⎜

Exemple : Soustraire 3 fois (Ligne 1) à (Ligne 2) pour que l'élément ligne 2, colonne

⎜⎝1−12505−5−52−3−2−10⎞⎟
⎟⎠(1−12505−5−52−3−2−10)

nul :⎛⎜
Soustraire 2 fois (Ligne 1) à (Ligne 3) pour que l'élément ligne 3, colonne 1 soit

⎜⎝1−12505−5−50−1−6−20⎞⎟
⎟⎠(1−12505−5−50−1−6−20)

nul :⎛⎜
Soustraire 1/5 fois (Ligne 2) à (Ligne 3) pour que l'élément ligne 3, colonne 2 soit

⎜⎝1−12505−5−500−7−21⎞⎟
⎟⎠(1−12505−5−500−7−21)

nul :⎛⎜
Soustraire 1/5 fois (Ligne 2) à (Ligne 1) pour que l'élément ligne 1, colonne 2 soit

⎜⎝101405−5−500−7−21⎞⎟
⎟⎠(101405−5−500−7−21)

nul :⎛⎜
Soustraire 1/7 fois (Ligne 3) à (Ligne 1) pour que l'élément ligne 1, colonne 3 soit

⎜⎝100105−5−500−7−21⎞⎟
⎟⎠(100105−5−500−7−21)

nul :⎛⎜
Soustraire 5/7 fois (Ligne 3) à (Ligne 2) pour que l'élément ligne 2, colonne 3 soit

⎜⎝10010501000−7−21⎞⎟
⎟⎠(10010501000−7−21)

Exemple :⎛⎜
Simplifier les lignes en divisant par la valeur de la diagonale

⎜⎝100101020013⎞⎟
⎟⎠(100101020013)
Le vecteur résultat est la dernière colonne.
Exemple : 1,2,31,2,3 correspondant respectivement
à x,y,z𝑥,𝑦,𝑧 soit x=1,y=2,z=3𝑥=1,𝑦=2,𝑧=3
POSER UNE NOUVELLE QUESTION
Code source
dCode se réserve la propriété du code source pour "Elimination de Gauss (Pivot)".
Sauf code licence open source explicite (indiqué Creative Commons / gratuit),
l'algorithme pour "Elimination de Gauss (Pivot)", l'applet ou snippet (convertisseur,
solveur, chiffrement / déchiffrement, encodage / décodage, encryptage / décryptage,
 traducteur) ou les fonctions liées à "Elimination de Gauss (Pivot)" (calculer, convertir,
résoudre, décrypter / encrypter, déchiffrer / chiffrer, décoder / encoder, traduire)
codés en langage informatique (Python, Java, C#, PHP, Javascript, Matlab, etc.) ou les
données, en téléchargement, script, ou les accès API à "Elimination de Gauss (Pivot)"
ne sont pas publics, idem pour un usage hors ligne, PC, mobile, tablette, appli iPhone
ou Android !
Rappel : dCode est gratuit.

Citation
Le copier-coller de la page "Elimination de Gauss (Pivot)" ou de ses résultats est
autorisée (même pour un usage commercial) tant que vous citez dCode !
L'exportation des résultats sous forme de fichier .csv ou .txt est gratuite en cliquant
sur l'icone export
Citer comme source bibliographique :
Elimination de Gauss (Pivot) sur [Link] [site web en ligne], consulté le
04/05/2024, [Link]
Besoin d'Aide ?
Rendez-vous sur notre communauté Discord dCode pour participer au forum
d'entraide !
PS : Pour les messages codés, testez notre détecteur de chiffrement !

Questions / Commentaires
ENVOYER UN MESSAGE
Remarques et suggestions sont les bienvenues afin que dCode propose le meilleur
outil 'Elimination de Gauss (Pivot)' gratuit ! Merci !

Menu
 Calcul par Elimination Gaussienne (avec Pivot)
 Convertisseur de système d'équation en matrice
 Qu'est ce que la méthode du pivot de Gauss ?
 Comment calculer les solutions d'un système d'équations linéaires avec Gauss ?

Pages similaires
 Solveur d'Equation
 Matrice Echelonnée
 Intégrale Triple
 Multiplication à Inconnue(s)
 Dual Booléen
 Racine Cubique
 Calculs avec des Fractions
 LISTE DES OUTILS DCODE

Faire un don
 Paypal
 Amazon
 Autre

Forum/Aide

Mots-clés
elimination, pivot, gauss, jordan, matrice, systeme, equation
 Liens
 Contact
 A propos
 Application
 Prise2Tete
 Wikipedia

Élimination de Gauss-Jordan
11 langues
 Article
 Discussion
 Lire
 Modifier
 Modifier le code
 Voir l’historique
Outils

















Pour les articles homonymes, voir Pivot.

En mathématiques, plus précisément en algèbre linéaire, l'élimination de
Gauss-Jordan, aussi appelée méthode du pivot de Gauss, nommée en
hommage à Carl Friedrich Gauss et Wilhelm Jordan, est un algorithme 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 à une matrice, on obtient
sa forme échelonnée réduite.
Histoire[modifier | modifier le code]
Cette méthode est connue des mathématiciens chinois depuis au moins
le I siècle de notre ère. Elle est référencée dans le livre chinois Jiuzhang
er

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 II siècle avant notre ère.
e

En Europe, cette méthode a été découverte et présentée sous forme

moderne au XIX siècle. En 1810, Carl Friedrich Gauss présente sa méthode
e

des moindres carrés dans un livre étudiant le mouvement de

l'astéroïde Pallas1. 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 publie un livre
de géodésie précisant comment utiliser cette méthode et adoptant une
notation un peu différente2. C'est grâce à ce dernier livre que cette méthode
se diffusa dans tout l'Occident3. Elle est aujourd'hui connue sous le nom
d'élimination de Gauss-Jordan ou méthode du pivot de Gauss.
Algorithme[modifier | modifier le code]
Opérations[modifier | modifier le code]
L'algorithme de Gauss-Jordan produit la matrice é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 × m ;
L'algorithme de Gauss-Jordan est le suivant4 :
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
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) :

o é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,
o étape 1.2.1 : r = 1,
o étape 1.2.2 : r = k, il n'y a pas d'échange,
o étape 1.2.3 : on divise la ligne 1 par A(1, 1) = 2, soit ,
o étape 1.2.4 :
 ligne i = 2, on a A(2, 1) = -1 ; on calcule
,
 ligne i = 3, on a A(3, 1) = 0, la ligne n'est donc pas modifiée,
o la matrice est alors
;
 deuxième itération, j = 2 (et r = 1) :
o é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),
o étape 2.2.1 : r = 2,
o étape 2.2.2 : r = k, il n'y a pas d'échange.
o étape 2.2.3 : on divise la ligne 2 par A'(2, 2) = 3/2, soit ,
o étape 2.2.4 :
 ligne i = 1, on a A'(1, 2) = -1/2 ; on calcule
,
 ligne i = 3, on a A'(3, 2) = -1 ; on calcule
,
o la matrice est alors
;
 troisième itération, j = 3 (et r = 2) :
o étape 3.1 : le pivot de la troisième colonne, troisième ligne est 4/3.
Donc k = 3
o étape 3.2.1 : r = k,
o étape 3.2.2 : il n'y a aucune ligne à permuter,
o étape 3.2.3 : on divise la ligne 3 par A''(3, 3) = 4/3, elle devient
o étape 3.2.4 :
  ligne i = 1, on a A''(1, 3) = -1/3. La dernière étape annule ce
coefficient.
 ligne i = 2, on a A''(2, 3) = -2/3. La dernière étape annule ce
coefficient.
o la matrice est alors
qui est réduite échelonné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-exemples5.
Complexité algorithmique[modifier | modifier le code]
La complexité algorithmique asymptotique de l'élimination de Gauss
est O(n3) (notations de Landau) : n×n est la taille de la matrice et le
nombre d'instructions à réaliser est proportionnel à n3. Cet algorithme peut
être utilisé sur un ordinateur pour des systèmes avec des milliers
d'inconnues et d'équations[réf. 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. 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[modifier | modifier le code]
L'élimination de Gauss-Jordan peut être utilisée pour inverser
une matrice carrée si celle-ci 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, on applique l'algorithme de Gauss-Jordan
à la matrice augmentée. La matrice finale est de la forme [ I | A−1 ] et
contient l'inverse de la matrice initiale dans sa section de droite.
Exemple[modifier | modifier le code]
Admettons la matrice suivante:
Pour trouver l'inverse de cette matrice, il faut générer la matrice
augmentée [ A | I ] comme suit:
En appliquant l'algorithme de Gauss-Jordan, on obtient la matrice
augmentée sous sa forme échelonnée réduite suivante:
[afficher]
 Démonstration

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[modifier | modifier le code]
Effectuer une opération élémentaire O sur les n lignes d'une
matrice revient à la multiplier à gauche par la matrice
élémentaire (inversible) Gs := O(In).
En notant O1, …, Os les opérations élémentaires que l'on
effectue sur A, et Gs = Os(In) les matrices élémentaires
associées, on aboutit donc, dans la section de gauche, à la
matrice
et dans celle de droite, à la matrice
Ainsi, B est inversible et BA = In, donc B−1 = A et A−1 = B.
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 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 ) et ont pour indice de colonnes k1,
…, kr , 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 ki 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 ki, et
en déterminant les coefficients situés aux lignes d'indice ki 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.
[afficher]
Exemple 1 (détaillé)

[afficher]
Exemple 2

[afficher]
Exemple 3

Déterminant[modifier | modifier le code]

Cette section a besoin d'être recyclée (novembre 2014).
Une réorganisation et une clarification du contenu sont
nécessaires. Améliorez-le ou discutez des points à améliorer.
Cet algorithme permet également de calculer le déterminant
d'une matrice :
avec p le nombre de permutations de lignes, et 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
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 :
On divise la ligne 1 par 2 de sorte que l'on obtienne un 1
sur la diagonale :
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) :
On recherche le pivot dans la colonne 2 :
On échange les lignes 2 et 3 :
On divise la ligne 2 par (3/2) de sorte que
l'on obtienne 1 sur la diagonale :
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) :
On recherche le pivot dans la
colonne 3 :
On divise la ligne 3 par (4/3)
de sorte que l'on obtienne 1
sur la diagonale :
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 :
qui est réduite
échelonnée.
Le déterminant de la
matrice vaut donc .