Systèmes linéaires : n équations, p inconnues
Résoudre un système, c'est chercher toutes les valeurs des inconnues qui satisfont à la fois toutes les équations. Selon les cas il y en a une seule, aucune, ou une infinité — et c'est un seul nombre, le rang, qui décide. Cinq planches pour le voir, le calculer et mesurer ce que coûte le calcul.
Ce qu'on appelle un système n × p
Une équation est linéaire quand chaque inconnue n'y apparaît qu'au premier degré, multipliée par un nombre fixe : pas de x², pas de x·y, pas de √x. Un système linéaire de n équations à p inconnues x1, …, xp s'écrit :
a21x1 + a22x2 + … + a2pxp = b2
⋮
an1x1 + an2x2 + … + anpxp = bn
Les nombres aij sont les coefficients (premier indice : la ligne, c'est-à-dire l'équation ; second indice : la colonne, c'est-à-dire l'inconnue). Les bi forment le second membre. On range les coefficients dans un tableau à n lignes et p colonnes, la matrice A, et le système s'écrit en une ligne AX = B. Si tous les bi sont nuls, le système est dit homogène : il a toujours au moins la solution X = 0. Un système qui a au moins une solution est compatible ; sinon il est incompatible.
| n < p — moins d'équations que d'inconnues | n = p — système carré | n > p — plus d'équations que d'inconnues | |
|---|---|---|---|
| Cas typique | une infinité de solutions, avec p − n paramètres libres | une solution unique (déterminant non nul) | aucune solution : les équations en trop se contredisent |
| Mais aussi | aucune solution, si deux équations se contredisent | aucune ou une infinité si le déterminant est nul | une solution, si les équations en trop sont des conséquences des autres |
| Ce qui tranche | le rang r de A (nombre d'équations réellement indépendantes) : compatible si et seulement si le rang ne change pas quand on ajoute la colonne B ; il reste alors p − r paramètres libres (théorème de Rouché–Fontené, planches 2 à 4). | ||
Deux équations, deux inconnues : deux regards
Un système 2 × 2 se lit de deux façons. En lignes, chaque équation ax + by = c est une droite du plan, et la solution est le point commun aux deux droites. En colonnes, on regarde les deux colonnes de coefficients comme deux vecteurs C1 et C2, et l'on cherche combien de fois prendre C1 (c'est x) et combien de fois prendre C2 (c'est y) pour arriver exactement au vecteur B du second membre. Les deux lectures donnent les mêmes nombres.
Trois équations, trois inconnues : trois plans
Avec trois inconnues x, y, z, chaque équation ax + by + cz = d est un plan de l'espace. Trois plans peuvent se couper en un seul point, avoir une droite commune, n'avoir aucun point commun à tous les trois tout en se coupant deux à deux (le « prisme »), être parallèles… Le rang r de la matrice A — le nombre d'équations vraiment indépendantes — et le rang de la matrice complétée [A | B] suffisent à dire dans quel cas on est. Faites tourner la figure à la souris ou au doigt ; le curseur d₃ fait glisser le troisième plan parallèlement à lui-même.
La méthode du pivot de Gauss, pas à pas
Pour résoudre n'importe quel système, on n'utilise que trois gestes qui ne changent pas l'ensemble des solutions : échanger deux équations, multiplier une équation par un nombre non nul, retrancher à une équation un multiple d'une autre. On s'en sert d'abord pour faire apparaître des zéros sous la diagonale (la descente, ou échelonnement), puis au-dessus (la remontée de Jordan). Le nombre qui sert à éliminer est le pivot, entouré de rouge. Tous les calculs sont faits en fractions exactes.
n et p quelconques : le rang décide de tout
Choisissez le nombre d'équations n, le nombre d'inconnues p et le rang r (le nombre d'équations réellement indépendantes) ; la page tire un système au hasard ayant exactement ce rang et le réduit. Deux comptes résument alors tout : parmi les p inconnues, r sont principales (elles portent un pivot) et p − r sont libres, que l'on peut choisir à volonté ; parmi les n équations, r sont utiles et n − r se réduisent à des égalités « 0 = nombre » qui sont les conditions de compatibilité. Toutes les solutions s'écrivent X = X₀ + λ·V₁ + μ·V₂ + … : une solution particulière plus une combinaison de solutions du système homogène.
Signature : résoudre avec une machine
Sur le papier, le pivot de Gauss est exact. Dans un ordinateur, chaque nombre est arrondi à environ 16 chiffres significatifs (l'unité d'arrondi vaut u ≈ 1,1·10⁻¹⁶). Trois expériences montrent ce qui change alors : le choix du pivot devient une question de survie, certains systèmes amplifient les erreurs quoi qu'on fasse, et la méthode des déterminants, si élégante, devient impraticable.
Le système εx + y = 1, x + y = 2 a pour solution exacte x = 1/(1 − ε), y = (1 − 2ε)/(1 − ε), donc x ≈ 1 et y ≈ 1 dès que ε est petit. Le calcul « naïf » prend ε comme pivot ; le pivot partiel échange d'abord les lignes pour prendre le plus grand coefficient de la colonne.
La matrice de Hilbert H, de coefficients 1/(i + j − 1), est le système « qui tremble » par excellence : ses lignes sont presque proportionnelles. On fabrique B = H·(1, 1, …, 1) et l'on résout avec pivot partiel. Le conditionnement κ = ‖H‖·‖H⁻¹‖ mesure de combien le système peut amplifier une petite erreur ; on le calcule ici exactement, grâce à la formule connue de H⁻¹ à coefficients entiers. Règle pratique : on perd à peu près log₁₀ κ chiffres sur les 16 disponibles.
On compte réellement chaque multiplication, addition et division. La méthode de Gauss en demande exactement 2n³/3 + 3n²/2 − 7n/6. Les formules de Cramer, avec des déterminants développés selon la première ligne, demandent n + 1 déterminants de taille n, chacun coûtant D(n) = n·D(n − 1) + 2n − 1 opérations, soit un nombre qui croît comme une factorielle.
Repères historiques
- vers le Iᵉʳ s.Les Neuf Chapitres sur l'art du calcul (Chine), chapitre « Fangcheng » : les coefficients sont disposés en tableau sur une table à calcul et l'on élimine colonne par colonne — c'est déjà la méthode du pivot, nombres négatifs compris.
- 1683Seki Takakazu, au Japon, introduit les déterminants pour éliminer des inconnues ; Leibniz y arrive indépendamment en 1693, dans une lettre à L'Hôpital où il note les coefficients par des doubles indices.
- 1750Gabriel Cramer publie, dans son Introduction à l'analyse des lignes courbes algébriques, la règle qui porte son nom : chaque inconnue est un quotient de deux déterminants.
- 1809Gauss, dans la Theoria motus, puis à propos de l'orbite de l'astéroïde Pallas, systématise l'élimination pour résoudre les équations normales des moindres carrés.
- 1875Eugène Rouché, et Georges Fontené peu après, énoncent la condition de compatibilité par le rang (en Italie on dit Rouché–Capelli, en Allemagne Kronecker–Capelli).
- 1888Le géodésien Wilhelm Jordan popularise la remontée qui conduit à la forme réduite : c'est la méthode de Gauss–Jordan.
- 1947–1948Von Neumann et Goldstine étudient les erreurs d'arrondi de l'inversion des matrices ; Alan Turing nomme le « nombre de conditionnement ».
- 1961James Wilkinson montre que le pivot partiel rend la méthode de Gauss fiable en pratique : l'erreur commise est celle d'un système voisin résolu exactement (analyse rétrograde).
Ce qu'il faut retenir
Deux lectures
En lignes, un système est une intersection de droites, de plans ou d'hyperplans. En colonnes, c'est la question : B est-il une combinaison des colonnes de A, et de combien de façons ? Les deux lectures donnent les mêmes solutions.
Le rang décide
Avec r = rang de A : le système est compatible si et seulement si rang [A | B] = r ; il a alors une solution unique si r = p, et sinon une infinité décrite par p − r paramètres. Les n − r équations restantes sont des conditions sur B.
Calculer, c'est autre chose
Pour une machine, il faut choisir de grands pivots, se méfier des systèmes mal conditionnés (on perd environ log₁₀ κ chiffres) et oublier Cramer au-delà de 3 ou 4 inconnues : Gauss coûte environ 2n³/3 opérations.
Pour aller plus loin
Gauss, c'est une factorisation. Les multiplicateurs employés pendant la descente forment une matrice triangulaire inférieure L, et le résultat de la descente une matrice triangulaire supérieure U : A = LU (à une permutation des lignes près quand on échange). Une fois A factorisée, chaque nouveau second membre ne coûte plus qu'environ 2n² opérations.
Très grands systèmes. Pour des millions d'inconnues dont presque tous les coefficients sont nuls (éléments finis, réseaux), on préfère des méthodes itératives — Jacobi, Gauss–Seidel, gradient conjugué — qui améliorent une approximation au lieu de tout éliminer.
Système incompatible, mais on veut une réponse. Quand n > p et que les mesures sont bruitées, il n'y a en général aucune solution exacte : on cherche alors X qui rend ‖AX − B‖ le plus petit possible (moindres carrés). C'est l'objet de la page sur la décomposition en valeurs singulières et la pseudo-inverse.
Coefficients entiers, solutions entières. Si l'on exige des solutions en nombres entiers, les trois gestes du pivot ne suffisent plus (on ne peut pas diviser) : c'est la forme normale de Smith qui prend le relais.