La décomposition LU signifie décomposer une matrice carrée A en L et U de telle sorte que le produit de la matrice triangulaire inférieure L et de la matrice triangulaire supérieure U, c'est-à-dire A = LU, soit valable. Il est utilisé pour résoudre des équations simultanées, calculer des matrices inverses et calculer des équations matricielles. Il existe de nombreuses solutions telles que les solutions analytiques, les méthodes d'élimination gaussiennes et les méthodes récursives. La paire de L et U semble être déterminée de manière unique, mais cela dépend des conditions.
19 novembre Session d'étude en ligne sur l'algèbre linéaire Les débutants souhaitent la bienvenue à la 19e introduction à l'algèbre linéaire G Strang
tenir. S'il vous plaît rejoignez-nous.
Confirmez que la matrice 3x3 $ A $ peut être décomposée en une matrice triangulaire supérieure $ U $ et une matrice triangulaire inférieure $ L $ avec des pivots sur des éléments diagonaux.
U est une matrice triangulaire supérieure avec des pivots sur des éléments diagonaux. L est la matrice triangulaire inférieure. A peut être décomposé en une matrice triangulaire supérieure et une matrice triangulaire inférieure par la procédure d'élimination.
A=\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
2 & 7 & 9 \\
\end{array}
\right)
Ensuite, pour effacer l'élément 2 de la 3ème ligne et de la 1ère colonne de $ A $, soustrayez deux fois de la 3ème ligne à la 1ère ligne.
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
Ensuite, l'élément 3 de la 3ème ligne et de la 2ème colonne peut être supprimé en multipliant la 2ème ligne par 3 et en soustrayant de la 3ème ligne.
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 4 \\
\end{array}
\right)
Pour résumer cette procédure
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
2 & 7 & 9 \\
\end{array}
\right)
\ \rightarrow \
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
\ \rightarrow \
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 4 \\
\end{array}
\right)
Sera.
En multipliant une matrice à partir de la gauche de $ A $, la procédure d'élimination peut être effectuée à l'aide de la matrice. Tout d'abord, supprimez l'élément 2 de $ A $.
\left(
\begin{array}{rr}
1 & 0 & 0 \\
0 & 1 & 0 \\
-2 & 0 & 1 \\
\end{array}
\right)
\left(
\begin{array}{rr}
1 & 2 & 1 \\
0 & 1 & 1 \\
2 & 7 & 9 \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
1\times1+ 0\times0 +0\times2 & 1\times2+ 0\times1 +0\times7 & 1\times1+ 0\times1 +0\times9 \\
0\times1+ 1\times0 +0\times2 & 0\times2+ 1\times1 +0\times7 & 0\times1+ 1\times1 +0\times9 \\
-2\times1+0\times0 +1\times2 &-2\times2+ 0\times1 +1\times7 & -2\times1+ 0\times1 +1\times9 \\
\end{array}
\right)
=
\left(
\begin{array}{rr}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
La matrice utilisée pour cet effacement est la matrice unitaire $ I $ plus le multiplicateur $ l_ {31} = -2 $, qui est l'inverse des éléments positifs et négatifs de l'élément à effacer, et s'écrit $ E_ {31} $. c'est
E_{31}A=
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
Peut être écrit.
Ensuite, je veux effacer l'élément $ 3 $ sur le côté droit. Par conséquent, en multipliant $ E_ {32} $ de $ l_ {32} = -3 $ à partir de la gauche,
\left(
\begin{array}{cc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -3 & 1 \\
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
1\times1+ 0 \times0+0\times0 & 1\times2+ 0\times1 +0\times3 & 1\times1+ 0\times1 +0\times7 \\
0\times1+ 1 \times0+0\times0 & 0\times2+ 1\times1 +0\times3 & 0\times1+ 0\times1 +0\times7 \\
0\times1+(-3)\times0+1\times0&0\times2+(-3)\times1+1\times3 & 0\times1+(-3)\times1+1\times7 \\
\end{array}
\right)
=
\left(
\begin{array}{rr}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 4 \\
\end{array}
\right)
c'est
E_{32}
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 4 \\
\end{array}
\right)
=U
Sera. Aussi
E_{31}A=
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
De
E_{32}
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 3 & 7 \\
\end{array}
\right)
=E_{32}E_{31}A=U
Appel. Cela donne une matrice triangulaire supérieure avec des pivots.
Multipliez les deux côtés par $ E_ {32} ^ {-1} $
E_{32}^{-1}E_{32}E_{31}A=E_{32}^{-1}U
E_{32}^{-1}E_{32}E_{31}A=IE_{31}A=E_{31}A=E_{32}^{-1}U
c'est
E_{31}A=E_{32}^{-1}U
Si vous multipliez les deux côtés par $ E_ {31} ^ {-1} $
E_{31}^{-1}E_{31}A=E_{31}^{-1}E_{32}^{-1}U
c'est
A=E_{31}^{-1}E_{32}^{-1}U
Appelez aussi.
Ensuite, trouvez $ E_ {31} ^ {-1} $ et $ E_ {32} ^ {-1} $. Dans la méthode Gauss-Jordan, la matrice pour laquelle vous voulez trouver la matrice inverse est écrite dans les 3 premières lignes et 3 colonnes, puis une matrice rectangulaire composée de 3 lignes et 3 colonnes est créée en l'éliminant.
[E_{31} e_1 e_2 e_3]=
\left(
\begin{array}{cc}
1 & 0 & 0 &1&0&0\\
0 & 1 & 0 &0&1&0\\
-2 & 0 & 1&0&0&1 \\
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc}
1 & 0 & 0 &1&0&0\\
0 & 1 & 0 &0&1&0\\
0 & 0 & 1&2&0&1 \\
\end{array}
\right)
Je vais calculer.
E_{31}^{-1}=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
2&0&1 \\
\end{array}
\right)
a été obtenu. Aussi,
[E_{32} e_1 e_2 e_3]=
\left(
\begin{array}{cc}
1 & 0 & 0 &1&0&0\\
0 & 1 & 0 &0&1&0\\
0 & -3 & 1&0&0&1 \\
\end{array}
\right)
\rightarrow
\left(
\begin{array}{cc}
1 & 0 & 0 &1&0&0\\
0 & 1 & 0 &0&1&0\\
0 & 0 & 1&0&3&1 \\
\end{array}
\right)
De
E_{32}^{-1}=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
0&3&1 \\
\end{array}
\right)
Est obtenu.
Suivant
E_{31}^{-1}E_{32}^{-1}=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
2&0&1 \\
\end{array}
\right)
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
0&3&1 \\
\end{array}
\right)
=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
2&3&1 \\
\end{array}
\right)
Parce que c'est une matrice triangulaire inférieure
par conséquent
A=LU
=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
2&3&1 \\
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 4 \\
\end{array}
\right)
Le démontage est terminé.
Convertissez une matrice triangulaire supérieure avec pivots en une matrice triangulaire supérieure sans pivots en utilisant une matrice diagonale.
A=LU
=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
2&3&1 \\
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 4 \\
\end{array}
\right)
Utilisation de la matrice diagonale $ D $
A
=
\left(
\begin{array}{cc}
1&0&0\\
0&1&0\\
2&3&1 \\
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0 & 4 \\
\end{array}
\right)
\left(
\begin{array}{cc}
1 & 2 & 1 \\
0 & 1 & 1 \\
0 & 0 & 1 \\
\end{array}
\right)
= LDU_u = LDU
Peut être réécrit comme.
Confirmez que $ A = LDU = LDL ^ {T} $ lorsque $ A $ est une matrice symétrique.
A=\left(
\begin{array}{rrr}
1 & -1 & 2 \\
-1 & 2 & -1 \\
2 & -1 & 1 \\
\end{array}
\right)
Éliminez cela avec une matrice pour créer une matrice triangulaire supérieure pivotée.
E_{32}E_{31}E_{21}A=\left(
\begin{array}{rrr}
1 & -1 & 2 \\
0& 1 & 1 \\
0 & 0 & -4 \\
\end{array}
\right)
c'est
U=DU_u=
\left(
\begin{array}{rrr}
1 & 0 & 0 \\
0& 1 & 0 \\
0 & 0 & -4 \\
\end{array}
\right)
\left(
\begin{array}{rrr}
1 & -1 & 2 \\
0& 1 & 1 \\
0 & 0 & 1 \\
\end{array}
\right)
Peut être démonté en.
En outre, la matrice triangulaire inférieure
E_{32}^{-1}E_{31}^{-1}E_{21}^{-1}=\left(
\begin{array}{rrr}
1 & 0 & 0 \\
-1& 1 & 0 \\
2 & 1 & 1 \\
\end{array}
\right)
= U_u^{T}
Peut être confirmé.
Vérifiez la procédure ci-dessus en utilisant numpy et scipy.
import numpy as np
from scipy.linalg import inv
A = np.array([[1, 2, 1], [0, 1, 1], [2, 7, 9]])
E31=np.array([[1, 0, 0], [0, 1, 0], [-2, 0, 1]])
E32=np.array([[1, 0, 0], [0, 1, 0], [0, -3, 1]])
U=E32@E31@A
L=inv(E32)@inv(E31)
print("U:\n{}\n".format(U))
print("L:\n{}\n".format(L))
print("A:\n{}\n".format(L@U))
UU=np.triu(U,1)+np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
D=np.diag(U)
D=np.diag(D)
print("UU:\n{}\n".format(UU))
print("D:\n{}\n".format(D))
AA=L@D@(UU)
print("A:\n{}\n".format(AA))
U: [[1 2 1] [0 1 1] [0 0 4]]
L: [[1. 0. 0.] [0. 1. 0.] [2. 3. 1.]]
A: [[1. 2. 1.] [0. 1. 1.] [2. 7. 9.]]
UU: [[1 2 1] [0 1 1] [0 0 1]]
D: [[1 0 0] [0 1 0] [0 0 4]]
A: [[1. 2. 1.] [0. 1. 1.] [2. 7. 9.]]
J'ai pu le confirmer.
Ensuite, vérifions la matrice symétrique.
from scipy.linalg import inv
A = np.array([[1, -1, 2], [-1, 2, -1], [2, -1, 1]])
print("A:\n{}\n".format(A))
E21=np.array([[1, 0, 0], [1, 1, 0], [0, 0, 1]])
E31=np.array([[1, 0, 0], [0, 1, 0], [-2, 0, 1]])
E32=np.array([[1, 0, 0], [0, 1, 0], [0, -1, 1]])
U=E32@E31@E21@A
L=inv(E21)@inv(E31)@inv(E32)
print("U:\n{}\n".format(U))
print("L:\n{}\n".format(L))
print("A:\n{}\n".format(L@U))
UU=np.triu(U,1)+np.array([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
D=np.diag(U)
D=np.diag(D)
print("Uu:\n{}\n".format(UU))
print("D:\n{}\n".format(D))
AA=L@D@(UU)
print("LDUu:\n{}\n".format(AA))
A: [[ 1 -1 2] [-1 2 -1] [ 2 -1 1]]
U: [[ 1 -1 2] [ 0 1 1] [ 0 0 -4]]
L: [[ 1. 0. 0.] [-1. 1. 0.] [ 2. 1. 1.]]
A: [[ 1. -1. 2.] [-1. 2. -1.] [ 2. -1. 1.]]
Uu: [[ 1 -1 2] [ 0 1 1] [ 0 0 1]]
D: [[ 1 0 0] [ 0 1 0] [ 0 0 -4]]
LDUu: [[ 1. -1. 2.] [-1. 2. -1.] [ 2. -1. 1.]]
J'ai pu le confirmer.
Ensuite, décomposons en utilisant la fonction lu et la fonction lul de scipy. Notez que le pivot peut être attaché à la matrice triangulaire inférieure. De plus, on peut voir que la décomposition LU n'est pas déterminée de manière unique.
scipy.linalg.lu(a, permute_l=False, overwrite_a=False, check_finite=True)
Calculez la décomposition LU pivot de la matrice.
Démontage
A = P L U
P est la matrice de substitution, L'élément diagonal de L est 1.
import numpy as np
from scipy.linalg import lu
#np.random.seed(10)
#Générer une matrice avec des éléments aléatoires
#A = np.random.randint(1, 5, (5, 5))
A = np.array([[1, 2, 1], [0, 1, 1], [2, 7, 9]])
# PA=Décomposition LU
P, L, U = lu(A)
print("A:\n{}\n".format(A))
print("P:\n{}\n".format(P))
print("L:\n{}\n".format(L))
print("U:\n{}\n".format(U))
print("PLU:\n{}".format(P@L@U))
A: [[1 2 1] [0 1 1] [2 7 9]]
P: [[0. 1. 0.] [0. 0. 1.] [1. 0. 0.]]
L: [[ 1. 0. 0. ] [ 0.5 1. 0. ] [ 0. -0.66666667 1. ]]
U: [[ 2. 7. 9. ] [ 0. -1.5 -3.5 ] [ 0. 0. -1.33333333]]
PLU: [[1. 2. 1.] [0. 1. 1.] [2. 7. 9.]]
scipy.linalg.ldl(A, lower=True, hermitian=True, overwrite_a=False, check_finite=True) Calculez la décomposition LDLt ou Bunch-Kaufman d'une matrice symétrique / Hermit.
Cette fonction renvoie une matrice diagonale de bloc D constituée de blocs jusqu'à 2x2 et une matrice triangulaire inférieure L qui contient la décomposition A = L D L ^ H ou A = L D L ^ T et peut nécessiter une substitution. Si lower vaut False, la matrice triangulaire supérieure (qui devra peut-être être remplacée) retourne comme valeur de retour.
Vous pouvez utiliser la matrice de substitution pour trianguler la valeur de retour en mélangeant simplement les lignes. Cela correspond à une multiplication utilisant la matrice de substitution P.dot (lu), où P est la matrice de substitution I [:, perm].
from scipy.linalg import ldl
A = np.array([[1, -1, 2], [-1, 2, -1], [2, -1, 1]])
lu, d, perm = ldl(A)
print("lu:\n{}\n".format(lu[perm,:]))
print("d:\n{}\n".format(d))
print("lu.t:\n{}\n".format(lu[perm,:].T))
print("A:\n{}\n".format(lu.dot(d).dot(lu.T)))
lu: [[ 1. 0. 0. ] [ 0. 1. 0. ] [-0.33333333 -0.33333333 1. ]]
d: [[1. 2. 0. ] [2. 1. 0. ] [0. 0. 1.33333333]]
lu.t: [[ 1. 0. -0.33333333] [ 0. 1. -0.33333333] [ 0. 0. 1. ]]
A: [[ 1. -1. 2.] [-1. 2. -1.] [ 2. -1. 1.]]
Recommended Posts