Problème : la factorisation $LU$ , ou le pivot de Gauss comme produit de matrices

Exercice de TD · niveau 3 (difficile) · mathématiques (PTSI), chapitre 7 — Calcul matriciel et systèmes linéaires · E. Problèmes et applications

Énoncé

Soit $A \in M_{n} (K)$ , avec $n \geq 2$ . On dit que le pivot de Gauss s'effectue sans échange si, à chaque étape $k \in {1, \dots, n - 1}$ , le coefficient d'indice $(k, k)$ de la matrice courante — le pivot — est non nul ; on annule alors les coefficients situés sous lui par les opérations $L_{i} \leftarrow L_{i} - m_{i, k} L_{k}$ ( $i > k$ ), où le multiplicateur $m_{i, k}$ est le quotient du coefficient $(i, k)$ de la matrice courante par le pivot. On note $T$ l'ensemble des matrices triangulaires inférieures dont tous les coefficients diagonaux valent $1$ .

1) Pour $k$ fixé, on pose $G_{k} = I_{n} - \sum_{i > k} m_{i, k} E_{i, k}$ . Montrer que multiplier à gauche par $G_{k}$ effectue d'un coup les opérations $L_{i} \leftarrow L_{i} - m_{i, k} L_{k}$ pour $i > k$ , et que $G_{k}$ est inversible, d'inverse $I_{n} + \sum_{i > k} m_{i, k} E_{i, k}$ (calculer $E_{i, k} E_{j, k}$ pour $i, j > k$ ).

2) Montrer que $G_{1}^{- 1} G_{2}^{- 1} \dots G_{n - 1}^{- 1} = I_{n} + \sum_{1 \leq k < i \leq n} m_{i, k} E_{i, k}$ : les multiplicateurs se rangent d'eux-mêmes sous la diagonale. Vérifier, pour $n = 3$ , que le produit dans l'autre ordre, $G_{2}^{- 1} G_{1}^{- 1}$ , fait apparaître en position $(3, 1)$ le coefficient $m_{3, 1} + m_{3, 2} m_{2, 1}$ .

3) En déduire que, si le pivot s'effectue sans échange, $U = G_{n - 1} \dots G_{1} A$ est triangulaire supérieure, et que $A = LU$ avec $L \in T$ .

4) On suppose de plus $A$ inversible. Montrer que $U$ est inversible. Si $A = L_{1} U_{1} = L_{2} U_{2}$ , avec $L_{1}, L_{2} \in T$ et $U_{1}, U_{2}$ triangulaires supérieures, montrer que $L_{2}^{- 1} L_{1} = U_{2} U_{1}^{- 1}$ , que cette matrice est à la fois dans $T$ et triangulaire supérieure, et conclure que $L_{1} = L_{2}$ et $U_{1} = U_{2}$ .

5) Factoriser $A = 248137139$ , puis résoudre $A X = B$ pour $B = 51333$ par une descente $L Y = B$ suivie d'une remontée $U X = Y$ . Pourquoi vaut-il mieux factoriser une fois pour toutes lorsqu'on doit résoudre $A X = B$ pour de nombreux seconds membres — un même circuit soumis à plusieurs sources, un schéma numérique qui avance pas à pas, une structure étudiée en sciences industrielles sous plusieurs chargements ?

6) Montrer que $(0110)$ n'admet aucune écriture $LU$ avec $L \in T$ et $U$ triangulaire supérieure, mais qu'après échange de ses lignes, si. Énoncer le théorème obtenu.

Corrigé

Ce qu'on a le droit d'utiliser. La règle $E_{i, j} E_{k, l} = δ_{j, k} E_{i, l}$ et sa lecture de l'exercice 6 — $E_{i, j} A$ a pour ligne $i$ la ligne $j$ de $A$ , et ses autres lignes nulles ; les opérations sur les lignes comme produits à gauche ; l'inverse d'un produit ; et l'exercice 9, pour la stabilité des triangulaires. La stratégie : écrire chaque étape du pivot comme un produit, puis lire le produit des inverses sans le calculer.

1) Une étape du pivot est un produit. Pour $i > k$ , $E_{i, k} A$ a pour ligne $i$ la ligne $k$ de $A$ , et ses autres lignes nulles. Donc $G_{k} A = A - \sum_{i > k} m_{i, k} E_{i, k} A$ garde les lignes de $A$ jusqu'à l'indice $k$ , et sa ligne $i > k$ vaut $L_{i} - m_{i, k} L_{k}$ : $G_{k}$ effectue d'un coup les transvections de l'étape $k$ , qui n'interfèrent pas, puisqu'elles utilisent toutes la ligne $L_{k}$ , qu'aucune ne modifie. L'inverse : posons $N_{k} = \sum_{i > k} m_{i, k} E_{i, k}$ ; pour $i, j > k$ , $E_{i, k} E_{j, k} = δ_{k, j} E_{i, k} = 0$ car $j \neq = k$ , donc $N_{k}^{2} = 0$ et $(I_{n} - N_{k}) (I_{n} + N_{k}) = I_{n} - N_{k}^{2} = I_{n}$ , dans les deux ordres. $G_{k}^{- 1} = I_{n} + N_{k}$ : pour défaire l'étape, on rajoute ce qu'on avait retranché.

2) Les multiplicateurs se rangent. Pour $k < l$ , $N_{k} N_{l} = i > k \sum j > l \sum m_{i, k} m_{j, l} E_{i, k} E_{j, l} = i > k \sum j > l \sum m_{i, k} m_{j, l} δ_{k, j} E_{i, l} = 0,$ car $j > l > k$ interdit $j = k$ . En développant $(I_{n} + N_{1}) (I_{n} + N_{2}) \dots (I_{n} + N_{n - 1})$ , on obtient $I_{n}$ , la somme des $N_{k}$ , et des produits de plusieurs $N_{k}$ d'indices strictement croissants, qui commencent tous par un produit nul $N_{k_{1}} N_{k_{2}}$ avec $k_{1} < k_{2}$ . Donc $G_{1}^{- 1} G_{2}^{- 1} \dots G_{n - 1}^{- 1} = I_{n} + N_{1} + \dots + N_{n - 1} = I_{n} + 1 \leq k < i \leq n \sum m_{i, k} E_{i, k} .$ Chaque multiplicateur $m_{i, k}$ se place en position $(i, k)$ , sans interaction. Dans l'autre ordre, pour $n = 3$ : $G_{2}^{- 1} G_{1}^{- 1} = I_{3} + N_{1} + N_{2} + N_{2} N_{1}$ , et $N_{2} N_{1} = m_{3, 2} E_{3, 2} (m_{2, 1} E_{2, 1} + m_{3, 1} E_{3, 1}) = m_{3, 2} m_{2, 1} E_{3, 1}$ , puisque $E_{3, 2} E_{2, 1} = E_{3, 1}$ et $E_{3, 2} E_{3, 1} = 0$ : le coefficient $(3, 1)$ vaut $m_{3, 1} + m_{3, 2} m_{2, 1}$ , les multiplicateurs se mélangent.

3) La factorisation. Sans échange, l'étape $k$ multiplie la matrice courante à gauche par $G_{k}$ : elle annule la colonne $k$ sous la diagonale sans toucher aux colonnes déjà nettoyées, car les lignes modifiées reçoivent un multiple de la ligne $k$ , dont les $k - 1$ premiers coefficients sont nuls. Après l'étape $n - 1$ , $U = G_{n - 1} \dots G_{2} G_{1} A$ est triangulaire supérieure : c'est la forme échelonnée obtenue à la main. En multipliant à gauche par $G_{n - 1}^{- 1}$ , puis $G_{n - 2}^{- 1}$ , et ainsi de suite jusqu'à $G_{1}^{- 1}$ , $A = G_{1}^{- 1} G_{2}^{- 1} \dots G_{n - 1}^{- 1} U = LU,$ avec $L = I_{n} + \sum_{k < i} m_{i, k} E_{i, k} \in T$ . L'inverse d'un produit se prend dans l'ordre inverse — et c'est justement l'ordre où, par le 2), les multiplicateurs ne se mélangent pas. $L$ est la mémoire du pivot, $U$ en est le résultat.

4) L'unicité. $L$ est inversible (exercice 9), donc $U = L^{- 1} A$ aussi. Si $A = L_{1} U_{1} = L_{2} U_{2}$ , alors $U_{1} = L_{1}^{- 1} A$ est inversible, et en multipliant à gauche par $L_{2}^{- 1}$ et à droite par $U_{1}^{- 1}$ : $L_{2}^{- 1} L_{1} = U_{2} U_{1}^{- 1} .$ Le membre de gauche est dans $T$ , stable par produit et par inverse ; celui de droite est triangulaire supérieur, produit d'une triangulaire supérieure et de l'inverse d'une triangulaire supérieure inversible (exercice 9). Une matrice à la fois triangulaire inférieure et supérieure est diagonale, et dans $T$ sa diagonale est faite de $1$ : c'est $I_{n}$ . Donc $L_{1} = L_{2}$ et $U_{1} = U_{2}$ : si $A$ est inversible, sa factorisation $LU$ est unique. L'hypothèse compte : la matrice non inversible de lignes $(0, 0)$ et $(0, 1)$ vaut $(1 t 01) (0001)$ pour tout réel $t$ .

5) Le calcul. Étape 1 : pivot $2$ , multiplicateurs $m_{2, 1} = \frac{4}{2} = 2$ et $m_{3, 1} = \frac{8}{2} = 4$ ; $L_{2} \leftarrow L_{2} - 2 L_{1}$ et $L_{3} \leftarrow L_{3} - 4 L_{1}$ donnent $(0, 1, 1)$ et $(0, 3, 5)$ . Étape 2 : pivot $1$ , multiplicateur $m_{3, 2} = 3$ ; $L_{3} \leftarrow L_{3} - 3 L_{2}$ donne $(0, 0, 2)$ . Les pivots $2$ , $1$ , $2$ sont non nuls, et la forme échelonnée $U$ a pour lignes $(2, 1, 1)$ , $(0, 1, 1)$ , $(0, 0, 2)$ , tandis que $L = 124013001 .$ Contrôle : la deuxième ligne de $LU$ vaut $2 \times (2, 1, 1) + (0, 1, 1) = (4, 3, 3)$ , la troisième $4 \times (2, 1, 1) + 3 \times (0, 1, 1) + (0, 0, 2) = (8, 7, 9)$ . Descente $L Y = B$ : $y_{1} = 5$ , puis $2 y_{1} + y_{2} = 13$ donne $y_{2} = 3$ , puis $4 y_{1} + 3 y_{2} + y_{3} = 33$ donne $y_{3} = 4$ . Remontée $U X = Y$ : $2 x_{3} = 4$ donne $x_{3} = 2$ , puis $x_{2} + x_{3} = 3$ donne $x_{2} = 1$ , puis $2 x_{1} + x_{2} + x_{3} = 5$ donne $x_{1} = 1$ . $X = (1, 1, 2)^{⊤}$ , et en effet $A X = (2 + 1 + 2, 4 + 3 + 6, 8 + 7 + 18)^{⊤} = (5, 13, 33)^{⊤}$ . Pourquoi factoriser une fois pour toutes : l'étape $k$ met à jour $n - k$ lignes d'environ $n - k$ coefficients, soit environ $\frac{n ^{3}}{3}$ multiplications au total, alors qu'une descente en demande $0 + 1 + \dots + (n - 1) \approx \frac{n ^{2}}{2}$ , et une remontée autant. Pour une matrice de taille $1000$ , cela fait environ $3 \times 1 0^{8}$ multiplications pour factoriser, contre $1 0^{6}$ pour une descente et une remontée : quand seul le second membre change, on factorise une fois, et chaque résolution coûte ensuite environ trois cents fois moins.

6) Un pivot nul, et le théorème. Le produit $(1 ℓ 01) (u 0 v w)$ vaut $(u ℓ u v ℓ v + w)$ . Pour qu'il égale $(0110)$ , la position $(1, 1)$ impose $u = 0$ , et la position $(2, 1)$ vaut alors $ℓ u = 0$ au lieu de $1$ : contradiction, aucune écriture $LU$ . Le pivot bute dès la première étape sur un pivot nul. Après échange des lignes, on obtient $I_{2} = I_{2} \times I_{2}$ , qui convient. En général — nous l'admettrons —, pour toute matrice carrée $A$ , il existe une matrice $P$ , produit de matrices d'échange, telle que $P A$ admette une factorisation $LU$ : c'est ainsi que les bibliothèques de calcul numérique, en Python par exemple, résolvent les systèmes linéaires.

Le théorème obtenu — la factorisation $LU$ . Soit $A \in M_{n} (K)$ telle que l'algorithme du pivot de Gauss s'effectue sans échange de lignes. Alors $A = LU$ , où $L$ est triangulaire inférieure à diagonale de $1$ , ses coefficients sous-diagonaux étant les multiplicateurs du pivot, et où $U$ , la forme échelonnée obtenue, est triangulaire supérieure. Si de plus $A$ est inversible, cette factorisation est unique.

Ce que le problème installe. Un algorithme exécuté à la main depuis le chapitre d'algèbre est un produit de matrices, et ce point de vue en fait un théorème : existence, unicité, limite. C'est ainsi que l'on résout un grand système linéaire, en physique comme en ingénierie — les logiciels de calcul de structure des sciences industrielles le font à chaque chargement : on factorise une fois, puis on descend et on remonte. Et le chapitre des déterminants ajoutera que le déterminant de $A$ est le produit des pivots.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.

Problème : la factorisation LU, ou le pivot de Gauss comme produit de matrices

Énoncé

Corrigé

Problème : la factorisation $LU$ , ou le pivot de Gauss comme produit de matrices