méthode de Gauss

Imaginez trois équations empilées, chacune contenant les mêmes inconnues. Le geste de Gauss consiste à combiner les lignes pour faire disparaître une inconnue, puis une autre. Le tableau de nombres prend alors une forme d'escalier : la dernière ligne ne contient plus qu'une inconnue.

On résout cette dernière ligne, puis on remonte. Les transformations changent l'écriture du système, mais pas ses solutions : c'est ce qui autorise à simplifier sans perdre la réponse cherchée.

La méthode de Gauss est un algorithme d'élimination appliqué à un système d'équations linéaires, généralement représenté par sa matrice augmentée. Elle remplace successivement une ligne par sa somme avec un multiple d'une autre ligne, échange deux lignes ou multiplie une ligne par un scalaire non nul. Chacune de ces opérations conserve exactement l'ensemble des solutions.

À chaque colonne utile, on choisit un coefficient non nul appelé pivot. On annule les coefficients placés sous ce pivot, puis on recommence sur la sous-matrice restante. Le résultat est une matrice échelonnée, ou un système triangulaire lorsqu'il y a autant d'équations indépendantes que d'inconnues. La substitution régressive détermine alors les inconnues de la dernière à la première.

Il n'est pas nécessaire de diviser chaque ligne par son pivot : cette normalisation est facultative pour l'élimination de Gauss. Si l'on poursuit jusqu'à annuler aussi les coefficients au-dessus des pivots et à rendre chaque pivot égal à 1, on obtient la variante de Gauss-Jordan.

Écrivez le système sous forme de matrice augmentée. Dans la première colonne encore active, choisissez un pivot non nul ; si nécessaire, échangez deux lignes. Ajoutez aux lignes inférieures un multiple de la ligne du pivot afin d'annuler leurs coefficients dans cette colonne. Répétez sur la sous-matrice restante jusqu'à obtenir une forme échelonnée. Le processus s'arrête lorsque chaque ligne non nulle possède un pivot plus à droite que celui de la ligne précédente. Examinez alors la forme obtenue : une ligne contradictoire rend le système incompatible ; sinon, introduisez des paramètres pour les inconnues libres lorsqu'il y en a, puis déterminez les inconnues pivots par substitution régressive.

La méthode s'applique à un nombre fini d'équations linéaires dont les coefficients appartiennent à un corps, par exemple les nombres réels ou rationnels. Il faut pouvoir additionner les lignes, les multiplier par un scalaire et diviser uniquement par un pivot non nul. Un coefficient nul à la place prévue n'est pas un échec si une ligne inférieure fournit un pivot : on échange alors les deux lignes.

Si toute la colonne active est nulle sous la zone déjà traitée, aucun pivot n'existe dans cette colonne ; on passe à la suivante. Une ligne de la forme $0x+0y+0z=c0x+0y+0z=c$, avec un nombre c non nul, révèle un système sans solution. Une ligne entièrement nulle ne suffit pas, à elle seule, à signaler des inconnues libres : celles-ci apparaissent lorsque le nombre de pivots est inférieur au nombre d'inconnues.

Résolvons un système de trois équations, dont les inconnues sont les nombres x, y et z :Les données sont donc les neuf coefficients des inconnues et les trois nombres du second membre : 8, −11 et −3.

1. Élimination de x.
On remplace la deuxième ligne par deux fois cette ligne plus trois fois la première. On remplace la troisième ligne par sa somme avec la première :Le système obtenu a pour deux dernières équations $y+z=2y+z=2$ et $2y+z=52y+z=5$.

2. Élimination de y.
On remplace la troisième ligne par elle-même moins deux fois la deuxième :La dernière équation devient $-z=1-z=1$. La figure récapitule les trois matrices augmentées et les deux étapes d'élimination.

3. Remontée.
La dernière ligne donne $z=-1z=-1$. Puis $y+z=2y+z=2$ donne $y=3y=3$, et la première équation donne $x=2x=2$. Le triplet solution est donc $(x,y,z)=(2,3,-1)(x,y,z)=(2,3,-1)$. En le remplaçant dans les trois équations initiales, on retrouve respectivement 8, −11 et −3 : le contrôle est exact.

Pour résoudre à la main un petit système, la forme échelonnée rend visibles les inconnues déjà éliminées. Quand les coefficients sont entiers, choisir des combinaisons qui évitent les fractions réduit les erreurs de calcul.

Dans un calcul numérique, on échange souvent la ligne du pivot avec celle qui possède le plus grand coefficient en valeur absolue dans la colonne active. Ce pivot partiel limite l'amplification des erreurs d'arrondi.

Pour plusieurs seconds membres associés à la même matrice, une factorisation adaptée réutilise le travail d'élimination. Pour une grande matrice très creuse, une méthode itérative peut être préférable si le remplissage créé par Gauss devient coûteux.

Élimination de Gauss et Gauss-Jordan. La première s'arrête à une forme échelonnée puis remonte par substitution. Gauss-Jordan continue jusqu'à une forme échelonnée réduite : chaque pivot vaut 1 et demeure le seul coefficient non nul de sa colonne.

Élimination directe et méthode de Seidel. Gauss transforme le système par un nombre fini d'opérations exactes en arithmétique exacte. La méthode de Seidel construit des approximations successives et exige un critère de convergence ; elle est distincte malgré le nom fréquent « Gauss-Seidel ».

Résoudre un système et calculer une matrice inverse. Gauss peut servir aux deux tâches, mais elles ne se confondent pas. Pour un seul second membre, résoudre directement évite de construire toute la matrice inverse.

Pivot nul. Diviser par zéro est impossible. Si un coefficient non nul se trouve plus bas dans la colonne, il faut permuter les lignes ; si toute la partie disponible de la colonne est nulle, il faut chercher le pivot dans une colonne suivante.

Système singulier. Une ligne finale $0=10=1$ rend les équations incompatibles. Une ligne $0=00=0$ ne suffit pas, à elle seule, à conclure : il faut comparer le nombre de pivots au nombre d'inconnues pour repérer les variables libres.

Pivot très petit en calcul flottant. Un pivot non nul mais proche de zéro peut produire de grands multiplicateurs et amplifier les arrondis. Le pivot partiel choisit dans la colonne active le coefficient de plus grande valeur absolue ; un problème mal conditionné peut toutefois rester sensible.

Coût et remplissage. Pour une matrice dense carrée de taille n, l'élimination demande un nombre d'opérations proportionnel à $n^{3}n^3$. Sur une très grande matrice creuse, des coefficients nuls peuvent devenir non nuls ; une méthode exploitant la structure ou une méthode itérative peut alors mieux convenir.

La matrice échelonnée formalise la forme d'arrivée de l'élimination et permet de lire les pivots, le rang et les inconnues libres.

La matrice inverse montre une autre application des opérations sur les lignes : réduire une matrice inversible tout en appliquant les mêmes transformations à la matrice identité.

La méthode de Seidel ouvre sur les méthodes itératives, qui remplacent la triangularisation directe par une suite d'approximations lorsque leurs conditions de convergence sont satisfaites.