06 · Systèmes linéaires et pivot de Gauss

Intuition

Un système linéaire, c'est un ensemble d'équations du premier degré à plusieurs inconnues. Vous en résolvez depuis le collège, par substitution ou par combinaison. Le pivot de Gauss n'est rien d'autre que la méthode par combinaison, organisée : au lieu de bricoler, on suit une procédure fixe qui marche toujours, quel que soit le nombre d'équations.

Cette organisation a deux vertus. Elle évite les erreurs, et surtout elle est programmable — c'est l'algorithme qui résout les systèmes linéaires dans tous les logiciels de calcul, et il est en \(O(n^3)\).

1. Systèmes linéaires

Un système linéaire de \(n\) équations à \(p\) inconnues s'écrit

\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1p}x_p = b_1\\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2p}x_p = b_2\\ \quad\vdots\\ a_{n1}x_1 + a_{n2}x_2 + \dots + a_{np}x_p = b_n \end{cases} \]

Écriture matricielle : \(\mathbf{A}\mathbf{x} = \mathbf{b}\), avec \(\mathbf{A}\) de taille \(n\times p\), \(\mathbf{x}\) le vecteur colonne des inconnues, \(\mathbf{b}\) le second membre.

Les trois cas possibles, et seulement trois

Un système linéaire admet soit aucune solution, soit exactement une, soit une infinité.

Il ne peut jamais en avoir exactement 2, ni 17. La raison est géométrique : si \(\mathbf{x}_1\) et \(\mathbf{x}_2\) sont solutions, tous les points de la droite qui les relie le sont aussi — vérification en exercice.

Un système est dit homogène si \(\mathbf{b} = \mathbf{0}\). Il admet toujours au moins la solution nulle ; la question est de savoir s'il en a d'autres.

2. Opérations élémentaires

Les trois opérations autorisées

Elles transforment un système en un système équivalent — qui a exactement les mêmes solutions.

Notation	Opération	Condition
\(L_i \leftrightarrow L_j\)	Échanger deux lignes	—
\(L_i \leftarrow \lambda L_i\)	Multiplier une ligne par \(\lambda\)	\(\lambda \neq 0\)
\(L_i \leftarrow L_i + \lambda L_j\)	Ajouter à une ligne un multiple d'une autre	\(i \neq j\)

Les deux conditions ne sont pas décoratives

• \(\lambda\neq0\) : multiplier une ligne par 0 la détruit et fait perdre de l'information. Le système obtenu a plus de solutions que l'original.
• \(i\neq j\) : l'opération \(L_i \leftarrow L_i + \lambda L_i\) revient à multiplier par \(1+\lambda\), ce qui est interdit si \(\lambda = -1\).

Notez aussi que \(L_i \leftarrow \lambda L_i + \mu L_j\) exige \(\lambda\neq0\) : c'est l'erreur la plus fréquente en pratique, quand on combine deux lignes en oubliant que celle qu'on écrase doit survivre.

3. La matrice augmentée

Pour éviter de recopier les inconnues à chaque étape, on travaille sur le tableau des coefficients complété par le second membre :

\[ \left(\begin{array}{ccc|c} a_{11}&a_{12}&a_{13}&b_1\\ a_{21}&a_{22}&a_{23}&b_2\\ a_{31}&a_{32}&a_{33}&b_3 \end{array}\right) \]

Les opérations sur les lignes du système deviennent des opérations sur les lignes de ce tableau.

4. L'algorithme du pivot de Gauss

Objectif

Transformer la matrice en une forme échelonnée : chaque ligne commence par strictement plus de zéros que la précédente. Le système devient alors résoluble « en remontant ».

Procédure, colonne par colonne :

1. Dans la colonne courante, choisir un coefficient non nul — le pivot. Si toute la colonne (sous la ligne courante) est nulle, passer à la colonne suivante.
2. Amener le pivot sur la ligne courante par un échange si nécessaire.
3. Annuler tous les coefficients situés en dessous du pivot, par des opérations \(L_i \leftarrow L_i - \frac{a_{ik}}{\text{pivot}} L_{\text{pivot}}\).
4. Descendre d'une ligne, avancer d'une colonne, recommencer.

Puis remontée : on résout la dernière équation, on reporte dans l'avant-dernière, etc.

4.1 Exemple complet

\[ \begin{cases} x + 2y - z = 3\\ 2x - y + 3z = 1\\ -x + 3y + 2z = 4 \end{cases} \]

\[ \left(\begin{array}{ccc|c} 1&2&-1&3\\ 2&-1&3&1\\ -1&3&2&4 \end{array}\right) \]

Étape 1 — pivot \(= 1\) en position \((1,1)\). On annule dessous : \(L_2 \leftarrow L_2 - 2L_1\) et \(L_3\leftarrow L_3+L_1\).

\[ \left(\begin{array}{ccc|c} 1&2&-1&3\\ 0&-5&5&-5\\ 0&5&1&7 \end{array}\right) \]

Simplification — \(L_2\leftarrow -\frac15 L_2\) (licite, \(-\frac15\neq0\)) :

\[ \left(\begin{array}{ccc|c} 1&2&-1&3\\ 0&1&-1&1\\ 0&5&1&7 \end{array}\right) \]

Étape 2 — pivot \(= 1\) en position \((2,2)\). On annule dessous : \(L_3\leftarrow L_3 - 5L_2\).

\[ \left(\begin{array}{ccc|c} 1&2&-1&3\\ 0&1&-1&1\\ 0&0&6&2 \end{array}\right) \]

Forme échelonnée atteinte. Remontée :

• \(L_3\) : \(6z = 2\), donc \(z = \frac13\) ;
• \(L_2\) : \(y - z = 1\), donc \(y = 1+\frac13 = \frac43\) ;
• \(L_1\) : \(x + 2y - z = 3\), donc \(x = 3 - \frac83 + \frac13 = \frac{9-8+1}{3} = \frac23\).

\[ (x,y,z) = \left(\tfrac23, \tfrac43, \tfrac13\right) \]

Vérification dans l'équation 2 (celle qui n'a pas servi à la remontée) : \(2(\frac23) - \frac43 + 3(\frac13) = \frac43-\frac43+1 = 1\) ✓

Vérifiez toujours

Reportez la solution dans une équation du système d'origine, de préférence celle que vous n'avez pas utilisée en dernier. C'est trente secondes et cela attrape toutes les erreurs de calcul.

5. Lire le résultat : rang et cas dégénérés

Le nombre de pivots obtenus s'appelle le rang du système, noté \(r\).

La règle de lecture

Après échelonnement d'un système à \(p\) inconnues :

Situation	Conclusion
Une ligne \((0\ 0\ \cdots\ 0 \mid c)\) avec \(c \neq 0\)	Aucune solution — le système est incompatible
Pas de telle ligne, et \(r = p\)	Solution unique
Pas de telle ligne, et \(r < p\)	Infinité de solutions, décrites par \(p - r\) paramètres

Une ligne \((0\ 0\ 0 \mid 5)\) signifie « \(0 = 5\) » : c'est une contradiction. Une ligne \((0\ 0\ 0\mid 0)\) signifie « \(0=0\) » : elle est redondante, on la supprime.

5.1 Systèmes à infinité de solutions

Les inconnues associées à un pivot sont les inconnues principales ; les autres sont les paramètres, qu'on note souvent \(t\), \(s\)…

Exemple.

\[ \left(\begin{array}{ccc|c} 1&2&3&4\\ 0&1&2&1\\ 0&0&0&0 \end{array}\right) \]

Rang 2, trois inconnues : un paramètre. Pivots en colonnes 1 et 2, donc \(z\) est libre. Posons \(z = t\).

• \(L_2\) : \(y = 1-2t\) ;
• \(L_1\) : \(x = 4 - 2(1-2t) - 3t = 2 + t\).

\[ \mathcal{S} = \left\{ (2+t,\ 1-2t,\ t) \ \middle|\ t\in\mathbb{R}\right\} \]

Écriture vectorielle, plus parlante :

\[ \begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}2\\1\\0\end{pmatrix} + t\begin{pmatrix}1\\-2\\1\end{pmatrix} \]

C'est une droite de l'espace : un point particulier plus la direction.

La structure des solutions

L'ensemble des solutions de \(\mathbf{Ax}=\mathbf{b}\), quand il est non vide, est toujours de la forme

\[ \{\text{une solution particulière}\} + \{\text{solutions du système homogène}\} \]

C'est le même schéma que pour les équations différentielles, et ce n'est pas une analogie : c'est le même théorème sur les applications linéaires.

6. Choix du pivot et stabilité numérique

En calcul exact (fractions), n'importe quel pivot non nul convient — on choisit le plus commode, souvent un 1.

En calcul flottant, le choix compte énormément.

Le pivot partiel

Un pivot très petit produit des multiplicateurs \(\frac{a_{ik}}{\text{pivot}}\) très grands, qui amplifient les erreurs d'arrondi.

La stratégie de pivot partiel consiste à choisir, dans la colonne courante, le coefficient de plus grande valeur absolue. C'est ce que font toutes les implémentations sérieuses.

Exemple de catastrophe. En arithmétique à 3 chiffres significatifs :

\[ \begin{cases} 0{,}001\,x + y = 1\\ x + y = 2 \end{cases} \]

Sans échange, le multiplicateur vaut 1000 : \(L_2 \leftarrow L_2 - 1000 L_1\) donne \(-999y = -998\), soit \(y \approx 0{,}999\), puis \(x = \frac{1 - 0{,}999}{0{,}001} = 1\). Avec seulement 3 chiffres, \(y\) est arrondi à \(1{,}00\) et l'on obtient \(x = 0\) — au lieu de \(x \approx 1\).

Avec échange des lignes d'abord, le multiplicateur vaut \(0{,}001\) et le résultat est correct.

Coût de l'algorithme

Le pivot de Gauss demande environ \(\dfrac{2n^3}{3}\) opérations pour un système \(n\times n\). C'est bien mieux que les formules de Cramer, en \(O(n!)\), qu'on verra au chapitre 07 — et c'est la raison pour laquelle Cramer ne sert jamais en pratique.

Exemples traités

Exemple 1 — Système sans solution

\[ \begin{cases} x + y + z = 1\\ 2x+2y+2z = 3 \end{cases} \]

\(L_2\leftarrow L_2 - 2L_1\) :

\[ \left(\begin{array}{ccc|c}1&1&1&1\\0&0&0&1\end{array}\right) \]

La seconde ligne dit \(0 = 1\). Aucune solution.

Lecture géométrique : les deux équations décrivent des plans parallèles distincts. Ils ne se coupent pas.

Exemple 2 — Discussion selon un paramètre

Discuter, selon \(m\in\mathbb{R}\), le système

\[ \begin{cases} x + y = 1\\ x + m y = m \end{cases} \]

\(L_2\leftarrow L_2-L_1\) :

\[ \left(\begin{array}{cc|c}1&1&1\\0&m-1&m-1\end{array}\right) \]

Cas \(m \neq 1\). On peut diviser : \(y = 1\), puis \(x = 0\). Solution unique \((0,1)\).

Cas \(m = 1\). La seconde ligne devient \((0\ 0\mid 0)\) : elle disparaît. Il reste \(x+y=1\), soit une infinité de solutions : \(\{(1-t, t) \mid t\in\mathbb{R}\}\).

Le réflexe des discussions

À chaque fois que vous divisez par une expression contenant le paramètre, arrêtez-vous et traitez séparément le cas où elle s'annule. C'est là que se trouvent tous les points de l'exercice.

Exemple 3 — Système \(3\times4\)

\[ \begin{cases} x + y + z + t = 4\\ 2x + y - z + t = 2\\ x + 2y + 4z + 2t = 10 \end{cases} \]

\[ \left(\begin{array}{cccc|c} 1&1&1&1&4\\2&1&-1&1&2\\1&2&4&2&10 \end{array}\right) \]

\(L_2\leftarrow L_2-2L_1\), \(L_3\leftarrow L_3-L_1\) :

\[ \left(\begin{array}{cccc|c} 1&1&1&1&4\\0&-1&-3&-1&-6\\0&1&3&1&6 \end{array}\right) \]

\(L_3\leftarrow L_3+L_2\) :

\[ \left(\begin{array}{cccc|c} 1&1&1&1&4\\0&-1&-3&-1&-6\\0&0&0&0&0 \end{array}\right) \]

Rang 2, quatre inconnues : deux paramètres. Les pivots sont en colonnes 1 et 2, donc \(z\) et \(t\) sont libres. Posons \(z = s\), \(t = u\).

• \(L_2\) : \(-y-3s-u = -6\), donc \(y = 6-3s-u\) ;
• \(L_1\) : \(x = 4 - y - s - u = 4-(6-3s-u)-s-u = -2+2s\).

\[ \begin{pmatrix}x\\y\\z\\t\end{pmatrix} = \begin{pmatrix}-2\\6\\0\\0\end{pmatrix} + s\begin{pmatrix}2\\-3\\1\\0\end{pmatrix} + u\begin{pmatrix}0\\-1\\0\\1\end{pmatrix} \]

Vérification avec \(s=u=0\) : \((-2,6,0,0)\). Équation 1 : \(-2+6 = 4\) ✓ Équation 3 : \(-2+12 = 10\) ✓

Erreurs fréquentes

Erreur	Conséquence
\(L_i \leftarrow \lambda L_i + \mu L_j\) avec \(\lambda = 0\)	Perte d'information, solutions parasites
Modifier deux lignes « en même temps » avec elles-mêmes	Système non équivalent
Oublier de traiter le cas où le pivot s'annule (paramètre)	La discussion est fausse
Prendre \(r\) paramètres au lieu de \(p-r\)	Mauvais nombre de degrés de liberté
Ne pas vérifier la solution	Erreur de calcul non détectée

Exercices

★ Exercice 1. Résoudre par le pivot de Gauss.

\[ \text{a) } \begin{cases}x+y=5\\2x-y=1\end{cases} \qquad \text{b) } \begin{cases}3x+2y=7\\6x+4y=14\end{cases} \]

★ Exercice 2. Résoudre.

\[ \begin{cases} x+y+z=6\\ 2x - y + z = 3\\ x + 2y - z = 2 \end{cases} \]

★★ Exercice 3. Résoudre et donner l'ensemble des solutions sous forme vectorielle.

\[ \begin{cases} x + 2y - z = 1\\ 2x + 4y - 2z = 2\\ -x-2y+z=-1 \end{cases} \]

★★ Exercice 4. Déterminer pour quelles valeurs de \(a\) le système suivant a une solution unique, aucune, ou une infinité.

\[ \begin{cases} x + y + z = 1\\ x + 2y + 3z = 2\\ x + 4y + a z = 4 \end{cases} \]

★★ Exercice 5. Résoudre le système homogène

\[ \begin{cases} x - 2y + 3z = 0\\ 2x - y + z = 0\\ x + y - 2z = 0 \end{cases} \]

et interpréter géométriquement le résultat.

★★★ Exercice 6. Un atelier fabrique trois produits A, B, C. Chaque unité consomme :

	Matière (kg)	Main-d'œuvre (h)	Machine (h)
A	2	1	3
B	1	3	1
C	4	2	2

On dispose de 120 kg de matière, 100 h de main-d'œuvre, 130 h de machine, et on veut tout consommer exactement.

a) Écrire le système et le résoudre. b) La solution est-elle acceptable (les quantités doivent être positives) ?

★★★ Exercice 7. Soient \(\mathbf{x}_1\) et \(\mathbf{x}_2\) deux solutions distinctes de \(\mathbf{Ax}=\mathbf b\).

a) Montrer que \(\mathbf{x}_1 - \mathbf{x}_2\) est solution du système homogène. b) Montrer que pour tout \(t\in\mathbb{R}\), \(\mathbf{x}_1 + t(\mathbf{x}_2-\mathbf{x}_1)\) est solution de \(\mathbf{Ax}=\mathbf b\). c) En déduire qu'un système linéaire ne peut avoir exactement 2 solutions.

★★★ Exercice 8. Trouver le polynôme \(P(x) = ax^2+bx+c\) passant par les points \((1,6)\), \((2,11)\), \((3,18)\).

Généraliser : combien de points faut-il pour déterminer un polynôme de degré \(n\), et pourquoi le système correspondant a-t-il toujours une solution unique ?

★★★★ Exercice 9. Résoudre, en discutant selon \(m\) :

\[ \begin{cases} m x + y + z = 1\\ x + m y + z = m\\ x + y + m z = m^2 \end{cases} \]

★★★★ Exercice 10 — lien informatique. Écrire, en pseudo-code, l'algorithme du pivot de Gauss avec pivot partiel pour un système \(n\times n\).

a) Donner le nombre exact d'opérations arithmétiques (multiplications et divisions) de la phase d'élimination, en fonction de \(n\). b) Vérifier que ce nombre est \(\sim \frac{n^3}{3}\). c) Sur une machine effectuant \(10^{10}\) opérations flottantes par seconde, estimer le temps pour \(n = 10^4\). Comparer avec \(n=10^5\). d) Pourquoi le stockage devient-il un problème avant le temps de calcul ?

---

Corrigés

Corrigé — Exercice 1

a) \(L_2\leftarrow L_2-2L_1\) :

\[ \left(\begin{array}{cc|c}1&1&5\\0&-3&-9\end{array}\right) \]

\(y = 3\), puis \(x = 2\). \(\mathcal{S} = \{(2,3)\}\).

Vérification : \(2+3=5\) ✓ et \(4-3=1\) ✓

b) \(L_2\leftarrow L_2-2L_1\) :

\[ \left(\begin{array}{cc|c}3&2&7\\0&0&0\end{array}\right) \]

Rang 1, deux inconnues : un paramètre. Avec \(y=t\) : \(x = \frac{7-2t}{3}\).

\[ \mathcal{S} = \left\{\left(\tfrac{7-2t}{3},\ t\right) \ \middle|\ t\in\mathbb{R}\right\} \]

Les deux équations décrivent la même droite.

Corrigé — Exercice 2

\[ \left(\begin{array}{ccc|c}1&1&1&6\\2&-1&1&3\\1&2&-1&2\end{array}\right) \]

\(L_2\leftarrow L_2-2L_1\), \(L_3\leftarrow L_3-L_1\) :

\[ \left(\begin{array}{ccc|c}1&1&1&6\\0&-3&-1&-9\\0&1&-2&-4\end{array}\right) \]

\(L_3\leftarrow 3L_3+L_2\) :

\[ \left(\begin{array}{ccc|c}1&1&1&6\\0&-3&-1&-9\\0&0&-7&-21\end{array}\right) \]

\(z = 3\) ; \(-3y - 3 = -9\) donne \(y = 2\) ; \(x + 2+3 = 6\) donne \(x = 1\).

\(\mathcal{S} = \{(1,2,3)\}\).

Vérification équation 2 : \(2-2+3 = 3\) ✓

Corrigé — Exercice 3

\(L_2\leftarrow L_2-2L_1\), \(L_3\leftarrow L_3+L_1\) :

\[ \left(\begin{array}{ccc|c}1&2&-1&1\\0&0&0&0\\0&0&0&0\end{array}\right) \]

Les trois équations sont proportionnelles. Rang 1, trois inconnues : deux paramètres. Avec \(y=s\), \(z=u\) : \(x = 1-2s+u\).

\[ \begin{pmatrix}x\\y\\z\end{pmatrix} = \begin{pmatrix}1\\0\\0\end{pmatrix} + s\begin{pmatrix}-2\\1\\0\end{pmatrix} + u\begin{pmatrix}1\\0\\1\end{pmatrix} \]

C'est un plan de l'espace — les trois équations décrivaient le même plan.

Corrigé — Exercice 4

\(L_2\leftarrow L_2-L_1\), \(L_3\leftarrow L_3-L_1\) :

\[ \left(\begin{array}{ccc|c}1&1&1&1\\0&1&2&1\\0&3&a-1&3\end{array}\right) \]

\(L_3\leftarrow L_3-3L_2\) :

\[ \left(\begin{array}{ccc|c}1&1&1&1\\0&1&2&1\\0&0&a-7&0\end{array}\right) \]

Cas \(a\neq7\). Le pivot \(a-7\) est non nul : \(z = 0\), puis \(y = 1\), puis \(x = 0\). Solution unique \((0,1,0)\).

Cas \(a = 7\). La dernière ligne est \((0\ 0\ 0\mid0)\) : elle disparaît. Rang 2, trois inconnues, un paramètre. Avec \(z=t\) : \(y = 1-2t\) et \(x = 1-y-z = t\).

\[ \mathcal{S} = \{(t,\ 1-2t,\ t)\mid t\in\mathbb{R}\} \]

Il n'y a jamais de cas « aucune solution » : le second membre de la troisième ligne s'annule quoi qu'il arrive.

Corrigé — Exercice 5

\[ \left(\begin{array}{ccc|c}1&-2&3&0\\2&-1&1&0\\1&1&-2&0\end{array}\right) \]

\(L_2\leftarrow L_2-2L_1\), \(L_3\leftarrow L_3-L_1\) :

\[ \left(\begin{array}{ccc|c}1&-2&3&0\\0&3&-5&0\\0&3&-5&0\end{array}\right) \]

\(L_3\leftarrow L_3-L_2\) donne une ligne nulle. Rang 2, un paramètre.

Avec \(z = 3t\) (choisi pour éviter les fractions) : \(3y = 5(3t)\) donne \(y = 5t\) ; puis \(x = 2(5t) - 3(3t) = t\).

\[ \mathcal{S} = \left\{ t\begin{pmatrix}1\\5\\3\end{pmatrix} \ \middle|\ t\in\mathbb{R}\right\} \]

Interprétation. Les trois équations décrivent trois plans passant par l'origine. Ils ne se coupent pas en un point unique mais selon une droite — celle dirigée par \((1,5,3)\). Autrement dit, les trois plans appartiennent à un même faisceau.

Corrigé — Exercice 6

a) Avec \(x, y, z\) les quantités de A, B, C :

\[ \begin{cases} 2x + y + 4z = 120\\ x + 3y + 2z = 100\\ 3x + y + 2z = 130 \end{cases} \]

\[ \left(\begin{array}{ccc|c}2&1&4&120\\1&3&2&100\\3&1&2&130\end{array}\right) \]

Échangeons \(L_1\leftrightarrow L_2\) pour avoir un pivot égal à 1 :

\[ \left(\begin{array}{ccc|c}1&3&2&100\\2&1&4&120\\3&1&2&130\end{array}\right) \]

\(L_2\leftarrow L_2-2L_1\), \(L_3\leftarrow L_3-3L_1\) :

\[ \left(\begin{array}{ccc|c}1&3&2&100\\0&-5&0&-80\\0&-8&-4&-170\end{array}\right) \]

\(L_2\) donne directement \(y = 16\).

\(L_3\) : \(-8(16) - 4z = -170\), soit \(-128-4z = -170\), soit \(z = 10{,}5\).

\(L_1\) : \(x = 100 - 48 - 21 = 31\).

\[ (x,y,z) = (31,\ 16,\ 10{,}5) \]

Vérification dans l'équation matière : \(62+16+42 = 120\) ✓

b) Les trois quantités sont positives, donc la solution est mathématiquement acceptable. En revanche \(z = 10{,}5\) n'est un nombre d'unités valide que si le produit C est divisible — sinon il faudrait résoudre en nombres entiers, ce qui relève de la programmation linéaire en nombres entiers, au programme de recherche opérationnelle en deuxième année.

Corrigé — Exercice 7

a) \(\mathbf{A}(\mathbf x_1-\mathbf x_2) = \mathbf{Ax}_1 - \mathbf{Ax}_2 = \mathbf b - \mathbf b = \mathbf 0\) ✓

(On a utilisé la linéarité du produit matriciel.)

b) Posons \(\mathbf x = \mathbf x_1 + t(\mathbf x_2-\mathbf x_1)\).

\[ \mathbf{Ax} = \mathbf{Ax}_1 + t\,\mathbf A(\mathbf x_2-\mathbf x_1) = \mathbf b + t\cdot\mathbf 0 = \mathbf b \]

✓

c) Supposons le système ait au moins deux solutions distinctes \(\mathbf x_1 \neq \mathbf x_2\). Alors par b), tous les \(\mathbf x_1 + t(\mathbf x_2-\mathbf x_1)\) sont solutions, pour \(t\in\mathbb{R}\).

Ces vecteurs sont deux à deux distincts : si \(\mathbf x_1+t(\mathbf x_2-\mathbf x_1) = \mathbf x_1+t'(\mathbf x_2-\mathbf x_1)\) alors \((t-t')(\mathbf x_2-\mathbf x_1)=\mathbf 0\), et comme \(\mathbf x_2\neq\mathbf x_1\), on a \(t=t'\).

Il y a donc une infinité de solutions. \(\blacksquare\)

Le résultat

Un système linéaire a 0, 1 ou une infinité de solutions. Jamais 2, jamais 17. C'est ce qui distingue le linéaire du non linéaire : \(x^2 = 4\) a exactement deux solutions.

Corrigé — Exercice 8

Les conditions \(P(1)=6\), \(P(2)=11\), \(P(3)=18\) donnent

\[ \begin{cases} a+b+c=6\\ 4a+2b+c=11\\ 9a+3b+c=18 \end{cases} \]

\(L_2\leftarrow L_2-L_1\), \(L_3\leftarrow L_3-L_1\) :

\[ \left(\begin{array}{ccc|c}1&1&1&6\\3&1&0&5\\8&2&0&12\end{array}\right) \]

\(L_3\leftarrow L_3 - 2L_2\) : \((2\ 0\ 0\mid2)\), donc \(a = 1\). Puis \(L_2\) : \(3+b = 5\), donc \(b = 2\). Puis \(c = 6-1-2 = 3\).

\[ P(x) = x^2+2x+3 \]

Vérification : \(P(2) = 4+4+3 = 11\) ✓, \(P(3)=9+6+3=18\) ✓

Généralisation. Un polynôme de degré \(n\) a \(n+1\) coefficients : il faut donc \(n+1\) points d'abscisses distinctes.

La matrice du système est la matrice de Vandermonde

\[ \mathbf V = \begin{pmatrix} x_0^n & \cdots & x_0 & 1\\ \vdots & & \vdots & \vdots\\ x_n^n & \cdots & x_n & 1 \end{pmatrix} \]

dont le déterminant vaut \(\prod_{i<j}(x_j-x_i)\) — non nul dès que les abscisses sont deux à deux distinctes. Le système admet donc toujours une solution unique, ce qui est le théorème d'interpolation de Lagrange. On reverra ce déterminant au chapitre 07.

Corrigé — Exercice 9

\[ \left(\begin{array}{ccc|c}m&1&1&1\\1&m&1&m\\1&1&m&m^2\end{array}\right) \]

Échangeons pour placer un pivot sûr : \(L_1\leftrightarrow L_3\).

\[ \left(\begin{array}{ccc|c}1&1&m&m^2\\1&m&1&m\\m&1&1&1\end{array}\right) \]

\(L_2\leftarrow L_2-L_1\), \(L_3\leftarrow L_3-mL_1\) :

\[ \left(\begin{array}{ccc|c} 1&1&m&m^2\\ 0&m-1&1-m&m-m^2\\ 0&1-m&1-m^2&1-m^3 \end{array}\right) \]

Remarquons \(m-m^2 = -m(m-1)\) et \(1-m = -(m-1)\), donc \(L_2 = (m-1)\cdot(0,\ 1,\ -1 \mid -m)\).

\(L_3\leftarrow L_3+L_2\) :

\[ L_3 = \big(0,\ 0,\ (1-m^2)+(1-m) \ \big|\ (1-m^3)+(m-m^2)\big) \]

\[ = \big(0,\ 0,\ (1-m)(m+2) \ \big|\ (1-m)(1+m+m^2) + (1-m)m \big) \]

\[ = (1-m)\cdot\big(0,\ 0,\ m+2 \ \big|\ 1+2m+m^2\big) = (1-m)\cdot\big(0,0,m+2\mid (m+1)^2\big) \]

Cas 1 : \(m\neq1\) et \(m\neq-2\). On peut diviser \(L_2\) par \(m-1\) et \(L_3\) par \((1-m)(m+2)\). Le système est de rang 3 : solution unique.

\(L_3\) : \(z = \dfrac{(m+1)^2}{m+2}\).

\(L_2\) : \(y - z = -m\), donc \(y = z - m = \dfrac{(m+1)^2 - m(m+2)}{m+2} = \dfrac{1}{m+2}\).

\(L_1\) : \(x = m^2 - y - mz = m^2 - \dfrac{1 + m(m+1)^2}{m+2} = \dfrac{m^3+2m^2-1-m^3-2m^2-m}{m+2} = \dfrac{-(m+1)}{m+2}\).

\[ (x,y,z) = \left(\frac{-(m+1)}{m+2},\ \frac{1}{m+2},\ \frac{(m+1)^2}{m+2}\right) \]

Vérification \(m=0\) : \((-\frac12, \frac12, \frac12)\). Équation 1 : \(0 + \frac12+\frac12 = 1\) ✓

Cas 2 : \(m=1\). Le système devient trois fois \(x+y+z=1\). Rang 1, infinité de solutions à deux paramètres : c'est un plan.

Cas 3 : \(m=-2\). \(L_3\) devient \((0,0,0\mid 3\times1)\), soit après simplification du facteur \((1-m)=3\) : \(0 = (m+1)^2 = 1 \neq 0\). Aucune solution.

Le squelette d'une discussion

Échelonner en gardant les facteurs apparents, repérer les valeurs du paramètre qui annulent un pivot, puis traiter chacune séparément. Les points de l'exercice sont dans les cas particuliers, pas dans le cas générique.

Corrigé — Exercice 10

Pseudo-code.

pour k de 1 à n-1 :
    # pivot partiel
    p ← argmax_{i ≥ k} |A[i][k]|
    si A[p][k] == 0 : continuer      # colonne nulle
    échanger ligne k et ligne p
    pour i de k+1 à n :
        m ← A[i][k] / A[k][k]        # 1 division
        A[i][k] ← 0
        pour j de k+1 à n :
            A[i][j] ← A[i][j] − m·A[k][j]   # 1 multiplication
        b[i] ← b[i] − m·b[k]                # 1 multiplication

a) Comptage. À l'étape \(k\), il y a \(n-k\) lignes à traiter. Pour chacune : 1 division, puis \((n-k)\) multiplications pour les colonnes \(k+1..n\), plus 1 pour le second membre. Soit \((n-k+2)\) opérations par ligne.

\[ N(n) = \sum_{k=1}^{n-1}(n-k)\,(n-k+2) \]

Posons \(j = n-k\), qui va de \(n-1\) à 1 :

\[ N(n) = \sum_{j=1}^{n-1} j(j+2) = \sum_{j=1}^{n-1}j^2 + 2\sum_{j=1}^{n-1}j \]

\[ = \frac{(n-1)n(2n-1)}{6} + 2\cdot\frac{(n-1)n}{2} = \frac{(n-1)n(2n-1)}{6} + n(n-1) \]

b) Le terme dominant est \(\dfrac{2n^3}{6} = \dfrac{n^3}{3}\). Les termes en \(n^2\) et \(n\) sont négligeables devant lui quand \(n\) grandit :

\[ N(n) \sim \frac{n^3}{3} \]

Vérification \(n=3\) : formule exacte \(\frac{2\cdot3\cdot5}{6}+3\cdot2 = 5+6 = 11\). Comptage direct : étape 1, 2 lignes × 4 opérations = 8 ; étape 2, 1 ligne × 3 = 3. Total 11 ✓

c) Pour \(n = 10^4\) :

\[ \frac{(10^4)^3}{3} = \frac{10^{12}}{3} \approx 3{,}3\times10^{11} \text{ opérations} \]

À \(10^{10}\) op/s : environ 33 secondes.

Pour \(n = 10^5\) : \(\frac{10^{15}}{3} \approx 3{,}3\times10^{14}\) opérations, soit \(3{,}3\times10^4\) s \(\approx\) 9 heures.

Multiplier la taille par 10 multiplie le temps par 1000 — signature du cube.

d) Le stockage. Une matrice \(n\times n\) en double précision occupe \(8n^2\) octets.

\(n\)	Mémoire
\(10^4\)	800 Mo
\(10^5\)	80 Go
\(10^6\)	8 To

À \(n = 10^5\), la matrice ne tient plus en mémoire vive sur une machine ordinaire, alors que le calcul ne prendrait « que » neuf heures. C'est le stockage qui bloque en premier.

C'est pourquoi les gros systèmes réels ne sont jamais résolus par Gauss dense : on exploite le fait qu'ils sont creux (la plupart des coefficients sont nuls) et l'on utilise des méthodes itératives — gradient conjugué, GMRES — qui ne stockent jamais la matrice complète. C'est précisément le contenu du module d'analyse numérique de la filière étudiante, et le point de départ de l'optimisation numérique du semestre 3.

---

Chapitre suivant : Déterminant.