TD2 - ALG II

TD — Algèbre II 2 : élimination de Gauss et substitution

🔊 Écouter la source audio

Couverture : de 00:00:00 à 01:59:46 sur un audio de 02:00:04 (2 h 00). Le prof explique les algorithmes et fait les exercices au tableau jusqu’à 01:09:14, puis laisse une longue séance de travail individuel (≈ 01:09 → 01:52) où il ne parle que par intermittence pour aider ; il reprend une correction collective guidée de la structure de la substitution de 01:52:58 à 02:00:04.

Support : énoncé TD2.pdf + les fonctions MATLAB pré-complétées fournies sur WebCampus (dossier « TD2 – élimination de Gauss / substitution régressive ») : Substi.m, ElimGauss.m, ElimGaussPerm.m, permutation.m, launch.m, superior.m, inferior.m. Tout est dans Bac 2/ALG II/Exo/TD - 2/ ; le TD repose sur le ALG II - Cours 3 (systèmes carrés, $PA=LU$, pivotage).

---

PARTIE 1 — Contexte : système $AX=B$ et matrices triangulaires — [00:00:00]

1. Comment se déroulent les TD — [00:00:00]

• « Ce qu’on va souvent faire, c’est faire… une résolution analytique des méthodes et des algorithmes que vous avez vus dans le cadre du cours de théorie. Et à chaque fois, implémenter ces méthodes sur machine. »
• « Il se peut que parfois les deux heures ne soient pas assez pour faire l’implémentation des méthodes… il ne faut pas hésiter à terminer chez vous. »
• Ne pas compter sur une éventuelle heure de RAB en fin de quadri : « ne comptez pas sur ça » ; si une séance n’est pas finie, « une séance est terminée chez vous et posez des questions par rapport à ça ».

2. Contexte du jour : $A$ carrée, $\det A\ne 0$ — [00:00:46]

• « Aujourd’hui… on va travailler sur l’élimination de Gauss et la méthode de substitution » pour résoudre les systèmes $AX=B$.
• ⚠️ En général $A$ est rectangulaire ($m$ lignes, $n$ colonnes) ; « ici, aujourd’hui, on va supposer que $m$ est égal à $n$, c’est-à-dire que la matrice est carrée ».
• Comme on cherche la solution (système déterminé) : « on va supposer que le déterminant de la matrice est non nul », c’est-à-dire que la matrice est inversible ⚠️ [sic : « un persil » enregistré — comp. « non singulière »].
• « En fonction du type de système et du type de matrice, vous avez différentes possibilités » → le cas le plus simple : les matrices triangulaires.

3. Matrices triangulaires : substitution régressive ou progressive — [00:01:25]

• Triangulaire supérieure → substitution régressive ; triangulaire inférieure → substitution progressive.
• « Ceci… vous l’avez bien vu décomposé… dans le cadre du cours de théorie ? Oui ? »

$$\text{tri. infeˊrieure}⟹\text{substitution progressive};\text{tri. supeˊrieure}⟹\text{substitution reˊgressive}$$

---

PARTIE 2 — Exercice 1 : substitution régressive sur un système triangulaire — [00:02:09]

4. L’exemple : un système triangulaire supérieur $4\times 4$ — [00:02:09]

On demande de résoudre $AX=B$ avec ($n=4$) :

$$A=\left[\begin{array}{cccc}2& -6& 6& 4\\ 0& 1& -1& 0\\ 0& 0& -1& 1\\ 0& 0& 0& 4\end{array}\right]B=\left[\begin{array}{c}2\\ -3\\ 5\\ 10\end{array}\right]$$

• « Vous êtes dans quel cas de figure ici ? — Matrice [triangulaire] supérieure. » → substitution régressive : « je vais [remonter] du bas vers le haut ».
• ⚠️ La lecture orale de la matrice est très dégradée dans la transcription [00:02:30] ; les valeurs ci-dessus sont celles de l’énoncé/launch.m, et elles sont cohérentes avec tous les calculs faits au tableau (cf. § 5).

5. Application : $x_4$, $x_3$, $x_2$, $x_1$ — [00:03:24]

Le principe récité à l’oral (« on applique une recette, mais vous pouvez tous comprendre pourquoi on arrive à cette formule-là ») :

$$x_n=\frac{b_n}{a_{nn}};x_i=\frac{1}{a_{ii}}(b_i-\sum _{j=i+1}^n{a}_{ij}{x}_j)(i=n-1,\dots ,1)$$

• $x_4=\frac{b_4}{a_{44}}=\frac{10}{4}=\frac{5}{2}$ ⚠️ [00:08:56] « 5B » enregistré = 5/2.
• $x_3=\frac{5-1\cdot \frac{5}{2}}{-1}=\frac{5-2,5}{-1}=-2,5=-\frac{5}{2}$ → « j’ai 5 moins 2,5, ça fait de nouveau 2,5, donc je me retrouve avec moins 5 demis » ⚠️ le coefficient $a_{34}=+1$ ; le signe moins vient du dénominateur $-1$.
• $x_2=\frac{b_2-a_{23}{x}_3-a_{24}{x}_4}{a_{22}}=\frac{-3-(-1)(-\frac{5}{2})-0}{1}=-\frac{11}{2}$ (le terme en $a_{24}$ saut car $a_{24}=0$).
• $x_1=\frac{2-(-6)(-\frac{11}{2})-6(-\frac{5}{2})-4(\frac{5}{2})}{2}=\frac{2-(33-15+10)}{2}=\frac{2-28}{2}=-13$ → la ligne 1 donne « moins 66 sur 2 » ($-6\cdot \frac{11}{2}$), « plus [30] sur 2 » ($-6\cdot \frac{-5}{2}$), « moins 20 sur 2 » ($-4\cdot \frac{5}{2}$) « ça fait moins 13 ».

$$\boxed{x=(-13,-\frac{11}{2},-\frac{5}{2},\frac{5}{2})}$$

⚠️ Vérification des signes du transcript partiellement bruitée [00:07:40–00:09:35] ; le résultat $-13$ est confirmé en remplaçant dans la première équation ($2(-13)-6(-\frac{11}{2})+6(-\frac{5}{2})+4\cdot \frac{5}{2}=2$).

6. Pourquoi cette formule marche — [00:09:36]

• La raison se lit de bas en haut : la dernière équation donne directement $x_n$ ; chaque équation suivante, étant triangulaire supérieure, ne fait intervenir que $x_i$ et des $x_j$ déjà calculés → on isole $x_i$ en fonction du reste.
• « C’est comme ça que je fais apparaître au final la somme des éléments $a_{ij}$ des inconnues que j’ai déjà pu calculer. »

7. Cramer : écarté en pratique — [00:10:30]

• « La méthode de Cramer est une méthode que vous avez vue aussi… Alors, on ne va pas le faire ici… parce que ce n’est pas spécialement pertinent. » Pour une matrice $4\times 4$, « je vous demande de calculer à chaque fois 4 déterminants ».
• « Vous pouvez l’implémenter numériquement si vous le souhaitez, mais ici, en pratique, ça n’a pas d’intérêt. Au final, on passerait le délai à calculer 4 déterminants, ce qui n’est pas le but. »

---

PARTIE 3 — Dérivation de l’algorithme d’élimination de Gauss — [00:11:04]

8. Objectif : transformer $AX=B$ en système triangulaire — [00:11:04]

• Le prof interroge : dans le cours de théorie, avez-vous vu d’où vient la formule de Gauss ? Réponse : globalement non, « vous faisiez des opérations sur des lignes, vous soustrayiez des lignes… mais vous n’avez pas vu pourquoi on arrive à cette formule finale ». → « On va le voir alors, pourquoi on peut faire ça. »
• « Le but de l’élimination de Gauss : partir d’un système d’équations linéaires et progressivement transformer ce système en un système triangulaire, en faisant des opérations sur les lignes. »
• Formalisation : on transforme $AX=B$ en une suite de systèmes $A^{k}X=B^k$ où, « à chaque étape $k$, on élimine la variable $x_k$ des équations $k+1$ jusqu’à $n$ » ; « après $n-1$ étapes, on obtient un système triangulaire (supérieur) ».

$$AX=B\stackrel{\text{eˊtape }k}{\to }{A}^{k+1}X=B^{k+1}\stackrel{n-1\text{ eˊtapes}}{\to }\text{triangulaire supeˊrieur }{A}^n$$

• « En théorie, on vous dit : prenez une telle ligne, faites la ligne moins la ligne… mais c’est pas évident de transformer ça numériquement en un programme. » D’où l’étude de l’itération générique $k\to k+1$ : si on sait faire une étape, on sait répéter.

9. L’itération $k\to k+1$ : exemple générique $n=5$ à l’étape 3 — [00:15:59]

On suppose $n=5$ et on débute l’étape $k=3$ ; la forme de la matrice est alors :

$$\left[\begin{array}{ccccc}\cdot & \cdot & \cdot & \cdot & \cdot \\ & \cdot & \cdot & \cdot & \cdot \\ & & \underset{\text{ligne du pivot}}{\underbrace{a_{33}{a}_{34}{a}_{35}}}& & \\ & & a_{43}{a}_{44}{a}_{45}& & \\ & & a_{53}{a}_{54}{a}_{55}& & \end{array}\right]B=\left[\begin{array}{c}{b}_1\\ b_2\\ b_3\\ b_4\\ b_5\end{array}\right]$$

• Les $0$ sous la diagonale aux colonnes $1,2$ proviennent des étapes 1 et 2 : « à l’étape 1, j’ai éliminé $x_1$ dans toutes les autres équations… ici, je n’ai plus de $x_2$ ». On ne touche pas à $b_3$ (déjà mis à jour) mais on travailler avec $b_3,b_4,b_5$.
• Mise à zéro : « je viens mettre un zéro [en position] $a_{43}$ en soustrayant un certain nombre de fois la ligne 3 ». Question : quel facteur mettre devant $L_3$ ? → $L_4\leftarrow L_4-\frac{a_{43}}{a_{33}}\cdot L_3$, « comme ça, si je multiplie par $a_{33}$, je fais bien apparaître un 0 ». Idem $L_5\leftarrow L_5-\frac{a_{53}}{a_{33}}\cdot L_3$.
• Pourquoi cette opération est-elle licite ? « on garde des systèmes qui sont équivalents, et s’ils sont équivalents, ils auront la même solution ». ⚠️ Concret : remplacer une ligne par elle-même moins un multiple d’une autre ligne ; on ne peut pas remplacer une ligne par un multiple seul d’une autre (« vous ne pourriez pas », passage bruité).
• Pourquoi ne travailler qu’à partir de la ligne du pivot ? Si pour mettre un zéro en $a_{43}$ on utilisait la ligne 2 (déjà triangulée), « à la place du 0, je viens mettre une croix → on perd le système triangulaire » ; « c’est ça qui est important de travailler à partir du pivot » : « si on perd ça, on perd tout ce qu’on a déjà fait, tout l’aspect triangulaire ».
• Le pivot $a_{33}$ ne bouge pas (il reste inchangé) ainsi que tout ce qui précède.

10. La formule de mise à jour : $a_{ij}\leftarrow a_{ij}-\frac{a_{ik}}{a_{kk}}{a}_{kj}$ — [00:25:42]

En raisonnant sur les coefficients ($k=3$, ligne du pivot fixée, colonnes variables) :

• Chaque élément du bloc conservé garde sa valeur moins le facteur $\frac{a_{ik}}{a_{kk}}$ × l’élément de la ligne du pivot :

$$a_{ij}^{(k+1)}=a_{ij}^{(k)}-\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}{a}_{kj}^{(k)}i,j=k+1,\dots ,n$$

• « Ce gros mastodonte qu’on avait [dans la théorie]… il s’explique de manière assez rigoureuse. » Pour $i=1,\dots ,k$ on recopie la même chose (et on met des zéros là où prévu) ; ici « vous voyez bien que pour la matrice $A$, ce que j’obtiens… c’est bien $a_{ij}-a_{ik}/a_{kk}$ ».

11. Mise à jour du second membre $B$ — [00:27:56]

• « J’ai fait exactement la même chose pour $B$ » : on retire le même facteur à l’élément $b_i$ correspondant :

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

• Pour $i\le k$ les équations « font partie… de ma triangulaire supérieure » : on les laisse inchangées.
• « Est-ce que c’est clair pour tout le monde ? … pour $B_i$ ça va ? Ou il faut l’écrire ? » → le prof écrit la ligne $b_4$ de l’exemple : $b_4^{(k+1)}=b_4^{(k)}-\frac{a_{43}}{a_{33}}{b}_3^{(k)}$.

12. Hypothèse implicite : pivots non nuls — [00:30:51]

• « Il y a quand même une certaine hypothèse implicite qu’on fait quand on fait cet algorithme. Quelle est cette hypothèse ? — On n’aura pas de pivots nuls. »
• « L’algorithme est bien posé si $a_{kk}\ne 0$ pour tout $k=1,\dots ,n$ » → on rencontrera ce cas à la Partie 6 (pivotage).

---

PARTIE 4 — Exercice 2a : élimination de Gauss à la main — [00:31:57]

13. Système, initialisation et la méthode « encadrer la sous-matrice » — [00:31:57]

Système test (Exercice 2a de l’énoncé) :

$$A=\left[\begin{array}{cccc}1& 2& 1& 1\\ 0& 1& 2& 1\\ 1& 0& 1& 2\\ 2& 1& 0& 1\end{array}\right]b=\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]$$

• « Poser $k=1$ : initialiser, il n’y a rien à faire » → $A^{(1)}=A$, $b^{(1)}=b$. On construit $A^{(2)}$ : la première ligne reste la même (« pas besoin de calcul »).
• « À la première étape, la seule chose qu’on doit venir calculer nous-mêmes, c’est les éléments qui font partie de la sous-matrice $k+1$ jusqu’à $n$ . »
• ⚠️ Méthode mémotechnique recommandée [00:34:50] : au lieu de recopier toutes les valeurs, « vous entourez la sous-matrice que vous devez mettre à jour » ; pour chaque élément, regarder le plus proche sur la ligne du pivot et sur la colonne du pivot :

$$\text{nouvel eˊleˊment}=\text{eˊleˊment}-\frac{\text{eˊleˊment sur la colonne du pivot}}{\text{pivot}}\times \text{eˊleˊment sur la ligne du pivot}$$

• « Et de manière générale, quand vous avez un 0 ici, ne calculez jamais, par pitié ! Dès que j’ai un 0 [dans la colonne du pivot], je vais tout multiplier par 0 sur la ligne en question… je vais garder exactement les mêmes éléments. »
• Étape $k=1$ (pivot $a_{11}=1$) : $L_2$ inchangée ($a_{21}=0$) ; $L_3\leftarrow L_3-L_1=[0,-2,0,1]$ ; $L_4\leftarrow L_4-2L_1=[0,-3,-2,-1]$. Le second membre ne change pas (les facteurs se multiplient par $b_1=0$).

$$A^{(2)}=\left[\begin{array}{cccc}1& 2& 1& 1\\ 0& 1& 2& 1\\ 0& -2& 0& 1\\ 0& -3& -2& -1\end{array}\right]b^{(2)}=\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]$$

14. Étapes $k=2$ puis $k=3$ — [00:40:12]

• Étape $k=2$, pivot $a_{22}=1$ : on recopie tout ce qui précède et on ne met à jour que la sous-matrice $\mathrm{3..4}\times \mathrm{3..4}$.
  • $L_3\leftarrow L_3-(-2)L_2=[0,0,4,3]$ (car $\frac{a_{32}}{a_{22}}=\frac{-2}{1}$) ;
  • $L_4\leftarrow L_4-(-3)L_2=[0,0,4,2]$ ;
  • $b$ inchangé car $b_2=0$.

$$A^{(3)}=\left[\begin{array}{cccc}1& 2& 1& 1\\ 0& 1& 2& 1\\ 0& 0& 4& 3\\ 0& 0& 4& 2\end{array}\right]b^{(3)}=\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]$$

• Étape $k=3$, pivot $a_{33}=4$ : seul $L_4$ change, 2 − 4·3/4 = 2 − 3 = −1 en $a_{44}$ et 0 − 4·1/4 = −1 en $a_{43}$ ; $b_4=0-1\cdot 1=-1$.

$$A^{(4)}=\left[\begin{array}{cccc}1& 2& 1& 1\\ 0& 1& 2& 1\\ 0& 0& 4& 3\\ 0& 0& 0& -1\end{array}\right]b^{(4)}=\left[\begin{array}{c}0\\ 0\\ 1\\ -1\end{array}\right]$$

15. Substitution régressive finale — [00:44:11]

« Il vous reste à résoudre $A^{(4)}x=b^{(4)}$ via la substitution régressive. »

• $x_4=\frac{-1}{-1}=1$ ; $x_3=\frac{1-3\cdot 1}{4}=-\frac{1}{2}$ ; $x_2=\frac{0-(2\cdot (-\frac{1}{2})+1\cdot 1)}{1}=0$ ; $x_1=\frac{0-(2\cdot 0+1\cdot (-\frac{1}{2})+1\cdot 1)}{1}=-\frac{1}{2}$.

$$\boxed{x=(-\frac{1}{2},0,-\frac{1}{2},1)}$$

⚠️ Le transcript [00:36:00–00:39:00] mélange les valeurs ; les matrices $A^{(2)},A^{(3)},A^{(4)}$ ci-dessus sont vérifiées par l’algorithme et compatibles avec les valeurs lues (« 2 moins 4 fois 3 sur 4 → 2 moins 3 = moins 1 », « 0… divisé par 4 → moins 1 »).

---

PARTIE 5 — Coder : écraser en place, pas de matrices intermédiaires — [00:45:29]

16. Une seule matrice en mémoire — [00:45:29]

• « Vous voyez ici qu’à chaque étape, on stocke une nouvelle matrice. J’ai $A^{(1)},A^{(2)},A^{(3)},A^{(4)}$. Est-ce que je suis obligé [d’en créer de nouvelles] ? — Non. »
• Deux raisons :
  1. la taille ne change jamais : « on garde un système à $n$ équations, $n$ inconnues… je sais qu’à la fin je vais garder un nombre d’équations » ;
  2. « quand on arrive à la matrice $A^{(3)}$, on n’a plus besoin de celles de $A^{(1)}$ et $A^{(2)}$ » → « tout ce qui a été calculé avant, vous pouvez le remettre dans la matrice que vous êtes en train de traiter… autant le laisser ».
• « En écrasant dans la matrice en question, vous gardez une seule matrice en mémoire, et à la fin de vos itérations, la matrice $A$ que vous avez écrasée est une matrice triangulaire. »
• ⚠️ Ordre des opérations : il faut utiliser les valeurs courantes de la ligne du pivot pour créer les nouvelles, puis écraser (sinon on multiplie par des $0$ avant d’avoir utilisé la ligne : « vous n’avez rien changé »).
• Motivation mémoire : une matrice $5\times 5$, $10\times 10$ même $100\times 100$, « ce n’est pas un problème » ; mais « une matrice 10 millions × 10 millions… créer 10 millions de matrices intermédiaires, là ça commence à devenir chaud et inutile ».

---

PARTIE 6 — Pivot nul : le pivotage (permutation de lignes) — [00:48:19]

17. Que faire si un pivot est nul — [00:48:19]

• « Qu’est-ce qui se passe si un pivot est nul dans l’élimination de Gauss ? — Permuter les lignes. »
• « On regarde, parmi les lignes du pivot, un élément non nul, je viens permuter les lignes et je continue à partir de là. De nouveau, permuter les lignes ne change pas le système d’équations. → on parle de pivotage. »
• ⚠️ « Vous n’allez travailler qu’entre les lignes qui sont en dessous du pivot. Pourquoi ? Si vous allez chopper la deuxième ligne que vous venez de [traiter]… vous n’allez plus avoir une matrice triangulaire supérieure. »

18. Exercice 3 : exemple avec permutation — [00:49:29]

Système (Exercice 3 de l’énoncé) :

$$A=\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 2\\ 2& 3& 4\end{array}\right]b=\left[\begin{array}{c}8\\ 11\\ 12\end{array}\right]$$

• Étape $k=1$, pivot $a_{11}=1$ :
  • $L_2\leftarrow L_2-L_1=[0,0,1]$, $b_2=11-8=3$ ;
  • $L_3\leftarrow L_3-2L_1=[0,1,2]$, $b_3=12-2\cdot 8=-4$.
• Étape $k=2$ : pivot $a_{22}^{(2)}=0$ → on permute les lignes 2 et 3 (celle de $b$ avec) :

$$A_{(2)}=\left[\begin{array}{ccc}1& 1& 1\\ 0& 1& 2\\ 0& 0& 1\end{array}\right]b_{(2)}=\left[\begin{array}{c}8\\ -4\\ 3\end{array}\right]$$

• « Attention, si vous avez changé [les lignes] dans $A$, changez aussi dans $B$, parce que l’équation fait intervenir aussi le second membre. »
• Le système est désormais triangulaire supérieur → « pas besoin de continuer » (les deux dernières lignes forment un bloc triangulaire $2\times 2$).
• (Q&R sur le code [00:54:32–00:58:17], bruitées : il faut renvoyer les vecteurs permutés — analogie Python « $v=4$, return $v$ » — et surtout permuter $b$ aussi.)

$$\text{solution}:x_3=3,x_2=-4-2\cdot 3=-10,x_1=8-(-10)-3=15⟹\boxed{x=(15,-10,3)}$$

---

PARTIE 7 — Implémentation MATLAB — [01:02:41]

19. Les fichiers fournis (pré-complétés) — [01:02:41]

• « Cette deuxième [séance], vous allez implémenter la substitution régressive et la méthode d’élimination de Gauss avec et sans permutation en MATLAB. »
• « Vous ne codez pas depuis zéro » : sur WebCampus, section « TD2 – élimination de Gauss, substitution régressive », il y a l’énoncé + les fonctions MATLAB pré-complétées : « vous devez juste compléter aux endroits [indiqués] ».
• Fichiers concernés :
  • Substi.m : solution de $AX=B$ (substitution régressive et progressive) ;
  • ElimGauss.m : élimination de Gauss sans permutation ;
  • ElimGaussPerm.m : élimination de Gauss avec permutation ;
  • permutation.m : fonction d’aide (pas obligatoire) qui permute deux lignes quand un pivot est nul ;
  • launch.m : le « main » (dans chaque section : une matrice, un second membre, l’appel de la fonction) ;
  • superior.m / inferior.m : la correction de la semaine passée pour tester si une matrice est triangulaire supérieure/inférieure.

20. Les règles de code — [01:03:33]

• Base de travail : « pour l’élimination de Gauss, basez-vous sur l’algorithme présenté ici… une boucle de 1 jusqu’à $n-1$ dans laquelle vous faites ces différentes opérations ». C’est « une double boucle » pour le sous-bloc.
• ⚠️ A\b : « en MATLAB, ce slash, quand vous faites A\b, ça va vous donner la solution du système $Ax=b$ » (méthode interne de MATLAB = vérité de référence). → on compare Substi(A,b) / ElimGauss(A,b) avec A\b pour vérifier.
• « Toutes vos fonctions ainsi que le main dans lequel sont appelées vos fonctions doivent être enregistrés dans le même dossier. »
• ⚠️ « Ne venez pas créer plein de matrices intermédiaires. Écrasez tout dans la même matrice que vous retournez à la fin de votre algorithme. »
• Le prof ne donnera pas la solution des codes (« vous savez vérifier si vous avez la bonne réponse », via A\b) ; il passe entre les bancs pour débuguer et aiguiller.

21. Consignes pratiques et évaluation — [01:07:35]

• « Pour tester si votre matrice est triangulaire supérieure ou inférieure, n’hésitez pas à utiliser la correction que je vous ai donnée la semaine passée… c’est pour ça que la question posée la semaine dernière n’était pas anodine. » Sans perte de généralité, on suppose que l’utilisateur a rentré « une INF ou une SUP » et « on regarde juste laquelle ».
• ⚠️ Sauvegarde : « n’oubliez pas de vous sauvegarder ou de vous envoyer votre code » (les PC du pool ne conservent rien) — le travail de groupe demandera des codes fonctionnels et complétés.
• « La partie MATLAB sera beaucoup évaluée dans le travail de groupe ; à l’examen écrit, c’est beaucoup plus les développements analytiques qu’on fait ensemble au tableau. »

---

PARTIE 8 — Travail en séance : aide individuelle — [01:09:14]

22. Rappels lancés pendant le travail — [01:11:18]

• « En général, pour tout le monde : testez si la matrice est triangulaire supérieure ou inférieure. Ne perdez pas de temps là-dessus. Prenez exactement le code que je vous ai… donné en correction » ; « vous ne devez pas commencer à tester si elle est SUP, ou INF, ou aucun des deux ».
• Pendant ≈ 45 minutes le transcript n’est que bruit de fond (le prof aide les étudiants individuellement ; bribes sur n = size(A,1), la boucle inverse n-1:-1:1 et la somme, repris proprement à la Partie 9).

---

PARTIE 9 — Correction guidée : la structure de Substi et de Gauss — [01:52:58]

23. Structure de la substitution régressive/progressive — [01:52:58]

• D’abord tester la triangularité : « ça, on l’a fait au TD la semaine passée… ça permet juste de savoir si j’ai une triangulaire sup ou inf » → superior(A) / inferior(A).
• Initialisation : « x = zeros(n,1) », où « $n=$ n = size(A,1) » (nombre de lignes de $A$).
• Dernier élément (« exactement ce qu’on a fait au tableau ») : x(n) = b(n)/A(n,n).
• Boucle régressive, avec une somme intermédiaire :

for i = n-1:-1:1
    sum = 0;
    for j = i+1:n
        sum = sum + A(i,j)*x(j);     % x(j) déjà calculé
    end
    x(i) = (b(i) - sum)/A(i,i);
end

• Le piège central : « à chaque $i$ fixé, j’ai une somme à calculer… c’est pour ça que je mets sum = 0 ; for j = i+1:n ; sum = sum + A(i,j)*x(j) . » « Beaucoup d’entre vous ont buté là-dessus… La première chose que vous faites à la main, c’est calculer toute votre somme pour l’étape courante → c’est une opération que vous devez faire dans votre boucle chez vous. »
• Variante progressive (triangulaire inférieure) : x(1) = b(1)/A(1,1), puis for i = 2:n, somme sur j = 1:i (le terme $j=i$ ajoute $x(i)=0$ initial : sans effet), x(i) = (b(i) - sum)/A(i,i).

24. Rappel : squelette de l’élimination de Gauss — [01:57:11]

• « Pour une étape courante $k$, on va mettre des zéros sur une colonne… ne pas changer la première [ligne] et mettre à jour tout un sous-bloc. La mise à jour de ce sous-bloc, c’est une double boucle. »

for k = 1:n-1
    % (avec permutation : permuter une ligne sous le pivot si A(k,k) == 0)
    for i = k+1:n
        for j = k+1:n
            A(i,j) = A(i,j) - A(i,k)*A(k,j)/A(k,k);
        end
        b(i)   = b(i)   - A(i,k)*b(k)/A(k,k);
        A(i,k) = 0;
    end
end
x = Substi(A, b);        % substitution régressive finale

• Sans permutation (ElimGauss), si A(k,k) == 0 → error(...) ; avec permutation (ElimGaussPerm), on appelle permutation(A,b,k,i) dès qu’un pivot est nul.
• « Rassurez-vous, c’est normal que vous ayez du mal : c’est la deuxième fois que vous manipulez MATLAB… l’important, c’est que ce soit clair maintenant dans l’idée, que vous compreniez la mécanique et la démarche à suivre. »

---

PARTIE 10 — Fin de séance — [01:58:02]

25. Conclusion — [01:58:02]

• « On n’a pas de questions, ça va s’arrêter là pour aujourd’hui. » Travail à terminer chez soi ; les codes doivent être sauvegardés/remis (travail de groupe).

---

Points clés — [résumé]

• Deux méthodes pour $AX=B$ ($A$ carrée, $\det A\ne 0$) : la substitution (si $A$ est triangulaire) et l’élimination de Gauss (cas général).
• Substitution régressive ($A$ tri. sup.) : $x_n=b_n/a_{nn}$ ; pour $i=n-1,\dots ,1$, $x_i=(b_i-{\sum }_{j>i}{a}_{ij}{x}_j)/a_{ii}$.
• Substitution progressive ($A$ tri. inf.) : $x_1=b_1/a_{11}$ ; pour $i=2,\dots ,n$, $x_i=(b_i-{\sum }_{j<i}{a}_{ij}{x}_j)/a_{ii}$.
• Gauss = transformer $AX=B$ en système triangulaire supérieur par opérations sur les lignes $L_i\leftarrow L_i-\frac{a_{ik}}{a_{kk}}{L}_k$, puis substitution régressive.
• Itération $k$ : seuls les éléments $i,j\in \{k+1,\dots ,n\}$ changent ; $a_{ij}\leftarrow a_{ij}-\frac{a_{ik}}{a_{kk}}{a}_{kj}$ ; $b_i\leftarrow b_i-\frac{a_{ik}}{a_{kk}}{b}_k$ ; le pivot et les lignes d’au-dessus sont recopiés.
• ⚠️ Travailler uniquement à partir de la ligne du pivot, sinon on casse la forme triangulaire déjà construite.
• ⚠️ Pivot nul → pivoter (permuter la ligne avec une ligne en dessous qui a un élément non nul) et permuter $b$ en même temps.
• Code : écraser la matrice en place (une seule matrice en mémoire) ; ordre des opérations : calculer avec les valeurs courantes puis écraser.
• Mnémotechnique : « entourer la sous-matrice », et « s’il y a un 0 dans la colonne du pivot, ne jamais calculer ».
• MATLAB : fonctions + launch.m dans le même dossier ; A\b = solution MATLAB pour vérifier ; tester la triangularité via superior(A)/inferior(A) ; x = zeros(n,1) ; boucle interne de somme dans la substitution.
• Cramer écarté : en pratique, trop de déterminants à calculer.

---

Doutes / à vérifier

• ⚠️ [00:00:58–00:01:09] « en général matrice $A$ rectangulaire, $m$ lignes et $m$ colonnes » : le prof dit « $m$ » pour les deux dimensions (confusion $m=n$) ; il veut dire : en général rectangulaire $m\times n$, et aujourd’hui carrée $n\times n$.
• ⚠️ [00:01:17] « le déterminant… est un nul, c’est-à-dire que la matrice est un persil » — dictat probable de « non singulière » (= inversible, $\det A\ne 0$).
• ⚠️ [00:02:30–00:03:19] Lecture de la matrice de l’Exercice 1 complètement dégradée (« moins 6, 0, 1, moins 1, 0, 0, 0… 2 ») ; les valeurs exactes sont restaurées depuis l’énoncé et launch.m (A = [[2,-6,6,4],[0,1,-1,0],[0,0,-1,1],[0,0,0,4]], b = (2,-3,5,10)) et tous les calculs du tableau concordent.
• ⚠️ [00:08:47–00:09:02] Déroulé de $x_3$ et $x_1$ : « moi/sur 2 », « 5 moins 2,5 »… le transcript saute plusieurs nombres ; la reconstruction du § 5 est validée par retour arrière dans $AX=B$.
• ⚠️ [00:06:00–00:07:00] Pour $x_2$ : « 2 moins moins, comme le coefficient $a_{24}$ c’est $0$ » — l’ASR donne « 2 » pour $b_2=-3$ ; le calcul est rétabli dans le § 5.
• ⚠️ [00:23:20–00:24:00] Justification de la transformation de ligne : « je ne peux pas dire que $L_4$ devient $L_4$ [fois…] » (fragment « la ligne 4NL ») ; le sens (remplacer $L_4$ par $L_4-\lambda L_3$ seulement, jamais par un multiple seul) est clair mais la phrase exacte est à réécouter.
• ⚠️ [00:36:00–00:39:00] Pendant l’étape $k=1$ de l’Exercice 2a, le prof dit « l’élément courant $b_3$, c’est 0 » ; en réalité c’est $b_1=0$ (appliqué aux $b_i$ via le facteur $a_{i1}/a_{11}$) qui laisse $b$ inchangé à l’étape 1, et c’est $b_2=0$ qui le laisse inchangé à l’étape 2. Le transcript brouille $b_1$/$b_2$/$b_3$.
• ⚠️ [00:54:32–00:58:17] Discussion sur permutation (retour des vecteurs, mise à jour de $b$) copieuses et très bruitées (« il y a une colonne… c’est la colonne ») ; les seuls points fiables sont : on permute deux lignes (avec les $b$ correspondants) et on renvoie/affecte les résultats.
• ⚠️ [01:28:00–01:31:00] « Un vecteur de 0… on remplit parenthèse 4… parfois de moins 1… 2 points de moins 1 » : a mangé la discussion de x = zeros(n,1) et de la boucle for i = n-1:-1:1 (le « 2 points » = deux-points : de la syntaxe MATLAB).
• ⚠️ [01:46:55–01:52:26] Interventions individuelles bruitées (n = size(A,1), indices des boucles) ; le contenu fiable est repris dans la correction collective de la Partie 9.
• ⚠️ Colonne 1 de l’Ex. 2a : le transcript annonce « [première ligne] 1, 2, 1 » pour $A^{(2)}$ mais la matrice compte 4 colonnes (1, 2, 1, 1) ; launch.m confirme $L_1=(1,2,1,1)$.

---

Annexe — l’énoncé du TD (énoncé TD2.pdf) et les codes fournis

TD 2 : Systèmes d’équations linéaires — substitution et élimination de Gauss

Implémenter les fonctions telles qu’elles sont décrites et vérifier chaque résultat avec une fonction prédéfinie de MATLAB (A\b).

Exercice 1 — [x] = Substi(A,b). À compléter dans Substi.m : résolution par substitution (régressive ou progressive) d’un système dont la matrice est triangulaire (supérieure ou inférieure). Tester avec $A=\left[\begin{array}{cccc}2& -6& 6& 4\\ 0& 1& -1& 0\\ 0& 0& -1& 1\\ 0& 0& 0& 4\end{array}\right]$ et $b=\left[\begin{array}{c}2\\ -3\\ 5\\ 10\end{array}\right]$, et vérifier avec A\b.

Exercice 2 — [x] = ElimGauss(A,b). Élimination de Gauss sans permutation, avec message d’erreur si un pivot est nul. Tester avec :

• (a) $A=\left[\begin{array}{cccc}1& 2& 1& 1\\ 0& 1& 2& 1\\ 1& 0& 1& 2\\ 2& 1& 0& 1\end{array}\right]$, $b=\left[\begin{array}{c}0\\ 0\\ 1\\ 0\end{array}\right]$ ;
• (b) $A=\left[\begin{array}{ccccc}1& 3& 4& 5& 7\\ 2& 3& 7& 10& 11\\ -3& 4& 66& -5& 7\\ -4& 1& 2& 6& 3\\ 56& 78& 1& 1& 1\end{array}\right]$, $b=\left[\begin{array}{c}8\\ 11\\ 12\\ 12\\ 12\end{array}\right]$ ⚠️ la $4^e$ ligne était tronquée dans l’extraction du PDF ; restaurée via launch.m.

Exercice 3 — [x] = ElimGaussPerm(A,b). Élimination de Gauss avec permutation de lignes quand un pivot est nul (on peut s’appuyer sur permutation.m). Tester avec $A=\left[\begin{array}{ccc}1& 1& 1\\ 1& 1& 2\\ 2& 3& 4\end{array}\right]$, $b=\left[\begin{array}{c}8\\ 11\\ 12\end{array}\right]$.

Le squelette de Substi.m (structure recopiée au tableau, § 23)

function [x] = Substi(A,b)
    N = size(A,1);
 
    testSup = superior(A);   % true si A triangulaire supérieure
    testInf = inferior(A);   % true si A triangulaire inférieure
 
    x = zeros(N,1);
 
    if (testSup == true)              % substitution régressive
        x(N) = b(N)/A(N,N);
        for i = N-1:-1:1
            sum = 0;
            for j = i+1:N
                sum = sum + A(i,j)*x(j);
            end
            x(i) = (b(i) - sum)/A(i,i);
        end
    elseif (testInf == true)          % substitution progressive
        x(1) = b(1)/A(1,1);
        for i = 2:N
            sum = 0;
            for j = 1:i
                sum = sum + A(i,j)*x(j);
            end
            x(i) = (b(i) - sum)/A(i,i);
        end
    else
        error("Votre matrice n'est pas triangulaire")
    end
end

Le squelette de l’élimination de Gauss (sans permutation, § 24)

function [x] = ElimGauss(A,b)
    N = size(A,1);
 
    for k = 1:N-1
        if (A(k,k) == 0)
            error("Vous ne pouvez pas résoudre ce système via l'élimination de Gauss")
        end
        for i = k+1:N
            for j = k+1:N
                A(i,j) = A(i,j) - A(i,k)*A(k,j)/A(k,k);
            end
            b(i)   = b(i)   - A(i,k)*b(k)/A(k,k);
            A(i,k) = 0;
        end
    end
 
    x = Substi(A,b);
end

La fonction d’aide permutation.m

function [A,b] = permutation(A,b,k,l)
    % Permute les lignes k et l de A, et les composantes k et l de b
    C = A;   c = b;
    A(k,:) = C(l,:);   A(l,:) = C(k,:);
    b(k)   = c(l);     b(l)   = c(k);
end