Systèmes linéaires et pivot de Gauss
Cours 2 — Algèbre linéaire et analyse de données
L3 GBI — Université d’Évry
Le problème
Préparer un milieu de culture
Trois solutions mères, trois composants.
| g/L | Glucose | Azote | Phosphate |
|---|---|---|---|
| S₁ | 20 | 5 | 1 |
| S₂ | 10 | 20 | 2 |
| S₃ | 0 | 0 | 10 |
| Cible | 30 | 25 | 13 |
Quels volumes \(x_1, x_2, x_3\) ?
Mise en équations
\[ \begin{cases} 20x_1 + 10x_2 \phantom{{}+ 10x_3} = 30 \\ \phantom{2}5x_1 + 20x_2 \phantom{{}+ 10x_3} = 25 \\ \phantom{2}\;\,x_1 + \phantom{1}2x_2 + 10x_3 = 13 \end{cases} \]
Trois équations, trois inconnues.
Le même problème, partout
Doser un mélange. Équilibrer une réaction.
Ajuster un modèle. Estimer des flux métaboliques.
Le plus ancien problème Résolution de systèmes linéaires : Chine, 200 av. J.-C.
Équation linéaire
\[ a_1 x_1 + a_2 x_2 + \dots + a_n x_n = b \]
Les \(a_i\) : les coefficients. Le nombre \(b\) : le second membre.
Les \(x_i\) : les inconnues.
\[\sum_{j=1}^{n} a_j x_j = b, \qquad a_j,\, b \in \mathbb{R} \ \text{connus}\]
Linéaire ?
Oui
\(3x_1 - 5x_2 = 1\)
\(x_1 = 2(\sqrt{6} - x_2) + x_3\)
\(\pi x_1 - \sqrt{2}\,x_2 = 0\)
Non
\(x_1 x_2 = 4\)
\(\sqrt{x_1} - 2x_2 = 1\)
\(x_1^2 + x_2 = 3\)
Chaque inconnue : puissance 1, jamais multipliée par une autre.
\[\forall j \in \{1,\dots,n\}, \quad x_j \ \text{au degré } 1\]
Attention
\(\sqrt{6}\) et \(\pi\) : des coefficients, pas des inconnues.
La linéarité concerne les \(x_i\), pas les nombres qui les accompagnent.
Système linéaire
\(m\) équations, \(n\) inconnues :
\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \\ \quad\vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \end{cases} \]
Double indice : \(a_{ij}\) — ligne \(i\), colonne \(j\).
\[\forall i \in \{1,\dots,m\}, \quad \sum_{j=1}^{n} a_{ij}\,x_j = b_i\]
Solution
Un \(n\)-uplet \((s_1, \dots, s_n)\) vérifiant toutes les équations à la fois.
L’ensemble des solutions : toutes ces listes, et rien d’autre.
\[\mathcal{S} = \left\{\, \mathbf{x} \in \mathbb{R}^n \;\middle|\; \forall i, \ \sum_{j=1}^{n} a_{ij}x_j = b_i \,\right\}\]
Résoudre Décrire l’ensemble des solutions. Pas en trouver une.
Deux questions
Existence — au moins une solution ?
Unicité — au plus une solution ?
\[\mathcal{S} \neq \emptyset \qquad\qquad \operatorname{card} \mathcal{S} \leqslant 1\]
Les réponses, avant tout calcul, par la géométrie.
Lecture géométrique
Une équation, deux inconnues
Figure 1
Une droite du plan. Chaque point : une solution.
\[\mathcal{D} = \bigl\{ (x_1, x_2) \in \mathbb{R}^2 \;\bigm|\; x_1 + 2x_2 = 6 \bigr\}\]
Deux équations
Deux droites.
Les solutions communes : les points d’intersection.
Trois configurations, pas une de plus.
\[\mathcal{S} = \mathcal{D}_1 \cap \mathcal{D}_2\]
Cas 1 — sécantes
Figure 2
Un point. Une solution unique.
Cas 2 — parallèles
Figure 3
Aucun point commun. Aucune solution.
Cas 3 — confondues
Figure 4
Toute la droite. Une infinité de solutions.
Le résultat
Trois cas, jamais plus Un système linéaire admet zéro, une, ou une infinité de solutions.
Jamais exactement deux. Jamais exactement dix-sept.
\[\operatorname{card} \mathcal{S} \in \{\, 0, \ 1, \ +\infty \,\}\]
Pourquoi jamais deux
Deux solutions distinctes \(\mathbf{u}\) et \(\mathbf{v}\).
Alors tous les points de la droite \((\mathbf{u}\mathbf{v})\) : encore des solutions.
Deux entraîne l’infini.
\[\mathbf{u}, \mathbf{v} \in \mathcal{S}, \ \mathbf{u} \neq \mathbf{v} \ \Longrightarrow \ \forall t \in \mathbb{R}, \ (1-t)\,\mathbf{u} + t\,\mathbf{v} \in \mathcal{S}\]
Vocabulaire
Compatible — au moins une solution.
Incompatible — aucune solution.
\[\mathcal{S} \neq \emptyset \qquad\qquad \mathcal{S} = \emptyset\]
Trois inconnues
Une équation \(a_1x_1 + a_2x_2 + a_3x_3 = b\) : un plan de l’espace.
| Configuration | Solutions |
|---|---|
| Trois plans sécants en un point | une |
| Trois plans se coupant selon une droite | une infinité |
| Deux plans parallèles | aucune |
| Trois plans confondus | une infinité |
Au-delà
\(n = 500\,000\) : plus aucune image.
D’où l’algèbre L’intuition géométrique s’arrête à 3. Le calcul, non.
Systèmes équivalents
L’idée
Transformer le système en un système plus simple,
sans changer l’ensemble des solutions.
Définition
Deux systèmes équivalents : même ensemble de solutions.
Notation : \(\sim\)
\[S \sim S' \iff \mathcal{S} = \mathcal{S}'\]
Trois opérations élémentaires
Échange — permuter deux lignes. \(L_i \leftrightarrow L_j\)
Dilatation — multiplier une ligne par \(\lambda \neq 0\). \(L_i \leftarrow \lambda L_i\)
Transvection — ajouter à une ligne un multiple d’une autre. \(L_i \leftarrow L_i + \lambda L_j\)
La condition qui compte
\(\lambda \neq 0\) dans la dilatation.
Multiplier une ligne par \(0\) : l’équation disparaît, des solutions apparaissent.
Pourquoi ça marche
Chaque opération est réversible.
| Opération | Inverse |
|---|---|
| \(L_i \leftrightarrow L_j\) | \(L_i \leftrightarrow L_j\) |
| \(L_i \leftarrow \lambda L_i\) | \(L_i \leftarrow \frac{1}{\lambda} L_i\) |
| \(L_i \leftarrow L_i + \lambda L_j\) | \(L_i \leftarrow L_i - \lambda L_j\) |
Aucune solution perdue, aucune inventée.
\[S \ \xrightarrow{\ O\ } \ S' \ \text{avec } O \ \text{inversible} \ \Longrightarrow \ \mathcal{S} = \mathcal{S}'\]
Exemple — départ
\[ \begin{cases} x_1 - 2x_2 + \phantom{1}x_3 = \phantom{1}0 \\ \phantom{x_1 - {}} 2x_2 - 8x_3 = \phantom{1}8 \\ 5x_1 \phantom{{}- 2x_2} - 5x_3 = 10 \end{cases} \]
Exemple — éliminer \(x_1\)
\(L_3 \leftarrow L_3 - 5L_1\)
\[ \begin{cases} x_1 - \phantom{1}2x_2 + \phantom{1}x_3 = \phantom{1}0 \\ \phantom{x_1 - {}}\;\, 2x_2 - \phantom{1}8x_3 = \phantom{1}8 \\ \phantom{x_1 - {}} 10x_2 - 10x_3 = 10 \end{cases} \]
Exemple — normaliser
\(L_2 \leftarrow \tfrac{1}{2}L_2\)
\[ \begin{cases} x_1 - \phantom{1}2x_2 + \phantom{1}x_3 = \phantom{1}0 \\ \phantom{x_1 - {}}\;\;\, x_2 - \phantom{1}4x_3 = \phantom{1}4 \\ \phantom{x_1 - {}} 10x_2 - 10x_3 = 10 \end{cases} \]
Exemple — éliminer \(x_2\)
\(L_3 \leftarrow L_3 - 10L_2\)
\[ \begin{cases} x_1 - 2x_2 + \phantom{3}x_3 = \phantom{-3}0 \\ \phantom{x_1 - {}}\;\;\, x_2 - 4x_3 = \phantom{-3}4 \\ \phantom{x_1 - 2x_2 + {}} 30x_3 = -30 \end{cases} \]
Exemple — remonter
\(x_3 = -1\), puis \(x_2 = 4 + 4x_3 = 0\), puis \(x_1 = 2x_2 - x_3 = 1\).
\[ (x_1, x_2, x_3) = (1,\; 0,\; -1) \]
Vérification dans les trois équations d’origine : indispensable.
Le poids de la notation
Les \(x_i\) recopiés à chaque ligne, à chaque étape.
Seuls les coefficients changent.
Matrices augmentées
Ne garder que les nombres
\[ \begin{cases} x_1 - 2x_2 + \phantom{1}x_3 = \phantom{1}0 \\ \phantom{x_1 - {}} 2x_2 - 8x_3 = \phantom{1}8 \\ 5x_1 \phantom{{}- 2x_2} - 5x_3 = 10 \end{cases} \]
\[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 & 10 \end{array}\right] \]
Deux matrices
Matrice des coefficients — \(3 \times 3\), à gauche de la barre.
Matrice augmentée — \(3 \times 4\), barre comprise.
La barre : un rappel visuel, sans statut mathématique.
\[A = (a_{ij}) \in \mathcal{M}_{m,n}(\mathbb{R}), \quad \mathbf{b} \in \mathbb{R}^m, \quad [\,A \mid \mathbf{b}\,] \in \mathcal{M}_{m,n+1}(\mathbb{R})\]
Les places vides
Un coefficient absent : un zéro.
\(5x_1 - 5x_3 = 10\) donne la ligne \(\begin{bmatrix} 5 & 0 & -5 & 10\end{bmatrix}\).
Opérations sur les lignes
Les trois opérations élémentaires, transposées telles quelles.
Vocabulaire identique, notation identique, effet identique.
Formes échelonnées
Objectif
Une forme où les solutions se lisent.
Matrice échelonnée
Trois conditions :
- Lignes nulles en bas.
- Dans chaque ligne non nulle, le premier coefficient non nul est à droite de celui de la ligne au-dessus.
- En dessous d’un tel coefficient : que des zéros.
\(j(i)\) : colonne du pivot de la ligne \(i\), pour \(i \leqslant r\).
\[j(1) < j(2) < \dots < j(r), \qquad \text{lignes } r+1, \dots, m \ \text{nulles}\]
Pivot
Le premier coefficient non nul d’une ligne : son pivot.
Colonne contenant un pivot : colonne pivot.
Échelonnée
\[ \left[\begin{array}{rrrr} \boxed{2} & -3 & 1 & 4 \\ 0 & \boxed{1} & 5 & -2 \\ 0 & 0 & 0 & \boxed{3} \end{array}\right] \]
Trois pivots. L’escalier descend vers la droite.
Pas échelonnée
\[ \left[\begin{array}{rrrr} 1 & -3 & 1 & 4 \\ 0 & 0 & 0 & 0 \\ 0 & 2 & 5 & -2 \end{array}\right] \]
Ligne nulle au milieu.
Pas échelonnée non plus
\[ \left[\begin{array}{rrrr} 1 & -3 & 1 & 4 \\ 0 & 1 & 5 & -2 \\ 0 & 3 & 0 & 1 \end{array}\right] \]
Un \(3\) sous un pivot.
Échelonnée réduite
Deux conditions de plus :
- Chaque pivot vaut \(1\).
- Un pivot est seul non nul dans sa colonne.
\[\forall i \leqslant r, \quad a_{i,\,j(i)} = 1 \quad \text{et} \quad \forall k \neq i, \ a_{k,\,j(i)} = 0\]
Comparaison
Échelonnée
\[ \left[\begin{array}{rrr} 2 & -3 & 4 \\ 0 & 1 & -2 \\ 0 & 0 & 3 \end{array}\right] \]
Échelonnée réduite
\[ \left[\begin{array}{rrr} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{array}\right] \]
Un résultat important
Unicité Une matrice est équivalente à une seule matrice échelonnée réduite.
La forme échelonnée, elle, dépend du chemin suivi.
Conséquence : la position des pivots ne dépend pas du chemin.
\[\forall A, \ \exists!\ R \ \text{échelonnée réduite} \ : \ A \sim R\]
L’algorithme du pivot
Carl Friedrich Gauss
Méthode publiée en 1810, pour le calcul d’orbites.
Connue en Chine dix-huit siècles plus tôt.
Aujourd’hui : le cœur de tout logiciel de calcul numérique.
Deux phases
Descente — vers la forme échelonnée. Élimination sous les pivots.
Remontée — vers la forme échelonnée réduite. Élimination au-dessus.
Descente, étape par étape
- Colonne non nulle la plus à gauche.
- Un coefficient non nul en tête : par échange si nécessaire. C’est le pivot.
- Élimination de tout ce qui est en dessous, par transvections.
- Ligne du pivot mise de côté. Reprise sur ce qui reste.
Remontée
Pivots parcourus de droite à gauche.
Chacun ramené à \(1\) par dilatation.
Élimination au-dessus, par transvections.
Exemple — l’état initial
\[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 5 & 0 & -5 & 10 \end{array}\right] \]
Premier pivot : le \(1\) en haut à gauche.
Exemple — descente (1)
\(L_3 \leftarrow L_3 - 5L_1\)
\[ \left[\begin{array}{rrr|r} \boxed{1} & -2 & 1 & 0 \\ 0 & 2 & -8 & 8 \\ 0 & 10 & -10 & 10 \end{array}\right] \]
Colonne 1 terminée.
Exemple — descente (2)
\(L_3 \leftarrow L_3 - 5L_2\)
\[ \left[\begin{array}{rrr|r} \boxed{1} & -2 & 1 & 0 \\ 0 & \boxed{2} & -8 & 8 \\ 0 & 0 & 30 & -30 \end{array}\right] \]
Forme échelonnée. Trois pivots.
Exemple — remontée (1)
\(L_2 \leftarrow \tfrac{1}{2}L_2\), \(L_3 \leftarrow \tfrac{1}{30}L_3\)
\[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 1 & -1 \end{array}\right] \]
Pivots à \(1\).
Exemple — remontée (2)
\(L_2 \leftarrow L_2 + 4L_3\), \(L_1 \leftarrow L_1 - L_3\)
\[ \left[\begin{array}{rrr|r} 1 & -2 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{array}\right] \]
Colonne 3 nettoyée.
Exemple — remontée (3)
\(L_1 \leftarrow L_1 + 2L_2\)
\[ \left[\begin{array}{rrr|r} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{array}\right] \]
Forme échelonnée réduite.
Exemple — lecture
\[ \begin{cases} x_1 \phantom{{}+ x_2 + x_3} = \phantom{-}1 \\ \phantom{x_1 + {}} x_2 \phantom{{}+ x_3} = \phantom{-}0 \\ \phantom{x_1 + x_2 + {}} x_3 = -1 \end{cases} \]
Aucun calcul restant. La réponse est écrite.
Choix du pivot
Un pivot \(\neq 0\) suffit en théorie.
En pratique numérique : le plus grand en valeur absolue.
Un petit pivot amplifie les erreurs d’arrondi.
Lire les solutions
Deux sortes d’inconnues
Variable liée — inconnue dont la colonne porte un pivot.
Variable libre — toutes les autres.
\[x_j \ \text{liée} \iff j \in \{\, j(1), \dots, j(r) \,\}, \qquad \text{libres} : n - r\]
Cas 1 — solution unique
\[ \left[\begin{array}{rrr|r} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & -1 \end{array}\right] \]
Trois pivots, trois inconnues. Aucune variable libre.
Cas 2 — aucune solution
\[ \left[\begin{array}{rrr|r} 1 & -2 & 1 & 0 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 0 & \boxed{5} \end{array}\right] \]
Dernière ligne : \(0 = 5\).
Le signal Un pivot dans la colonne du second membre : système incompatible.
\[\text{pivot en colonne } n+1 \iff \mathcal{S} = \emptyset\]
Cas 3 — une infinité
\[ \left[\begin{array}{rrr|r} 1 & 0 & -7 & 8 \\ 0 & 1 & -4 & 4 \\ 0 & 0 & 0 & 0 \end{array}\right] \]
Deux pivots, trois inconnues. \(x_3\) : libre.
Description paramétrique
\[ \begin{cases} x_1 = 8 + 7x_3 \\ x_2 = 4 + 4x_3 \\ x_3 \ \text{libre} \end{cases} \]
\(x_3\) parcourt \(\mathbb{R}\) : une droite de solutions.
Sous forme vectorielle
\[ \begin{aligned} \mathbf{x} &= \begin{pmatrix} 8 + 7t \\ 4 + 4t \\ t \end{pmatrix} = \begin{pmatrix} 8 \\ 4 \\ 0 \end{pmatrix} + t \begin{pmatrix} 7 \\ 4 \\ 1 \end{pmatrix}, \quad t \in \mathbb{R} \end{aligned} \]
Un point de départ, une direction.
Déjà une combinaison linéaire.
\[\mathcal{S} = \bigl\{\, \mathbf{p} + t\,\mathbf{d} \;\bigm|\; t \in \mathbb{R} \,\bigr\}\]
Le théorème
Existence et unicité Système compatible \(\iff\) aucun pivot dans la colonne du second membre.
Solution unique \(\iff\) compatible et aucune variable libre.
\[\mathcal{S} \neq \emptyset \iff \text{aucun pivot en colonne } n+1\]
\[\operatorname{card} \mathcal{S} = 1 \iff \mathcal{S} \neq \emptyset \ \text{ et } \ r = n\]
Récapitulatif
| Pivot dans la dernière colonne | Variables libres | Solutions |
|---|---|---|
| oui | — | aucune |
| non | non | une seule |
| non | oui | une infinité |
Un système à paramètre
\[ \begin{cases} mx_1 + x_2 = 1 \\ \phantom{m}x_1 + x_2 = m \end{cases} \]
\(L_1 \leftarrow L_1 - L_2\) : \((m-1)x_1 = 1 - m\)
\(m \neq 1\) : solution unique. \(m = 1\) : une infinité.
\[m \neq 1 \Rightarrow \operatorname{card} \mathcal{S} = 1, \qquad m = 1 \Rightarrow \operatorname{card} \mathcal{S} = +\infty\]
Retour au milieu de culture
\[ \begin{cases} 20x_1 + 10x_2 \phantom{{}+ 10x_3} = 30 \\ \phantom{2}5x_1 + 20x_2 \phantom{{}+ 10x_3} = 25 \\ \phantom{2}\;\,x_1 + \phantom{1}2x_2 + 10x_3 = 13 \end{cases} \]
\[ (x_1, x_2, x_3) = (1,\; 1,\; 1) \]