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

1. 矩阵的转置

1.1 定义

矩阵的转置，即矩阵的行列进行互换。
$$A=\left[\begin{array}{ccc}1& 2& 3\\ 4& 5& 6\end{array}\right]$$
矩阵$A$的转置
B = A ⊤ = [ 1 4 2 5 3 6 ] B=A^\top= \begin{bmatrix} 1 & 4\\ 2 & 5\\ 3 & 6 \end{bmatrix} B=A⊤= ​123​456​ ​

1.2 性质

$$\begin{array}{r}(A^{\top }{)}^{\top }=A\\ (A+B{)}^{\top }=A^{\top }+B^{\top }\\ (kA{)}^{\top }=k{A}^{\top }\\ (AB{)}^{\top }=B^{\top }{A}^{\top }\end{array}$$

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

令矩阵$C=AB$
$C_{ij}=A_{ro{w}_i}{B}_{co{l}_j}$

矩阵$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= \begin{bmatrix} A_{r1}B_{c1} &A_{r1}B_{c2} ....A_{r1}B_{c_n}\\ A_{r2}B_{c1} &A_{r2}B_{c2} ....A_{r2}B_{c_n}\\ ...\\ A_{r_m}B_{c1} &A_{r_m}B_{c2} ....A_{r_m}B_{c_n}\\ \end{bmatrix} C= ​Ar1​Bc1​Ar2​Bc1​...Arm​​Bc1​​Ar1​Bc2​....Ar1​Bcn​​Ar2​Bc2​....Ar2​Bcn​​Arm​​Bc2​....Arm​​Bcn​​​ ​
则矩阵$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 ⊤ \begin{align} C^{\top}&= \begin{bmatrix} 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}\\ \end{bmatrix} \nonumber\\ \nonumber&= \begin{bmatrix} 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}\\ \end{bmatrix}\\ &=B^{\top}A^{\top} \nonumber \end{align} C⊤​= ​Ar1​​Bc1​​Ar1​​Bc2​​...Ar1​​Bcn​​​Ar2​​Bc1​​....Arm​​Bc1​​Ar2​​Bc2​​....Arm​​Bc2​​Arm​​Bc2​​....Arm​​Bcn​​​ ​= ​Bc1​​Ar1​​Bc2​​Ar1​​...Bcn​​Ar1​​​Bc1​​Ar2​​....Bc1​​Arm​​Bc2​​Ar2​​....Bc2​​Arm​​Bc2​​Arm​​....Bcn​​Arm​​​ ​=B⊤A⊤​
简单来说就是$C^{\top }$的$i$行$j$列是$C$的第$j行$第$i$列；
所以$C^{\top }$的一行对应$C$的一列，而列是由$B$形成的，所以把它放在前面转置，$A$也转置放后面。

2. 矩阵的LU分解

矩阵性质

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

验证:

$$\begin{gathered} AB{B}^{-1}{A}^{-1}=A(B{B}^{-1})A^{-1}=AI{A}^{-1}=I \\ {B}^{-1}{A}^{-1}AB=B^{-1}(A^{-1}A)B=B^{-1}IB=I \end{gathered}$$

• $(A^{-1}{)}^{\top }=(A^{\top }{)}^{-1}$

证明

$$\begin{gathered} A{A}^{-1}=I \\ (A{A}^{-1}{)}^{\top }=I \\ (A^{-1}{)}^{\top }{A}^{\top }=I \\ (A^{-1}{)}^{\top }=(A^{\top }{)}^{-1} \end{gathered}$$

2.1 矩阵$LU$分解

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

举例子
$$A=\left[\begin{array}{cc}2& 1\\ 8& 7\end{array}\right]$$
普通消元
$$\begin{gathered} E_{21}A=U \\ \left[\begin{array}{cc}1& 0\\ -4& 1\end{array}\right]\left[\begin{array}{cc}2& 1\\ 8& 7\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 0& 3\end{array}\right] \end{gathered}$$
我们将$E_{21}$放到矩阵右边去
$$\begin{gathered} E_{21}A=U \\ {E}_{21}^{-1}{E}_{21}A=E_{21}^{-1}U \\ A=LU \\ \left[\begin{array}{cc}2& 1\\ 8& 7\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 4& 1\end{array}\right]\left[\begin{array}{cc}2& 1\\ 0& 3\end{array}\right] \end{gathered}$$

如果再将$U$主对角线化，就变为
$$\begin{gathered} A=LDU \\ \left[\begin{array}{cc}2& 1\\ 8& 7\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 4& 1\end{array}\right]\left[\begin{array}{cc}2& 0\\ 0& 3\end{array}\right]\left[\begin{array}{cc}1& \frac{1}{2}\\ 0& 1\end{array}\right] \end{gathered}$$

2.2 为什么需要化为$A=LU$的形式，而非$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\\ \begin{bmatrix}\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -5 & 1\\ \end{bmatrix} \begin{bmatrix}\ 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix}= \begin{bmatrix}\ 1 & 0 & 0\\ 2 & 1 & 0\\ 10 & -5 & 1\\ \end{bmatrix} E32​E21​=E ​ 100​01−5​001​ ​ ​ 1−20​010​001​ ​= ​ 1210​01−5​001​ ​
而对于$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}\\ \begin{bmatrix}\ 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix} \begin{bmatrix}\ 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 5 & 1\\ \end{bmatrix}= \begin{bmatrix}\ 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 5 & 1\\ \end{bmatrix} L=E21−1​E32−1​ ​ 120​010​001​ ​ ​ 100​015​001​ ​= ​ 120​015​001​ ​

在$EA=U$的分解中，前面的行变换会影响到后续的行变化，出现了$E_{31}=10$的情况；

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

2.3 消元次数

不考虑行变化。
考虑$n\ast n$的方阵$A$化为上三角矩阵的操作次数。

考虑第一列上三角化，即消去第一列非$a_{11}$的元素，执行的操作大概为$n^2$次
每次行变化涉及$n$次操作，$n-1$行需要消去第一行；即为$n(n-1)$近似$n^2$;
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= \begin{bmatrix} a_{11}\ a_{12} ...a_{1n}\\ a_{21}\ a_{22} ...a_{2n}\\ ......\\ a_{n1}\ a_{n2} ...a_{nn}\\ \end{bmatrix} \stackrel{}\longrightarrow \begin{bmatrix} a_{11}\ a_{12} ...a_{1n}\\ 0\ a_{22} ...a_{2n}\\ ......\\ 0\ a_{n2} ...a_{nn}\\ \end{bmatrix} A= ​a11​ a12​...a1n​a21​ a22​...a2n​......an1​ an2​...ann​​ ​⟶​ ​a11​ a12​...a1n​0 a22​...a2n​......0 an2​...ann​​ ​
第一列完成上三角化后，后续就是$(n-1)(n-1)$矩阵的第一列上三角化。
重复该操作直到矩阵$A$上三角化。操作次数
$$Cnt=\sum _{k=1}^n{k}^2=\frac{n(n+1)(2n+1)}{6}\approx \frac{1}{3}{n}^3$$
其实也可以用积分来求

$${\int }_1^n{k}^{2}dx=\frac{1}{3}{k}^3+c$$
积分其实就是连续情况的求和。

对于右侧操作数$Ax=b$，操作次数大约为$n^2$次。
(${\sum }_{i=1}^{n-1}n=\frac{n(n-1)}{2}$)文章来源地址https://www.toymoban.com/news/detail-850070.html

到了这里，关于线性代数笔记4--矩阵A的LU分解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！