Méthode de Gauss pour les systèmes d’équations linéaires

L’algorithme de Gauss permet de résoudre un système d’équations linéaires. Chaque étape nous permet d’obtenir, à l’aide d’opérations élémentaires sur les équations, un système linéaire équivalent au système initial. Les opérations autorisées sont :

ajouter à une équation une combinaison linéaire des autres
permuter les équations
multiplier ou diviser une équation par une constante non nulle.

On cherche, en utilisant ces opérations, à obtenir un système échelonné que l’on saura résoudre aisément. Pour expliquer ce que veut dire échelonner un système et comment le résoudre, le plus simple est de commencer par un exemple.
Considérons le système dont les inconnues sont x, y, z, t et où a, b sont des paramètres fixés.

( | x + 2y + z - t = a (E1 ) |{ 2x + 4y - z - 5t = 5a (E2 ) S ||( - x - 2y + z + 3t = b (E3 )

Choisissons une équation avec un coefficient non nul pour la première inconnue . Ici la première équation convient avec le coefficient 1, pour , qu’on appelle le premier pivot. On va utiliser ce pivot de notre algorithme pour faire disparaître l’inconnue des autres équations. On obtient un système linéaire équivalent :

( ′ ||{ x + 2y + z - t = a (E 1)′ = (E1 ) S ′ - 3z - 3t = 3a (E 2) = (E2 ) - 2 (E1 ) || + 2z + 2t = b + a (E ′3) = (E3 ) + (E1 ) (

Laissons de côté la première équation que l’on utilisera à la fin pour calculer . On remarque que dans les deux dernières équations la variable suivante n’apparaît pas. On est ramené à un système de deux équations avec ici deux variables en moins. Choisissons notre deuxième pivot. On le trouve dans l’équation (E ′2) . C’est le coefficient de . Nous allons l’utiliser pour éliminer des équations suivantes (ici, il n’en reste qu’une). Réécrivons notre nouveau système :

( || x + 2y + z - t = a (E ′1′) = (E ′1) |{ - 3z - 3t = 3a (E ′2′) = (E ′2) S ′′ 2 ′ ||| 0 = b + 3a (E ′3′) = (E ′3) + --(E2) ( 3

Remarques

La deuxième équation permettra de calculer . On remarque que dans la troisième équation la variable suivante n’apparaît pas.
Le système obtenu a la forme d’un escalier, avec deux grandes marches. On dit qu’on a échelonné le système.

Le système S′′ a des solutions si et seulement si les paramètres et vérifient 0 = b+ 3a ′′
(E 3) .
Quand ce système a des solutions (si b + 3a = 0 ), on détermine les solutions en remontant. Chaque marche permet de calculer une des lettres (on choisit celle qui est au coin de la marche) en fonction des lettres suivantes.
Ainsi, on peut trouver puis en fonction des variables libres (celles qui se trouvent sur le plat des marches) et . On obtient

z = - a - t

Puis,

x = 2a - 2y + 2t

L’ensemble des solutions peut s’écrire :

{(2a - 2y + 2t, y, - a - t, t) | y ∈ ℝ, t ∈ ℝ, }

Remarque : On peut écrire les composantes des solutions dans la base canonique de sous la forme :

( ) ( ) ( ) ( ) ( ) x 2a - 2y + 2t 2a - 2 2 | y | | y | | 0 | | 1 | | 0 | || z || = || - a - t || = || - a|| + y || 0 || + t || - 1|| |( |) |( |) |( |) |( |) |( |) t t 0 0 1

L’ensemble des solutions peut donc s’écrire

( ) ( ) ( ) | 2a| | - 2| | 2 | | 0 | | 1 | | 0 | || - a|| + Vect (|| 0 || , || - 1|| ). ( 0 ) ( 0 ) ( 1 )

Les solutions forment un espace affine de dimension . C’est le translaté du sous espace vectoriel :

( ) ( ) | - 2| | 2 | | 1 | | 0 | Vect (|| 0 || , || - 1|| ). ( 0 ) ( 1 )

Avec cet exemple on peut comprendre facilement le fonctionnement de l’algorithme pour un système quelconque d’équations.

On cherche un pivot, premier coefficient non nul d’une certaine variable dans une des équations. Par permutation, cette équation devient la première équation.
On utilise ce pivot et cette équation pour éliminer des équations suivantes.
S’il y a des équations dont le premier membre est nul on les place en dernier.
On recommence à l’étape 1 avec le système privé de la première équation.

L’algorithme s’arrête lorsqu’il ne reste plus que des équations 0 = ... . Les premières équations sont échelonnées.
Le système admet des solutions si et seulement si les équations 0 = ... sont vérifiées et dans ce cas on obtient les solutions en calculant les inconnues “coin de marche”, dites inconnues principales en fonction des autres inconnues, dites variables libres.
Voici un autre exemple déjà échelonné dans pour bien comprendre ces notions d’inconnues principales et de variables libres. La lettre désigne un paramètre réel fixé. Les inconnues x, y, z, t vérifient les deux équations :