Systèmes d'équations linéaires

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• reconnaître une équation linéaire et un système linéaire, et interpréter géométriquement leurs solutions dans le plan et dans l'espace;
• écrire la matrice augmentée d'un système et appliquer les trois opérations élémentaires sur les lignes en justifiant qu'elles ne modifient pas l'ensemble des solutions;
• exécuter l'algorithme de Gauss pour amener une matrice à la forme échelonnée, puis à la forme échelonnée réduite (Gauss–Jordan);
• distinguer variables pivots et variables libres, et écrire l'ensemble des solutions sous forme paramétrique vectorielle $\mathbf{x}=\mathbf{p}+s\mathbf{u}+t\mathbf{v}$;
• décider de l'existence et de l'unicité des solutions à l'aide de la forme échelonnée et du rang, y compris pour un système dépendant d'un paramètre;
• modéliser par un système linéaire un circuit électrique, une réaction chimique, un réseau de flux ou un problème d'interpolation, et le résoudre.

Des équations linéaires partout

L'algèbre linéaire est née d'un problème très concret: résoudre plusieurs équations du premier degré à plusieurs inconnues en même temps. Un ingénieur en rencontre dès ses premiers cours, et sous des habits très différents.

• Statique d'un treillis. À un nœud d'un treillis en équilibre, la somme des forces est nulle. Si deux barres inclinées de $60^{\circ }$ et $45^{\circ }$ par rapport à l'horizontale reprennent une charge verticale $P$, les efforts $F_1$ et $F_2$ vérifient et : deux équations linéaires, deux inconnues. Un treillis de pont en a plusieurs dizaines.

Dans tous ces cas, les inconnues n'apparaissent qu'à la puissance $1$, sans produit entre elles ni fonction appliquée à elles. C'est cette linéarité qui rend la résolution systématique, quel que soit le nombre d'inconnues, et qui permet aux logiciels de calcul de résoudre couramment des systèmes à plusieurs millions d'inconnues (méthode des éléments finis).

Équations et systèmes linéaires

Définitions

Ainsi $3x-2y+\sqrt{5}z=7$ est linéaire, mais $xy+z=1$, et ne le sont pas: dans une équation linéaire, chaque inconnue apparaît seule, multipliée par une constante. Les coefficients peuvent être des nombres quelconques, y compris nuls ou irrationnels; ce sont les qui doivent rester au premier degré.

Nous noterons souvent $\mathbf{x}=(x_1,\dots ,x_n)$ le vecteur des inconnues et $\mathbf{s}$ une solution. Résoudre un système, c'est décrire complètement son ensemble de solutions: dire s'il est vide, s'il est réduit à un point, ou en donner une description paramétrique lorsqu'il est infini.

Ces trois situations — une solution, aucune, une infinité — sont les seules possibles pour un système linéaire, quel que soit le nombre d'équations et d'inconnues; nous le démontrerons au théorème 1.4. En particulier, un système linéaire n'a jamais exactement deux solutions.

Interprétation géométrique

Dans le plan muni d'un repère, l'équation $ax+by=c$ avec $(a,b)\ne (0,0)$ est celle d'une droite. Un système de deux équations à deux inconnues demande donc les points communs à deux droites: elles sont sécantes (un point), strictement parallèles (aucun point) ou confondues (une droite entière de points). C'est exactement l'exemple 1.1.

Dans l'espace, l'équation $ax+by+cz=d$ avec $(a,b,c)\ne (0,0,0)$ est celle d'un plan. Deux plans distincts sont parallèles ou se coupent selon une droite; un système de trois équations à trois inconnues cherche les points communs à trois plans, et les configurations sont plus variées: un point (cas général), une droite (trois plans «en portefeuille» autour d'un axe), un plan entier (trois équations proportionnelles), ou rien du tout (deux plans parallèles, ou trois plans qui se coupent deux à deux selon trois droites parallèles, comme les faces d'un prisme).

Au-delà de trois inconnues, l'intuition visuelle s'arrête, mais le vocabulaire reste: l'ensemble des solutions d'une équation linéaire non triviale en $n$ inconnues est un hyperplan de ${\mathbb{R}}^n$, et résoudre un système, c'est intersecter des hyperplans. L'algèbre prendra le relais de la géométrie.

L'explorateur ci-dessous permet de faire varier la seconde droite d'un système $2\times 2$. Observez la quantité $a_1{b}_2-a_2{b}_1$, qui s'annule exactement lorsque les deux droites ont la même direction: c'est le du système, que le chapitre 3 étudiera en toute généralité.

Systèmes homogènes

Un système homogène est donc toujours compatible: la seule question est de savoir s'il possède des solutions non triviales. Géométriquement, ses équations sont des droites ou des plans passant par l'origine. À tout système (1.2) on associe le système homogène associé, obtenu en remplaçant chaque $b_i$ par $0$; le lien entre les deux ensembles de solutions est décrit au théorème 1.4.

Notation matricielle et opérations élémentaires

Matrice augmentée

Dans la résolution de l'exemple 1.1, les lettres $x$ et $y$ n'ont joué aucun rôle: seuls comptaient les coefficients et leur position. On les range dans un tableau rectangulaire.

Opérations élémentaires sur les lignes

Pour résoudre l'exemple 1.1 (a), nous avons combiné les équations entre elles. Trois manipulations suffisent à tout faire.

Chaque opération élémentaire est réversible par une opération élémentaire du même type: l'échange $L_i\leftrightarrow L_j$ est sa propre inverse, $L_i\leftarrow \lambda L_i$ s'annule par (c'est pour cela que est exigé), et s'annule par . Cette réversibilité est la clé du théorème fondamental de ce chapitre.

Démonstration. Il suffit de traiter une seule opération, puisqu'une suite d'opérations se traite en enchaînant l'argument. Notons $(S)$ le système de départ et $(S^{\prime })$ le système obtenu.

Montrons d'abord que toute solution $\mathbf{s}$ de $(S)$ est solution de $(S^{\prime })$. Pour l'échange de deux lignes, $(S^{\prime })$ contient les mêmes équations que $(S)$ dans un autre ordre, et $\mathbf{s}$ les vérifie toutes. Pour $L_i\leftarrow \lambda L_i$, la seule équation nouvelle est , qui est la -ième équation de multipliée par : elle est vraie puisque . Pour , la nouvelle -ième équation s'écrit

et c'est bien le second membre de la nouvelle ligne. Les autres équations sont inchangées. Dans les trois cas, $\mathbf{s}$ est solution de $(S^{\prime })$.

Réciproquement, $(S)$ s'obtient à partir de $(S^{\prime })$ par l'opération inverse, qui est encore une opération élémentaire: le même raisonnement montre que toute solution de $(S^{\prime })$ est solution de $(S)$. Les deux ensembles de solutions sont donc égaux. $\square$

L'algorithme de Gauss

Le théorème 1.1 autorise à transformer librement la matrice augmentée. Le but est d'atteindre une forme dans laquelle le système se résout «en remontant», équation par équation.

Forme échelonnée

La forme échelonnée dessine un escalier dont chaque marche commence à un pivot; en dessous de l'escalier, tout est nul. Lorsqu'une matrice augmentée est échelonnée, la dernière équation non nulle ne contient qu'une ou quelques inconnues, l'avant-dernière en contient au moins une de plus, et ainsi de suite: on résout de bas en haut par substitution rétrograde.

L'algorithme

Le principe est toujours le même: chaque pivot sert à «nettoyer» la colonne située sous lui, et une fois une colonne nettoyée, on ne touche plus à la ligne du pivot. Notez que le choix du pivot n'est pas unique — on aurait pu échanger $L_1$ et $L_3$ au départ — et que les formes échelonnées obtenues peuvent différer; l'ensemble des solutions, lui, ne dépend pas de ces choix (théorème 1.1).

Forme échelonnée réduite et méthode de Gauss–Jordan

On peut pousser l'élimination plus loin et supprimer aussi les coefficients situés au-dessus des pivots: la substitution rétrograde devient alors inutile, la solution se lit directement.

Démonstration (partielle). L'existence est établie par l'algorithme lui-même: l'élimination de Gauss produit une forme échelonnée, et les opérations de Gauss–Jordan (division par les pivots, élimination au-dessus des pivots) sont des opérations élémentaires qui conduisent à une forme échelonnée réduite. L'unicité, que nous admettons, se démontre au chapitre 5 à l'aide de la notion de rang: on montre que la position des pivots et les coefficients des colonnes libres sont déterminés par les relations linéaires entre les colonnes de la matrice, relations que les opérations sur les lignes conservent. $\square$

L'unicité est précieuse: alors qu'une matrice possède en général plusieurs formes échelonnées (selon les pivots choisis), sa forme échelonnée réduite est un objet canonique. Deux personnes qui réduisent la même matrice obtiendront la même réponse, ce qui facilite grandement la vérification des calculs.

Variables pivots et variables libres

Que se passe-t-il lorsqu'il y a moins de pivots que d'inconnues? Certaines colonnes de $A$ ne contiennent pas de pivot, et les inconnues correspondantes ne sont déterminées par aucune équation.

Pour décrire l'ensemble des solutions, on donne aux variables libres des valeurs arbitraires, appelées paramètres, et l'on en déduit les variables pivots. Lorsqu'il y a $k$ variables libres $s,t,\dots$, on obtient une écriture vectorielle

où $\mathbf{p}$ est une solution particulière (obtenue en annulant tous les paramètres) et $\mathbf{u},\mathbf{v},\dots$ sont des vecteurs de ${\mathbb{R}}^n$, un par variable libre. L'ensemble des solutions est un point translaté d'une droite, d'un plan, etc.: sa «dimension» est le nombre de variables libres.

Existence et unicité des solutions

Le théorème de discussion

La forme échelonnée contient toute l'information sur le nombre de solutions.

Démonstration. Par le théorème 1.1, le système échelonné a les mêmes solutions que le système initial; raisonnons sur lui.

(1) Si une ligne $(0\cdots 0\mid c)$ avec $c\ne 0$ est présente, elle code l'équation $0x_1+\cdots +0x_n=c$, qui n'a aucune solution: le système est incompatible. Réciproquement, supposons qu'aucune ligne de ce type n'apparaisse. Alors toute ligne non nulle possède un pivot dans une colonne de . Donnons la valeur à toutes les variables libres et résolvons de bas en haut: la dernière équation non nulle ne contient, parmi les variables pivots, que son propre pivot (les variables situées à droite sont libres, donc nulles), et se résout en divisant par le pivot; l'équation précédente ne contient alors qu'une variable pivot inconnue, et ainsi de suite. On construit ainsi une solution: le système est compatible.

(2) Supposons le système compatible. S'il n'y a pas de variable libre, la substitution rétrograde ci-dessus n'offre aucun choix: chaque variable est déterminée de manière unique par les équations, et la solution est unique. S'il existe une variable libre $x_j$, on peut lui donner n'importe quelle valeur réelle, les autres variables libres étant fixées, et compléter par substitution rétrograde en une solution; à des valeurs différentes de $x_j$ correspondent des solutions différentes, d'où une infinité de solutions. $\square$

Avec ce vocabulaire, le théorème 1.3 se reformule ainsi: le système est compatible si et seulement si $\mathrm{rg}(A\mid \mathbf{b})=\mathrm{rg}A$; un système compatible a une solution unique si et seulement si $\mathrm{rg}A=n$, et ses solutions dépendent de $n-\mathrm{rg}A$ paramètres. Le chapitre 5 fera du rang un outil central.

Démonstration. Soit $\mathbf{x}$ une solution de $(S)$ et posons $\mathbf{h}=\mathbf{x}-\mathbf{p}$. Pour chaque équation $i$, ${\sum }_j{a}_{ij}{h}_j={\sum }_j{a}_{ij}{x}_j-{\sum }_j{a}_{ij}{p}_j=b_i-b_i=0$: est solution de et . Réciproquement, si est solution de , alors , donc est solution de .

Pour la dernière affirmation: si $(S)$ possède deux solutions distinctes $\mathbf{p}$ et $\mathbf{q}$, alors $\mathbf{h}=\mathbf{q}-\mathbf{p}\ne 0$ est solution de $(S_0)$, et par le même calcul l'est aussi pour tout ; les vecteurs sont alors des solutions de , deux à deux distinctes: il y en a une infinité.

C'est exactement la structure de la formule (1.3): $\mathbf{p}$ est une solution particulière et $s\mathbf{u}+t\mathbf{v}+\dots$ décrit les solutions du système homogène associé. Vous retrouverez ce principe «solution particulière plus solution générale de l'équation homogène» pour les équations différentielles linéaires.

La démonstration, courte, fait l'objet de l'exercice 1.5: elle repose sur le fait qu'il ne peut y avoir plus de pivots que de lignes. Ce résultat est le germe de la notion de dimension (chapitre 4): on ne peut pas «bloquer» $n$ inconnues avec moins de $n$ contraintes linéaires.

Systèmes dépendant d'un paramètre

En pratique, les coefficients d'un système contiennent souvent une grandeur physique non fixée — une raideur, une résistance, une fréquence — et l'on veut savoir pour quelles valeurs le comportement change. On mène alors l'élimination avec le paramètre, en prenant garde de ne jamais diviser par une expression qui pourrait s'annuler.

Coût de l'algorithme et pivot partiel

Applications

Circuit électrique et lois de Kirchhoff

Équilibrage d'une équation chimique

Réseau de flux

Interpolation polynomiale

Synthèse

• Un système linéaire de $m$ équations à $n$ inconnues se code par sa matrice augmentée $(A\mid \mathbf{b})\in {\mathcal{M}}_{m\times (n+1)}(\mathbb{R})$; géométriquement, il décrit l'intersection de droites, de plans ou d'hyperplans.
• Les trois opérations élémentaires sur les lignes ($L_i\leftrightarrow L_j$, avec , ) sont réversibles et conservent l'ensemble des solutions (théorème 1.1).

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Lay, D. C., Lay, S. R. et McDonald, J. J., Algèbre linéaire et applications, 5e éd., Pearson, Montréal, chap. 1.
• Strang, G., Introduction to Linear Algebra, 5e éd., Wellesley-Cambridge Press, Wellesley, chap. 2.
• Grifone, J., Algèbre linéaire, 6e éd., Cépaduès, Toulouse, chap. 1.
• Liret, F. et Martinais, D., Algèbre 1re année, 2e éd., Dunod, Paris.
• Trefethen, L. N. et Bau, D., Numerical Linear Algebra, SIAM, Philadelphie, leçons 20–22 (élimination de Gauss et pivot partiel).
• Chemla, K. et Guo, S., Les neuf chapitres: le classique mathématique de la Chine ancienne et ses commentaires, Dunod, Paris (chapitre VIII, Fangcheng).