LU分解
Contents
LU分解#
本文是对《机器学习数学基础》第2章2.3.3节矩阵LU分解的拓展。
判断是否可LU分解#
并非所有矩阵都可以实现LU分解。
**定理1：**若 \(n\) 阶可逆矩阵 \(\pmb{A}\) 可以进行LU分解，则 \(\pmb{A}\) 的 \(k\) 阶顺序主子阵（leading principal submatrix）\(\pmb{A}_k\) 都是可逆的\(^{[1]}\)。
证明
将 \(\pmb{A}=\pmb{LU}\) 用分块矩阵表示：
其中 \(\pmb{L}_{11}、\pmb{U}_{11}\) 是 \(k\times k\) 分块矩阵。
因为 \(\pmb{L}\) 是单位下三角矩阵，且主对角线元素都是 \(1\) ，则其分块矩阵 \(\pmb{L}_{11}\) 亦为三角矩阵，且主对角线元素非零。同理，\(\pmb{U}_{11}\) 亦然。
所以 \(\pmb{L}_{11}\) 和 \(\pmb{U}_{11}\) 可逆，则 \(\pmb{A}_k=\pmb{L}_{11}\pmb{U}_{11}\) 可以。
证毕。
例：\(\pmb{A}=\begin{bmatrix}3&-1&2\\6&-1&5\\-9&7&3\end{bmatrix}\) 的顺序主子阵依次为：
定理2：（定理1的逆定理）若矩阵 \(\pmb{A}\) 的所有顺序主子阵 \(\pmb{A}_k\) 都可逆，则该矩阵存在LU分解。
证明（用归纳法）
\(k=1\) ，\(\pmb{A}_1=[a_{11}]\) 可逆，则 \(a_{11}\ne 0\) ，所以有：\(\pmb{A}_1=[1][a_{11}]\) ，即为LU分解。
设 \(k\) 阶顺序主子阵 \(\pmb{A}_k\) 可逆，且可LU分解，\(\pmb{A}_k=\pmb{L}_k\pmb{U}_k\) 。
\(k+1\) 阶顺序主子阵 \(\pmb{A}_{k+1}\) 可以表示为：
其中 \(\pmb{b}、\pmb{c}\) 是 \(k\) 维向量，\(d\) 是标量。则上式可以进一步写成：
通过对应关系，可知：
解得：
所以：\(\pmb{A}_{k+1}=\pmb{L}_{k+1}\pmb{U}_{k+1}\)
其中 \(\pmb{L}_{k+1}=\begin{bmatrix}\pmb{L}_k&\pmb{0}\\\pmb{c}^T\pmb{U}_k^{-1}&1\end{bmatrix},\pmb{U}_{k+1}=\begin{bmatrix}\pmb{U}_k&\pmb{y}\\\pmb{0}^T&d-\pmb{c}^T\pmb{A}^{-1}\pmb{b}\end{bmatrix}\)
因为 \(\pmb{A}_{k+1}\) 和 \(\pmb{L}_{k+1}\) 可逆，所以 \(\pmb{U}_{k+1}\) 可逆，则 \(d-\pmb{c}^T\pmb{A}^{-1}\pmb{b}\ne0\) 。即 \(\pmb{A}_{k+1}\) 可以分解为 \(\pmb{L}_{k+1}\pmb{U}_{k+1}\) 。
综上，定理得证。
LU分解的唯一性#
对于 \(\pmb{A}=\pmb{LU}\) 而言，\(\pmb{L}\) 是单位下三角矩阵，主对角线元素为 \(1\) 。对于 \(\pmb{U}\) ，以 \(3\times 3\) 为例，可以转化为：
所以：\(\pmb{A}=\pmb{LDU}'\)
假设 \(\pmb{A}=\pmb{L}_1\pmb{D}_1\pmb{U}_1'\) ，\(\pmb{A}=\pmb{L}_2\pmb{D}_2\pmb{U}_2'\) ，则：
由因为 \(\pmb{L}_i\) 和 \(\pmb{U}'_i\) 都可逆，所以：
继续以 \(3\) 阶方阵为例，将上式等号左右分别用矩阵方式展开，得：
所以：\(\pmb{D}_1=\pmb{D}_2\) ，非主元的值 \(* = 0\) ，故 \(\pmb{U}_1'\pmb{U}_2'^{-1}=\pmb{I}, \pmb{L}_1^{-1}\pmb{L}_2=\pmb{I}\)
所以：\(\pmb{U}_1'=\pmb{U}_2',\pmb{L}_1=\pmb{L}_2\) ，即 LU 分解具有唯一性。
证毕。
LU分解的应用#
求解线性方程组#
此应用在《机器学习数学基础》第2章2.3.3节中有详细介绍，请参阅。
计算行列式#
利用LU分解可以手工计算 \(n\) 阶行列式。
三角矩阵的行列式等于主对角元乘积。
所以：\(|\pmb{L}|=1\) ，则：