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

En seconde, tu résolvais un système de deux équations à deux inconnues « à vue » : substitution, ou une combinaison bien choisie. Cela marche parce que deux équations tiennent dans un regard. Écris trois équations à trois inconnues, puis cinq à cinq, et la méthode disparaît : il n'y a plus de combinaison « bien choisie », il faut une procédure qui aboutisse toujours, quels que soient les coefficients. C'est cette procédure — un algorithme, au sens plein du terme — qui fait l'objet de cette leçon.

Trois opérations, et trois seulement. 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 choisit dans la première colonne un coefficient non nul, 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 : la dernière ligne 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. 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.

Pourquoi c'est plus qu'une technique de calcul. Le nombre de lignes non nulles à la fin ne dépend pas des choix faits en route : c'est le rang du système. Ce seul entier décide de tout — combien de solutions, et de quelle forme. Toute la fin de la leçon en découle.

Le lycée résolvait des systèmes qui avaient une solution. Le supérieur commence là où cette hypothèse tombe : 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. Une fois l'échelonnement terminé, on compte les lignes non nulles : c'est le rang $r$ du système, à 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 sur $L_2$, qui n'a pas servi à l'expression finale : $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.

Change 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. Le développer par la formule des déterminants en demanderait de l'ordre de $n!$ : pour $n = 20$, la différence est celle entre un calcul instantané et un calcul impossible. Le pivot n'est pas une méthode d'attente, en espérant mieux : c'est la méthode.

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 le risque de recopie deux fois moindre.

Énoncé. Résoudre dans $\mathbb{R}^3$ le système

---

Étape 1 — choisir le pivot. Le coefficient de $x$ dans $L_1$ vaut $1$ : il est non nul, il est déjà en haut, et c'est un $1$, donc aucune fraction n'apparaîtra en l'utilisant. On le garde comme pivot ; aucun échange de lignes n'est nécessaire.

Étape 2 — éliminer $x$ des deux lignes du bas.

$L_2 \leftarrow L_2 - 3L_1$ : le coefficient de $x$ devient $3 - 3 \times 1 = 0$, celui de $y$ vaut $-1 - 3 \times 2 = -7$, celui de $z$ vaut $2 - 3 \times (-1) = 5$, et le second membre subit le même traitement : $13 - 3 \times (-3) = 13 + 9 = 22$. Il reste $-7y + 5z = 22$.

$L_3 \leftarrow L_3 + 2L_1$ : coefficient de $x$, $-2 + 2 = 0$ ; de $y$, $1 + 2 \times 2 = 5$ ; de $z$, $3 + 2 \times (-1) = 1$ ; second membre, $4 + 2 \times (-3) = 4 - 6 = -2$. Il reste $5y + z = -2$.

Le système est devenu

Étape 3 — éliminer $y$ de la dernière ligne. Le pivot de la deuxième ligne vaut $-7$. La combinaison $L_3 \leftarrow L_3 + \dfrac{5}{7} L_2$ ferait apparaître des fractions ; on lui préfère $L_3 \leftarrow 7L_3 + 5L_2$, qui est la composée de deux opérations élémentaires légitimes — la multiplication par $7 \neq 0$ est réversible — et qui garde tout entier :

Le système échelonné est donc

Trois lignes non nulles, trois inconnues : le rang vaut $3$, le système est de Cramer, la solution est unique.

Étape 4 — la remontée. La dernière ligne donne

On reporte dans la deuxième : $-7y + 5 \times 3 = 22$, soit $-7y = 22 - 15 = 7$, donc

On reporte les deux dans la première, dont le pivot vaut $1$ : $x + 2 \times (-1) - 3 = -3$, soit $x - 5 = -3$, donc

Étape 5 — vérifier, et sur la bonne ligne. La solution est le triplet $(2\ ;\ -1\ ;\ 3)$. On la contrôle dans $L_3$ du système de départ, ligne qui n'a pas servi à la remontée :

Vérifier dans une ligne déjà utilisée ne prouverait rien : elle a servi à fabriquer la réponse.

Contrôle de méthode. Trois réflexes valent pour tout système : après chaque opération, le second membre a-t-il subi le même sort que les coefficients ? Le nombre d'équations est-il resté le même (on ne supprime une ligne que si elle est entièrement nulle) ? Et la solution, une fois trouvée, satisfait-elle une ligne qui n'a pas servi à l'obtenir ?

Figure (fig.math.gaussian-elimination, SVG programmatique à produire) : 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 de l'exemple. 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.

Comptes et ordres de grandeur. La résolution d'un système $n \times n$ par le pivot coûte de l'ordre de $\dfrac{2n^3}{3}$ opérations, contre de l'ordre de $n!$ pour un développement par les déterminants : c'est la raison pratique pour laquelle le pivot est l'algorithme de référence, et pas seulement une méthode d'exposition.

Ce qui n'est pas dans cette leçon. Le vocabulaire des espaces vectoriels (sous-espace, base, dimension, théorème du rang) vient juste après dans le cycle et donnera son nom à ce qu'on décrit ici avec les mots « droite affine » et « nombre de paramètres ». L'inversion d'une matrice par le pivot, la réduction et les questions de stabilité numérique (pivot partiel, conditionnement) sont différées.

1. Oublier le second membre. Une opération élémentaire porte sur toute la ligne : si $L_2 \leftarrow L_2 - 3L_1$ change les coefficients, elle change aussi le nombre à droite du signe égal. C'est la faute la plus fréquente du chapitre, et la matrice augmentée $(A \mid B)$ existe exactement pour la rendre impossible à commettre.
2. Prendre pour pivot un coefficient qui peut s'annuler. Dès qu'une lettre apparaît dans les coefficients, diviser par $m - 3$ ou choisir $m$ comme pivot sans avoir séparé le cas $m = 3$ est une faute de raisonnement, pas d'inattention : on résout alors un système qui n'est pas celui de l'énoncé.
3. Lire une ligne « $0 = 0$ » comme l'absence de solution. C'est l'inverse : une ligne entièrement nulle signale une équation redondante, donc une inconnue libre, donc une infinité de solutions. La ligne qui interdit toute solution est $0 = c$ avec $c \neq 0$.
4. Donner une solution particulière quand $r < n$. Le triplet $(2\ ;\ -1\ ;\ 0)$ vérifie bien le système du deuxième exemple, mais ce n'est pas la réponse : la réponse est l'ensemble des solutions, décrit avec ses $n - r$ paramètres. Un correcteur lit « aucun paramètre » comme « le rang n'a pas été calculé ».
5. Multiplier une ligne par $0$, ou l'ajouter à elle-même. Ces deux opérations ne sont pas réversibles : elles détruisent une équation, et le système obtenu peut avoir plus de solutions que celui de départ. Seuls $\lambda \neq 0$ et $i \neq j$ sont autorisés.
6. Confondre $p$, $n$ et $r$. Le nombre d'équations, le nombre d'inconnues et le rang sont trois entiers différents. Quatre équations à trois inconnues peuvent avoir une solution unique ($r = 3$), et trois équations à trois inconnues peuvent n'en avoir aucune. « Autant d'équations que d'inconnues » ne garantit rien.
7. Vérifier dans une ligne qui a servi à la remontée. Elle sera satisfaite même si le calcul est faux plus haut. On contrôle toujours dans une ligne du système de départ restée à l'écart du calcul final.
8. Recopier les inconnues dans le désordre. La remontée donne les valeurs dans l'ordre $z$, puis $y$, puis $x$ ; le triplet réponse s'écrit dans l'ordre $(x\ ;\ y\ ;\ z)$. L'inversion des deux ordres est la faute que le modèle d'exercice à choix multiples associé à cette leçon traque : ses quatre propositions sont les mêmes trois nombres, dans quatre ordres différents.
9. Croire que l'escalier doit descendre d'exactement une colonne par ligne. Une marche peut sauter une colonne : c'est précisément le cas où une inconnue devient secondaire. L'escalier descend vers la droite, il ne descend pas régulièrement.

Le modèle d'entraînement. L'exercice associé à cette leçon sert un système $3 \times 3$ à coefficients entiers, fabriqué à partir d'une solution entière, et demande la valeur de l'une des trois inconnues — laquelle change à chaque tirage. Le corrigé déroule l'échelonnement complet puis la remontée, et vérifie sur la ligne restée à l'écart. Un modèle voisin, à choix multiples, demande le triplet solution parmi quatre triplets formés des mêmes trois nombres dans des ordres différents : là, seule une remontée menée jusqu'au bout et recopiée dans le bon ordre permet de trancher.

Énoncé type. Résoudre dans $\mathbb{R}^3$ le système

Quelle est la valeur de $y$ ?

Corrigé complet.

1. Rendre le premier pivot égal à $1$. Le coefficient de $x$ dans $L_1$ vaut $-1$ : on applique $L_1 \leftarrow -L_1$, opération légitime puisque $-1 \neq 0$. La première ligne devient

2. Éliminer $x$. $L_2 \leftarrow L_2 - 2L_1$ : pour $y$, $-3 - 2 \times (-2) = 1$ ; pour $z$, $1 - 2 \times (-3) = 7$ ; second membre, $-9 - 2 \times (-13) = -9 + 26 = 17$. Il reste $y + 7z = 17$. $L_3 \leftarrow L_3 - 3L_1$ : pour $y$, $1 - 3 \times (-2) = 7$ ; pour $z$, $-2 - 3 \times (-3) = 7$ ; second membre, $-4 - 3 \times (-13) = -4 + 39 = 35$. Il reste $7y + 7z = 35$.

3. Éliminer $y$. Le pivot de la deuxième ligne vaut $1$. $L_3 \leftarrow L_3 - 7L_2$ : pour $y$, $7 - 7 \times 1 = 0$ ; pour $z$, $7 - 7 \times 7 = -42$ ; second membre, $35 - 7 \times 17 = 35 - 119 = -84$. Le système échelonné est

Trois pivots pour trois inconnues : rang $3$, solution unique.

4. Remonter.

5. Contrôler sur la ligne restée à l'écart. $L_3$ du système de départ : $3 \times (-1) + 3 - 2 \times 2 = -3 + 3 - 4 = -4$. $\checkmark$

Réponse : $y = 3$ (la solution complète est le triplet $(-1\ ;\ 3\ ;\ 2)$).

Auto-contrôle. Ai-je reporté chaque opération sur le second membre ? Ai-je compté les lignes non nulles pour conclure au rang avant de remonter ? Et ai-je vérifié dans une ligne qui n'avait pas servi ?