Décomposition LU

Position dans le parcoursModule 2 sur 4 · Sujet 2 sur 3

2.2 Décomposition LU

—Score du lab— / 100XP total—Série—

L'élimination, mémorisée

L'élimination de Gauss résout $A\mathbf{x}=\mathbf{b}$ en retranchant des multiples d'une ligne aux lignes situées dessous, jusqu'à obtenir une matrice triangulaire supérieure $U$ . Les multiplicateurs employés méritent d'être conservés : placés sous la diagonale d'une matrice triangulaire inférieure $L$ dont la diagonale est faite de uns, ils donnent $A=LU$ . La décomposition enregistre toute l'élimination : le travail est fait une fois et réutilisé.

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

Pour résoudre, on résout d'abord $L\mathbf{y}=\mathbf{b}$ par substitution avant (de haut en bas), puis $U\mathbf{x}=\mathbf{y}$ par substitution arrière (de bas en haut). Chacune coûte environ $n^2$ opérations, alors que la factorisation en coûte environ $\tfrac{2}{3}n^3$ . Avec de nombreux seconds membres (de nombreux scénarios sur la même matrice), on factorise une fois et l'on ne paie que $n^2$ par scénario.

Une LU à la mainPrenons

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. Le multiplicateur est

4/2=2

: retranchez 2 fois la ligne 1 à la ligne 2 pour obtenir

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

, et

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Vérification :

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Résolvons

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

donne

y_1=3

y_2=9-2\cdot3=3

; puis

U\mathbf{x}=\mathbf{y}

donne

x_2=1

2x_1+1=3

, donc

\mathbf{x}=(1,1)

$L$ : triangulaire inférieure, des uns sur la diagonale, les multiplicateurs d'élimination en dessous.
$U$ : triangulaire supérieure, résultat de l'élimination ; sa diagonale contient les pivots.
Pivotage : échangez des lignes pour que le pivot soit grand, ce qui donne $PA=LU$ avec une matrice de permutation $P$ .

Un pivot nul ou minuscule exige un échange de lignesPour

\begin{pmatrix}0&1\\1&1\end{pmatrix}

, le premier pivot est 0 et l'élimination simple divise par zéro, alors que la matrice est parfaitement inversible. Échanger les lignes règle le problème. Un pivot minuscule, plutôt que nul, ne plante pas mais produit des multiplicateurs énormes et ruine la précision : les vraies bibliothèques pivotent donc toujours.

Lab : ce qui est noté

La matrice L15 pts
La matrice U15 pts
Un déterminant à partir de U15 pts
Résoudre avec L et U15 pts
Pourquoi pivoter15 pts
Les étapes d'une résolution LU10 pts
Pourquoi factoriser une fois15 pts

0/ 7 traités

1Matrice · vecteur15 ptsSans réponse

Soit $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Remplissez le facteur triangulaire inférieur $L$ (des uns sur la diagonale) de $A=LU$ , sans échange de lignes.

L =

2Matrice · vecteur15 ptsSans réponse

Soit $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Remplissez le facteur triangulaire supérieur $U$ .

U =

3Réponse numérique15 ptsSans réponse

La matrice $A=\begin{pmatrix}2&1&1\\4&3&3\\8&7&9\end{pmatrix}$ se factorise sans échange en $L=\begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}$ , $U=\begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$ . Trouvez $\det A$ .

\det A =

accepté : ± 0.001

4Réponse numérique15 ptsSans réponse

Soit $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Utilisez $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ et $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ pour résoudre $A\mathbf{x}=(5,13)$ . Que vaut $x_1$ ?

x_1 =

accepté : ± 0.001

5Choix15 ptsSans réponse

Que se passe-t-il si l'on applique l'élimination simple, sans échange de lignes, à $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ ?

6Remettre les étapes dans l'ordre10 ptsSans réponse

Mettez dans l'ordre les étapes de résolution de $A\mathbf{x}=\mathbf{b}$ par une LU avec pivotage.

Faites glisser pour réordonner, ou placez le focus sur un élément, Espace pour le soulever, les flèches pour le déplacer et Espace pour le déposer.

1Substitution avant : résoudre $L\mathbf{y}=P\mathbf{b}$
2Factoriser $PA=LU$
3Substitution arrière : résoudre $U\mathbf{x}=\mathbf{y}$
4Appliquer les échanges de lignes au second membre : $P\mathbf{b}$

7Expliquer avec des mots15 ptsSans réponse

Vous devez résoudre $A\mathbf{x}=\mathbf{b}$ pour 1 000 vecteurs $\mathbf{b}$ différents avec la même $A$ . En deux phrases, dites en quoi la LU aide.

Noté sur :La matrice n'est factorisée qu'une fois et les facteurs sont réutilisésChaque second membre supplémentaire ne coûte que deux résolutions triangulaires peu chères, environ n au carré0 / 400 caractères

Mode mathsSaisie au clavier ou en LaTeXExercice 1 sur 7 · Ctrl ⏎ pour vérifier

Décomposition LU

Position dans le parcoursModule 2 sur 4 · Sujet 2 sur 3

2.2 Décomposition LU

—Score du lab— / 100XP total—Série—

L'élimination, mémorisée

A=LU,\qquad L\mathbf{y}=\mathbf{b},\qquad U\mathbf{x}=\mathbf{y}

(1)

Une LU à la mainPrenons

A=\begin{pmatrix}2&1\\4&5\end{pmatrix}

. Le multiplicateur est

4/2=2

: retranchez 2 fois la ligne 1 à la ligne 2 pour obtenir

U=\begin{pmatrix}2&1\\0&3\end{pmatrix}

, et

L=\begin{pmatrix}1&0\\2&1\end{pmatrix}

. Vérification :

LU=\begin{pmatrix}2&1\\4&2+3\end{pmatrix}=A

. Résolvons

A\mathbf{x}=(3,9)

L\mathbf{y}=\mathbf{b}

donne

y_1=3

y_2=9-2\cdot3=3

; puis

U\mathbf{x}=\mathbf{y}

donne

x_2=1

2x_1+1=3

, donc

\mathbf{x}=(1,1)

$L$ : triangulaire inférieure, des uns sur la diagonale, les multiplicateurs d'élimination en dessous.
$U$ : triangulaire supérieure, résultat de l'élimination ; sa diagonale contient les pivots.
Pivotage : échangez des lignes pour que le pivot soit grand, ce qui donne $PA=LU$ avec une matrice de permutation $P$ .

Un pivot nul ou minuscule exige un échange de lignesPour

\begin{pmatrix}0&1\\1&1\end{pmatrix}

Lab : ce qui est noté

La matrice L15 pts
La matrice U15 pts
Un déterminant à partir de U15 pts
Résoudre avec L et U15 pts
Pourquoi pivoter15 pts
Les étapes d'une résolution LU10 pts
Pourquoi factoriser une fois15 pts

0/ 7 traités

1Matrice · vecteur15 ptsSans réponse

Soit $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Remplissez le facteur triangulaire inférieur $L$ (des uns sur la diagonale) de $A=LU$ , sans échange de lignes.

L =

2Matrice · vecteur15 ptsSans réponse

Soit $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Remplissez le facteur triangulaire supérieur $U$ .

U =

3Réponse numérique15 ptsSans réponse

\det A =

accepté : ± 0.001

4Réponse numérique15 ptsSans réponse

Soit $A=\begin{pmatrix}2&1\\4&5\end{pmatrix}$ . Utilisez $L=\begin{pmatrix}1&0\\2&1\end{pmatrix}$ et $U=\begin{pmatrix}2&1\\0&3\end{pmatrix}$ pour résoudre $A\mathbf{x}=(5,13)$ . Que vaut $x_1$ ?

x_1 =

accepté : ± 0.001

5Choix15 ptsSans réponse

Que se passe-t-il si l'on applique l'élimination simple, sans échange de lignes, à $\begin{pmatrix}0&1\\1&1\end{pmatrix}$ ?

6Remettre les étapes dans l'ordre10 ptsSans réponse

Mettez dans l'ordre les étapes de résolution de $A\mathbf{x}=\mathbf{b}$ par une LU avec pivotage.

Faites glisser pour réordonner, ou placez le focus sur un élément, Espace pour le soulever, les flèches pour le déplacer et Espace pour le déposer.

1Substitution avant : résoudre $L\mathbf{y}=P\mathbf{b}$
2Factoriser $PA=LU$
3Substitution arrière : résoudre $U\mathbf{x}=\mathbf{y}$
4Appliquer les échanges de lignes au second membre : $P\mathbf{b}$

7Expliquer avec des mots15 ptsSans réponse

Vous devez résoudre $A\mathbf{x}=\mathbf{b}$ pour 1 000 vecteurs $\mathbf{b}$ différents avec la même $A$ . En deux phrases, dites en quoi la LU aide.

Mode mathsSaisie au clavier ou en LaTeXExercice 1 sur 7 · Ctrl ⏎ pour vérifier

Décomposition LU

L'élimination, mémorisée

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

Décomposition LU

L'élimination, mémorisée

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.