线性代数之——A 的 LU 分解

1. A = LU

之前在消元的过程中，我们看到可以将矩阵 $A$A 变成一个上三角矩阵 $U$U， $U$U 的对角线上就是主元。下面我们将这个过程反过来，通一个下三角矩阵 $L$L 我们可以从 $U$U 得到 $A$A， $L$L 中的元素也就是乘数 $l_{ij}$lij​。

如果有一个 3*3 的矩阵，假设不需要进行行交换，那我们需要三个消元矩阵 $E_{21},E_{31},E_{32}$E21​,E31​,E32​ 来分别使矩阵 $A$A 的 (2, 1)、(3, 1) 和 (3, 2) 位置为零，然后我们就有

乘数 $l_{ij}$lij​ 正好就是 $L$L 中 $(i,j)$(i,j) 处的元素。因为当我们计算 $U$U 的第三行的时候，实际上是用 $A$A 的第三行减去 $U$U 的前两行的一些倍数。

因此有

下面看一个特殊的例子

如果 $A$A 的某一行以 0 开始，说明该位置不需要进行消元，也即 $L$L 中对应位置的元素为 0。

如果 $A$A 的某一列以 0 开始，该位置元素在消元过程始终不会改变，也即 $U$U 中对应位置的元素为 0。

由于 $L$L 的对角线上都是 1，而 $U$U 的对角线上为主元，因此，这是不对称的。我们可以进一步将 $U$U 进行分解，使得 $U$U 的对角线上元素也都为 1。

这时候， $A$A 的分解就变成了 $A=LU=LDU$A=LU=LDU，其中 $D$D 是一个对角矩阵， $L$L 是一个下三角矩阵， $U$U 是一个上三角矩阵。

当我们从左边的 $A$A 得到 $L$L 和 $U$U 后，我们就对右边的 $b$b 进行同样的消元过程得到 $Lc=b$Lc=b，然后再通过回带 $Ux=c$Ux=c 求出方程组的解。

2. 消元过程的计算复杂度

假设我们有一个 $n\ast n$n∗n 的矩阵，首先我们要将第一列主元以下的元素都变成 $0$0。这时候，每一个元素变成 $0$0 我们都需要 $n$n 次乘法和 $n$n 次减法，总共有 $n-1$n−1 个元素需要变成 $0$0，总的乘法次数为 $n(n-1)$n(n−1)，近似为 $n^2$n2。然后，我们要依次将后面列的主元下面的元素变成 $0$0，需要的总的乘法次数为 $n^2+(n-1{)}^2+\cdots +2+1\approx \frac{1}{3}{n}^3$n2+(n−1)2+⋯+2+1≈31​n3。

也就是说对左边的 $A$A 消元要进行 $\frac{1}{3}{n}^3$31​n3 次的乘法操作和 $\frac{1}{3}{n}^3$31​n3 次的加法操作。

再来看右边对 $b$b 进行消元，首先我们需要将 $b_2,b_3\cdots b_n$b2​,b3​⋯bn​ 都减去 $b_1$b1​，需要 $n-1$n−1 次操作，往后我们依次需要 $n-2,n-3\cdots 1$n−2,n−3⋯1 次操作。回带的时候，求解最后一个方程的时候，我们只需要进行 1 次操作，依次往上我们需要 $2,3\cdots n$2,3⋯n 次操作。因此，求解的过程总共需要 $n^2$n2 次的乘法操作和 $n^2$n2 次的加法操作

3. 转置和置换矩阵

$A$A 的转置矩阵称为 $A^T$AT，其中 $A^T$AT 的列就是 $A$A 的行，也即 $(A^T{)}_{ij}=A_{ji}$(AT)ij​=Aji​。

$(A+B{)}^T=A^T+B^T$(A+B)T=AT+BT
$(AB{)}^T=B^T{A}^T$(AB)T=BTAT

假设 $B$B 是一个向量 $x$x，那么对 $(Ax{)}^T=x^T{A}^T$(Ax)T=xTAT 的理解就是： $Ax$Ax 是对 $A$A 的列的线性组合， $x^T{A}^T$xTAT 则是对 $A^T$AT 的行的线性组合， $A$A 的列和 $A^T$AT 的行是一样的，所以线性组合后是一样的结果。

如果 $B$B 有多列的话，我们就很容易得到

同理，针对更多的矩阵，我们也有

$(ABC{)}^T=C^T{B}^T{A}^T$(ABC)T=CTBTAT

$(A^{-1}{)}^T=(A^T{)}^{-1}$(A−1)T=(AT)−1

$A{A}^{-1}=I\to (A{A}^{-1}{)}^T=I\to (A^{-1}{)}^T{A}^T=I\to (A^{-1}{)}^T=(A^T{)}^{-1}$AA−1=I→(AA−1)T=I→(A−1)TAT=I→(A−1)T=(AT)−1

转置形式的内积和外积

对称矩阵的转置等于它本身，也就是 $A^T=A$AT=A。而且，一个对称矩阵的逆矩阵也是对称的。

$(A^{-1}{)}^T=(A^T{)}^{-1}=A^{-1}$(A−1)T=(AT)−1=A−1

对于一个任意的矩阵 $R$R，可以是矩形的， $R^{T}R$RTR 和 $R{R}^T$RRT 都是一个对称的方阵。

$(R^{T}R{)}^T=R^T(R^T{)}^T=R^{T}R$(RTR)T=RT(RT)T=RTR

当 $A=A^T$A=AT 时，如果没有行交换，那么有 $A=LDU=LD{L}^T$A=LDU=LDLT，此时 $U$U 变成了 $L^T$LT。

置换矩阵 $P$P 每行每列都只有一个 1，而且 $P^T$PT、 $P{P}^T$PPT 和任意两个置换矩阵的乘积 $P_1{P}_2$P1​P2​ 都还是置换矩阵。此外，所有的置换矩阵都有 $P^T=P^{-1}$PT=P−1。

在 $n$n 阶的情况下，置换矩阵的总的个数为 $n!$n!。例如 2 阶置换矩阵只有 2 个，3 阶置换矩阵有 6 个。

如果在需要行交换的情况下，我们可以先引入一个置换矩阵 $P$P 使矩阵 $A$A 的行有正确的顺序，然后再进行消元，这样的话我们就有

$PA=LU$PA=LU

也可以进行消元，然后再用一个矩阵 $P_1$P1​ 来让主元有一个正确的顺序，这样的话我们就有

$A=L_1{P}_1{U}_1$A=L1​P1​U1​

如果 $A$A 是可逆的，置换矩阵 $P$P 将会使它的行有一个正确的顺序然后分解成 $PA=LU$PA=LU 的形式。

获取更多精彩，请关注「seniusen」!