ALG II - Cours 1

Algèbre linéaire II — Cours 1 : systèmes linéaires, Cramer, Gauss et factorisation LU

🔊 Écouter pt1 · Écouter pt2

---

1. Évaluation et organisation du cours — [00:00]

• Examen écrit classique qui mélange exercice et théorie.
• Théorie : petites nouvelles propriétés → 80 % de la note (en session).
• Travail de cours → 20 % de la note, réalisé lors d’une séance d’exercices (sur les ordinateurs du labo).

  • La séance a lieu sur les ordinateurs du labo : vous avez accès aux machines, mais pas l’inverse (pas de travail à distance). C’est justement pour cela qu’on peut mieux contrôler le travail.

• Ceux qui ont déjà réussi le travail de groupe l’année passée peuvent être dispensés (en discuter pendant la pause).

• La prof demande qui a déjà passé le cours/suivi le travail de groupe l’année passée ; les dispenses se règlent pendant la pause.

• Rappel administratif ([00:00]) : pour toute info vous pouvez toujours aller regarder dans le syllabus, « normalement tout est au tas ».

• Avis de la prof ([00:48]) : attention à l’horaire du cours ; à partir du prochain cours, si vous n’êtes pas à l’heure, on ne rentre pas — aujourd’hui c’est le premier cours, donc toléré.

---

2. Plan du cours — [00:01]

On poursuit l’algèbre linéaire I mais avec un accent numérique.

1. Chapitre 1 — Systèmes d’équations linéaires.
2. Chapitre 2 — Problème des moindres carrés.
3. Chapitre 3 — Valeurs propres et valeurs singulières.
4. Chapitre 4 — Optimisation linéaire.

Objectif

• Approche numérique de l’algèbre linéaire 1 : des algorithmes pour retrouver les solutions.
• Méthodes directes : donnent exactement la solution.
• Méthodes itératives : en plusieurs étapes → solution approchée.
• Accent sur l’algorithme (partie “papier”) puis sur l’implémentation numérique (en TD).

Le chapitre 1 est consacré aux systèmes d’équations linéaires ; on y rencontrera notamment l’implémentation (l’élimination) de Gauss.

⚠️ La prof utilisera des abréviations en écrivant au tableau : si une abréviation ou une explication n’est pas claire, n’hésitez pas à la demander / à l’interrompre.

---

3. Définitions : équation et système linéaires — [00:05]

Équation linéaire

• Une équation exige une inconnue — ici on a plusieurs inconnues $x_1,\dots ,x_n$.
• Une équation linéaire à $n$ inconnues $x_1,\dots ,x_n$ s’écrit

$$a_1{x}_1+a_2{x}_2+\cdots +a_n{x}_n=b$$

ou en notation somme : $\sum _{i=1}^n{a}_i{x}_i=b$.

• Pourquoi linéaire : pas de $x_1{x}_2$, pas de $x_1^2$, … une simple combinaison linéaire des inconnues.
• Dans ce cours on travaille uniquement dans $\mathbb{R}$ (pas de complexes).
• Coefficients : les $a_i\in \mathbb{R}$. Second membre : le scalaire $b$.

Système d’équations linéaires

• $m$ équations linéaires reliées aux mêmes $n$ inconnues $x_1,\dots ,x_n$ :

$$\{\begin{array}{l}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n=b_1\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n=b_2\\ ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n=b_m\end{array}$$

• Coefficients : $a_{ij}$ (deux indices, $i=1\dots m$, $j=1\dots n$), tous réels. Second membre : vecteur $b=(b_1,\dots ,b_n)$.

Solution d’un système

• Pour un jeu de coefficients et un vecteur $b$ fixés : une solution est un vecteur $(x_1,\dots ,x_n)$ qui satisfait les $m$ équations du système.

---

4. Interprétation géométrique (cas $2\times 2$) — [00:13]

Pour $m=n=2$, chaque équation est l’équation d’une droite (en isolant $x_2$ : $y=px+q$). Trois cas :

Cas	Droites	Solutions
Sécantes	se croisent en un point	1 solution unique
Confondues	la même droite	infiniment de solutions
Parallèles	jamais croisées	aucune solution

• Sans solution → système inconsistant.
• Avec une ou plusieurs solutions → système consistant.

La prof demande quel objet géométrique représente une équation à 2 inconnues : un étudiant répond « un plan » — non, ce n’est pas un plan : en isolant $x_2$ (en appelant $y$ et $x$) on obtient $y=px+q$, donc chaque équation est une droite. (Attention : ne pas confondre avec le cas 3D.) On peut avoir des droites confondues (∞ solutions), sécantes (solution unique) ou parallèles (aucune).

---

5. Notation matricielle : $Ax=b$ — [00:18]

• Écrire le système avec toutes ses équations est lourd ; les inconnues n’apportent pas d’information structurelle → on passe à l’écriture matricielle.
• $A$ : matrice $m$ lignes × $n$ colonnes des coefficients (rectangulaire en général, pas carrée), $A=(a_{ij})$, $i=1\dots m$, $j=1\dots n$, ou $A\in {\mathbb{R}}^{m\times n}$.
• $x$ : vecteur colonne $(x_1,\dots ,x_n)$ ; $b$ : vecteur colonne des seconds membres.

$$\underset{m\times n}{\underbrace{A}}\underset{n}{\underbrace{x}}=\underset{m}{\underbrace{b}}$$

• Dans un premier temps on étudie les systèmes carrés ($m=n$).

Avantage d’un système carré : s’il existe une solution, on peut l’isoler ; si $A$ est inversible, la solution est

$$x=A^{-1}b.$$

Une matrice rectangulaire ne s’inverse pas (on verra des techniques plus tard, « à priori on ne peut pas les inverser ») — c’est pourquoi on commence par les systèmes carrés.

---

6. Règle de Cramer — [00:21]

Donne une formulation analytique, explicite, de la solution pour un système carré — mais très lourde en calcul (peu utilisée en pratique).

Certains étudiants ont déjà vu Cramer en réto, d’autres non → la prof le revoit quand même au tableau.

Théorème

Soit $A$ une matrice carrée d’ordre $n$, non singulière / régulière (i.e. $\det A\ne 0$) et $b$ un vecteur de dimension $n$. Alors la $i$-ème composante de la solution de $Ax=b$ est

$$\boxed{x_i=\frac{1}{\det A}\det B_i},$$

où $B_i$ est la matrice $A$ dans laquelle on remplace la $i$-ème colonne par le vecteur $b$ :

$$B_i=[A_1\dots A_{i-1}b{A}_{i+1}\dots A_n].$$

(Notation : $A_j$ = $j$-ème colonne de $A$.)

• C’est un ratio de deux déterminants (rappels) : $\det B_i$ au numérateur, $\det A$ au dénominateur.
• Rappels : une matrice singulière est une matrice de déterminant nul ; régulière = non singulière (c’est la même chose), c.-à-d. $\det A\ne 0$. Comme on divise par $\det A$, il faut que la matrice soit régulière.
• $B_i$ se construit en remplaçant la colonne $i$ : $B_1=[b,A_2,\dots ,A_n]$, $B_2=[A_1,b,A_3,\dots ,A_n]$, …, $B_n=[A_1,\dots ,A_{n-1},b]$.

• La définition du déterminant est déjà très lourde (elle demande de calculer $n$ déterminants d’ordre $n-1$, eux-mêmes…), et en plus on ne calcule pas un mais deux déterminants par composante → on n’utilisera pas ça en pratique (on le rappelle quand même).

Cas particulier $n=1$

$$A=[a],\det A=a\ne 0\Rightarrow x=\frac{b}{a}\text{(solution de }ax=b).$$

Exemple $n=2$ — [00:28]

$$\{\begin{array}{l}2x+3y=1\\ x-y=0\end{array}\Rightarrow A=\left(\begin{array}{cc}2& 3\\ 1& -1\end{array}\right),b=\left(\begin{array}{c}1\\ 0\end{array}\right).$$

• $\det A=2(-1)-3(1)=-5$.
• $x=x_1=\frac{1}{-5}\det \left(\begin{array}{cc}1& 3\\ 0& -1\end{array}\right)=\frac{-1}{-5}=\frac{1}{5}$.
• $y=x_2=\frac{1}{-5}\det \left(\begin{array}{cc}2& 1\\ 1& 0\end{array}\right)=\frac{-1}{-5}=\frac{1}{5}$.
• Vérification en réintroduisant dans le système : $2(\frac{1}{5})+3(\frac{1}{5})=\frac{5}{5}=1$ ✓ et $\frac{1}{5}-\frac{1}{5}=0$ ✓.

• On obtient la solution sans résoudre par substitution (comme on l’aurait fait en inversant le système) : c’est une illustration pour s’échauffer, premier cours.

Démonstration complète du théorème de Cramer — [00:32]

Objectif. Montrer que chaque composante de la solution de $Ax=b$ est $x_i=\frac{\det B_i}{\det A}$, avec $A$ carrée d’ordre $n$, $\det A\ne 0$.

---

Étape 0. Hypothèses et point de départ — [00:32]

• $A$ est carrée d’ordre $n$ et régulière (non singulière), c’est-à-dire $\det A\ne 0$.
• $\det A\ne 0$ ⟹ $A$ est invertible ⟹ l’inverse $A^{-1}$ est bien défini (condition déjà vue : déterminant non nul).
• La solution de $Ax=b$ est alors

$$x=A^{-1}b.$$

• Il existe plusieurs notations possibles pour le déterminant ; la prof précise qu’on peut écrire le déterminant de $A$ de différentes façons ($\det A$, $|A|$, …).

Étape 1. Décomposer l’image de $x$ sur une composante — [00:33]

• On a $x=A^{-1}b$, avec $b\in {\mathbb{R}}^n$ colonne. Fixons la $i$-ème composante $x_i$.
• Par définition du produit matrice-vecteur : la $i$-ème composante est obtenue en multipliant la $i$-ème ligne de $A^{-1}$ par le vecteur $b$ :

$$x_i=(\text{i-eˋme ligne de }{A}^{-1})\cdot b.$$

• (Précision faite en cours : ce n’est pas une colonne, mais bien une ligne, puisque l’on prend un produit matrice × colonne.)

• Un étudiant propose d’abord « la $i$-ème colonne » ; la prof corrige : pour obtenir l’élément $x_i$ on prend la $i$-ème ligne de la matrice inverse fois le vecteur colonne $b$.

Étape 2. Matrice inverse via la matrice des cofacteurs transposée — [00:34]

• On se rappelle la formule de l’inverse. Ce n’est pas une « matrice des conjugués » : c’est la matrice des cofacteurs transposée :

$$A^{-1}=\frac{1}{\det A}(\text{cof}(A){)}^T.$$

• On note $A_{ij}$ le cofacteur $(i,j)$ :

$$A_{ij}=(-1{)}^{i+j}\det (\text{matrice }A\text{ obtenue en supprimant la ligne }i\text{ et la colonne }j).$$

• Le facteur $(-1{)}^{i+j}$ donne le signe (pas un coefficient en plus).
• La transposée est essentielle : elle permute l’ordre des lignes et colonnes, c’est elle qui aligne correctement les indices dans le produit.

Étape 3. Que contient la $i$-ème ligne de $(\text{cof}(A){)}^T$ ? — [00:36]

• On regarde explicitement la $i$-ème ligne de la transposée :

$$(\text{cof}(A){)}^T=\left(\begin{array}{cccc}{A}_{11}& A_{21}& \dots & A_{n1}\\ A_{12}& A_{22}& \dots & A_{n2}\\ ⋮& & & ⋮\\ A_{1n}& A_{2n}& \dots & A_{nn}\end{array}\right).$$

• Donc la $i$-ème ligne est la suite

$$(A_{1i},A_{2i},\dots ,A_{ni}),$$

• c’est-à-dire que la transposition prend bien les éléments de la $i$-ème colonne des cofacteurs et les met en $i$-ème ligne. Les éléments $A_{11}$, $A_{21}$… se lisent « ligne 1, ligne 2…, indice de colonne fixé $=i$ ».

Étape 4. Produire la $i$-ème composante — [00:38]

• En multipliant cette ligne par le vecteur $b=(b_1,\dots ,b_n{)}^T$ :

$$x_i=\frac{1}{\det A}(A_{1i}{b}_1+A_{2i}{b}_2+\cdots +A_{ni}{b}_n),$$

c’est-à-dire

$$x_i=\frac{1}{\det A}\sum _{j=1}^n{A}_{ji}{b}_j.$$

• Notation à bien voir : dans $A_{ji}$, le premier indice $j$ parcourt les lignes, le second indice $i$ est fixé (on est dans la $i$-ème colonne de cofacteurs, ramenée en $i$-ème ligne après transposition).

Étape 5. Formuler l’objectif restant — [00:39]

• On sait désormais

$$x_i\cdot \det A=\sum _{j=1}^n{A}_{ji}{b}_j.$$

• Il suffit de montrer que ce membre de droite vaut exactement $\det B_i$, où

$$B_i=[A_1\dots A_{i-1}b{A}_{i+1}\dots A_n],$$

i.e. $A$ dont la $i$-ème colonne est remplacée par $b$.

• Si ce montré, on aura ${\sum }_j{A}_{ji}{b}_j=\det B_i$, donc $x_i=\frac{\det B_i}{\det A}$, et le théorème est démontré.

Étape 6. Développement de $\det B_i$ le long de sa colonne $i$ — [00:40]

• Rapport : pour calculer un déterminant, on peut développer le long d’une ligne ou d’une colonne de son choix (propriété du déterminant).
• Dans $B_i$, la colonne $i$ est $b$ : elle contient les éléments $b_1,b_2,\dots ,b_n$.
• On développe $\det B_i$ le long de cette colonne $i$ :

$$\det B_i=\sum _{j=1}^n{b}_j\cdot C_{ji},$$

où $C_{ji}$ est le cofacteur de la position $(j,i)$ dans la matrice $B_i$.

• Concrètement, le premier terme est $b_1$ fois le cofacteur de la position $(1,i)$ :

$$\det B_i=b_1\cdot C_{1i}+b_2\cdot C_{2i}+\cdots +b_n\cdot C_{ni}.$$

• Attention aux indices : dans ce cofacteur, on supprime la ligne $j$ et la colonne $i$.
  • $j$ = ligne du élément courant ($b_j$) ; ici on prend $b_1$ → on supprime la ligne 1.
  • $i$ = colonne développée (la colonne de $b$).

Étape 7. Le cofacteur de $B_i$ est celui de $A$ — [00:41]

• On supprime dans $B_i$ la ligne $j$ et la colonne $i$.
• Or la colonne $i$ de $B_i$ est exactement la colonne remplacée par $b$ : en la supprimant, elle disparaît.
• Il reste alors, dans $B_i$, exactement la même chose que dans $A$ privée de sa ligne $j$ et de sa colonne $i$ — les autres colonnes de $B_i$ sont celles de $A$.
• D’où

$$C_{ji}=A_{ji},$$

c’est-à-dire que le cofacteur de la position $(j,i)$ de $B_i$ coïncide avec le cofacteur de la position $(j,i)$ de $A$.

• La prof insiste sur les indices : les cofacteurs ont chaque fois une ligne ; ici on a multiplié par $b_1$ donc la ligne supprimée est la ligne 1, et la colonne supprimée est la colonne $i$ (celle de $b$).

Étape 8. Coup de théâtre final — [00:42]

• En substituant $C_{ji}=A_{ji}$ dans le développement de l’Étape 6 :

$$\det B_i=\sum _{j=1}^n{b}_j{A}_{ji}=\sum _{j=1}^n{A}_{ji}{b}_j.$$

• Mais le membre de droite est exactement celui trouvé à l’Étape 4 :

$$\sum _{j=1}^n{A}_{ji}{b}_j=x_i\cdot \det A.$$

• Donc

$$\det B_i=x_i\cdot \det A⟹\boxed{x_i=\frac{\det B_i}{\det A}}■$$

Leçon méthodologique (rappel de la prof) : la démonstration découle simplement de la définition du déterminant et de quelques-unes de ses propriétés (développement le long d’une colonne, choix de la ligne/colonne). Pas de magie : juste la définition appliquée judicieusement.

En pratique on ne l’utilise pas : chaque $\det$ demande ~$n!$ d’étapes (récursion), et il faut deux déterminants par composante → $\sim 2n!$ calculs. La méthode constructive (Gauss) sera préférée. Solution explicite mais peu utilisée en pratique.

---

7. Élimination de Gauss — [00:44]

Idée : une méthode constructive — on transforme le système en un système équivalent plus simple à résoudre. Contrairement à Cramer (formule directe), on a ici des étapes avant de vraiment obtenir la solution.

La prof demande si l’élimination de Gauss a déjà été vue : visiblement pas en ALG I pour ce groupe → on l’étudie donc ici.

Transformations élémentaires (sur les LIGNES)

1. Multiplier une équation par un coefficient non nul.
2. Ajouter à une équation une combinaison linéaire d’autres lignes.

✅ Ne change pas l’ensemble des solutions du système. ⚠️ Ces transformations ne fonctionnent que sur les lignes (pré-multiplier par un scalaire sur une colonne change le système).

Exemple motivationnel $2\times 2$ (pour comprendre les opérations) — [00:45]

On part de $\{\begin{array}{l}2x+3y=1\\ x-y=0\end{array}$.

• Multiplier la ligne 1 par 2 : $L_1\leftarrow 2L_1$ ⟹ $4x+6y=2$. La solution ne change pas : « pour autant que vous fassiez la même chose à gauche et à droite, vous ne changez pas la solution finale ».
• Additionner deux lignes : on place dans la ligne 2 le résultat de $L_1+L_2$ :
  • $4x+x=5x$ ;
  • $6y-y=5y$ ;
  • $2+0=2$. ⟹ nouvelle ligne 2 : $5x+5y=2$.

• La prof reconnaît elle-même que « ce n’était pas intelligent » (aucune inconnue n’est éliminée ici), mais ça illustre le principe : choisies intelligemment, ces opérations permettent d’éliminer des inconnues (méthode vue en secondaire). C’est exactement le principe de l’élimination de Gauss.

Exemple $3\times 3$ — [00:50]

$$\{\begin{array}{l}2u+v+w=1\\ 4u+v=-2\\ -2u+2v+w=7\end{array}$$

• Étape 1 — éliminer $u$ des lignes 2 et 3 en combinant avec la ligne 1 :
  • $L_2\leftarrow L_2-2L_1$ : $4u-2(2u)=0u$, $v-2v=-v$, $0-2w=-2w$, $-2-2(1)=-4$ ⟹ $0u-v-2w=-4$.
  • $L_3\leftarrow L_3+L_1$ : $-2u+2u=0u$, $2v+v=3v$, $w+w=2w$, $7+1=8$ ⟹ $0u+3v+2w=8$.

$$\{\begin{array}{l}2u+v+w=1\\ -v-2w=-4\\ 3v+2w=8\end{array}$$

• Étape 2 — éliminer $v$ de la ligne 3 avec la ligne 2 (pas la ligne 1, sinon on réintroduirait $u$) :
  • $L_3\leftarrow L_3+3L_2$ : $0u+3(0u)=0$, $3v+3(-v)=0v$, $2w+3(-2w)=-4w$, $8+3(-4)=-4$ ⟹ $-4w=-4$. (La prof réécrit bien les zéros.) On a éliminé $v$ de la 3e équation.
• La 3e équation n’a plus qu’une seule inconnue ($w$) → résolution par substitution :
  • $-4w=-4$ ⇒ $w=1$.
  • $w=1$ dans $L_2$ : $-v-2=-4$ ⇒ $v=2$.
  • $v=2,w=1$ dans $L_1$ : $2u+2+1=1$ ⇒ $2u=-2$ ⇒ $u=-1$.

Solution : $(u,v,w)=(-1,2,1)$.

• (La vérification en remplaçant dans le système est laissée « on ne va pas le faire ici ».)

Le système final est « équivalent » ⚠️

Pas le même système, mais même ensemble de solutions (c’est « hyper important ») — le dernier système est équivalent au système de départ, donc équivalent pour la résolution.

---

8. Pivots et méthode générale — [01:00]

• En dimension $n$ : on tue progressivement les coefficients sous la diagonale :
  1. colonne 1 : tuer tous les éléments sous $a_{11}$ (en dehors de la position $(1,1)$) ;
  2. colonne 2 : tuer ceux sous $a_{22}$ ; … etc.
• « Tuer » = combiner les lignes pour faire apparaître des zéros.
• Les éléments diagonaux $a_{11},a_{22},a_{33},\dots$ s’appellent les pivots (ce sont des éléments particuliers). Dans l’exemple, le coefficient $2$ devant la première équation est le premier pivot — c’est lui qui a servi à supprimer $u$ des autres équations ; ensuite les pivots utilisés sont $-1$ puis $-4$ (attention : les éléments diagonaux évoluent au fil des étapes d’élimination).

Formule systématique du multiplicateur

Pour tuer l’élément en ligne $i$, colonne $k$ :

$$\text{multiplicateur}=-\frac{a_{ik}}{{\text{pivot}}_k}=-\frac{a_{ik}}{a_{kk}}$$

puis $L_i\leftarrow L_i+\text{multiplicateur}\cdot L_k$.

• C’est « toujours moins cette formule-là » : le coefficient est l’élément à tuer (sur la ligne/colonne voulue) divisé par le pivot (l’élément diagonal de la même colonne).
  • Pour tuer $a_{21}=4$ : $-\frac{4}{2}=-2$ ⟹ $L_2-2L_1$. ✓
  • Pour tuer $a_{31}=-2$ : $-\frac{-2}{2}=+1$ ⟹ $L_3+L_1$. ✓
  • Pour tuer $a_{32}=3$ (3e ligne, 2e colonne) avec le 2e pivot $a_{22}=-1$ : $-\frac{3}{-1}=+3$ ⟹ $L_3+3L_2$. ✓
• C’est une méthode systématique : il suffit de savoir « je travaille sur cette ligne, cette colonne → j’utilise cette formule ». Du coup on peut la faire exécuter par un ordinateur.

Question d’un étudiant : est-ce que, pour éliminer le $u$ de la 3e ligne, on aurait pu utiliser le $u$ de la 2e ligne ? Réponse : ça fonctionnerait tant qu’on n’a pas modifié cette ligne, mais on perd la méthode générale (on ne saurait plus « où aller prendre ses éléments », surtout pour les lignes 2, 3, 4…), or ici on veut une méthode uniforme exécutable par un ordinateur. (Le coefficient $-1$ de la 2e ligne n’était donc pas utilisé pour cette étape.)

Remontée

• On arrive à une dernière équation à une seule inconnue → résolution par substitution pour remonter.
• L’algorithme mélange les deux phases → on l’appelle « élimination–substitution » (descente puis remontée).
• Variante : phase de remontée en tuant aussi les éléments au-dessus des pivots (on remonte dans l’autre sens) : après la descente, on tue les éléments au-dessus du dernier pivot, puis ceux au-dessus de l’avant-dernier, en se combinant non pas avec la première ligne mais avec la dernière ligne, puis l’avant-dernière, etc.

L’algorithme complet (général) est dans le syllabus (page 7) et se programme en TD.

⚠️ Conditions de validité (discutées au retour de pause) : comme on divise par les pivots, il faut qu’aucun pivot ne soit nul ; plus précisément, il faut qu’il y ait au moins un pivot non nul au départ et qu’aucun pivot nul n’apparaisse en cours d’étapes… mais c’est « plus ou moins vrai » : en réalité, la non-singularité de la matrice $A$ sera la condition suffisante (ce sera abordé plus loin dans le cours). Remarque : un pivot nul = « embêtant » / pas idéal.

Pause annoncée à [01:07] — 10 minutes, reprise prévue à « 59 ».

---

9. Complexité de l’élimination de Gauss — [01:10]

• Complexité (coût algorithmique) = le nombre d’opérations que l’ordinateur devra effectuer. On ne le compte pas de façon exacte, on essaie de l’estimer (ordre dominant).
• À quoi ça sert : comparer deux algorithmes à l’aide de leur coût de calcul / nombre d’opérations.

Dérivation pour un système $n$ équations / $n$ inconnues

On regarde ce qui se passe à la première étape : objectif = zéros sous la première colonne. (Les coefficients qui apparaissent sont de nouveaux coefficients recalculés, ce ne sont plus les mêmes.)

Sur une ligne donnée (la ligne 2, la même opération que sur toutes les autres) : $L_2\leftarrow L_2-\frac{a_{21}}{a_{11}}{L}_1$. On pose le multiplicateur $K=\frac{a_{21}}{a_{11}}$.

• Calcul de $K$ : une seule opération, 1 division (« il n’y a rien d’autre que la division »).
• Pour chacun des autres éléments de la ligne ($j=2,\dots ,n$) : on recalcule

$${\tilde{a}}_{2j}=a_{2j}-K\cdot a_{1j},$$

soit 2 opérations (1 multiplication + 1 soustraction). ⚠️ Attention, pas 3 : $K$ a déjà été calculé, on le réutilise juste. Ces 2 opérations sont à faire $n-1$ fois.

• Pour le second membre : ${\tilde{b}}_2=b_2-K\cdot b_1$ → encore 2 opérations.
• Total pour une ligne : $1+2(n-1)+2=2n+1$ opérations.

Cette même opération se répète sur les $n-1$ lignes restantes ($L_3,\dots ,L_n$) :

$$(n-1)(2n+1)=2n^2-n-1\text{pour la premieˋre eˊtape.}$$

Étape 2 : mêmes opérations, mais sur $n-2$ lignes et avec des lignes qui ne gardent plus que $n-1$ éléments à recalculer → sous-total $(n-2)(2(n-1)+1)$. Et ainsi de suite pour les étapes 2 à $n$ (sur $n-1$ lignes, puis $n-2$, …, jusqu’à une seule ligne).

Bilan : en posant $m$ = nombre de lignes encore traitées ($m=n-k+1$), chaque étape coûte $(m-1)(2m+1)$, donc

$$T(n)=\sum _{m=1}^n(m-1)(2m+1)=\sum _{m=1}^n(2m^2-m-1)=2\sum _{m=1}^n{m}^2-\sum _{m=1}^{n}m-n.$$

On utilise les formules connues :

$$\sum _{i=1}^{n}i=\frac{n(n+1)}{2}\text{et}\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}\text{(deˊjaˋ rencontreˊe, aˋ (re)trouver).}$$

Développement :

$$2\sum i^2=2\cdot \frac{n(n+1)(2n+1)}{6}=\frac{n(n+1)(2n+1)}{3}=\frac{2}{3}{n}^3+n^2+\frac{n}{3},$$

puis

$$T(n)=\frac{2}{3}{n}^3+n^2+\frac{n}{3}-\frac{n(n+1)}{2}-n=\frac{2}{3}{n}^3+\frac{1}{2}{n}^2-\frac{7}{6}n.$$

Le calcul complet donne donc

$$T(n)=\frac{2}{3}{n}^3+\frac{1}{2}{n}^2-\frac{7}{6}n=\frac{2}{3}{n}^3+O(n^2).$$

⚠️ On n’a compté que la phase descendante (élimination). La complexité complète de l’algorithme inclut aussi la phase de remontée (substitution) : à estimer chez soi — elle coûte de l’ordre de $n^2$ opérations, ce qui est négligeable devant $\frac{2}{3}{n}^3$.

Conclusion : l’élimination de Gauss est de complexité cubique, de coût $\mathcal{O}(\frac{2}{3}{n}^3)$. C’est ce coût (nombre d’opérations) qui permet de comparer des algorithmes.

---

10. Interprétation matricielle : matrices élémentaires — [01:25]

On a travaillé « à la main, système par système » ; mais une équation linéaire se représente matriciellement, donc on traduit l’algorithme d’élimination en matrices — cela mènera à la factorisation $A=LU$, simple interprétation matricielle de Gauss.

Matrice augmentée — [01:27]

• Dans $Ax=b$, le vecteur $x$ n’apporte pas d’information ; l’information est dans $A$ et dans $b$.
• Pour ne pas traîner les $x$ à chaque étape, on écrit une seule matrice augmentée :

$$[A\mid b],$$

parfois appelée « système étendu » ([système étendu] est équivalent à $Ax=b$). On l’utilisera dans la suite.

Principe de construction des matrices d’élimination

• Pré-multiplier une matrice par l’identité ne change rien sur les lignes.
• Pour remplacer $L_2$ par $L_2-2L_1$ : on part de l’identité, on reprend la ligne 2 à l’identique, et on combine avec $-2$ fois la ligne 1 → on place $-2$ en position $(2,1)$. C’est une pré-multiplication (ligne pour ligne) qui réalise l’opération.

Application à l’exemple $3\times 3$ (matrice $A=\left(\begin{array}{ccc}2& 1& 1\\ 4& 1& 0\\ -2& 2& 1\end{array}\right)$, $b=\left(\begin{array}{c}1\\ -2\\ 7\end{array}\right)$)

• Étape 1 : $L_2\leftarrow L_2-2L_1$ ⟺ prémultiplier par (identité avec $-2$ en position $(2,1)$)

$$E_1=\left(\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ 0& 0& 1\end{array}\right).$$

• Étape 1 bis : $L_3\leftarrow L_3+L_1$ ⟺ $E_2=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\right)$ (le $+1$ en position $(3,1)$).
• Étape 2 : $L_3\leftarrow L_3+3L_2$ ⟺ $E_3=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 3& 1\end{array}\right)$ (le $+3$ en position $(3,2)$).
• Vérification (laissée en exercice) : $E_2{E}_{1}A$ redonne la matrice d’étape 1, c.-à-d.

$$E_2{E}_{1}A=\left(\begin{array}{ccc}2& 1& 1\\ 0& -1& -2\\ 0& 3& 2\end{array}\right),E_2{E}_{1}b=\left(\begin{array}{c}1\\ -4\\ 8\end{array}\right).$$

(La prof invite à vérifier chez soi que l’on retrouve les coefficients du système obtenu à l’étape 1.)

Après toutes les étapes :

$$E_3{E}_2{E}_{1}A=U,U\text{ triangulaire supeˊrieure},$$

avec $U=\left(\begin{array}{ccc}2& 1& 1\\ 0& -1& -2\\ 0& 0& -4\end{array}\right)$ (les zéros sous la diagonale, dernier coefficient $-4$), et le membre de droite transformé en $E_3{E}_2{E}_{1}b$.

• Mnémonique : la matrice est triangulaire supérieure car l’information se trouve sur la partie supérieure (le moyen de retenir, c’est là où se trouve l’information). $U$ pour Upper.
• La structure triangulaire de $U$ donne directement une solution très facile du système équivalent (la dernière équation n’a plus qu’une inconnue).
• Les matrices $E_i$ sont triangulaires inférieures : on obtient donc une matrice triangulaire supérieure en prémultipliant par un produit de matrices triangulaires inférieures.

Inversibilité des matrices élémentaires

• Chaque matrice d’élimination $E_i$ est inversible (triangulaire, pas de zéro sur la diagonale).
• L’inverse d’une matrice triangulaire inférieure reste une triangulaire inférieure (et le produit de triangulaires inférieures est triangulaire inférieure).
• Exemple : $E_1^{-1}$ est la même matrice avec $+2$ en position $(2,1)$ ; pour $E_2$, l’élément $(3,1)$ devient $1$ (signe conservé/inversé selon le cas).
• Pour un produit, l’inverse se lit dans l’autre sens :

$$(E_3{E}_2{E}_1{)}^{-1}=E_1^{-1}{E}_2^{-1}{E}_3^{-1}.$$

---

11. Factorisation $A=LU$ — [01:41]

Puisque $E_3{E}_2{E}_{1}A=U$, en inversant :

$$A=(E_3{E}_2{E}_1{)}^{-1}U=LU,$$

où

• $L$ : triangulaire inférieure avec des 1 sur la diagonale ($L$ pour lower, « important ») ;
• $U$ : triangulaire supérieure avec les pivots sur la diagonale (ici $2,-1,-4$ : les pivots de l’élimination de Gauss).

Interprétation : « se factoriser » = s’écrire comme un produit de deux matrices ; l’élimination de Gauss = factoriser $A$ en un produit d’une matrice triangulaire inférieure et d’une triangulaire supérieure. C’est une interprétation matricielle de l’algorithme.

Variante $LDU$

• On écrit parfois $A=LDU$ (avec Un autre $U$, note $\tilde{U}$ sur l’exemple ; en général on parle de $LDU$) : $D$ = matrice diagonale des pivots, et $U$ ($\tilde{U}$) un triangulaire supérieure à 1 sur la diagonale, obtenue en divisant chaque ligne de $U$ par son pivot.
• Existence à condition que les pivots soient non nuls (sinon on ne peut pas écrire la factorisation).
• La semaine prochaine : on reprendra cette factorisation et on montrera qu’elle est unique, à condition qu’elle existe — sous l’hypothèse des pivots non nuls, il n’y a qu’une seule façon de factoriser.

• En TD on ne la fera peut-être pas toujours, mais en théorie on l’utilisera souvent.

---

Points clés — [résumé]

• Évaluation : examen écrit 80 % (théorie = petites propriétés) + travail de cours 20 % (séance d’exercices sur ordinateurs du labo, mieux contrôlé). Dispense possible si travail de groupe réussi l’année passée. Ponctualité requise dès le 2e cours.
• Plan : systèmes linéaires → moindres carrés → valeurs propres/singulières → optimisation linéaire. Approche numérique (méthodes directes vs itératives, accent sur les algorithmes). Abréviations au tableau → demander si pas clair.
• Équation linéaire : $\sum a_i{x}_i=b$ ; système = $m$ équations, mêmes $n$ inconnues. Solution = vecteur satisfaisant toutes les équations. On travaille sur $\mathbb{R}$.
• Géométrie 2×2 : droites sécantes → 1 solution ; confondues → ∞ ; parallèles → 0 (système inconsistant, sinon consistant). Chaque équation = une droite (pas un plan).
• Notation matricielle : $Ax=b$ avec $A\in {\mathbb{R}}^{m\times n}$, $x\in {\mathbb{R}}^n$, $b\in {\mathbb{R}}^m$. Systèmes carrés : $x=A^{-1}b$.
• Cramer : $x_i=\det B_i/\det A$ (remplacer colonne $i$ par $b$), $A$ régulière (det ≠ 0). Solution explicite mais ~ $n!$ calculs (deux déterminants par composante) → peu utilisée.
• Gauss : transformations sur les lignes (multiplier par scalaire non nul, ajouter des combinaisons) ne changent pas l’ensemble des solutions. On tue les coefficients sous la diagonale avec les pivots, multiplicateur $=-\frac{a_{ik}}{a_{kk}}$. Deux phases : descente (élimination) + remontée (substitution). Méthode systématique → exécutable par ordinateur.
• Conditions de validité : pivots non nuls (au moins un au départ, aucun nul n’apparaissant) ; en réalité non-singularité de $A$ suffit (à venir).
• Complexité de Gauss : $\mathcal{O}(\frac{2}{3}{n}^3)$ ; calcul exact $T(n)=\frac{2}{3}{n}^3+\frac{1}{2}{n}^2-\frac{7}{6}n$ (K : 1 division ; 2 opérations par élément, $n-1$ fois ; $2n+1$ par ligne ; $(n-1)(2n+1)$ à l’étape 1). Substitution ~ $n^2$ négligeable.
• Matrices élémentaires $E_i$ = identités avec le multiplicateur en position $(i,k)$ ; chaque étape est une pré-multiplication. $E_3{E}_2{E}_{1}A=U$, tour « triangulaire supérieure / inférieure » = où se trouve l’info. Chaque $E_i$ inversible (triangulaire, diag. non nulle) ; $(E_3{E}_2{E}_1{)}^{-1}=E_1^{-1}{E}_2^{-1}{E}_3^{-1}$.
• Factorisation : $A=LU$ ($L$ triangulaire inférieure à 1 sur la diagonale, $U$ triangulaire supérieure avec les pivots sur la diagonale) ; variante $A=LDU$ ($D$ = pivots, $U$ à 1 sur la diagonale) unique si les pivots sont non nuls.

---

Doutes / à vérifier

• Refaire l’exemple 3×3 en matriciel (matrice augmentée) pour vérifier $E_3{E}_2{E}_1[A|b]$ (valeurs intermédiaires : $E_2{E}_{1}A$, $E_2{E}_{1}b=(1,-4,8)$).
• Calcul de complexité complet $\frac{2}{3}{n}^3+\frac{1}{2}{n}^2-\frac{7}{6}n$ → détaillé en section 9 (avec les formules $\sum i$, $\sum i^2$).
• Lire l’algorithme exact (syllabus p. 7) et le programmer en TD.
• Règle de Cramer : retrouver la preuve à partir de la définition du déterminant + un développement par colonne → démonstration complète en section 6.