Élimination de Gauss

Choisissez pour chaque colonne la ligne qui servira de pivot. Observez ensuite le processus d'élimination à l'œuvre. Dans la deuxième configuration, votre choix détermine la réponse : prenez le nombre minuscule pour pivot et x vaudra 0 au lieu de 1.

Exemple résolu — Élimination de Gauss

Déterminant	-1
Résidu	8,8818 × 10⁻¹⁶

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

La théorie — Élimination de Gauss276 mots

L'élimination transforme un système en un système triangulaire équivalent, que vous pouvez ensuite résoudre par remontée. Son importance ne vient pas du fait qu'elle fonctionne, puisque d'autres méthodes y parviennent également. L'enjeu véritable est ce qu'elle coûte. C'est ce critère qui détermine la méthode qu'une machine exécutera en pratique.

Ce que signifie chaque symbole

n: le nombre d'inconnues. C'est l'unique paramètre dont dépend le coût.
pivot: le coefficient par lequel vous divisez une ligne. L'ordre imposé par l'algorithme dispense la procédure de toute prise de décision. La valeur qui s'y trouve est ce qui garantit sa stabilité en virgule flottante.

Suppose: Un système plein sans structure exploitable. Les systèmes creux, à bande ou symétriques sont moins coûteux. Le choix de la méthode spécialisée adéquate constitue d'ailleurs l'essentiel de l'algèbre linéaire numérique.
Ne tient plus quand: Le coût est cubique. Et cette croissance cubique dresse un mur. L'élimination sur n inconnues prend environ n³/3 multiplications et tout autant d'additions. Si vous les comptez sur une élimination réelle, vous trouvez 333 300 multiplications à n = 100, contre les 333 333 de l'estimation. Cet exposant vous inflige une pénalité de croissance fixe. Doubler les inconnues multiplie le travail par exactement 8. Dès lors, 100 inconnues exigent 333 300 multiplications et 200 en requièrent 2 666 600. Une machine capable d'éliminer mille inconnues en une seconde a donc besoin de huit secondes pour deux mille, et d'environ deux heures et quart pour vingt mille. Voilà la forme de ce mur. C'est pourquoi la véritable question en algèbre linéaire numérique n'est presque jamais de savoir comment résoudre un système plein, mais plutôt comment éviter d'en avoir un.

Deux opérations invariables dans un ordre sans équivoque 🖖

Deux équations réclamaient une seule opération : soustraire un multiple d'une ligne à une autre. Trois équations nécessitent cette même manipulation plus une étape supplémentaire, et la liste des tâches indique les deux. Il s'agit d'une permutation pour placer un nombre exploitable dans le pivot, suivie d'une élimination. L'ordre est immuable : annulez la première colonne, puis la deuxième. Lisez ensuite la solution sur la dernière ligne et remontez le système. Suivez cette méthode et vous n'aurez plus jamais besoin d'astuce pour savoir quelle équation attaquer. C'est toute la différence entre un casse-tête et une procédure. C'est aussi pour cela que l'approche passe à l'échelle : la même routine appliquée à mille inconnues fait encore tourner tous les logiciels d'ingénierie du monde, soixante ans après qu'on lui a donné un nom.

Le déterminant est le produit des pivots 🖖

Observez les pivots pendant l'élimination et multipliez-les entre eux. Changez ensuite le signe une fois pour chaque permutation de ligne. Vous obtenez le déterminant, un résultat qui découle naturellement du travail que vous faisiez déjà. La plupart des gens découvrent plutôt les déterminants par le développement en cofacteurs. Il est pourtant utile de comprendre pourquoi personne ne les calcule ainsi. Les cofacteurs coûtent environ n! opérations, contre n³ pour l'élimination. Sur un système 20 × 20, cela représente 2 × 10¹⁸ contre 8 000. C'est ce facteur de 10¹⁴ qui décide laquelle des deux approches on peut raisonnablement confier à une machine. La formule que l'on enseigne en premier à tout le monde est celle qu'aucune machine n'a jamais utilisée.

Un choix dans la procédure change tout le résultat 🖖

Cliquez sur Sans pivotement. Le coefficient principal vaut 10⁻¹⁷, l'algorithme divise consciencieusement par cette valeur, et la réponse pour x est 0 alors que la vraie solution est 1. Tout fonctionne normalement et aucune règle n'a été violée. La division par un nombre minuscule multiplie l'erreur d'arrondi déjà présente. Au moment d'atteindre le sommet de la phase de remontée, cette erreur a complètement dévoré le résultat. Il s'agit d'un précipice, et non d'une pente : en abaissant ce coefficient, 10⁻¹² livre encore quatre chiffres exacts et 10⁻¹⁵ en donne trois, puis 10⁻¹⁶ renvoie 2,22 et 10⁻¹⁷ renvoie 0. La limite se situe à l'epsilon machine, l'écart entre 1 et le nombre suivant qu'un type double peut représenter. Cochez la case et l'algorithme divise plutôt par le plus grand nombre disponible, ce qui permet à chacun de ces cas de se résoudre exactement. C'est pourquoi la carte des résidus figure sur cette page : elle réinjecte le résultat dans les équations initiales, et constitue l'unique moyen de différencier une solution véritable d'une réponse en apparence certaine.

Problèmes entièrement résolus

Résolution de 2x + y − z = 8 et le coût en précision 7 étapes
Résolvez 2x + y − z = 8, −3x − y + 2z = −11, −2x + y + 2z = −3, puis déterminez ce que l'élimination vous a coûté en précision.
1. Écrivez ceci sous la forme d'une matrice augmentée. Les lettres ne jouent aucun rôle, alors omettez-les et conservez les colonnes.
  
  $2 - 3 - 2 1 - 1 1 - 1 22 8 - 11 - 3$
2. Choisissez comme pivot le plus grand élément de la première colonne, soit −3 dans la deuxième ligne, et remontez-le. Chaque permutation de ligne inverse le signe du déterminant, il faut donc les compter.
  
  $R_{1} \leftrightarrow R_{2} (∣ - 3∣ > ∣2∣)$
3. Annulez le reste de la première colonne en soustrayant des multiples de la ligne du pivot.
  
  $R_{2} \to R_{2} - \frac{2}{- 3} R_{1}, R_{3} \to R_{3} - \frac{- 2}{- 3} R_{1}$
4. Répétez l'opération sur la deuxième colonne, puis lisez la ligne du bas. Elle contient une seule inconnue et sa valeur.
  
  $R_{2} \leftrightarrow R_{3} (\frac{5}{3} > \frac{1}{3}) \Rightarrow \frac{1}{5} z = - \frac{1}{5}$
5. Procédez à la substitution en remontant. La dernière ligne vous donne z. La ligne centrale donne ensuite y, et celle du haut donne x.
  
  $z = - 1, y = 3, x = 2$
6. Multipliez les pivots et appliquez le changement de signe pour deux permutations afin d'obtenir le déterminant. Vérifiez la réponse en remplaçant les valeurs dans les équations de départ plutôt que dans le système réduit.
  
  $det = (- 3) (\frac{5}{3}) (\frac{1}{5}) (- 1)^{2} = - 1$
7. Le résidu vaut environ 10⁻¹⁶, ce qui n'est pas zéro. C'est l'ordre de grandeur des arrondis qu'un ordinateur ne peut pas éviter, et c'est ce qu'il est honnête de signaler. Une réponse qui se prétend exacte résulte soit d'une arithmétique entière, soit d'un manque de vérification. Changez le coefficient principal pour 10⁻¹⁷ en désactivant le pivotement. Ce même résidu devient alors 1, ce qui constitue une alarme criante.
  
  $i max ∣ A_{i} x - b_{i} ∣ \approx 9 \times 1 0^{- 16}$
Réponse

x = 2, y = 3, z = −1, déterminant −1. Ce résidu d'environ 10⁻¹⁶ indique que l'arithmétique est aussi exacte que l'autorise la virgule flottante. Désactivez le pivotement sur un système mal conditionné, et c'est ce nombre qui vous alertera que la réponse est fausse.
Un déterminant de 0, deux fois, avec deux sens différents 7 étapes
Ce préréglage n'a aucune solution et le suivant en a une infinité, et tous deux affichent un déterminant de 0. Trouvez ce qui les sépare vraiment, puis décidez ce que changer le second membre pourrait jamais vous apporter.
1. Le pivot partiel cherche dans la première colonne le plus grand coefficient. Il y trouve 3 dans la dernière ligne : le premier mouvement est donc un échange.
  
  $123121122375 R_{1} \leftrightarrow R_{3} 321121221573 (∣3∣ > ∣2∣ > ∣1∣)$
2. Videz la colonne : retranchez ⅔ de la nouvelle première ligne à la deuxième, et ⅓ de cette même ligne à la troisième.
  
  $R_{2} \to R_{2} - \frac{2}{3} R_{1}, R_{3} \to R_{3} - \frac{1}{3} R_{1} : 300 1 \frac{4}{3} \frac{2}{3} 2 \frac{2}{3} \frac{1}{3} 5 \frac{11}{3} \frac{4}{3}$
3. Dans la deuxième colonne, 4/3 se trouve déjà au-dessus de 2/3, il n'y a donc rien à échanger. Retranchez la moitié de la ligne 2 à la ligne 3.
  
  $R_{3} \to R_{3} - \frac{1}{2} R_{2} : 300 1 \frac{4}{3} 0 2 \frac{2}{3} 0 5 \frac{11}{3} - \frac{1}{2}$
4. La ligne 3 est maintenant vide à gauche et porte −½ à droite, ce qui se lit 0 = −½. Deux pivots seulement ont été posés, 3 et 4/3, là où trois inconnues en réclament trois, et un pivot manquant annule le produit.
  
  $pivots 3, \frac{4}{3} — two, not three ⟹ det A = 0, last row: 0 = - \frac{1}{2}$
5. Le rang est ce que le déterminant dissimule. La matrice des coefficients a deux lignes indépendantes. La matrice augmentée en a trois, parce que ce −½ résiduel est une ligne que rien ne peut annuler. Rang 2 contre rang 3, voilà ce que veut dire « aucune solution ».
  
  $rank A = 2 < rank [A ∣ b] = 3 ⟹ no solution$
6. Le préréglage Une équation trois fois fait la même arithmétique et dit autre chose. Chaque ligne est un multiple de la première, donc les deux rangs valent 1 et le déterminant vaut de nouveau 0. L'ensemble des solutions a 3 − 1 = 2 directions libres : le plan x + y + z = 3 tout entier. L'outil dit « une infinité » sans dire dans combien de directions.
  
  $Infinitely many: rank A = rank [A ∣ b] = 1, det A = 0, dim = 3 - 1 = 2 (x + y + z = 3)$
7. Changez un nombre et regardez quelle grandeur bouge. Mettez 6 à la place du 7 au second membre de la ligne 2. La matrice des coefficients reste intacte, donc le déterminant ne bronche pas, mais le rang de la matrice augmentée tombe à 2 et la réponse devient une droite de solutions au lieu de rien.
  
  $b_{2} = 7 \to 6 : rank [A ∣ b] = 2 = rank A ⟹ dim = 3 - 2 = 1$
Réponse

Le déterminant indique seulement si la matrice des coefficients possède un jeu complet de pivots. Le second membre n'y entre jamais, et c'est pourquoi il ne peut pas séparer les deux préréglages là où les deux rangs le peuvent : aucune solution quand ils diffèrent, et un ensemble de solutions de dimension 3 − rang quand ils coïncident. Une fois le déterminant à 0, aucun second membre ne vous achètera une réponse unique ; vous en obtiendrez zéro ou toute une famille, et le choix entre ces deux cas est tout ce que b décide. La fiche du résidu s'éteint pour la raison même de son existence : un résidu réclame une solution à réinjecter dans les équations.

$dim = n - rank A when rank [A ∣ b] = rank A; det A = 0 ⟹ no b gives exactly one$

Parcours

Trouver x, à partir du signe moins

Références (1)

Two centuries of the method being reinvented and misattributed, including how Gauss's name came to be on it: J. F. Grcar, "How ordinary elimination became Gaussian elimination." Historia Mathematica 38:2 (2011), 163–218.

Par l’équipe 42Math · Mis à jour 2026-08-26

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Mathématiques →

Exemples de problèmes

Système qui se résout - Deux échanges et trois éliminations donnent x = 2, y = 3, z = −1. Le résidu avoisine 10⁻¹⁶. C'est l'arithmétique poussée à la limite de précision d'un ordinateur.
Sans pivot - Le premier coefficient est 10⁻¹⁷. L'algorithme divise par cette valeur puisque le pivot est désactivé. Le résultat affiche x = 0 au lieu de 1, avec un résidu de 1 au lieu de 0. Cochez la case. Le même système se résout alors exactement.
Une équation trois fois - Chaque ligne est un multiple de la première. Après élimination, deux lignes s'annulent complètement. Le déterminant vaut 0 et le système ne fixe plus un point : il fixe un plan.
Contradictoire - La deuxième ligne contredit la première : le membre de gauche est identique mais celui de droite diffère. L'élimination aboutit à 0 = 1. Aucune arithmétique ne pourra sauver cela.