TD3 - ALG II

TD — Algèbre II 3 : factorisation $LU$ et pivotage

🔊 Écouter la source audio

Couverture : de 00:00:00 à 01:42:41 sur un audio de 01:42:51 (1 h 42). Le prof développe la factorisation $LU$ : idée, construction de $L$ et $U$, lien avec l’élimination de Gauss, pivotage partiel et $PA=LU$ (00:00 → 00:27), puis deux exercices au tableau — une factorisation sans pivotage qui échoue sur un pivot nul (00:27 → 00:48), et un exemple complet avec pivotage à chaque étape (01:12 → 01:41). Au milieu, la séance est ponctuée d’une pause hors-sujet sur l’emploi du temps (00:48 → 00:55) et d’un exercice individuel pour les étudiants (00:55 → 01:12).

Support : pas d’énoncé PDF distribué. Le prof a scanné ses notes sur WebCampus (« Rappels théoriques », celui de la matière de l’examen) et s’y réfère — voir aussi le ALG II - Cours 3 ($PA=LU$, pivotage) et le TD2 - ALG II (élimination de Gauss, substitution). « 9 fois sur 10, il y a une question de factorisation LU à l’examen. » ⚠️ La qualité de l’enregistrement s’est dégradée pendant les exercices numériques ; les matrices des exemples ne sont reconstruites que partiellement (fragments marqués ⚠️).

---

PARTIE 1 — La factorisation $LU$ : principe et construction — [00:00:00]

1. Rappel de la méthode de substitution — [00:00:00]

« La semaine passée, on avait dit que la méthode de substitution… » → deux pyramides à connaître :

• substitution progressive : système triangulaire inférieur $Ly=b$ ; on calcule les inconnues de haut en bas (la 1ʳᵉ équation ne contient qu’une inconnue).
• substitution régressive : système triangulaire supérieur $Ux=y$ ; on calcule de bas en haut.

C’est la méthode qu’il faudra coder en MATLAB (fonctions inferior.m / superior.m du TD2 - ALG II).

2. Le problème du jour : factoriser $A=LU$ — [00:01:46]

« On va transformer la matrice $A$ en une multiplication d’une matrice $L$ par une matrice $U$. »

• Objectif : factoriser $A\in {\mathbb{R}}^{n\times n}$ sous la forme

$$A=LU,$$

avec $L$ triangulaire inférieure à diagonale unité (matrice normée, $l_{ii}=1$) et $U$ triangulaire supérieure.

• On ne modifie pas le vecteur $b$ — différence clé avec l’élimination de Gauss (qui transforme $b$ au fil des opérations) : ici b reste tel quel, on ne travaille que sur $A$.

3. Résolution en trois temps : $Ax=b$ devient $LUx=b$ — [00:04:50]

Pour résoudre $Ax=b$ une fois la factorisation $A=LU$ obtenue :

1. Factoriser $A=LU$ (étape qui ne dépend pas de $b$ ; on peut donc la réutiliser pour plusieurs seconds membres).
2. Résoudre $Ly=b$ par substitution progressive — le $b$ garde sa valeur initiale.
3. Résoudre $Ux=y$ par substitution régressive.

Schéma (repris au tableau) :

$$Ax=b⟺L(Ux)=b⟹\underset{\text{subst. progressive}}{\underbrace{Ly=b}}\Rightarrow \underset{\text{subst. reˊgressive}}{\underbrace{Ux=y}}\Rightarrow x.$$

4. Interprétation matricielle : les matrices élémentaires $E_k$ — [00:06:01]

Pour construire $L$ et $U$, on reprend exactement le geste de Gauss (voir ALG II - Cours 3) :

• À chaque itération $k$, l’élimination revient à pré-multiplier par une matrice élémentaire $E_k$ : $A^{(k+1)}=E_k{A}^{(k)}$.
• $E_k$ = matrice identité dans laquelle on place les multiplicateurs dans la colonne $k$ sous la diagonale.
• $U$ est la dernière matrice de Gauss obtenue en fin de processus : c’est exactement la matrice triangulaire supérieure recherchée.
• Les $E_k$ sont des matrices normées sur la diagonale ; leurs inverses $E_k^{-1}$ se calculent très facilement (on change simplement le signe de la colonne).

5. Résultat 1 : $L$ est le produit des $E_k^{-1}$ — [00:09:20]

[00:09:50] « Le premier théorème qui nous permet de calculer facilement $L$… » — [00:10:22] « La preuve, en fait, ne se trouve même pas dans le syllabus. »

$$L=E_1^{-1}{E}_2^{-1}\cdots E_{n-1}^{-1}.$$

C’est ce qui explique la forme « triangulaire inférieure » de $L$ : un produit de matrices triangulaires inférieures reste triangulaire inférieur, et les diagonales unités se multiplient en une diagonale unité ($L$ est normée).

• Comment construire $U$ ? → [00:09:20] Exactement comme Gauss : $U$ est la dernière matrice de Gauss (la matrice triangulaire supérieure une fois l’élimination terminée). C’est « U = dernière matrice de Gauss ».

6. Résultat 2 : construction de $L$ colonne par colonne — [00:13:22]

« Pour $i$ qui va de $k+1$ jusqu’à $n$, avec $k$ qui lui-même… »

La formule opérationnelle (le « théorème ») :

$$l_{ik}=\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}},i=k+1,\dots ,n,k=1,\dots ,n-1,$$

où $a_{ik}^{(k)}$ désigne la valeur courante (après les $k-1$ premières étapes d’élimination) et $a_{kk}^{(k)}$ le pivot. Autrement dit :

Dans la colonne du pivot, on ne met pas de 0 (contrairement à Gauss) : on y stocke les quotients $a_{ik}/a_{kk}$, qui remplissent exactement la colonne $k$ de $L$.

• Les $l_{ik}$ sont les multiplicateurs successifs de l’élimination de Gauss ;
• On peut mettre à jour $L$ et $U$ au fil des itérations ([00:43:38] « à la dernière étape $k$, on fait 0 à 3 »), sans attendre la fin ;
• Vérification : on multiplie $L$ et $U$ et on doit retomber exactement sur $A$ ([00:47:23] « on a bien la factorisation $A=L\cdot U$ »).

7. Bien posée de la factorisation : pivots non nuls ⇔ mineurs emboîtés — [00:14:56]

• [00:15:20] « De manière générale, dire qu’aucun pivot n’est nul est équivalent à dire que les $n-1$ premiers mineurs principaux (mineurs emboîtés, en cabochon / emboîtés) sont non nuls. »

Définition (mineurs emboîtés) : ce sont les déterminants des sous-matrices principales de tête

$$\det A^{(1)}=a_{11},\det A^{(2)}=\left|\begin{array}{cc}{a}_{11}& a_{12}\\ a_{21}& a_{22}\end{array}\right|,\dots ,\det A^{(n-1)}.$$

Si l’un de ces mineurs est nul, un pivot s’annule à l’étape correspondante → pas de factorisation $LU$ sans pivotage.

8. Pivotage partiel : on échange la ligne du pivot — [00:15:56]

• [00:16:15] « En général, on prend le maximum des éléments sous la ligne » (en valeur absolue) jusqu’à la diagonale incluse, et on permute sa ligne avec la ligne du pivot.
• Pivotage toujours avant d’effectuer l’opération d’élimination.
• Pourquoi ? Stabilité numérique : si le pivot $a_{kk}$ est très petit, le multiplicateur $l_{ik}=a_{ik}/a_{kk}$ devient énorme et amplifie les erreurs d’arrondi.

Exemple donné en cours : 0, $10^{-6}$, 7 dans la colonne du pivot → on choisit 7. Avec $10^{-6}$, le multiplicateur vaut $1/10^{-6}\approx 10^6$, ce qui détruit la précision des calculs.

• [00:17:07] On n’est pas obligé de pivoter quand les pivots sont non nuls. Mais on peut aussi pivoter « tout le temps », comme exercice d’application.
• [00:18:05] On peut de toute façon pivoter quand on veut (pas obligatoirement avant l’étape). En revanche, pivoter tôt ou tard donne des factorisations $PA=LU$ différentes — mais toutes aussi valides.

---

PARTIE 2 — Pivotage et $PA=LU$ — [00:17:18]

9. Écrire les permutations dans le processus de Gauss — [00:18:05]

Pour un exemple conceptuel en $n=4$ ([00:19:10] « on suppose qu’on a n=4 et qu’on va calculer de… »), le déroulé avec pivotage s’écrit :

$$A_1=P_1{A}_0,A_2=P_2{E}_1{A}_1,\dots$$

• $P_k$ est la matrice de permutation qui échange la ligne $k$ avec la ligne contenant le pivot.
• On obtient finalement ([00:22:28]) « où $P$ est le produit de matrices de permutation » :

$$PA=LU,$$

avec $P=P_2{P}_1\cdots$ (en injectant les permutations d’ordre convenable).

Construction de $M$ (= matrice de permutation $P_k$) — [00:23:02]

• Partir de la matrice identité ;
• permuter dans l’identité les deux lignes concernées.

Ex. permuter les lignes 1 et 3 de l’identité ($4\times 4$) → $P_1=\left(\begin{array}{cccc}0& 0& 1& 0\\ 0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\end{array}\right)$.

• Pivotage complet (on peut aussi permuter des colonnes) : c’est la formulation générale $PAQ=LU$, avec $P$ et $Q$ des matrices de permutation (produit de permutations de lignes / de colonnes).

---

PARTIE 3 — Exercice 1 : une factorisation sans pivotage qui « casse » — [00:27:55]

11. Déroulement du premier exemple — [00:27:55]–[00:48:00]

Le prof commence une factorisation $LU$ sans pivotage au tableau (deuxième exemple après l’exercice conceptuel $n=4$).

• Méthode appliquée ([00:32:44] « La factorisation $L$ sans pivotage ») : à chaque étape, colonne du pivot divisée par le pivot → remplissage de $L$ ; les autres lignes transformées par « ce qu’on faisait en Gauss ».
• On peut mettre $L$ et $U$ à jour en même temps, puis calculer les étapes suivantes.

⚠️ Reconstruction partielle de la matrice (audio très bruitée) : seuls des fragments des valeurs sont audibles — un bloc $2\times 2$ d’en-tête de la forme $\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)$ est identifiable, avec ligne suivante de la forme ~$(3,5,6,7)$. Les valeurs exactes du reste de la matrice n’ont pas pu être reconstituées de façon fiable ; la démarche en revanche est claire :

1. Itération $k=1$ : pivot $a_{11}=1$ ; on remplit la 1ʳᵉ colonne de $L$ par les rapports « $a_{i1}$ sur le premier élément » → $l_{21}=a_{21}/a_{11}=2$.
2. On transforme les lignes suivantes (opérations de Gauss) : [00:35] « 4 moins 2 point 2 sur 1 → 0 » [00:36] ; les valeurs qui deviennent nulles sont juste à côté du pivot mais celles qui restent peuplent $U$.
3. Itération $k=2$ : le pivot $a_{22}^{(2)}$ vaut 0 ([00:43:38] « c’est exactement pourquoi c’est 0, 1 moins 1… » et [00:46] « l’élément $a_{22}$ à l’étape 2 qui vaut 0 »).
4. Blocage : impossible de diviser par le pivot nul → pas de factorisation $LU$ sans pivotage pour cette matrice.

Bilan de l’exercice 1 — [00:47]

• On pouvait prédire l’échec avant de calculer : le 2ᵉ mineur emboîté (déterminant du bloc $2\times 2$ d’en-tête $\left|\begin{array}{cc}1& 2\\ 2& 4\end{array}\right|=1\cdot 4-2\cdot 2=0$) est nul.
• Par le critère de la section 7 : pivots non nuls ⇔ mineurs emboîtés non nuls.
• Remède : pivotage partiel → voir l’exercice 3 (sections 14–15).

---

PARTIE 4 — Pause hors-sujet + exercice individuel — [00:48:40]

12. Discussion d’organisation (hors-sujet) — [00:48:40]–[00:55:00]

Conversation sur l’emploi du temps (cours de CESA à 18 h, cours de Modélisation — « comme Modé c’est moi, je peux trouver une alternative », « on va zapper un cours », « 15 heures », etc.). Aucun contenu de cours. Non repris dans la note.

13. Exercice 2 (à faire par les étudiants) : factoriser $LU$ sans pivotage — [00:55:37]–[00:56:09]

« On va reprendre. Ici, je vous laisse faire vous-même la factorisation de la matrice. Pour cette factorisation-là, vous n’avez pas besoin de pivotage. Je vous laisse faire les détails ; je vais uniquement afficher la réponse finale au tableau, les matrices $L$ et $U$. »

Modalités ([00:55:37]–[00:56:09]) :

• travail individuel au tableau/aux places jusqu’à 17 h 30 ;
• le détail complet des itérations est exigé, la réponse finale seule ($L$, $U$) sera donnée par le prof.

Le prof n’aura pas le temps de corriger au propre dans le flux — la correction est glissée par fragments pendant qu’il aide les étudiants ([01:08]–[01:12]) ; on y entend des étapes de division par le pivot :

[01:08:43] « C’est plus ou moins moins 1. » — [01:08:48] « 3/2, c’est [±] 1 ». — [01:09:50] « Donc c’est $1$ moins $0\times 0$ sur 2 → 1 » — [01:10:13] « $3,2,1$ moins $0\times 1$ sur 2 » — [01:10:32] « c’est $0\times 1$ sur 2 ».

⚠️ Ces fragments correspondent aux rapports « $a_{ik}^{(k)}/a_{kk}^{(k)}$ » de l’étape en cours, mais les matrices de cet exercice n’ont pas pu être reconstruites (bruit ASR).

Observations pédagogiques pendant le travail — [01:08:43]–[01:12:00]

• [01:10:32]–[01:11:12] Un 0 dans une colonne ou une ligne ⇒ cette colonne/ligne ne sera pas modifiée par la suite : « si tu as un 0 ici, tu sais que la colonne ne va pas être modifiée ; c’est pareil pour les lignes : un 0 ici, la ligne va rester conservée. C’est seulement quand tu n’as pas de 0 que ça se modifie. » → astuce de vérification : les lignes/colonnes où apparaît un 0 courent tout droit dans $U$.
• Vérifier ses calculs en multipliant $L$ par $U$ et en retombant sur $A$.

---

PARTIE 5 — Exercice 3 : factorisation avec pivotage à chaque étape — [01:12:23]

14. Redémarrage en « mode pivotage » — [01:12:23]–[01:18:30]

Le prof reprend le principe après le travail individuel : « maintenant, ici, on suppose qu’on est dans le cas avec pivotage », sur une matrice (notée $A$) dont seule la ligne $\left(\begin{array}{ccc}4& 2& 4\end{array}\right)$ est clairement audible après permutation de la 1ʳᵉ itération.

Itération $k=1$ — [01:15:44]–[01:18:34]

1. Rappel de la règle : « globalement, l’idée, c’est qu’à chaque itération on vient chercher l’élément le plus grand en valeur absolue en dessous de l’élément du pivot, et on va permuter la ligne associée à cet élément et la ligne du pivot. On fait toujours le pivotage avant d’effectuer n’importe quelle opération. »
2. Même si on n’a pas de 0, on va ici pivoter systématiquement, pour montrer l’algorithme : on permute $l_1\leftrightarrow l_3$ → matrice de permutation $P_1$ (lignes 1 et 3 échangées dans l’identité). La nouvelle 1ʳᵉ ligne devient $\left(\begin{array}{ccc}4& 2& 4\end{array}\right)$.
3. On calcule les multiplicateurs après la permutation : 1ʳᵉ colonne de $L$ = $\left(\begin{array}{c}1\\ l_{21}\\ l_{31}\end{array}\right)$, $l_{i1}=a_{i1}/a_{11}$.

Détail important : à la 1ʳᵉ itération on pivote dans $A$ mais pas dans $L$, « puisque $L$ n’existe pas encore » ([01:18:34]). On applique la permutation avant de calculer $L$.

4. On complète $U$ au fur et à mesure. ⚠️ Fragments audibles : « il faut faire 1, 1,5, 1,4 ; 0, 1, 1,5 » pour $L$, et « 4, 6, 7, 0, 1, moins 5 demi » puis « 5, 2, 1 » pour le dernier élément — valeurs non recoupées, à vérifier en refaisant l’exercice.

Remarque cruciale : deux façons d’obtenir une factorisation différente — [01:17:24]–[01:19:30]

• [01:17:24] « Si on ne permutait pas, à un moment donné, à la deuxième étape, on aurait un pivot nul → on serait obligé de permuter. »
• [01:18] « Là, plutôt que de permuter seulement quand on y est obligé, si j’ai permuté dès le début, je n’aurai plus $P\times A$[→ $A$ d’origine]… et je calcule une autre factorisation $LU$ de cette matrice-là. »
• Conclusion : on peut pivoter quand on veut ; chaque choix donne la factorisation $LU$ (unique) de la matrice $P\cdot A$ correspondante ([01:19:24] « ta factorisation LU et la mienne, ce seront pour deux matrices $P\cdot A$ qui seront différentes l’une de l’autre, mais ce n’est pas un problème »).

15. Itérations suivantes et matrice de permutation finale — [01:19:30]–[01:41:03]

• $k=2$ : si la règle « maximum en valeur absolue » donne déjà le pivot, pas de permutation → « pas besoin de permuter » → $P_2$ = identité (d’ordre $n-1$) ; on met à jour $L$ (colonne 2) et $U$.
• Matrice $B$ ([01:24:25] « C’est parti pour $B$ ») : ⚠️ premières lignes audibles $\left(\begin{array}{cccc}2& 1& 0& 0\\ 4& -2& 1& 0\\ & & \ddots & \end{array}\right)$. On permute $l_1\leftrightarrow l_2$ (comme $|4|>|2|$) → $P_1$ = lignes 1 et 2 échangées dans l’identité ; $B_1$ commence par $\left(\begin{array}{cccc}4& -2& 1& 0\end{array}\right)$.
• $k=3$ ([01:25:38] : « on permute $l_2$ et $l_3$ » pour rester dans l’exercice « permuter systématiquement », même si ce n’est pas nécessaire) → $P_2$ ; on permute aussi $l_2$ et $l_3$ dans $L$, pas dans $U$ (la faute classique, corrigée par le prof : [01:25] « Ah non, il faut permuter dans L »).

Règle d’or : quand on permute dans $A$, on permute aussi (déjà) dans $L$ — [01:23:00]–[01:26:00]

Le prof martèle cette règle pendant les exercices ([01:10:48]–[01:11:12] à l’exercice individuel, puis [01:23]–[01:26] sur la matrice $B$) :

« Si on permute dans $A$, on permute aussi dans $L$. »

• À la 1ʳᵉ itération, on ne permute rien dans $L$ : $L$ n’existe pas encore ([01:18:34] « je n’ai pas encore construit de $L$, donc je ne vais pas permuter dans $L$ pour le moment »).
• Aux itérations suivantes, la ligne permutée doit aussi être échangée dans la partie déjà construite de $L$ — c’est une faute d’inattention classique ([01:25] « Ah oui, mais c’est une faute complète, c’est là qu’il faut changer »).
• On ne permute jamais dans $U$ : [01:26] « Attention, on permute que dans L, pas dans U. » $U$ se construit à partir de la matrice permutée, il est déjà correct.

Le résultat final — [01:39]–[01:41]

• À la fin : $PA=LU$ avec $P=P_2{P}_1$ (les $P_k$ « s’empilent » ; quand une étape ne permute pas, $P_k$ = identité et $P=P_1$ seulement le cas échéant).
• Vérification systématique conseillée : compter $P\cdot A$ (permuter les lignes de $A$) puis multiplier $L\cdot U$ et comparer.
• [01:41:03] : « À l’examen, si vous voulez le dire, vous n’avez pas fait comme [la méthode du corrigé], vous faites $P\times A$, vous multipliez $L\times U$, ça va marcher. »

---

PARTIE 6 — Conseils d’examen et annonces — [01:41:03]

16. La factorisation LU à l’examen — [01:41:03]–[01:42:41]

« Notez que 9 fois sur 10, il y a une question de calculer une factorisation $LU$ à l’examen. C’est des points garantis. N’allez pas vous tromper là-dessus. »

• Le calcul est long mais simple ; ce qui est le plus délicat, c’est de comprendre pourquoi l’algorithme a été conçu (les matrices $E_k$), pas le calcul en lui-même (« le calcul en lui-même, ce n’est pas compliqué »).
• Semaine prochaine : « rendez-vous au pool, où vous allez coder » (implémentation de la substitution).
• Pas de correctif posté pour cette séance : chacun doit envoyer ses codes au prof s’ils ne fonctionnent pas, mais il faut d’abord « essayer vraiment de le faire par soi-même » pour savoir tout implémenter.
• Les codes devront être opérationnels pour le travail de groupe ; le travail de groupe sert aussi à évaluer les codes informatiques.

---

Points clés

• $A=LU$ : $L$ triangulaire inférieure normée ($l_{ii}=1$), $U$ triangulaire supérieure = dernière matrice de Gauss.
• $L$ colonne par colonne : dans la colonne du pivot, on ne met pas de 0, on stocke les multiplicateurs $l_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)}$.
• On ne touche pas à $b$ dans la factorisation : $Ly=b$ (progressive) puis $Ux=y$ (régressive).
• Existence : $LU$ sans pivotage existe (et est unique) ssi les $n-1$ premières mineurs emboîtés (mineurs principaux de tête) sont non nuls.
• Pivotage partiel : on échange la ligne du pivot avec la ligne de plus grand élément en valeur absolue sous la diagonale → on évite des multiplicateurs énormes qui amplifient les erreurs d’arrondi (ex. $0,10^{-6},7\to 7$).
• $PA=LU$ : on construit $P_k$ en permutant les lignes de l’identité ; pivotage avant l’opération.
• Règle d’or : on permute aussi dans $L$ (sauf à la 1ʳᵉ itération où $L$ n’existe pas), jamais dans $U$.
• Vérifications : multiplier $L\cdot U$ et retomber sur $A$ (ou $P\cdot A$) ; un 0 dans une ligne/colonne ⇒ cette ligne/colonne ne change plus.

Doutes / à vérifier

• ⚠️ Matrices exactes des exercices non reconstituées (audio très dégradé sur les valeurs) : exercice 1 (bloc d’en-tête $\left(\begin{array}{cc}1& 2\\ 2& 4\end{array}\right)$ avec 2ᵉ mineur emboîté nul) et exercices 3 (matrices $A$, $B$). Les valeurs $L/U$ données en cours (fragments « 1, 1.5, 1.4 », « 4, 6, 7 / 0, 1, −5/2 », « 5, 2, 1 », « 4, −2, 1, 0 ») n’ont pas été recoupées.
• Le calcul « $l_{21}=a_{21}/a_{11}=2$ » de l’exercice 1 est cohérent avec le bloc d’en-tête, mais la suite de la matrice est incertaine.
• Recompréhension de l’exemple $B$ (permutation $l_1\leftrightarrow l_2$, pivotage aux étapes 2 et 3) possible par le quiz : refaire l’exercice en entier et comparer avec les fragments.