《机器学习数学基础》补充资料：矩阵的LU分解

本文是对《机器学习数学基础》第2章2.3.3节矩阵LU分解的拓展。

判断是否可LU分解

并非所有矩阵都可以实现LU分解。

定理1： 若 $n$ 阶可逆矩阵 $A$ 可以进行LU分解，则 $A$ 的 $k$ 阶顺序主子阵（leading principal submatrix）$A_k$ 都是可逆的${}^{[1]}$。

证明

将 $A=LU$ 用分块矩阵表示：

$$A=LU=\left[\begin{array}{cc}{L}_{11}& 0\\ L_{21}& L_{22}\end{array}\right]\left[\begin{array}{cc}{U}_{11}& U_{12}\\ 0& U_{22}\end{array}\right]=\left[\begin{array}{cc}{L}_{11}{U}_{11}& L_{11}{U}_{12}\\ L_{21}{U}_{11}& L_{21}{U}_{12}+L_{22}{U}_{22}\end{array}\right]$$

其中 $L_{11}、U_{11}$ 是 $k\times k$ 分块矩阵。

因为 $L$ 是单位下三角矩阵，且主对角线元素都是 $1$ ，则其分块矩阵 $L_{11}$ 亦为三角矩阵，且主对角线元素非零。同理，$U_{11}$ 亦然。

所以 $L_{11}$ 和 $U_{11}$ 可逆，则 $A_k=L_{11}{U}_{11}$ 可以。

证毕。

例：$A=\left[\begin{array}{ccc}3& -1& 2\\ 6& -1& 5\\ -9& 7& 3\end{array}\right]$ 的顺序主子阵依次为：

$$\begin{array}{rl}{A}_1& =[3]=[1][3]\\ A_2& =\left[\begin{array}{cc}3& -1\\ 6& -1\end{array}\right]=\left[\begin{array}{cc}1& 0\\ 2& 1\end{array}\right]\left[\begin{array}{cc}3& -1\\ 0& 1\end{array}\right]\\ A_3& =A=LU\end{array}$$

定理2：（定理1的逆定理）若矩阵 $A$ 的所有顺序主子阵 $A_k$ 都可逆，则该矩阵存在LU分解。

证明（用归纳法）

$k=1$ ，$A_1=[a_{11}]$ 可逆，则 $a_{11}\ne 0$ ，所以有：$A_1=[1][a_{11}]$ ，即为LU分解。

设 $k$ 阶顺序主子阵 $A_k$ 可逆，且可LU分解，$A_k=L_k{U}_k$ 。

$k+1$ 阶顺序主子阵 $A_{k+1}$ 可以表示为：

$$A_{k+1}=\left[\begin{array}{cc}{A}_k& b\\ c^T& d\end{array}\right]$$

其中 $b、c$ 是 $k$ 维向量，$d$ 是标量。则上式可以进一步写成：

$$A_{k+1}=\left[\begin{array}{cc}{A}_k& b\\ c^T& d\end{array}\right]=\left[\begin{array}{cc}{L}_k& 0\\ x^T& 1\end{array}\right]\left[\begin{array}{cc}{U}_k& y\\ 0^T& z\end{array}\right]$$

通过对应关系，可知：

$$b=L_{k}y,c^T=x^T{U}_k,d=x^{T}y+z$$

解得：

$$y=L_k^{-1}b,x^T=c^T{U}_k^{-1},z=d-x^{T}y=d-c^T(U_k^{-1}{L}_k^{-1})b=d-c^T{A}^{-1}b$$

所以：$A_{k+1}=L_{k+1}{U}_{k+1}$

其中 $L_{k+1}=\left[\begin{array}{cc}{L}_k& 0\\ c^T{U}_k^{-1}& 1\end{array}\right],U_{k+1}=\left[\begin{array}{cc}{U}_k& y\\ 0^T& d-c^T{A}^{-1}b\end{array}\right]$

因为 $A_{k+1}$ 和 $L_{k+1}$ 可逆，所以 $U_{k+1}$ 可逆，则 $d-c^T{A}^{-1}b\ne 0$ 。即 $A_{k+1}$ 可以分解为 $L_{k+1}{U}_{k+1}$ 。

综上，定理得证。

LU分解的唯一性

对于 $A=LU$ 而言，$L$ 是单位下三角矩阵，主对角线元素为 $1$ 。对于 $U$ ，以 $3\times 3$ 为例，可以转化为：

$$U=\left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]=\left[\begin{array}{ccc}{u}_{11}& 0& 0\\ 0& u_{22}& 0\\ 0& 0& u_{33}\end{array}\right]\left[\begin{array}{ccc}1& \frac{u_{12}}{u_{11}}& \frac{u_{13}}{u_{11}}\\ 0& 1& \frac{u_{23}}{u_{22}}\\ 0& 0& 1\end{array}\right]=D{U}^{\prime }$$

所以：$A={LDU}^{\prime }$

假设 $A=L_1{D}_1{U}_1^{\prime }$ ，$A=L_2{D}_2{U}_2^{\prime }$ ，则：

$$L_1{D}_1{U}_1^{\prime }=L_2{D}_2{U}_2^{\prime }$$

由因为 $L_i$ 和 $U_i^{\prime }$ 都可逆，所以：

$$\begin{array}{rl}{L}_1^{-1}{L}_1{D}_1{U}_1^{\prime }{U}_2^{\prime -1}& =L_1^{-1}{L}_2{D}_2{U}_2^{\prime }{U}_2^{\prime -1}\\ D_1{U}_1^{\prime }{U}_2^{\prime -1}& =L_1^{-1}{L}_2{D}_2\end{array}$$

继续以 $3$ 阶方阵为例，将上式等号左右分别用矩阵方式展开，得：

$$\left[\begin{array}{ccc}(D_1{)}_{11}& \ast & \ast \\ 0& (D_1{)}_{22}& \ast \\ 0& 0& (D_1{)}_{33}\end{array}\right]=\left[\begin{array}{ccc}(D_2{)}_{11}& 0& 0\\ \ast & (D_2{)}_{22}& 0\\ \ast & \ast & (D_2{)}_{33}\end{array}\right]$$

所以：$D_1=D_2$ ，非主元的值 $\ast =0$ ，故 $U_1^{\prime }{U}_2^{\prime -1}=I,L_1^{-1}{L}_2=I$

所以：$U_1^{\prime }=U_2^{\prime },L_1=L_2$ ，即 LU 分解具有唯一性。

证毕。

LU分解的应用

求解线性方程组

此应用在《机器学习数学基础》第2章2.3.3节中有详细介绍，请参阅。

计算行列式

利用LU分解可以手工计算 $n$ 阶行列式。

$$|A|=|LU|=|L||U|$$

三角矩阵的行列式等于主对角元乘积。

所以：$|L|=1$ ，则：

$$|A|=|U|=\prod _{i=1}^n{u}_{ii}$$

参考文献

[1]. https://ccjou.wordpress.com/2010/09/01/lu-分解/