矩阵的 LU 分解

本节的主要目的是从矩阵的角度理解高斯消元法，最后找到所谓的 $\boldsymbol{L}$ 矩阵，使得矩阵 $\boldsymbol{A}$ 可以转变为上三角阵 $\boldsymbol{U}$，即完成 $\boldsymbol{LU}$ 分解得到 $\boldsymbol{A}=\boldsymbol{LU}$。

首先继续了解一些矩阵乘法和逆矩阵的相关内容。

一、矩阵性质补充

1.1 矩阵乘积的逆矩阵

由于 $\boldsymbol{ABB}^{-1}\boldsymbol{A}^{-1}=\boldsymbol{A}(\boldsymbol{BB}^{-1})\boldsymbol{A}^{-1}=\boldsymbol{I}$，比较等式两端可得 $(\boldsymbol{AB})^{-1}=\boldsymbol{B}^{-1}\boldsymbol{A}^{-1}$。

1.2 矩阵乘积的转置

矩阵 $\boldsymbol{A}$ 的转置矩阵记为 $\boldsymbol{A}^T$，对矩阵进行转置就是将 $\boldsymbol{A}$ 矩阵的行变为 $\boldsymbol{A}^T$ 的列，而完成后 $\boldsymbol{A}$ 的列也就成为了 $\boldsymbol{A}^T$ 的行，看起来矩阵如同沿着对角线进行了翻转。

$\boldsymbol{A}=\left[{\begin{array}{cc}2&1&4\\0&0&3\end{array}}\right]$，则 ${\boldsymbol{A}^T}=\left[{\begin{array}{cc}2&0\\1&0\\4&3\end{array}}\right]$

其数学表达式为 $(\boldsymbol{A}^T)_{ij}=\boldsymbol{A}_{ji}$，即 $\boldsymbol{A}^T$ 的第 $i$ 行第 $j$ 列的元素为原矩阵 $\boldsymbol{A}$ 中第 $j$ 行第 $i$ 列的元素。

由定义可证明，$(\boldsymbol{AB})^T=\boldsymbol{B}^T\boldsymbol{A}^T$。

1.3 转置矩阵的逆矩阵

$\boldsymbol{AA}^{-1}=\boldsymbol{I}$ 两边取转置，并应用积的转置公式，得到 $(\boldsymbol{A}^{-1})^T(\boldsymbol{A}^T)=\boldsymbol{I}$，根据逆矩阵定义得到 $(\boldsymbol{A}^T)^{-1}=(\boldsymbol{A}^{-1})^T$。

二、矩阵的 LU 分解

我们已经看到了如何应用消元法将矩阵 $\boldsymbol{A}$ 转变为上三角阵 $\boldsymbol{U}$，这就引出了矩阵的 $\boldsymbol{LU}$ 分解，它是理解矩阵 $\boldsymbol{A}$ 性质的重要方法。

在没有行交换的情况下，矩阵 $\boldsymbol{A}$ 通过左乘一系列消元矩阵 $\boldsymbol{E}_{ij}$ 可以转化为 $\boldsymbol{U}$。在二阶矩阵中，进行一次消元操作即可达到这一效果。

$\begin{array}{l}\left[{\begin{array}{cc}1&0\\{\rm{-}4}&1\end{array}}\right]\left[{\begin{array}{cc}2&1\\8&7\end{array}}\right]=\left[{\begin{array}{cc}2&1\\0&3\end{array}}\right]\\\begin{array}{cc}{}&{\boldsymbol{E}_{21}}&{}&{}&{}\boldsymbol{A}&{}&{}&{}&{}&\boldsymbol{U}&{}\end{array}\end{array}$

在等式两侧左乘 $\boldsymbol{E}_{21}^{-1}$，得到 $\boldsymbol{E}_{21}^{-1}\boldsymbol{E}_{21}\boldsymbol{A}=\boldsymbol{E}_{21}^{-1}\boldsymbol{U}$ 即 $\boldsymbol{A}=\boldsymbol{E}_{21}^{-1}\boldsymbol{U}$，就得到了矩阵 $\boldsymbol{A}$ 的 $\boldsymbol{LU}$ 分解结果。

$\begin{array}{l}\left[{\begin{array}{cc}2&1\\8&7\end{array}}\right]=\left[{\begin{array}{cc}1&0\\4&1\end{array}}\right]\left[{\begin{array}{cc}2&1\\0&3\end{array}}\right]\\\begin{array}{cc}{}&{}\boldsymbol{A}&{}&{}&{}&\boldsymbol{L}&{}&{}&{}&\boldsymbol{U}&{}\end{array}\end{array}$

其中 $\boldsymbol{U}$ 为上三角阵（Upper triangular matrix），主元依次排列于它的对角线上，$\boldsymbol{E}_{21}^{-1}$ 即 $\boldsymbol{L}$ 为下三角阵（Lower triangular matrix）。有时我们也通过分解得到对角阵 $\boldsymbol{D}$（diagonal matrix），例如

$\begin{array}{l}\left[{\begin{array}{cc}2&1\\8&7\end{array}}\right]=\left[{\begin{array}{cc}1&0\\4&1\end{array}}\right]\left[{\begin{array}{cc}2&0\\0&3\end{array}}\right]\left[{\begin{array}{cc}1&\frac{1}{2}\\0&1\end{array}}\right]\\\begin{array}{cc}{}&\boldsymbol{A}&{}&{}&{}&\boldsymbol{L}&{}&{}&{}&\boldsymbol{D}&{}&{}&{}&\boldsymbol{U}&{}&{}\end{array}\end{array}$

对于三阶矩阵不需要换行进行消元的情况则有：

$\boldsymbol{E}_{32}(\boldsymbol{E}_{31}(\boldsymbol{E}_{21}\boldsymbol{A}))=\boldsymbol{U}$，左乘逆矩阵可得 $\boldsymbol{A}=\boldsymbol{E}_{21}^{-1}\boldsymbol{E}_{31}^{-1}\boldsymbol{E}_{32}^{-1}\boldsymbol{U}=\boldsymbol{LU}$。

设定一组消元矩阵，其中 $\boldsymbol{E}_{31}$ 为单位阵 $\boldsymbol{I}$，其它两个消元矩阵如下：

$\begin{array}{l}\left[{\begin{array}{cc}1&0&0\\0&1&0\\0&{\rm{-}5}&1\end{array}}\right]\left[{\begin{array}{cc}1&0&0\\{\rm{-}2}&1&0\\0&0&1\end{array}}\right]=\left[{\begin{array}{cc}1&0&0\\{\rm{-}2}&1&0\\{10}&{\rm{-}5}&1\end{array}}\right]\\\begin{array}{cc}{}&{}&{\boldsymbol{E}_{32}}&{}&{}&{}&{}&{}&{\boldsymbol{E}_{21}}&{}&{}&{}&{}&{}&{}&\boldsymbol{E}&{}\end{array}\end{array}$

可以看到在消元矩阵 $\boldsymbol{E}$ 的左下角出现了数 $10$。

而在右侧操作则不会有这种情况发生，运算顺序会发生变化，$\boldsymbol{L}=\boldsymbol{E}^{-1}=\boldsymbol{E}_{21}^{-1}\boldsymbol{E}_{32}^{-1}$。

$\begin{array}{l}\left[{\begin{array}{cc}1&0&0\\2&1&0\\0&0&1\end{array}}\right]\left[{\begin{array}{cc}1&0&0\\0&1&0\\0&5&1\end{array}}\right]=\left[{\begin{array}{cc}1&0&0\\2&1&0\\0&5&1\end{array}}\right]\\\begin{array}{cc}{}&{}&{\boldsymbol{E}_{21}^{-1}}&{}&{}&{}&{\boldsymbol{E}_{32}^{-1}}&{}&{}&{}&{}&{}&\boldsymbol{L}&{}&{}\end{array}\end{array}$

如果没有行交换操作，则消元矩阵的因子可以直接写入矩阵 $\boldsymbol{L}$。没有多余的交叉项出现是 $\boldsymbol{LU}$ 分解要优于 $\boldsymbol{EA}=\boldsymbol{U}$ 这种形式的原因之一。

三、消元法所需运算量

在一些应用中我们需要处理超大型矩阵，即使用计算机来处理这一问题，也需要评估所需的计算量。

如果我们把 “先乘后减” 大致记为一次运算，那么对于一个 $n\times{n}$ 矩阵，对于一行进行消元要进行 $n$ 次运算，由于有 $n$ 行所以进行了 $n^2$ 次运算，结果得到了第一列除第一主元外都消成 $0$ 的矩阵。随后开始对除第一行第一列之外的剩余部分进行消元，这相当于一个 $(n-1)\times(n-1)$ 的矩阵，那么就要进行 $(n-1)^2$ 次运算，以此类推。

最后需要的运算次数为 $1^2+2^2+\cdots+n^2$，利用积分公式可以估算其数值。

$1^2+2^2+\cdots+n^2=\sum\limits_{i=1}^n{i^2}\approx\int_0^n{x^2}\mathrm{d}x=\frac{1}{3}{n^3}$

四、行交换

如果主元的位置出现了 $0$，就需要进行 “行交换”。我们可以通过左乘一个置换矩阵（Permutation Matrix）实现 “行交换” 的操作，例如：

${\boldsymbol{P}_{21}}=\left[{\begin{array}{cc}0&1&0\\1&0&0\\0&0&1\end{array}}\right]$

可以实现 $3\times{3}$ 矩阵的第一行与第二行的交换。所有的 $3\times{3}$ 的置换矩阵包括：

$\left[{\begin{array}{cc}1&0&0\\0&1&0\\0&0&1\end{array}}\right]\left[{\begin{array}{cc}1&0&0\\0&0&1\\0&1&0\end{array}}\right]\left[{\begin{array}{cc}0&1&0\\1&0&0\\0&0&1\end{array}}\right]\left[{\begin{array}{cc}0&1&0\\0&0&1\\1&0&0\end{array}}\right]\left[{\begin{array}{cc}0&0&1\\1&0&0\\0&1&0\end{array}}\right]\left[{\begin{array}{cc}0&0&1\\0&1&0\\1&0&0\end{array}}\right]$

对于 $n\times{n}$ 矩阵存在着 $n!$ 个置换矩阵。

对于某阶的置换矩阵集合而言，置换矩阵的两两乘积仍在这个集合中，置换矩阵的逆矩阵也在此集合中。

置换矩阵的逆矩阵即为它的转置 $\boldsymbol{P}^{-1}=\boldsymbol{P}^T$，证明如下：

$\boldsymbol{P}$ 的第 $i$ 行和 $\boldsymbol{P}^{-1}$ 的第 $i$ 列相乘会得到 $1$，与其他列相乘都得到 $0$，所以 $\boldsymbol{P}^{-1}$ 的第 $i$ 列只能是 $\boldsymbol{P}$ 的第 $i$ 行行向量的转置（让分量 $1$ 出现在向量里的相同位置），其他各列以此类推，则 $\boldsymbol{P}$ 的每一个行向量转置就得到 $\boldsymbol{P}^{-1}$ 的列向量，这也就是矩阵转置 $\boldsymbol{P}^T$ 的定义。因此可得 $\boldsymbol{P}^{-1}=\boldsymbol{P}^T$。

五、参考资料

• MIT—线性代数笔记 04 矩阵的 LU 分解 (opens new window)