提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

04A的LU分解

分解
2023-09-27 14:27:31 时间

一、逆矩阵性质补充

如果 A A A B B B是可逆的，那么 A B AB AB的逆矩阵是什么？根据逆矩阵的定义，我们仅需要找出一个矩阵 T T T使得 A B AB AB满足：
( A B ) T = T ( A B ) = I (AB)T=T(AB)=I (AB)T=T(AB)=I可以取 T = B − 1 A − 1 T=B^{-1}A^{-1} T=B−1A−1，结合矩阵的括号可移动性，有：
A B ( B − 1 A − 1 ) = A ( B B − 1 ) A − 1 = A I A − 1 = A A − 1 = I AB(B^{-1}A^{-1})=A(BB^{-1})A^{-1}=AIA^{-1}=AA^{-1}=I AB(B−1A−1)=A(BB−1)A−1=AIA−1=AA−1=I
性质1： A B AB AB的逆等于 B − 1 A − 1 B^{-1}A^{-1} B−1A−1。两矩阵相乘的逆等于两矩阵逆反向的乘（乘的逆等于逆的反乘）

转置矩阵是将原矩阵的行放到对应的列的位置。知道了转置矩阵的定义，那它有什么性质呢？

  • ( A + B ) T = A T + B T (A+B)^T=A^T+B^T (A+B)T=AT+BT
  • ( A B ) T = B T A T (AB)^T=B^TA^T (AB)T=BTAT
  • ( k A ) T = k A T (kA)^T=kA^T (kA)T=kAT
  • ( A T ) T = A (A^T)^T=A (AT)T=A

对比一下矩阵的逆和转置：

运算逆转置
A B AB AB ( A B ) − 1 = B − 1 A − 1 (AB)^{-1}=B^{-1}A^{-1} (AB)−1=B−1A−1 ( A B ) T = B T A T (AB)^{T}=B^TA^T (AB)T=BTAT
k A kA kA ( k A ) − 1 = 1 k A − 1 (kA)^{-1}=\frac{1}{k}A^{-1} (kA)−1=k1​A−1 ( k A ) T = k A T (kA)^T=kA^{T} (kA)T=kAT
A + B A+B A+B ( A + B ) − 1 = u n d e f i n e d (A+B)^{-1}=undefined (A+B)−1=undefined ( A + B ) T = A T + B T (A+B)^T=A^T+B^T (A+B)T=AT+BT

二、矩阵的LU分解

第二节建立了线性方程组消元过程与矩阵乘法的关系，即任何一个行变换都可以通过左乘特定矩阵消元过程。消元过程等价于系数矩阵 A A A与若干个诸如： E 21 E_{21} E21​ E 31 E_{31} E31​ E 32 E_{32} E32​[1]矩阵按变换顺序相乘后变成了上三角矩阵 U U U[1]：
E A = U EA=U EA=U行变换矩阵 E E E必然是可逆的，因为我们总能找到一个矩阵，让他还原成 I I I。左右两边都乘以 E − 1 E^{-1} E−1则：
E − 1 E A = E − 1 U E^{-1}EA=E^{-1}U E−1EA=E−1U记 U = E − 1 U=E^{-1} U=E−1，上述式子为：
A = L U A=LU A=LU这就是我们今天的主角， L U LU LU分解。那么为什么我们需要使用 L L L来描述消元过程而不是 E E E？

在此之前，需要介绍一个重要的结论：矩阵行变换等价于左乘其单位矩阵进行相同行变换后的矩阵。

考察二阶矩阵：
A = [ 1 0 4 7 ] A=\begin{bmatrix}1&0\\4&7\end{bmatrix} A=[14​07​]左乘一个什么矩阵能够将 A A A矩阵变成上三角矩阵？答：减去四倍的第一行，对一个同维度的单位矩阵进行同样的运算再将其乘在左边即得到：
E 21 = [ 1 0 − 4 3 ] E_{21}=\begin{bmatrix}1&0\\-4&3\end{bmatrix} E21​=[1−4​03​]
消元之后得到的上三角函数 U U U如下：
U = [ 1 0 0 − 3 ] U=\begin{bmatrix}1&0\\0&-3\end{bmatrix} U=[10​0−3​]容易观察得出， A A A进行了一次行变换将矩阵变成 U U U，这个行变换是第二行减去第一行的四倍。也就是左乘一个单位矩阵进行同样变换（第二行减去第一行的四倍）的后的矩阵 E 21 E_{21} E21​:
：
E 21 A = U E_{21}A=U E21​A=U考虑一个三阶矩阵 A A A，进行了三次消元得到了矩阵 U U U：分别左乘了矩阵 E 21 E_{21} E21​ E 31 E_{31} E31​ E 32 E_{32} E32​，即：
E 32 E 31 E 21 A = U (1) E_{32}E_{31}E_{21}A=U\tag{1} E32​E31​E21​A=U(1)由前面提到的矩阵乘积逆的性质，有： A = E 21 − 1 E 31 − 1 E 32 − 1 U (2) A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U\tag{2} A=E21−1​E31−1​E32−1​U(2)假设 E 21 = [ 1 0 0 − 2 1 0 0 0 1 ] , E 32 = [ 1 0 0 0 1 0 0 − 5 1 ] , E 31 = [ 1 0 0 0 1 0 0 0 1 ] = I E_{21}=\begin{bmatrix}1&0&0\\-2&1&0\\0&0&1\end{bmatrix},E_{32}=\begin{bmatrix}1&0&0\\0&1&0\\0&-5&1\end{bmatrix},E_{31}=\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\end{bmatrix}=I E21​=⎣⎡​1−20​010​001​⎦⎤​,E32​=⎣⎡​100​01−5​001​⎦⎤​,E31​=⎣⎡​100​010​001​⎦⎤​=I，先计算（1） A A A左乘的总矩阵: E = E 32 E 31 E 21 = [ 1 0 0 − 2 1 0 10 − 5 1 ] E=E_{32}E_{31}E_{21}=\begin{bmatrix}1&0&0\\-2&1&0\\10&-5&1\end{bmatrix} E=E32​E31​E21​=⎣⎡​1−210​01−5​001​⎦⎤​

再观察(2)：
L = E 21 − 1 E 31 − 1 E 32 − 1 = [ 1 0 0 2 1 0 0 5 1 ] L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}=\begin{bmatrix}1&0&0\\2&1&0\\0&5&1\end{bmatrix} L=E21−1​E31−1​E32−1​=⎣⎡​120​015​001​⎦⎤​

Tips1 : 关于消元矩阵的逆有一定的规律（不考虑行交换）：

  1. 对于一个没有行交换的消元矩阵，其一定是一个下三角矩阵；如果我们要取消这个消元，只需要将对角线下元素取负数乘到左边即可；
  2. 没有行交换的消元总是可逆的，且仍然是下三角矩阵；

Tips2 ：为什么要得到 L L L而不是 E E E?

  1. 因为我们需要分解 A A A，而不是分解 U U U;
  2. 通常来说，矩阵相乘会打乱元素，无法分辨每一次的变换，但是对于 L L L位置和值都保持不变，， E − 1 E^{-1} E−1是下三角矩阵

容易观察出， E E E相对于 L L L更加复杂，不纯粹，因为它多了个10，我无法从每次变换中找到这个数，相反， L L L更加简单，所有的数都可以在每次变换中找出！这也就意味着，我们可以直接由行变换轻松写出最终的 L L L矩阵，而不能简单的写出 E E E矩阵。

L U LU LU分解算法复杂度，消除第一列需要进行 10 0 2 100^2 1002，第二列需要 9 9 2 99^2 992消元运算，…，故总的时间为： ∑ k = 1 n k 2 = 1 3 n 3 − 1 = O ( n 3 ) \sum_{k=1}^{n}k^2=\frac{1}{3}n^3-1=O(n^3) k=1∑n​k2=31​n3−1=O(n3)

置换矩阵（Permutation）

就是矩阵进行行变换的矩阵，前面已经简单提到过。一个 n n n阶方阵共有 n ! n! n!个置换矩阵。

[1] E i j E_{ij} Eij​表示消元矩阵，表示消去第 i i i行，第 j j j列的元素（化为0）
[2] 上三角矩阵，主对角线以下都是0的矩阵；下三角矩阵，主对角线上都是0的矩阵，主对角线可以为0。

【20220529】参考对应教材重新补充了 L U LU LU分解的优点：容易观测！

相关文章