线性方程组与本征值问题(01)：LU 分解

LU 分解是指把一个方阵分解成一个上三角和一个下三角矩阵的乘积 \[ \mathbf{A}\pmb{x} = \pmb{b}\Rightarrow\begin{cases}\displaystyle\mathbf{L}\pmb{y}=\pmb{b} \\\\\displaystyle \mathbf{U}\pmb{x} = \pmb{y} \end{cases}\qquad (\mathbf{A}=\mathbf{L}\mathbf{U}) \] 通常, 我们会取\(\mathbf{L}\)的对角元为\(1\), 并且判断唯一性时总是忽略这个自由度. 如果知道系数矩阵的 LU 分解, 就把一个复杂的方程组转化为两步较简单的解方程组. 显然, LU 分解的一个特例就是 Gauss 消元法.

想要把 LU 分解应用到问题中, 我们需要从数学上解决它的存在性和唯一性, 或者在什么样的条件下, 有唯一的 LU 分解.

LU 分解的唯一性

给定一个矩阵\(\mathbf{A}\in\mathbb{C}^{n\times n}\), 如果\(\mathbf{A}\)具有 LU 分解并且秩满足\(\text{rank}(\mathbf{A})\ge n-1\), 则这个分解唯一.

证明相当简单. 假设存在另一个 LU 分解\(\mathbf{A} = \mathbf{D}\mathbf{H}\). 先考虑\(\mathbf{A}\)满秩的情形.

1. \(\mathbf{A}\)满秩

因为乘法运算不让秩增大, 而\(\mathbf{A}\)已经满秩了, 因此所有三角矩阵也满秩.

这样可以得到 \[ \mathbf{L}\mathbf{U}=\mathbf{D}\mathbf{H}\Rightarrow\mathbf{D}^{-1}\mathbf{L}=\mathbf{H}\mathbf{U}^{-1} \] 上(下)三角矩阵参与的求逆和乘法运算, 结果仍然是上(下)三角矩阵, 因此左边仍是下三角, 右边仍是上三角, 相等, 说明两者都是对角矩阵. 即 \[ \mathbf{D}^{-1}\mathbf{L}=\text{diag}\{c_1,c_2,\cdots,c_n\} \] 把\(\mathbf{D}\)乘过去, 立即得到\(\mathbf{L}\)的对角元 \[ l_{ii}=c_id_{ii}\ ,\qquad i=1,2,\cdots,n \] 考虑到 LU 分解取下三角矩阵的对角元为\(1\), 有\(c_i=1(\forall i)\). 因此\(\mathbf{D}^{-1}\mathbf{L}=\mathbf{I}\), 即 \[ \mathbf{D}=\mathbf{L}\ ,\qquad \mathbf{U}=\mathbf{H} \] 这说明根本不是新的分解, 得证.

2. \(\mathbf{A}\)不满秩

我们进行分块 \[ \mathbf{A}=\begin{pmatrix} \mathbf{A}_m & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{pmatrix} \] 作为\(m\)阶主子矩阵, \(\mathbf{A}_m\)是满秩的, 如果它具有分解(显然具有, 因为我们假设\(\mathbf{A}\)能够分解), 则\(\mathbf{L}\)的\((1,1), (1,2)\)块和\(\mathbf{U}\)的\((1,1),(2,1)\)块已经确定了: \[ \mathbf{L}=\begin{pmatrix} \mathbf{L}_m & \mathbf{O} \\ \mathbf{L}_{21} & \mathbf{L}_{22} \end{pmatrix} \\ \mathbf{U}=\begin{pmatrix} \mathbf{U}_m & \mathbf{U}_{12} \\ \mathbf{O} & \mathbf{U}_{22} \end{pmatrix} \] 它给出 \[ \mathbf{L}_m\mathbf{U}_{12}=\mathbf{B} \\ \mathbf{L}_{21}\mathbf{U}_m=\mathbf{C} \\ \mathbf{L}_{21}\mathbf{U}_{12}+\mathbf{L}_{22}\mathbf{U}_{22}=\mathbf{D} \] 由于\(\mathbf{L}_m\)和\(\mathbf{U}_m\)满秩, 那么前两式相当于多个独立的线性方程组, 系数矩阵为满秩方阵, 因此\(\mathbf{U}_{12}\)和\(\mathbf{L}_{21}\)有唯一解.

\(\mathbf{L}_{22}\)和\(\mathbf{U}_{22}\)有赖于我们给出的限制条件. 前面提到, 约定\(\mathbf{L}\)的对角元都为\(1\), 因此\(\mathbf{L}\)满秩, 而\(\mathbf{U}\)的秩为\(m\), 将后\(n-m\)列用前\(m\)列线性表出, 立即得到 \[ \mathbf{U}_{22}=\mathbf{O} \] 第三式由此成为恒等式, 对于\(\mathbf{L}_{22}\)没有更多的限制条件了. 幸好\(\text{rank}(\mathbf{A})=n-1\), \(\mathbf{L}_{22}\)是个\(1\times1\)的矩阵, 唯一元被强制归一了, 因此仍是唯一的.

LU 分解的存在性

关于 LU 分解是否存在, 有如下定理:

\(\forall\mathbf{A}\in M_{n}(\mathbb{R})\), \(\mathbf{A}\)存在 LU 分解的充分条件为:

\(\mathbf{A}\)的所有主子矩阵\(\mathbf{A}_i\ ,\ i=1,2,\cdots,n-1\)都是可逆的.

这个条件和\(\text{rank}{\mathbf{A}}\ge n-1\)等价.

注意, 它并没有对\(\mathbf{A}\)本身是否可逆有要求. 证明这个定理需要归纳法. 对于第\(m+1\)个主子矩阵, 进行分块: \[ \mathbf{A}_{m+1}=\begin{pmatrix} \mathbf{A}_m & \pmb{u} \\ \pmb{v}^{\mathbf{T}} & \lambda \end{pmatrix} \] 如果\(\mathbf{A}_m\)存在 LU 分解: \[ \mathbf{A}_m=\mathbf{L}_m\mathbf{U}_m \] 则可以验证, \(\mathbf{A}_{m+1}\)可以写作 \[ \begin{aligned} \mathbf{A}_{m+1}&=\mathbf{L}_{m+1}\mathbf{U}_{m+1} \\ \mathbf{L}_{m+1}&=\begin{pmatrix} \mathbf{L}_m & \mathbf{O} \\ \pmb{v}^\mathbf{T}\mathbf{U}_m^{-1}&1 \end{pmatrix} \\ \mathbf{U}_{m+1}&=\begin{pmatrix} \mathbf{U}_m & \mathbf{L}_m^{-1}\pmb{u} \\ \mathbf{O} & \lambda - \pmb{v}^\mathbf{T}\mathbf{A}_m^{-1}\pmb{u} \end{pmatrix} \end{aligned} \] 这个式子要求\(\mathbf{A}_m\)分解为两个满秩矩阵. 因此从\(m=1\)开始归纳直到\(m=n-1\), 条件为其中各阶主子矩阵满秩, 则\(\mathbf{A}\)存在 LU 分解.

结合前面, 我们证明了: 当\(\mathbf{A}\)的\(1\sim n-1\)阶主子矩阵非奇异(即\(\text{rank}\mathbf{A} \ge n-1\)), 存在唯一的 LU 分解. 实际上必要性也成立(证明略), 这是个充要条件.