Il a été établi dans le contenu se trouvant dans l'article 083 qu’une matrice $A$ inversible admet une décomposition $LU$ si et seulement si tous ses mineurs principaux sont inversibles.
Dans cet article vous mettrez en évidence une méthode qui généralise cette factorisation à condition d’y rajouter une matrice $P$ dite de permutation, lorsque la condition sur les mineurs n’est pas satisfaite.
L’échec de la décomposition $LU$ pour certaines matrices
Pour illustrer la situation, vous allez vérifier que la matrice suivante :
A= \begin{pmatrix}
1 & 2 & 2\\
2 & 4 & -1\\
1 & -1 & 1
\end{pmatrix}n’admet pas de décomposition $LU.$
Note. Cela est causé par la défaillance du mineur principal d’ordre $2$ qui est nul :
\begin{vmatrix}
1 & 2 \\
2 & 4
\end{vmatrix} = 4\times 1-2\times 2=0.Raisonnez par l’absurde en supposant qu’il existe neuf nombres réels $\ell_{21}$, $\ell_{31}$, $\ell_{32}$, $u_{11}$, $u_{12}$, $u_{13}$, $u_{22}$, $u_{23}$ et $u_{33}$, de sorte que $A$ s’écrive sous la forme $A=LU$ avec :
L= \begin{pmatrix}
1 & 0 & 0\\
\ell_{21} & 1 & 0\\
\ell_{31} & \ell_{32} & 1
\end{pmatrix}et
U= \begin{pmatrix}
u_{11}& u_{12} & u_{13}\\
0 & u_{22} & u_{23}\\
0 & 0 & u_{33}
\end{pmatrix}.Le calcul de la première ligne de $L$ avec la première colonne de $U$ fournit $u_{11} = 1.$
Le calcul de la première ligne de $L$ avec la deuxième colonne de $U$ fournit $u_{12} = 2.$
Le calcul de la deuxième ligne de $L$ avec la première colonne de $U$ fournit $\ell_{21}u_{11} = 2$ soit $\ell_{21} = 2.$
Le calcul de la deuxième ligne de $L$ avec la deuxième colonne de $U$ fournit $\ell_{21}u_{12}+u_{22} = 4$ soit $u_{22} = 0.$
A ce stade il a été montré que :
L= \begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
\ell_{31} & \ell_{32} & 1
\end{pmatrix}et
U= \begin{pmatrix}
1&2 & u_{13}\\
0 & 0 & u_{23}\\
0 & 0 & u_{33}
\end{pmatrix}.Le calcul de la première ligne de $L$ avec la troisième colonne de $U$ fournit $u_{13} = 2.$
Le calcul de la deuxième ligne de $L$ avec la troisième colonne de $U$ fournit $2u_{13} +u_{23}= -1$ soit $u_{23}= -5.$
Le calcul de la troisième ligne de $L$ avec la première colonne de $U$ fournit $\ell_{31}= 1.$
Ainsi vous avez obtenu :
L= \begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
1 & \ell_{32} & 1
\end{pmatrix}et
U= \begin{pmatrix}
1&2 & 2\\
0 & 0 & -5\\
0 & 0 & u_{33}
\end{pmatrix}.Le calcul de la troisième ligne de $L$ avec la deuxième colonne de $U$ fournit $2\ell_{31}= -1$ soit $2 = -1$, contradiction.
Déterminez une factorisation $PLU$ de la matrice $A$
Obtention de la première colonne de la matrice $U$
Le coefficient de $A$ situé à la première ligne et à la première colonne est non nul, vous le choisissez comme pivot, que vous encadrez :
A= \begin{pmatrix}
\boxed{1} & 2 & 2\\
2 & 4 & -1\\
1 & -1 & 1
\end{pmatrix}.Vous effectuez l’opération élémentaire $L_2\leftarrow L_2-2L_1$ sur la matrice $A$ et vous obtenez la matrice :
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
1 & -1 & 1
\end{pmatrix}Cette opération élémentaire sur les lignes se traduit par une multiplication de $A$ à gauche par une matrice de transvection :
\begin{pmatrix}
1 & 0 & 0\\
-2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix} A= \begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
1 & -1 & 1
\end{pmatrix}Note. Pour plus d’informations sur cette opération, vous pouvez vous référer au contenu écrit dans l'article 274.
L’élimination de la matrice de transvection s’effectue en multipliant par une matrice qui représente l’opération élémentaire réciproque de cette transvection qui est $L_2\leftarrow L_2+2L_1.$ Vous multipliez l’égalité précédente à gauche par la matrice $\begin{pmatrix}1 & 0 & 0\\2 & 1 & 0\\0 & 0 & 1\end{pmatrix}$ :
\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0\\
-2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix} A=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
1 & -1 & 1
\end{pmatrix}.Or, le produit :
\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0\\
-2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}est égal à la matrice identité.
Ainsi :
A=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
1 & -1 & 1
\end{pmatrix}.Vous utilisez le même pivot afin de poursuivre la factorisation de la matrice $A$ :
Vous effectuez l’opération élémentaire $L_3\leftarrow L_3-L_1$ sur la matrice où le pivot est encadré et vous obtenez, en suivant la même démarche que celle explicitée ci-dessus :
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
1 & -1 & 1
\end{pmatrix}
= \begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{pmatrix}\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & -3 & -1
\end{pmatrix}.Ainsi, tout se passe bien, le produit de deux matrices triangulaires inférieures étant lui-même une matrice triangulaire inférieure :
\begin{align*}
A&=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}
\left[ \begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{pmatrix}\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & -3 & -1
\end{pmatrix}\right] \\
&=\left[\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
0 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
1 & 0 & 0\\
0 & 1 & 0\\
1 & 0 & 1
\end{pmatrix}\right]\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & -3 & -1
\end{pmatrix}\\
&=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
1 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & \boxed{-3} & -1
\end{pmatrix}.
\end{align*}
Le second pivot, $-3$, est mal positionné. Il va donc falloir utiliser une permutation des lignes $2$ et $3$ de la matrice $\begin{pmatrix}\boxed{1} & 2 & 2\\0 & 0 & -5\\0 & \boxed{-3} & -1\end{pmatrix}.$
Notez $P$ la matrice de permutation suivante qui correspond à l’échange des lignes $2$ et $3$ à partir de la matrice identité :
P = \begin{pmatrix}
1 & 0 & 0\\
0 & 0 & 1\\
0 & 1 & 0
\end{pmatrix}.Vous avez :
P \begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & \boxed{-3} & -1
\end{pmatrix} = \begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & -5
\end{pmatrix}.Comme $P$ est involutive ($P ^2$ est la matrice identité), vous multipliez l’égalité précédente à gauche par $P$ et vous obtenez :
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & \boxed{-3} & -1
\end{pmatrix} = P \begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & \boxed{-5}
\end{pmatrix}.Du coup, vous avez obtenu :
\begin{align*}
A
&=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
1 & 0 & 1
\end{pmatrix}
\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & 0 & -5\\
0 & \boxed{-3} & -1
\end{pmatrix} \\
&=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
1 & 0 & 1
\end{pmatrix} P \begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & \boxed{-5}
\end{pmatrix}.
\end{align*}
Eliminez la difficulté
Le problème a priori, c’est que :
\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
1 & 0 & 1
\end{pmatrix} P = \begin{pmatrix}
1 & 0 & 0\\
2 & 0 & 1\\
1 & 1 & 0
\end{pmatrix}.En effet, la multiplication à droite par $P$ revient à effectuer l’opération élémentaire $C_2\leftrightarrow C_3$ qui se passe sur les colonnes.
Ainsi, la matrice triangulaire inférieure semble être perdue :
\begin{align*}
A
&=\begin{pmatrix}
1 & 0 & 0\\
2 & 1 & 0\\
1 & 0 & 1
\end{pmatrix} P \begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & \boxed{-5}
\end{pmatrix}\\
&= \begin{pmatrix}
1 & 0 & 0\\
2 & 0 & 1\\
1 & 1 & 0
\end{pmatrix}\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & \boxed{-5}
\end{pmatrix}.
\end{align*}
Pour retrouver une matrice triangulaire inférieure, une solution consiste à multiplier l’égalité précédente par $P$ à gauche.
\begin{align*}
PA
&= P \begin{pmatrix}
1 & 0 & 0\\
2 & 0 & 1\\
1 & 1 & 0
\end{pmatrix}\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & \boxed{-5}
\end{pmatrix} \\
&= \begin{pmatrix}
1 & 0 & 0\\
1 & 1 & 0\\
2 & 0 & 1
\end{pmatrix}\begin{pmatrix}
\boxed{1} & 2 & 2\\
0 & \boxed{-3} & -1\\
0 & 0 & \boxed{-5}
\end{pmatrix}.
\end{align*}
Concluez
Vous avez obtenu $PA = LU$ avec :
\begin{align*}
P &= \begin{pmatrix}
1 & 0 & 0\\
0 & 0 & 1\\
0 & 1 & 0
\end{pmatrix}\\
L &= \begin{pmatrix}
1 & 0 & 0\\
1 & 1 & 0\\
2 & 0 & 1
\end{pmatrix}\\
U &= \begin{pmatrix}
1 & 2 & 2\\
0 & -3 & -1\\
0 & 0 & -5
\end{pmatrix}.
\end{align*}Comme $P$ est involutive, vous obtenez au final, après multiplication à gauche par $P$ :
\boxed{A=PLU.}Prolongements
La factorisation $PLU$ peut être utilisée afin de choisir le pivot d’une colonne ayant la plus forte valeur absolue afin de réduire les erreurs d’arrondis et la stabilité numérique. Cela s’appelle la méthode du pivot partiel.
Quitte à rajouter une matrice $Q$ de permutation à droite, la matrice $A$ peut se factoriser sous la forme $PLUQ$ où à chaque étape, le pivot est choisi parmi l’ensemble des coefficients situés dans le coin inférieur droit ayant le maximum de valeur absolue. Cela s’appelle la méthode du pivot global.
Partagez !
Diffusez cet article auprès de vos connaissances susceptibles d'être concernées en utilisant les boutons de partage ci-dessous.
Aidez-moi sur Facebook !
Vous appréciez cet article et souhaitez témoigner du temps que j'y ai passé pour le mettre en œuvre. C'est rapide à faire pour vous et c'est important pour moi, déposez un j'aime sur ma page Facebook. Je vous en remercie par avance.
Lisez d'autres articles !
Parcourez tous les articles qui ont été rédigés. Vous en trouverez sûrement un qui vous plaira !