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_{p, 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 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$ tel que $A$ est inversible.

Théorème 7

Formules de CramerUn 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 polynomiale $P : R \to R$ et $λ > 0$ tels que $∥ e^{t A} ∥ \leq e^{- λ t} P (t)$ .

equation-de-sylvester

Application 10

Équation de SylvesterSoient $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 + X B = 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

Théorème de 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_{p, 1} (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_{n, m} 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 vide si $B \neq = 0$ et $K^{m}$ si $B = 0$ ). On note $L_{i}$ la ligne numéro $i$ de $A$ pour tout $i \in [[1, n]]$ .

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_{1}}$ peuvent être quelconques et on passe à la colonne $d_{1} + 1$ , ce qui nous donne un système de $n$ équations à $m - d_{1}$ 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 _{i, 1}^{(1)}}{a _{1, 1}^{(1)}} L_{1}$ 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_{2} + \dots + a_{n, m}^{(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

Résolution par remontéeTrois 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 $m - 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} ⋮ α_{m, m} 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-upperSoit $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 CholeskySoit $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 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 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 PLUSoit $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 QRSoit $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’IwasawaSoit $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 $R X = (^{t} Q Y$ c’est-à-dire, un seul système triangulaire (contre deux pour la factorisation LU).