162 Systèmes d’équations linéaires ; opérations élémentaires, aspects algorithmiques et conséquences théoriques.

Systèmes d’équations linéaires ; opérations élémentaires, aspects algorithmiques et conséquences théoriques.

algebra

Soit $K$ un corps commutatif.

Généralités

Définitions

[GRI]
p. 143

Définition 1.

On appelle système linéaire à $p$ équations en $n$ inconnues, un système d’équations de la forme $⎩ ⎨ ⎧ a_{1, 1} x_{1} + \dots + a_{1, n} x_{n} = b_{1} ⋮ a_{p, 1} x_{1} + \dots + a_{1, n} x_{n} = b_{p} (S)$ où $\forall i \in [[1, p]], \forall j \in [[1, n]], a_{i, j} \in K, b_{i} \in K$ .
On appelle solution de $(S)$ tout vecteur $x = (x_{1}, \dots, x_{n}) \in K^{n}$ dont les composantes $(x_{i})_{i \in [[1, n]]}$ satisfont toutes les équations.
$(S)$ est dit compatible s’il admet au moins une solution.

p. 38

Exemple 2. Le système ci-dessous est linéaire, $⎩ ⎨ ⎧ 2 x + y - 2 z + 3 w = 1 3 x + 2 y - z + 2 w = 4 3 x + 3 y + 3 z - 3 w = 5$ il n’est pas compatible.

Écriture sous forme matricielle

p. 144

Proposition 3. On considère le système $(S)$ de la Définition 1. On peut l’écrire sous forme matricielle $A X = B (S)$ avec $A = (a_{i, j})_{i \in [[1, p]] j \in [[1, n]]} \in M_{p, n} (K)$ , $X = (x_{j})_{j \in [[1, n]]} \in M_{n, 1} (K)$ et $B = (b_{i})_{i \in [[1, p]]} \in M_{p, 1} (K)$ .

Définition 4. On appelle rang du système $(S)$ le rang de la matrice $A$ .

Proposition 5. Soit $A X = B$ un système linéaire à $n$ équations et $n$ inconnues. Si $A$ est inversible, on a une unique solution, donnée par $X = A^{- 1} B$ .

Étude de systèmes particuliers

Systèmes de Cramer

Définition 6. On appelle système de Cramer, un système linéaire à $n$ équations et $n$ inconnues $A X = B$ .

Théorème 7 (Formules de Cramer). Un système de Cramer $A X = B$ admet une unique solution donnée par $X = (x_{i})_{i \in [[1, n]]}$ où $\forall i \in [[1, n]], x_{i} = \frac{det ( A _{i} )}{det ( A )}$ avec $A_{i}$ obtenue en remplaçant la $i$ -ième colonne de $A$ par $B$ .

Exemple 8. Le système $⎩ ⎨ ⎧ 2 x - 5 y + 2 z = 7 x + 2 y - 4 z = 3 3 x - 4 y - 6 z = 5$ est de Cramer, son unique solution est $(5, 1, 1)$ .

Équations de Sylvester

[I-P]
p. 177

Lemme 9. Soit $∥.∥$ une norme d’algèbre sur $M_{n} (C)$ , et soit $A \in M_{n} (C)$ une matrice dont les valeurs propres sont de partie réelle strictement négative. Alors il existe une fonction polynômiale $P : R \to R$ et $λ > 0$ tels que $∥ e^{t A} ∥ \leq e^{- λ t} P (t)$ .

equation-de-sylvester

Application 10 (Équation de Sylvester). Soient $A$ et $B \in M_{n} (C)$ deux matrices dont les valeurs propres sont de partie réelle strictement négative. Alors pour tout $C \in M_{n} (C)$ , l’équation $A X + XB = C$ admet une unique solution $X$ dans $M_{n} (C)$ .

Méthodes générales de résolution

Théorème de Rouché-Fontené

[GOU21]
p. 144

Lemme 11. Soit $A \in M_{p, n} (K)$ . Soit $r = rang (A)$ . Il existe un déterminant $Δ$ d’ordre $r$ extrait de $A$ .

Définition 12.

Le déterminant $Δ$ précédent est le déterminant principal de $A$ .
Les équations (resp. inconnues) dont les indices sont deux des lignes (resp. colonnes) de $Δ$ s’appellent les équations principales (resp. inconnues principales).
Si $Δ = det (a_{i, j})_{i \in I j \in J}$ , on appelle déterminants caractéristiques les déterminants d’ordre $r + 1$ de la forme

$(a_{i, j})_{i \in I j \in J}$ $(b_{i})_{i \in I}$

$(a_{k, j})_{j \in J}$ $b_{k}$

avec $k \in / J$ .

$(a_{i, j})_{i \in I j \in J}$	$(b_{i})_{i \in I}$
$(a_{k, j})_{j \in J}$	$b_{k}$

Théorème 13 (Rouché-Fontené). Un système de rang $r$ $A X = B$ avec $A \in M_{p, n} (K)$ , $X \in M_{n, 1} (K)$ et $B \in M_{1, p} (K)$ admet des solutions si et seulement si $p = r$ ou les $p - r$ déterminants caractéristiques sont nuls. Le système est alors équivalent au système des équations principales. Les inconnues principales étant déterminées par un système de Cramer à l’aide des inconnues non principales.

Exemple 14. Si, $(S) ⟺ ⎩ ⎨ ⎧ x + 2 y + z + t = 1 x - z - t = 1 - x + y + z + 2 t = m m \in R$ on a $rang (A) = 2$ , $(S)$ admet des solutions si et seulement si $m = - 1$ , et $(S) ⟺ {x + 2 y = 1 + z - t x = 1 + z + t ⟺ {x = 1 + z + t y = - t$

Algorithme du pivot de Gauss

Opérations élémentaires

[ROM21]
p. 186

Définition 15. Soit $A = (a_{i, j})_{i \in [[1, n]] j \in [[1, m]]} \in M_{n, m} (K)$ .

On dit que $A$ est échelonnée en lignes si elle est nulle ou si elle est non nulle et il existe un entier $r$ compris entre $1$ et $n$ tel que :
- Les $r$ premières lignes de $A$ sont non nulles.
- Les $n - r$ dernières lignes de $A$ sont nulles.
- En notant $\forall i \in [[1, n]], d_{i} = min {j \in [[1, m]] ∣ a_{i, j} \neq = 0}$ , on a $1 \leq d_{1} < d_{2} < \dots < d_{r} \leq m$
On dit que $A$ est échelonnée en colonnes si $(^{t} A$ est échelonnée en lignes.

Proposition 16. Avec les notations précédentes, si $A$ est échelonnée en lignes, alors $rang (A) = r$ .

Définition 17. On dit qu’un système linéaire $A X = B$ est échelonné si la matrice $A$ est échelonnée en lignes.

Théorème 18.

La multiplication à gauche par une matrice de dilatation $D_{i} (λ)$ (obtenue à partir de la matrice identité en remplaçant le coefficient $1$ à la $i$ -ième ligne par $λ$ ) a pour effet de multiplier la ligne $i$ par $λ$ .
La multiplication à gauche par une matrice de transvection $T_{i, j} (λ)$ (obtenue à partir de la matrice identité en remplaçant le coefficient $0$ à la $i$ -ième ligne et $j$ -ième colonne par $λ$ ) a pour effet de multiplier la ligne $i$ par la somme de la ligne $i$ et de la ligne $j$ multipliée par $λ$ .
La multiplication à droite fait des effets similaires sur les colonnes.

Remarque 19. Pour effectuer une permutation des lignes $i$ et $j$ , il suffit de multiplier à gauche par $D_{j} (- 1) T_{i, j} (1) T_{j, i} (- 1) T_{i, j} (1)$

Définition 20. On appelle opération élémentaire une des opérations citées précédemment.

Théorème 21. Une opération élémentaire sur les lignes d’un système linéaire le transforme en un système équivalent.

Résolution pratique

On cherche à résoudre le système linéaire de $n$ équations à $m$ inconnues :

$⎩ ⎨ ⎧ a_{1, 1} x_{1} + \dots + a_{1, m} x_{m} = b_{1} ⋮ a_{n, 1} x_{1} + \dots + a_{1, n} x_{m} = b_{n} (S)$

mis sous forme matricielle $A X = B$ . On suppose $A \neq = 0$ (sinon l’ensemble des solutions de $(S)$ est $K^{n}$ ). On note $L_{i}$ la ligne numéro $i$ de $A$ pour tout $i \in [[1, m]]$ .

Théorème 22 (Échelonnement par pivot).

Si les premières colonnes $C_{1}, \dots, C_{d_{1}}$ de la matrice $A$ sont nulles, les variables $x_{1}, \dots, x_{d}$ peuvent être quelconques et on passe à la colonne $d_{1} + 1$ , ce qui nous donne un système de $n$ équations à $m - d$ inconnues. On suppose donc que la première colonne de la matrice $A$ n’est pas nulle et en permutant la ligne $1$ avec une des lignes suivantes on se ramène à un système $A^{(1)} X = B^{(1)}$ avec $a_{1, 1}^{(1)} \neq = 0$ . On élimine alors $x_{1}$ des lignes $2$ à $n$ en effectuant les opérations élémentaires $L_{i} \leftarrow L_{i} - \frac{a _{1, 1}^{(1)}}{a _{1, 1}^{(1)}} L_{i}$ pour $i \in [[2, n]]$ , ce qui donne le système : $⎩ ⎨ ⎧ a_{1, 1}^{(1)} x_{1} + a_{1, 2}^{(1)} x_{2} + \dots + a_{1, m}^{(1)} x_{m} = b_{1}^{(1)} a_{2, 2}^{(2)} x_{2} + \dots + a_{2, m}^{(2)} x_{m} = b_{2}^{(2)} ⋮ a_{n, 2}^{(2)} x_{1} + \dots + a_{1, n}^{(2)} x_{m} = b_{n}^{(2)}$
- Si l’un des coefficients $a_{i, 2}^{(2)}$ est non nul (pour $i \in [[1, n]]$ ), on recommence avec un procédé analogue pour éliminer $x_{2}$ des équations $3$ à $n$ .
- Si tous les coefficients $a_{i, 2}^{(2)}$ sont nuls, on passe alors à la colonne suivante. Et on recommence ainsi de suite.
Au bout d’un nombre fini d’étapes, on aboutit à un système échelonné qui est équivalent au système $(S)$ .

Une fois le système échelonné, on peut procéder à la résolution.

Théorème 23 (Remontée). Trois cas de figure sont possibles.

Soit on a obtenu un système de Cramer triangulaire supérieur d’ordre $n = m = r$ . Un tel système a une unique solution et se résout alors en remontée. Dans ce cas, $A$ est de rang $n = m$ .
Soit on a obtenu un système de $r \leq n$ équations à $m > r$ inconnues. Les $r$ premières inconnues sont les inconnues principales et les autres inconnues non principales. Ces dernières sont alors utilisées comme paramètres en second membre et on résout le système d’inconnues principales $x_{1}, \dots, x_{r}$ . L’ensemble des solutions est un espace affine de dimension $n - r$ et le rang de la matrice est $r$ .
Soit on a obtenu un système de $n$ équations à $r = m < n$ inconnues, de la forme : $⎩ ⎨ ⎧ α_{1, 1} x_{1} + α_{1, 2} x_{2} + \dots + α_{1, m} x_{m} = β_{1} α_{2, 2} x_{2} + \dots + α_{2, m} x_{m} = β_{2} ⋮ α_{n, 2} x_{1} + \dots + α_{1, n} x_{m} = β_{m} 0 = β_{m + 1} ⋮ 0 = β_{n}$ si l’un des $β_{i}$ pour $i \in [[m + 1, n]]$ est non nul, alors le système est incompatible. Sinon, le système des équations principales est un système de Cramer, qui admet une unique solution. Dans ce cas, la matrice est de rang $m$ .

[GRI]
p. 38

Exemple 24. $⎩ ⎨ ⎧ x + 2 y - z = 1 2 x + 3 y + z = 2 x + 4 y - 6 z = 2 ⟺ ⎩ ⎨ ⎧ x + 2 y - z = 1 - y + 3 z = 0 2 y - 5 z = 1 ⟺ ⎩ ⎨ ⎧ x + 2 y - z = 1 - y + 3 z = 0 z = 1$ On a pour unique solution $(- 4, 3, 1)$ .

Comparaison avec les formules de Cramer

[FFN]
p. 38

Théorème 25. L’algorithme du pivot de Gauss pour résoudre un système $A X = B$ a un complexité de $O (n^{3})$ . L’utilisation des formules de Cramer se fait en $O (n (n + 1)!)$ .

Conséquences théoriques

Familles libres

[GRI]
p. 44

Proposition 26. La méthode du pivot permet de décider si une famille est libre (en échelonnant la matrice formée des vecteurs de cette famille).

Exemple 27. La famille $1 - 2 - 3, 23 - 1, 321$ est libre.

Rang, équivalence

[C-G]
p. 24

Proposition 28. Soit $M \in M_{n, m} (K)$ de rang $r$ . Par des opérations élémentaires sur des lignes et des colonnes de $M$ , on peut la transformer en $(I_{r} 0 00)$

Commutant d’une matrice

Soit $A \in M_{n} (K)$ .

[GOU21]
p. 289

Lemme 29. Si $π_{A} = χ_{A}$ , alors $A$ est cyclique : $\exists x \in K^{n} ∖ {0} tel que (x, A x, \dots, A^{n - 1} x) est une base de K^{n}$

[FGN2]
p. 160

Notation 30.

On note $T_{n} (K)$ l’ensemble des matrices carrées triangulaires supérieures d’ordre $n$ à coefficients dans le corps $K$ .
On note $C (A)$ le commutant de $A$ .

Lemme 31. $dim_{K} (C (A)) \geq n$

Lemme 32. Le rang de $A$ est invariant par extension de corps.

dimension-du-commutant

Théorème 33. $K [A] = C (A) ⟺ π_{A} = χ_{A}$

Décompositions

Décomposition LU

[ROM21]
p. 690

Définition 34. Les sous-matrices principales d’une matrice $(a_{i, j})_{i, j \in [[1, n]]} \in M_{n} (K)$ sont les matrices $A_{k} = (a_{i, j})_{i, j \in [[1, k]]} \in M_{k} (K)$ où $k \in [[1, n]]$ . Les déterminants principaux sont les déterminants des matrices $A_{k}$ , pour $k \in [[1, n]]$ .

Théorème 35 (Décomposition lower-upper). Soit $A \in GL_{n} (K)$ . Alors, $A$ admet une décomposition $A = LU$ (où $L$ est une matrice triangulaire inférieure à diagonale unité et $U$ une matrice triangulaire supérieure) si et seulement si tous les déterminants principaux de $A$ sont non nuls. Dans ce cas, une telle décomposition est unique.

Corollaire 36. Soit $A \in GL_{n} (K) \cap S_{n} (K)$ . Alors, on a l’unique décomposition de $A$ : $A = L D (^{t} L$ où $L$ est une matrice triangulaire inférieure et $D$ une matrice diagonale.

Application 37 (Décomposition de Cholesky). Soit $A \in M_{n} (R)$ . Alors, $A \in S_{n}^{++} (R)$ si et seulement s’il existe $B \in GL_{n} (R)$ triangulaire inférieure telle que $A = B (^{t} B$ . De plus, une telle décomposition est unique si on impose la positivité des coefficients diagonaux de $B$ .

[GRI]
p. 368

Exemple 38. On a la décomposition de Cholesky : $(1225) = (1201) (1021)$

[C-G]
p. 257

Proposition 39. Soit $A \in GL_{n} (K)$ vérifiant les hypothèses du Théorème 35. On définit la suite $(A_{k})$ où $A_{0} = A$ et $\forall k \in N$ , $A_{k + 1}$ est la matrice obtenue à partir de $A_{k}$ à l’aide du pivot de Gauss sur la $(k + 1)$ -ième colonne. Alors, $A_{n - 1}$ est la matrice $U$ de la décomposition $A = LU$ du Théorème 35.

Remarque 40. Pour résoudre un système linéaire $A X = Y$ , on se ramène à $A = LU$ en $O (\frac{2}{3} n^{3})$ . Puis, on résout deux systèmes triangulaires en cascade : $L X^{'} = Y puis U X = X^{'}$ ceux-ci demandant chacun $O (2 n^{2})$ opérations.

Théorème 41 (Décomposition PLU). Soit $A \in GL_{n} (K)$ . Alors, il existe $P \in GL_{n} (K)$ , matrice de permutations, telle que $P^{- 1} A$ admet une décomposition $LU$ .

Décomposition QR

[ROM21]
p. 692

Théorème 42 (Décomposition QR). Soit $A \in GL_{n} (R)$ . Alors, $A$ admet une décomposition $A = QR$ où $Q$ est une matrice orthogonale et $R$ est une matrice triangulaire supérieure à coefficients diagonaux strictement positifs. On a unicité d’une telle décomposition.

Corollaire 43 (Théorème d’Iwasawa). Soit $A \in GL_{n} (R)$ . Alors, $A$ admet une décomposition $A = Q D R$ où $Q$ est une matrice orthogonale, $D$ est une matrice diagonale à coefficients strictement positifs et $R$ est une matrice triangulaire supérieure à coefficients diagonaux égaux à $1$ . On a unicité d’une telle décomposition.

[GRI]
p. 272

Exemple 44. On a la factorisation QR suivante, $011101110 = \frac{1}{6} 033 2 - 1 1 22 - 2 \frac{1}{6} 23003301122$ qui peut être obtenue via un procédé de Gram-Schmidt.

p. 368

Remarque 45. Pour résoudre un système linéaire $A X = Y$ , si l’on a trouvé une telle factorisation $A = QR$ , on résout $RX = (^{t} Q Y$ c’est-à-dire, un seul système triangulaire (contre deux pour la factorisation LU).