Systèmes de Cramer/Pivot de Gauss
Introduction[modifier | modifier le wikicode]
La méthode du « pivot de Gauss », ou « élimination de Gauss-Jordan », est un algorithme efficace permettant de résoudre — lorsque c’est possible — un système d'équations linéaires. Contrairement à la méthode de Cramer, le pivot de Gauss ne requiert pas la connaissance des matrices (sauf pour sa démonstration) et donne même des solutions lorsque le système n’est pas de Cramer.
Numériquement, l'implémentation sur ordinateur de cet algorithme donne généralement de mauvais résultats (même s'il est rapide) : les erreurs d'arrondi se cumulent et faussent généralement la solution. Néanmoins, il n'utilise que des additions et multiplications, ce qui en fait le meilleur du point de vue du rapport simplicité/efficacité disponible en calcul manuel.
Présentation de l'algorithme & exemple[modifier | modifier le wikicode]
L'objectif du pivot de Gauss est de ramener le système d'équations linéaires à un système étagé (dont on sait qu’il est soluble), c'est-à-dire de la forme « triangulaire » suivante :
Il suffit en effet d’en déduire z avec la dernière ligne, de le remplacer par sa valeur dans la ligne au-dessus, d’en déduire y, de le remplacer par sa valeur dans la ligne au-dessus, d’en déduire x... et c’est fini ! La résolution est complètement machinale une fois que le système est mis sous cette forme.
Voyons maintenant comment s'y prendre :
Pour décrire l'algorithme, nous allons prendre un exemple, plutôt qu'une définition formelle :
- Étape 1 : choix du pivot : on choisit un « pivot », c'est-à-dire l'un des monômes du système. Le premier pivot est le premier monôme de la première ligne, le second est le second monôme de la seconde ligne, etc. On commence donc avec « x » pour pivot.
- Étape 2 : élimination : on soustrait aux lignes suivantes la ligne du pivot un nombre suffisant de fois pour que tous les termes en « x » (1er pivot), en « y » (2e pivot) etc. s'annulent. Dans notre exemple, la première étape :
Il faut soustraire 3 fois la première ligne (ligne du pivot) à la seconde, et 2 fois la première ligne à la troisième. Cela donne :
- Retour à l'étape 1 avec le pivot suivant.
- Fin de l'algorithme : l'algorithme se termine :
- lorsqu’il a atteint le n-ième coefficient de la n-ième ligne (le système admet une unique solution), ou
- lorsqu’il atteint un pivot nul. (Le système n'admet pas une unique solution.)
La suite des étapes donne (pivot : y) :
On en déduit z = 3, puis y = 2, puis x = 1. On vérifie que ce triplet est solution.
Remarques[modifier | modifier le wikicode]
|
Il y a un ordre précis dans le choix du pivot. |
La méthode du pivot de Gauss permet également de calculer le rang, l'inverse et le déterminant d'une matrice. Sa complexité est en , ce qui en fait un algorithme plus efficace que la méthode de Cramer, plus général que celle-ci. Néanmoins, il ne s'agit pas du « meilleur algorithme envisageable » : on pense qu'un tel algorithme atteindrait une complexité proche de . Nous avons évoqué plus haut la faible précision de cet algorithme — en réalité, dans certains contextes, il est possible d'obtenir une précision exacte — mais ce n’est pas avec des nombres réels !
Cette notion de complexité signifie que, si on tente de résoudre un système de n équations à n inconnues, il faut effectuer de l’ordre de n³ opérations. Dans notre exemple, n = 3 — il faut tout de même effectuer de l’ordre de 27 opérations.
Il existe une variante : une fois le système étagé, on repart à partir de la dernière ligne pour éliminer les termes en z, puis de l'avant dernière pour éliminer les termes en y etc. on aboutit ainsi à un système diagonal, dont les solutions sont immédiates. C’est ce qu’il faut faire lors du calcul de l'inverse d'une matrice.
