TD4 - ALG II

TD/TP — Algèbre II 4 : Factorisation $LU$ en MATLAB

🔊 Écouter la source audio

Séance de TP (salle machine) — le professeur intervient peu et l’enregistrement est dominé par le bruit de la salle ; le contenu ci-dessous est reconstruit à partir de l’énoncé, du code MATLAB et des « Rappels théoriques ». Les rares passages oraux fiables sont regroupés plus bas.

Support écrit de référence : Rappels théoriques.pdf — chapitre 1, § 1.1 (p. 2-4).

---

Énoncé — TD 3 (Partie 2) : Factorisation $LU$

Énoncé : Énoncé TD 3.pdf — code MATLAB de la session : LUClassique.m, LUPivotPartiel.m, permu_ligne.m, inferior.m, superior.m, Substi.m, launch.m.

• ⚠️ Discrepance de noms : le matériel est rangé dans le dossier « TD - 4 », mais le PDF de l’énoncé s’intitule « TD 3 » (Énoncé TD 3.pdf). Le contenu correspond bien à cette session (factorisation $LU$).

Exercice 1. On considère les matrices suivantes :

$$A=\left(\begin{array}{ccc}1& 2& 3\\ 2& 4& 1\\ 4& 6& 7\end{array}\right)(3\times 3),B=\left(\begin{array}{cccc}2& 1& 0& 0\\ 4& -2& 1& 0\\ 0& 4& 0& 1\\ 0& 0& 4& 7\end{array}\right)(4\times 4),C=\left(\begin{array}{cccc}2& 1& 0& 0\\ 0& -2& 1& 0\\ -1& 0& 1& 1\\ 0& 0& 0& 7\end{array}\right)(4\times 4).$$

On vous demande de :

• calculer la factorisation $LU$ classique des matrices $A$, $B$ et $C$ ;
• calculer la factorisation $LU$ avec pivotage partiel des matrices $A$ et $B$ ;
• calculer la factorisation $LU$ avec pivotage complet de la matrice $C$.

Exercice 2. Créer une fonction Matlab function [L,U] = LUClassique(A,n) donnant la factorisation $LU$ classique. INPUT $A$ (ordre $n$) ; OUTPUT $L$ triangulaire inférieure, $U$ triangulaire supérieure telle que $A=LU$. INFO : affiche un message d’erreur si un des pivots est nul. Tester sur $A$, $B$, $C$ ; comparer avec les résultats à la main.

Exercice 3. Créer function [L,U,P] = LUPivotPartiel(A,n) ($PA=LU$). On implémentera d’abord function A = permu_ligne(A,l1,l2) (permute deux lignes). Tester sur $A$, $B$, $C$.

Exercices supplémentaires

Exercice 4. Créer function [L,U,P,Q] = LUPivotComplet(A,n) telle que $PAQ=LU$. Tester sur $C$.

Exercice 5. Créer trois fonctions Matlab donnant la solution d’un système carré $Ax=b$ via factorisation $LU$ : (a) classique, (b) avec pivotage partiel, (c) avec pivotage complet. Systèmes de test :

$$\text{Systeˋme 1 : }\left(\begin{array}{cccc}2& 1& 0& 0\\ 4& -2& 1& 0\\ 0& 4& 0& 1\\ 0& 0& 4& 7\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)=\left(\begin{array}{c}2\\ -3\\ 7\\ 6\end{array}\right),\text{Systeˋme 2 : }\left(\begin{array}{cccc}2& 1& 0& 0\\ 0& -2& 1& 0\\ -1& 0& 1& 1\\ 0& 0& 0& 7\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\\ x_3\\ x_4\end{array}\right)=\left(\begin{array}{c}4\\ 1\\ -3\\ 2\end{array}\right).$$

🎓 syllabus : Rappels théoriques ch. 1 § 1.1 (p. 2-4) — « Factorisation $LU$ » (p. 2-3), « Pivotage partiel » et « Pivotage complet » (p. 3), formule $PAQ=LU$ (p. 3) et résolution $Ax=b$ par $Ly=Pb$, $Uz=y$, $x=Qz$ (p. 4).

---

Code MATLAB de la séance

LUClassique.m — fourni complet

Signature fournie : function [L,U]=LUClassique(A) (⚠️ l’énoncé demande LUClassique(A,n)). Elle calcule $A=LU$ colonne par colonne en mettant à jour $A$ sur place : à l’étape $k$, on stocke la colonne $k$ de $L$, on recopie la ligne $k$ dans $U$, puis on soustrait $l_{ik}{u}_{kj}$ au bloc restant.

for k = 1 : n - 1
    for i = k:n
        L(i , k) = A(i ,k)/A(k , k);
        for j = k : n
            if A(k , k) == 0
                error("Le pivot est nul")
            end
            U(k , j) = A(k , j);
            if i ~= k && j ~= k
                A(i , j) = A(i , j) - L(i , k)*U(k , j);
            end
        end
    end
% Pas 3 : poser u_nn = a_nn et l_nn = 1
U(n,n) = A(n , n) ;
L(n , n) = 1;
end

🎓 syllabus : Rappels théoriques ch. 1 § « Factorisation LU » (p. 2-3) — « $l_{ik}:=a_{ik}^{(k)}/a_{kk}^{(k)}$, $u_{kj}:=a_{kj}^{(k)}$, $a_{ij}^{(k+1)}:=a_{ij}^{(k)}-l_{ik}{u}_{kj}$ » ; « Les $a_{kk}^{(k)}$ sont appelés pivots et l’algorithme suppose qu’ils sont non nuls ».

• ⚠️ À vérifier dans le fichier fourni (constat, sans conclure) : le test if A(k,k)==0 est placé après la division L(i,k)=A(i,k)/A(k,k) — un pivot nul serait donc utilisé avant d’être testé. Le « Pas 3 » (U(n,n), L(n,n)) comme le end du for k semblent à l’intérieur de la boucle k. C’est l’état du fichier provisoire, à confirmer avec le prof.

LUPivotPartiel.m — à compléter

Squelette à remplir (les parties ... votre code ici ...). Le schéma attendu suit le syllabus :

for k=1:n-1
    % choisir un indice s dans {k,...,n} tel que |a(k)_sk| = max_l |a(k)_lk|
    ... votre code ici ...
    % permuter les lignes l et s dans A(k) et dans L
    ... votre code ici ...
    % mettre a jour P, la matrice de permutation
    ... votre code ici ...
    % mettre a jour L, U et A
    ... votre code ici ...
end

• À implémenter : choisir $s$ tel que $|a_{sk}^{(k)}|={\max }_{l\in \{k,\dots ,n\}}|a_{lk}^{(k)}|$ ; permuter la ligne $k$ avec la ligne $s$ dans $A$ et dans $L$ ; accumuler $P$ ; puis effectuer la mise à jour $LU$ habituelle.
• On utilise d’abord la fonction permu_ligne (voir ci-dessous).

🎓 syllabus : Rappels théoriques ch. 1 § « Pivotage partiel » (p. 3) — on choisit $s$ maximisant $|a_{lk}^{(k)}|$ sur $l\in \{k,\dots ,n\}$, puis on permute la ligne $k$ avec la ligne $s$ dans $A^{(k)}$ et dans $L$.

permu_ligne.m — à compléter

Squelette function A=permu_ligne(A,l1,l2) à remplir (... votre code ici ...) : renvoie $A$ avec les lignes $l_1$ et $l_2$ permutées.

inferior.m, superior.m, Substi.m — helpers fournis

• inferior(M) / superior(M) : testent si $M$ est triangulaire inférieure / supérieure (parcours while, affichage d’un message).
• Substi(A,b) : résout $Ax=b$ pour $A$ triangulaire — substitution régressive si $A$ est supérieure, progressive si elle est inférieure ; error(...) sinon.

if (testSup == true)      % substitution régressive
    x(N) = b(N)/A(N,N);
    for i = N-1:-1:1
        s = 0;
        for j = i+1:N
            s = s + A(i,j)*x(j);
        end
        x(i) = (b(i)-s)/A(i,i);
    end
elseif (testInf == true)  % substitution progressive
    x(1) = b(1)/A(1,1);
    for i = 2:N
        s = 0;
        for j = 1:i
            s = s + A(i,j)*x(j);
        end
        x(i) = (b(i)-s)/A(i,i);
    end
else
    error("Votre matrice n'est pas triangulaire")
end

🎓 syllabus : Rappels théoriques ch. 1 § 1.1 (p. 2) — triangulaire inférieure → substitution progressive ($x_i=(b_i-{\sum }_{j<i}{a}_{ij}{x}_j)/a_{ii}$) ; triangulaire supérieure → substitution régressive ($x_i=(b_i-{\sum }_{j>i}{a}_{ij}{x}_j)/a_{ii}$).

• ⚠️ À vérifier dans le fichier fourni : dans la branche progressive, la somme interne va de j = 1:i (elle inclut donc $a_{ii}{x}_i$, pas encore calculé) ; à confirmer avec le prof.

launch.m — script de test

Script de vérification : il factorise $B$ puis contrôle L*U contre $B$, et (section pivotage) contrôle L*U - P*A contre zéro.

B=[2 1 0 0; 4 -2 1 0; 0 4 0 1; 0 0 4 7];
[L,U] = LUClassique(B);
disp(L*U);      % vérification, doit être égal à B
...
[L,U,P] = LUPivotPartiel(A);
disp(L*U - P*A);   % doit être nul puisque PA = LU

---

Remarques orales du professeur (fragments fiables)

Le professeur n’intervient que ponctuellement ; seules les phrases suivantes sont exploitables.

• But de la séance / travail de groupe — [00:01:13] : « Vous allez devoir dans le travail de groupe utiliser la factorisation LU avec pivotage partiel et sans pivotage. Donc vous devez faire en sorte que, pour le travail de groupe, vos codes soient opérationnels. Pour l’implémentation, basez-vous sur les rappels qu’il y a sur le campus. »
• Construction de $P$ — [00:00:45] : « il y avait juste l’aspect algorithmique pour [celle] avec le pivotage, où on n’a pas spécialement expliqué comment construire la matrice $P$ au fur et à mesure des itérations. Mais… quand on [écrivait] la matrice $P$ tout à la fin, à chaque fois, on prenait la matrice identité et on appliquait $E_i$ sur le résultat précédent. »
• Exercice 5 (résolution $AX=B$) — [00:02:01] : « C’est plutôt l’exercice 5 que je trouvais intéressant : à partir de la factorisation LU que vous avez trouvée, résoudre différents systèmes linéaires $AX=B$ via la factorisation LU. »
• Pivot nul $\Rightarrow$ division par zéro — [00:44:11] : « si jamais tu as un pivot qui est nul, tu dois lui dire : « Attention, il y a un pivot nul, on arrête tout ce qui se passe. » Il faut mettre un message [d’erreur] et sortir [de l’algorithme]. » ; [00:50:07] : « dès que vous avez un pivot nul, vous sortez de votre boucle et vous envoyez un message et vous dites que la factorisation n’est pas possible. »
• $\mathrm{NaN}$ — [00:43:15] : « Un $\mathrm{NaN}$, c’est quelque chose qui n’est pas représentatif… typiquement une opération qui n’a pas de [sens] » (résultat d’une division par zéro).
• break vs flag — [01:01:21] : « Je vous conseille [d’]utiliser un flag, parce que si vous mettez break, il va sortir uniquement de la première boucle for… vous mettez un flag. »
• Maximum en valeur absolue / fonction max — [01:33:23] : « Vous avez deux possibilités : soit vous faites un code qui calcule le maximum d’un vecteur… soit vous pouvez utiliser la fonction max de MATLAB. » ; [01:34:19] : « Vous mettez max([1, 2, 3]), il va vous donner $3$. Ça ne vous arrange pas. » — « ce qui vous intéresse, c’est où est le $4$ ? » → [M, I] = max(...).

---

Points clés

• But du TP : implémenter $A=LU$ (classique et pivotage partiel), la permutation de lignes, puis résoudre $AX=B$ par $Ly=Pb$, $Ux=y$.
• Factorisation : $L$ normée ($l_{ii}=1$), remplie colonne par colonne → $n-1$ étapes ; $l_{ik}=a_{ik}^{(k)}/a_{kk}^{(k)}$, $u_{kj}=a_{kj}^{(k)}$, $a_{ij}\leftarrow a_{ij}-l_{ik}{u}_{kj}$.
• Pivot nul (sans pivotage) ⟹ division par zéro ($\mathrm{NaN}$ / $\pm \infty$) : afficher un message d’erreur et arrêter.
• Pivotage partiel : $s$ tel que $|a_{sk}|={\max }_{l\ge k}|a_{lk}|$ ; permuter $A$ et $L$ ; sortir d’une double boucle par un flag, pas par un break.
• MATLAB : max seul donne la valeur ; [M,I]=max(...) donne aussi l’indice (la ligne à permuter).
• Vérification : L*U == A (classique) et L*U - P*A == 0 (pivotage) — voir launch.m.

Doutes / à vérifier

• ⚠️ Audio peu informatif : séance en salle machine, l’enregistrement est dominé par les conversations des étudiants ; seules les phrases citées ci-dessus sont fiables.
• ⚠️ Notes - Facto LU.pdf (dossier « TD - 4 ») est manuscrit : l’OCR est illisible → non utilisé comme source.
• ⚠️ Identité du professeur non confirmée dans l’audio ; on reprend la mention des TD précédents (« nouveau titulaire, remplace M. Wreckin »).
• ⚠️ Points de code à confirmer : dans LUClassique.m, le test if A(k,k)==0 est placé après la division, et le « Pas 3 » semble dans la boucle k ; dans Substi.m, la somme progressive va jusqu’à j=i. Ce sont des constats sur les fichiers fournis, pas des conclusions.