【线性代数】2-6:三角矩阵( $A=LU$ and $A=LDU$ )

Abstract: 如何将矩阵分解成三角矩阵
Keywords: A=LU,A=LDU,Factorization

本课视频课程已上线:A=LU分解

三角矩阵

今晚苹果要新版本iPhone了,不知不觉iPhone已经十年了,然而我只用过iPhone4和6,技术的不断创新,给人们带来了方便,也改变了产业结构和生活方式,这应该与自然的变迁类似,无法阻挡的历史潮流,人类一切的进步都源自于对未知事物的探索,希望各位继续努力,为人类的进步,为人类与自然的和谐相处努力。

因数分解(Factorization)

因式分解,开始学的时候肯定是分解多项式,将一串长的式子分解成几个因式相乘的形式,矩阵也可以,把一个矩阵分解成几个矩阵相乘的形式,但是问题来了,从表述上看,多项式分解的结果是整体变得简单了,但是矩阵分解好像越分越多啊,是多了,但是多出来这些矩阵都很有特点,他们的形状固定,大部分元素是0.
回想一下消元的过程

A to U
$$
E_{21}A=
\begin{bmatrix}1&0\newline -3&1\end{bmatrix}
\begin{bmatrix}2&1\newline 6&8\end{bmatrix}=
\begin{bmatrix}2&1\newline 0&5\end{bmatrix}=U
$$
U to A

$$
E_{21}^{-1}U=
\begin{bmatrix}1&0\newline 3&1\end{bmatrix}=
\begin{bmatrix}2&1\newline 0&5\end{bmatrix}=
\begin{bmatrix}2&1\newline 6&8\end{bmatrix}=A
U
$$
从U到A的过程就是我们今天的男一号,$A=LU$

消元的解释说明

1:$E^{-1}$ 都是lower triangular 下三角矩阵,对角线元素全部为1

2:$E^{-1}$ 就是$L$,把U变回A的系数矩阵

3:每个消元系数$l_{ij}$ 只会把对应的(i,j)位置的元素干掉,不会影响其他位置,尤其是已经完成消元的位置

$A=LU$

这是不包含行交换的消元过程的矩阵形式,上三角矩阵U对角线上全是pivot,对角下为0,L的对角线全是1,对角线下面是消元的乘子。
有两条规律,总结如下

1:A的某行开头是0,那么对应的L的位置也是0
2:A的某列开头是0,那么对应的U的位置也是0

$A=LU$ 成立的关键还是要回顾消元过程,当某元素(pivot)所在的列一下都是0了以后,做下一个pivot消元的时候,对已完成的,为0的列没有影响,但是后面的非零列是有影响的,大部分非零列已经不是原始的列了,这种做法能保证解空间不变,但是矩阵的列空间已经发生改变了,具体后面讲到列空间的时候会有说明。

$A=LDU$

$A=LU$ 数学家们喜欢0,喜欢1,喜欢对称,$A=LU$ 显然不那么对称,U对角线上是主元,L对角线上是1,这太不美观了
然后再分解一下,
Divide U by a diagonal natrix D that contains the pivots
啥意思?就是这个意思:
$$
\begin{bmatrix}
d_1&\,&\,&\,\newline
\,&d_2&\,&\,\newline
\,&\,&\ddots&\,\newline
\,&\,&\,&d_n\newline
\end{bmatrix}
\begin{bmatrix}
1&u_{12}/d_1&u_{13}/d_1&.\newline
\,&1&u_{23}/d_2&.\newline
\,&\,&\ddots&\vdots\newline
\,&\,&\,&1\newline
\end{bmatrix}
$$
如果除法不好理解那就当做$D^{-1}U$然后根据row model 或者 col model一看,发现上面式子没问题。
所以系数矩阵A就能分解成 $A=LDU$

Why

你一定跟我当时一样心中一万匹羊驼在奔腾,觉得折腾这玩意有啥用啊,折腾过来折腾过去,没啥用啊,这么弄的目的是啥嘛,但是当天晚上回家看数值分析的书,刚好也讲这个过程,原来这么做的目的是为了减轻计算,举个例子$Ax=b$这种计算过程在工程应用里非常常见,而且多半时间是A不变,不同的b来解不同的x,那么按照高斯消元法,每次要从头消元,因为b改变了增广矩阵,但是很多计算是冗余的,所以使用三角矩阵的好处就是可以大大减少冗余计算

第一步:就是把矩阵分解成 $LU$ 或者 $LDU$ 形式(factor)
第二步:通过回代,把x求出来(solve)

$$
Ax=b\\
LUx=b\\
c=L^{-1}b……(1)\\
Ux=c\\
x=U^{-1}c……(2)
$$
过程(1)(2)并不需要求逆,而是通过回代的过程进行,根据计算时间复杂度(也就是计算量,计算次数),factor的时间复杂度是$O(\frac{1}{3}n^3)$,solve的时间复杂度大概是$O(n^2)$,如果你对时间复杂度不了解,可以去看《算法导论》的最开始那一章,这个理论还是非常有用的,尤其是对研究算法的童鞋。通过回代而不是消元,能够降低不少多余的计算。

带状矩阵(band matrix)

带状矩阵,只有对角线附近元素不为0,其他位置都是0,这种矩阵factor的时间复杂度是$O(nw^2)$,solve的时间复杂度大概是$O(2nw)$ w是非零元素的个数

总结

本文知识点比较连贯,就不总结了,总结的是一点,如果看一本书看不太懂,可以看看别的书,或者别人的解释,兼听则明,然后就有可能豁然开朗。

0%