矩阵的LU分解

reference的内容为唯一教程，接下来的内容仅为本人的课后感悟，对他人或无法起到任何指导作用。

Reference

1. Course website: Factorization into A = LU | Unit I: Ax = b and the Four Subspaces | Linear Algebra | Mathematics | MIT OpenCourseWare
2. Course video: 麻省理工公开课：线性代数-A的LU分解-网易公开课 (163.com)
3. Course summary: Factorization into A = LU (mit.edu)
4. Extra reading: Section 2.6 in Introduction to Linear Algebra, Fifth Edition by Gilbert Strang.

---

前面讲了怎么用矩阵表示线性方程组，怎么用消元法解方程组并用矩阵乘法（初等矩阵左乘）表示，怎么用高斯-若尔当变换求方阵的逆，最重要的是让我们从线性组合和线性变换（我偷看了后面的内容）的角度去理解这些东西。

这一讲算是作为消元法的一个支线补充，从矩阵的角度描述消元的过程，个人感觉这部分内容也没啥大用。

Elementary Matrices for Elimination

假设行变换只包括用行与行之间的加减，不包括置换。

可以把矩阵消元的过程表示为：

\[\begin{align*}\mathbf{A}\mathbf{x}=\mathbf{b}&\Rightarrow \mathbf{E}_{nn-1}\cdots(\mathbf{E}_{n3}\cdots\mathbf{E}_{43})(\mathbf{E}_{n2}\cdots\mathbf{E}_{32})(\mathbf{E}_{n1}\cdots\mathbf{E}_{31}\mathbf{E}_{21})\mathbf{Ax}=\mathbf{c}\\ &\Rightarrow \mathbf{Ux}=\mathbf{c} \end{align*} \]

通过对矩阵\(\mathbf{A}\)左乘一系列初等矩阵（都是下三角（Lower Triangular）的，对角线为1，仅左下角有元素）会得到一个上三角（Upper Triangular）的矩阵，右侧的向量也相应变化。接着使用回代法求解。之前使用增广矩阵的方式化上三角阵。

A=LU

这时我们可以得到：\(\mathbf{E}_{nn-1}\cdots(\mathbf{E}_{n3}\cdots\mathbf{E}_{43})(\mathbf{E}_{n2}\cdots\mathbf{E}_{32})(\mathbf{E}_{n1}\cdots\mathbf{E}_{31}\mathbf{E}_{21})\mathbf{A}=\mathbf{U}\)，即\(\mathbf{EA}=\mathbf{U}\)。由初等行变换矩阵的定义很容易发现 \(\mathbf{E}_{ij}\) ，组合 \(\mathbf{E}\) 都是下三角的，而且 \(\mathbf{E}_{ij}\) 的逆是将非对角线元素取相反数（非对角线 \(e_{ij}\) 表示对矩阵 \(\mathbf{A}\) 第 \(i\) 行加第 \(j\) 行乘这个数字，只有再减去相同的数才能变成单位阵。因此求逆的结果也是个行变换，是下三角的，而且是将非对角线元素取相反数）。用 \(\mathbf{L}_{ij}\) 表示\(\mathbf{E}_{ij}^{-1}\)，\(l_{ij}=-e_{ij}\) 表示对矩阵 \(\mathbf{A}\) 第 \(i\) 行减第 \(j\) 行乘这个数字，则有：

\[\begin{align*} \mathbf{A}=(\mathbf{L}_{21}\mathbf{L}_{31}\cdots\mathbf{L}_{n1})(\mathbf{L}_{32}\cdots\mathbf{L}_{n2})(\mathbf{L}_{43}\cdots\mathbf{L}_{n3})\cdots\mathbf{L}_{nn-1}\mathbf{U}\Rightarrow \mathbf{A}=\mathbf{LU}\\ \end{align*} \]

Why A=LU instead of EA=U?

为什么呢？无论是矩阵 \(\mathbf{L}\) 还是 \(\mathbf{E}\) 都是下三角的，因为行变换的组合是下三角的。但是矩阵 \(\mathbf{E}\) 的非对角线元素没有意义，因为行变换是把上面行的元素作用到下面的行，非对角线元素的值只和这一列上面的行有关，\(\mathbf{E}\) 的组合顺序是从上面行到下面行，非对角线 \(i\) 行 \(j\) 列的元素和 \(e_{ij},e_{(i-1)j},\cdots,e_{1j}\) 都有关，混淆了。

但是 \(\mathbf{L}\) 的组合顺序是从下面行到上面行，非对角线 \(i\) 行 \(j\) 列的元素只和第 \(j\) 行有关，一图解释：

因此 \(\mathbf{L}\) 非对角线 \(i\) 行 \(j\) 列的元素正好等于 \(l_{ij}\)，表示对矩阵 \(\mathbf{A}\) 第 \(j\) 行减第 \(i\) 行乘这个数字。（ \(\mathbf{E}\) 由于混淆的缘故非对角线 \(i\) 行 \(j\) 列的元素不是 \(e_{ij}\) ）

有时为了让矩阵 \(\mathbf{U}\) 对角线全为 1，单独提取出一个对角阵 \(\mathbf{D}\)，使\(\mathbf{A}=\mathbf{LDU}\)，其实是一样的。

程序中只需要记录矩阵 \(\mathbf{L}\) 就可以把 \(\mathbf{A}\) 化为 \(\mathbf{U}\)，\(\mathbf{b}\) 化为 \(\mathbf{c}\)，再利用回代法求解，非常方便。

Computational Cost of Elimination and Substitution

消元：

把一次行变换（乘法和加法）当作一次运算，则对矩阵 \(\mathbf{A}_{n\times n}\) 消元运算的次数为：

\[\sum_{i=1}^{n}(i-1)\times i=\frac{(n-1)n(n+1)}{3}\approx{\frac{n^3}{3}} \]

可以大概看作平方和然后再大概看成从1到n的积分（教材），也可以参考这个网站。

对向量 \(\mathbf{b}_{n\times 1}\) 消元运算的次数为：

\[\sum_{i=1}^{n}(i-1)=\frac{(n-1)n}{2} \]

回代：

回代的时候最后一个元素除一次对角线，倒数第二行元素需要多一次减法和一次回代的乘法（系数），倒数第三行再多一次减法和一次回代的乘法，反正是类似 \(1+3+5+7+\cdots\) 之类的等差数列求和，结果肯定是 \(n^2\) 级别的。

总的来说复杂度属于 \(O(n^3)\)。