Systèmes linéaires et méthode du pivot de Gauss

La substitution et les combinaisons restent valables avec davantage d’inconnues. Pour organiser systématiquement ces opérations, on utilise une procédure finie, en calcul exact, qui permet soit de décrire les solutions, soit de constater leur absence. C'est cette procédure — un algorithme, au sens plein du terme — qui fait l'objet de cette leçon.

Trois types usuels d’opérations élémentaires. On transforme un système en un autre système qui a exactement les mêmes solutions au moyen de trois opérations dites élémentaires sur les lignes :

• échanger deux lignes : $L_i \leftrightarrow L_j$ ;
• multiplier une ligne par un scalaire non nul : $L_i \leftarrow \lambda L_i$ avec $\lambda \neq 0$ ;
• ajouter à une ligne un multiple d'une autre ligne : $L_i \leftarrow L_i + \mu L_j$ avec $i \neq j$.

Chacune de ces trois opérations est réversible : on sait revenir en arrière par une opération du même type. C'est cela, et rien d'autre, qui garantit que le système obtenu a le même ensemble de solutions que le système de départ. Les deux restrictions comptent : $\lambda = 0$ effacerait une équation sans retour possible, et ajouter à une ligne un multiple d'elle-même revient à la multiplier par $1 + \mu$, donc à l'effacer si $\mu = -1$.

Ce qu'on vise : la forme échelonnée. L'algorithme du pivot consiste à faire descendre les inconnues en escalier. On cherche dans la première colonne encore à traiter un coefficient non nul ; si elle n’en contient aucun parmi les lignes restantes, on passe à la colonne suivante. Sinon on choisit ce coefficient, le pivot ; on l'amène en première ligne par un échange s'il le faut ; puis on ajoute à chacune des lignes suivantes le multiple de la première qui annule leur coefficient en $x$. La première inconnue a disparu partout sauf en haut. On recommence sur le système qui reste, une inconnue et une ligne de moins. Le processus s'arrête forcément : à chaque tour, il y a une ligne de moins à traiter.

Le résultat est un système échelonné : dans chaque ligne non nulle, la première inconnue à coefficient non nul — son pivot — se trouve strictement plus à droite que celui de la ligne au-dessus. L'escalier est la forme visible de l'algorithme.

Puis la remontée. Un système échelonné se lit de bas en haut : si chaque inconnue porte un pivot et que le système est compatible, la dernière ligne non nulle ne contient qu’une inconnue, on la calcule ; on reporte sa valeur dans l'avant-dernière, qui n'en contient plus qu'une à son tour ; et ainsi jusqu'en haut. C'est la substitution remontante. Dans un système compatible avec des inconnues libres, on les choisit comme paramètres puis on exprime les autres en fonction d’elles. Une variante, la forme échelonnée réduite, pousse l'élimination vers le haut aussi et normalise chaque pivot à $1$ : le système se lit alors directement, sans remontée. Les deux donnent la même réponse ; la seconde coûte plus d'opérations et sert surtout quand on veut lire l'ensemble des solutions d'un coup.

Rang des coefficients et compatibilité. Le rang $r$ de la matrice des coefficients $A$ est le nombre de pivots de sa forme échelonnée. Le rang de la matrice augmentée peut être plus grand. Il faut d’abord exclure une ligne impossible $0=c$, $c\neq0$ ; alors seulement $r$ détermine le nombre d’inconnues libres. Le rang seul ne décide pas de la compatibilité.

Sans présumer l’existence d’une solution, un système peut n'en avoir aucune, ou en avoir une infinité, et l'algorithme du pivot le dit sans qu'on ait à le deviner.

Ce que la forme échelonnée laisse voir. On compte les lignes dont la partie coefficients est non nulle après échelonnement : c’est le rang $r$ de $A$, à ne jamais confondre avec le nombre $n$ d'inconnues ni avec le nombre $p$ d'équations. Les inconnues qui portent un pivot sont les inconnues principales ($r$ d'entre elles) ; les autres, $n - r$, sont les inconnues secondaires, ou paramètres. Trois cas, et seulement trois :

1. Une ligne $0 = c$ avec $c \neq 0$ apparaît. Le système est incompatible : aucune solution. La ligne dit qu'une combinaison des équations de départ impose une égalité fausse.
2. Aucune telle ligne, et $r = n$. Chaque inconnue porte un pivot, la remontée donne une valeur et une seule : solution unique. On dit que le système est de Cramer lorsqu'en outre $p = n$.
3. Aucune telle ligne, et $r < n$. Les $n - r$ inconnues secondaires se choisissent librement, et la remontée exprime les principales en fonction d'elles : une infinité de solutions, décrite par $n - r$ paramètres.

Le troisième cas, en clair. Prenons

La troisième ligne est exactement la somme des deux premières : elle n'apporte rien. Le rang vaut $2$ pour $3$ inconnues. On garde $z$ comme paramètre : $L_1 + L_2$ donne $3x = 6$, soit $x = 2$ ; $L_1$ donne alors $y - z = -1$, soit $y = z - 1$. L'ensemble des solutions est

Vérification dans l’équation originale $L_2$, qui a aussi participé au calcul de $x$ : $2 \times 2 - (t - 1) + t = 4 - t + 1 + t = 5$ pour toute valeur de $t$. Géométriquement, c'est une droite de l'espace : un point particulier, plus toutes les translations le long d'une direction. Une solution particulière plus les solutions du système homogène associé (celui dont tous les seconds membres sont nuls) — cette décomposition est le squelette de tout ce que l'algèbre linéaire dira plus tard.

Changez le second membre de la troisième ligne en $7$, sans rien toucher d'autre : la même combinaison $L_3 - L_1 - L_2$ donne maintenant $0 = 1$. Le système devient incompatible, et rien dans son allure ne le laissait prévoir. C'est bien le calcul, pas l'œil, qui tranche.

La discussion selon un paramètre. C'est la vraie nouveauté par rapport au lycée, et le piège le plus coûteux : un coefficient contient une lettre, et le pivot qu'on s'apprêtait à utiliser peut être nul. Soit $m$ un réel et

Les opérations $L_2 \leftarrow L_2 - L_1$ et $L_3 \leftarrow L_3 - L_1$ sont légitimes quel que soit $m$ (elles n'utilisent que le pivot $1$ de la première ligne) et donnent $y + 2z = 1$ puis $y + (m - 1)z = 2$. Une soustraction de plus, $L_3 \leftarrow L_3 - L_2$, laisse

Tout est dit par cette seule ligne. Si $m \neq 3$, alors $z = \dfrac{1}{m - 3}$, puis $y = 1 - \dfrac{2}{m - 3}$ et $x = 1 - y - z = \dfrac{1}{m-3}$ : rang $3$, solution unique. Si $m = 3$, la ligne devient $0 = 1$ : rang $2$ pour un système incompatible, aucune solution. On n'a jamais divisé par $m - 3$ avant d'avoir séparé les deux cas — c'est exactement ce que la faute classique oublie de faire.

Le coût, et pourquoi il faut le connaître. Résoudre un système $n \times n$ par le pivot demande de l'ordre de $\dfrac{2n^3}{3}$ opérations. Un développement naïf récursif des déterminants par cofacteurs a un coût factoriel. Les déterminants peuvent eux-mêmes être calculés par élimination en coût cubique ; la comparaison ne vise donc pas tous leurs algorithmes.

Un mot sur l'écriture matricielle. On ne recopie pas les inconnues à chaque ligne : on travaille sur la matrice augmentée $(A \mid B)$, dont les colonnes sont les coefficients et la dernière le second membre. Les trois opérations élémentaires deviennent des opérations sur les lignes de cette matrice. Le contenu ne change pas, l'écriture est deux fois plus courte, et les répétitions à recopier sont réduites, sans garantie chiffrée sur le risque d’erreur.

Énoncé. Discutez selon les réels $m,c$ le système

Éliminer sans diviser par un paramètre. Appliquez $L_2\leftarrow L_2-L_1$, puis $L_3\leftarrow L_3-2L_1$. On obtient $y+2z=1$ et $y+(m+2)z=1+c$. Enfin $L_3\leftarrow L_3-L_2$ donne $mz=c$.

Séparer les cas. Si $m\neq0$, alors $z=c/m$, $y=1-2c/m$ et $x=c/m$ : une solution unique et rang3. Si $m=0,c\neq0$, la dernière ligne est impossible : le rang des coefficients vaut2 mais celui de la matrice augmentée vaut3. Il n’y a aucune solution. Si $m=c=0$, la dernière ligne est $0=0$ : deux pivots pour trois inconnues, et toutes les solutions sont $(t;1-2t;t)$, $t\in\mathbb R$.

Contrôler les trois équations. Pour $m\neq0$, la somme $x+y+z$ vaut1 ; $x+2y+3z$ vaut2 ; le troisième membre gauche vaut $3+c$. Pour $m=c=0$, la même substitution vaut pour tout $t$. Le rang seul n’aurait pas séparé les deux cas de rang2 : le second membre compte aussi.

Figure (fig.math.gaussian-elimination, SVG programmatique existant) : deux panneaux superposés, la marche de l'algorithme en haut, la lecture du résultat en bas.

• Panneau du haut — les trois états de la matrice augmentée d’un exemple distinct du guidage. Trois tableaux $3 \times 4$ alignés de gauche à droite, séparés par deux flèches portant l'opération effectuée. (1) La matrice de départ, colonnes $x$, $y$, $z$ puis, après un trait vertical, le second membre : lignes $(1, 2, -1 \mid -3)$, $(3, -1, 2 \mid 13)$, $(-2, 1, 3 \mid 4)$. (2) Après élimination de $x$ : $(1, 2, -1 \mid -3)$, $(0, -7, 5 \mid 22)$, $(0, 5, 1 \mid -2)$ ; la flèche qui y mène porte « $L_2 \leftarrow L_2 - 3L_1$ ; $L_3 \leftarrow L_3 + 2L_1$ ». (3) Après élimination de $y$ : $(1, 2, -1 \mid -3)$, $(0, -7, 5 \mid 22)$, $(0, 0, 32 \mid 96)$ ; la flèche porte « $L_3 \leftarrow 7L_3 + 5L_2$ ». Dans le troisième tableau, les trois pivots $1$, $-7$ et $32$ sont entourés d'un cadre épais et marqués d'un petit triangle en coin — la couleur ne porte aucune information à elle seule — et un trait en escalier descend de gauche à droite en longeant les zéros créés. Sous le troisième tableau, une flèche remontante étiquetée « remontée : $z = 3$, puis $y = -1$, puis $x = 2$ ».
• Panneau du bas — les trois issues, côte à côte. Trois petites matrices échelonnées $3 \times 4$ schématiques, où un pivot est noté $\ast$ et un coefficient quelconque un point. À gauche, trois pivots : légende « rang $3$ = nombre d'inconnues : une solution ». Au centre, deux pivots et une dernière ligne $(0, 0, 0 \mid c)$ avec $c \neq 0$, hachurée : légende « ligne impossible : aucune solution ». À droite, deux pivots et une dernière ligne entièrement nulle $(0, 0, 0 \mid 0)$, hachurée dans l'autre sens : légende « rang $2$ pour $3$ inconnues : une inconnue libre, une infinité de solutions ». Sous ce troisième cas, la droite $(2\ ;\ t-1\ ;\ t)$ dessinée dans un repère de l'espace, avec le point $(2\ ;\ -1\ ;\ 0)$ marqué et le vecteur $(0\ ;\ 1\ ;\ 1)$ posé dessus.

Ce qu'il faut lire. Le panneau du haut montre que l'algorithme ne fabrique rien : il ne fait que creuser des zéros sous les pivots, une colonne à la fois, et le second membre voyage avec. Le panneau du bas montre que la forme finale, à elle seule, contient la réponse à « combien de solutions ? » — on la lit avant même d'avoir remonté quoi que ce soit.

La figure en détail : la figure comprend deux parties. En haut, trois tableaux de nombres à trois lignes et quatre colonnes, séparés par un trait vertical avant la dernière colonne, montrent le même système à trois moments : tel qu'il est écrit, après que la première inconnue a été éliminée des deux dernières lignes, puis après que la deuxième inconnue a été éliminée de la dernière ligne. Deux flèches portent les opérations qui font passer d'un tableau au suivant. Dans le dernier tableau, les trois coefficients qui servent de pivots sont encadrés et marqués d'un repère en coin, et un trait en forme d'escalier longe les zéros créés sous eux. Une flèche remontante rappelle que la dernière ligne donne la troisième inconnue, puis la deuxième, puis la première. En bas, trois schémas de systèmes échelonnés illustrent les trois issues possibles : trois pivots pour trois inconnues, donc une seule solution ; une dernière ligne où tous les coefficients sont nuls mais pas le second membre, donc aucune solution ; une dernière ligne entièrement nulle, donc une inconnue libre et une infinité de solutions, dessinées comme une droite de l'espace passant par un point marqué et dirigée par un vecteur.