当前位置:   article > 正文

线性代数笔记4--矩阵A的LU分解

线性代数笔记4--矩阵A的LU分解

1. 矩阵的转置

1.1 定义

矩阵的转置,即矩阵的行列进行互换。
A = [ 1 2 3 4 5 6 ] A=

[123456]
A=[142536]
矩阵 A A A的转置
B = A ⊤ = [ 1 4 2 5 3 6 ] B=A^\top=
[142536]
B=A= 123456

1.2 性质

( A ⊤ ) ⊤ = A ( A + B ) ⊤ = A ⊤ + B ⊤ ( k A ) ⊤ = k A ⊤ ( A B ) ⊤ = B ⊤ A ⊤

(A)=A(A+B)=A+B(kA)=kA(AB)=BA
(A)=A(A+B)=A+B(kA)=kA(AB)=BA

简单证明下性质 ( 4 ) (4) (4)
假设矩阵 A : ( m , r ) A:(m,r) A:(m,r) m m m r r r列;矩阵 B : ( r , n ) B:(r,n) B:(r,n) r r r n n n列。

令矩阵 C = A B C=AB C=AB
C i j = A r o w i B c o l j C_{ij}=A_{row_i}B_{col_j} Cij=ArowiBcolj

矩阵 C C C的形式为
C = [ A r 1 B c 1 A r 1 B c 2 . . . . A r 1 B c n A r 2 B c 1 A r 2 B c 2 . . . . A r 2 B c n . . . A r m B c 1 A r m B c 2 . . . . A r m B c n ] C=

[Ar1Bc1Ar1Bc2....Ar1BcnAr2Bc1Ar2Bc2....Ar2Bcn...ArmBc1ArmBc2....ArmBcn]
C= Ar1Bc1Ar2Bc1...ArmBc1Ar1Bc2....Ar1BcnAr2Bc2....Ar2BcnArmBc2....ArmBcn
则矩阵 C C C的转置为
C ⊤ = [ A r 1 B c 1 A r 2 B c 1 . . . . A r m B c 1 A r 1 B c 2 A r 2 B c 2 . . . . A r m B c 2 . . . A r 1 B c n A r m B c 2 . . . . A r m B c n ] = [ B c 1 A r 1 B c 1 A r 2 . . . . B c 1 A r m B c 2 A r 1 B c 2 A r 2 . . . . B c 2 A r m . . . B c n A r 1 B c 2 A r m . . . . B c n A r m ] = B ⊤ A ⊤
C=[Ar1Bc1Ar2Bc1....ArmBc1Ar1Bc2Ar2Bc2....ArmBc2...Ar1BcnArmBc2....ArmBcn]=[Bc1Ar1Bc1Ar2....Bc1ArmBc2Ar1Bc2Ar2....Bc2Arm...BcnAr1Bc2Arm....BcnArm]=BA
C= Ar1Bc1Ar1Bc2...Ar1BcnAr2Bc1....ArmBc1Ar2Bc2....ArmBc2ArmBc2....ArmBcn = Bc1Ar1Bc2Ar1...BcnAr1Bc1Ar2....Bc1ArmBc2Ar2....Bc2ArmBc2Arm....BcnArm =BA

简单来说就是 C ⊤ C^{\top} C i i i j j j列是 C C C的第 j 行 j行 j i i i列;
所以 C ⊤ C^{\top} C的一行对应 C C C的一列,而列是由 B B B形成的,所以把它放在前面转置, A A A也转置放后面。

2. 矩阵的LU分解

矩阵性质

  • ( A B ) − 1 = B − 1 A − 1 (AB)^{-1}=B^{-1}A^{-1} (AB)1=B1A1

验证:

A B B − 1 A − 1 = A ( B B − 1 ) A − 1 = A I A − 1 = I B − 1 A − 1 A B = B − 1 ( A − 1 A ) B = B − 1 I B = I ABB^{-1}A^{-1} =A(BB^{-1})A^{-1} =AIA^{-1} =I\\ B^{-1}A^{-1}AB =B^{-1}(A^{-1}A)B =B^{-1}IB =I ABB1A1=A(BB1)A1=AIA1=IB1A1AB=B1(A1A)B=B1IB=I

  • ( A − 1 ) ⊤ = ( A ⊤ ) − 1 (A^{-1})^{\top} =(A^{\top})^{-1} (A1)=(A)1

证明

A A − 1 = I ( A A − 1 ) ⊤ = I ( A − 1 ) ⊤ A ⊤ = I ( A − 1 ) ⊤ = ( A ⊤ ) − 1 AA^{-1}=I\\ (AA^{-1})^{\top} = I\\ (A^{-1})^{\top}A^{\top} =I\\ (A^{-1})^{\top} =(A^{\top})^{-1} AA1=I(AA1)=I(A1)A=I(A1)=(A)1

2.1 矩阵 L U LU LU分解

L L L指的是下三角矩阵的意思;
U U U指的是上三角矩阵的意思;

举例子
A = [ 2 1 8 7 ] A=

[2187]
A=[2817]
普通消元
E 21 A = U [ 1 0 − 4 1 ] [ 2 1 8 7 ] = [ 2 1 0 3 ] E_{21}A=U\\
[1041]
[2187]
=
[2103]
E21A=U[1401][2817]=[2013]

我们将 E 21 E_{21} E21放到矩阵右边去
E 21 A = U E 21 − 1 E 21 A = E 21 − 1 U A = L U [ 2 1 8 7 ] = [ 1 0 4 1 ] [ 2 1 0 3 ] E_{21}A=U\\ E_{21}^{-1}E_{21}A=E_{21}^{-1}U\\ A=LU\\
[2187]
=
[1041]
[2103]
E21A=UE211E21A=E211UA=LU[2817]=[1401][2013]

如果再将 U U U主对角线化,就变为
A = L D U [ 2 1 8 7 ] = [ 1 0 4 1 ] [ 2 0 0 3 ] [ 1 1 2 0 1 ] A=LDU\\

[2187]
=
[1041]
[2003]
[11201]
A=LDU[2817]=[1401][2003][10211]

2.2 为什么需要化为 A = L U A=LU A=LU的形式,而非 E A = U EA=U EA=U

假设不存在行交换的情况;

对于 E A = U EA=U EA=U
E 32 E 21 = E [   1 0 0 0 1 0 0 − 5 1 ] [   1 0 0 − 2 1 0 0 0 1 ] = [   1 0 0 2 1 0 10 − 5 1 ] E_{32}E_{21}=E\\

[ 100010051]
[ 100210001]
=
[ 1002101051]
E32E21=E  100015001  120010001 =  1210015001
而对于 A = L U A=LU A=LU
L = E 21 − 1 E 32 − 1 [   1 0 0 2 1 0 0 0 1 ] [   1 0 0 0 1 0 0 5 1 ] = [   1 0 0 2 1 0 0 5 1 ] L=E_{21}^{-1}E_{32}^{-1}\\
[ 100210001]
[ 100010051]
=
[ 100210051]
L=E211E321  120010001  100015001 =  120015001

E A = U EA=U EA=U的分解中,前面的行变换会影响到后续的行变化,出现了 E 31 = 10 E_{31}=10 E31=10的情况;

而这在 A = L U A=LU A=LU分解中不会出现,且只需要填上消元乘数即可。

2.3 消元次数

不考虑行变化。
考虑 n ∗ n n * n nn的方阵 A A A化为上三角矩阵的操作次数。

考虑第一列上三角化,即消去第一列非 a 11 a_{11} a11的元素,执行的操作大概为 n 2 n^{2} n2
每次行变化涉及 n n n次操作, n − 1 n-1 n1行需要消去第一行;即为 n ( n − 1 ) n(n-1) n(n1)近似 n 2 n^2 n2;
A = [ a 11   a 12 . . . a 1 n a 21   a 22 . . . a 2 n . . . . . . a n 1   a n 2 . . . a n n ] ⟶ [ a 11   a 12 . . . a 1 n 0   a 22 . . . a 2 n . . . . . . 0   a n 2 . . . a n n ] A=

[a11 a12...a1na21 a22...a2n......an1 an2...ann]
\stackrel{}\longrightarrow
[a11 a12...a1n0 a22...a2n......0 an2...ann]
A= a11 a12...a1na21 a22...a2n......an1 an2...ann a11 a12...a1n0 a22...a2n......0 an2...ann
第一列完成上三角化后,后续就是 ( n − 1 ) ( n − 1 ) (n-1)(n-1) (n1)(n1)矩阵的第一列上三角化。
重复该操作直到矩阵 A A A上三角化。操作次数
C n t = ∑ k = 1 n k 2 = n ( n + 1 ) ( 2 n + 1 ) 6 ≈ 1 3 n 3 Cnt=\sum_{k=1}^{n}k^2=\frac{n(n+1)(2n+1)}{6} \approx \frac{1}{3}n^3 Cnt=k=1nk2=6n(n+1)(2n+1)31n3
其实也可以用积分来求

∫ 1 n k 2 d x = 1 3 k 3 + c \int_1^{n}k^2 dx=\frac{1}{3}k^3+c 1nk2dx=31k3+c
积分其实就是连续情况的求和。

对于右侧操作数 A x = b Ax=b Ax=b,操作次数大约为 n 2 n^2 n2次。
( ∑ i = 1 n − 1 n = n ( n − 1 ) 2 \sum_{i=1}^{n-1}n=\frac{n(n-1)}{2} i=1n1n=2n(n1))

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/384373
推荐阅读
相关标签
  

闽ICP备14008679号