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是非零元素的个数

总结

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