LU分解

1. LU分解的定义

1.1 定义

设 $A$ 为 $n$ 阶方阵，若 $A$ 可以分解为：

$A=LU$

其中 $L$ 为下三角矩阵，$U$ 为上三角矩阵，则称为 $A$ 的 LU 分解。

1.2 存在条件

定理：若 $A$ 的所有顺序主子式都不为零（${\Delta }_k\ne 0$，$k=1,2,\dots ,n-1$），则 $A$ 的 LU 分解存在且唯一（在指定 $L$ 或 $U$ 的对角线元素时）。

1.3 PLU 分解

对于一般的矩阵，可能需要行交换才能进行 LU 分解：

$PA=LU$

其中 $P$ 为置换矩阵。这称为 PLU 分解，对任何可逆矩阵都存在。

2. Doolittle 分解

2.1 定义

在 Doolittle 分解中，$L$ 为单位下三角矩阵（主对角线为1），$U$ 为上三角矩阵：

$A=LU=\left(\begin{array}{cccc}1& 0& \cdots & 0\\ l_{21}& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ l_{n1}& l_{n2}& \cdots & 1\end{array}\right)\left(\begin{array}{cccc}{u}_{11}& u_{12}& \cdots & u_{1n}\\ 0& u_{22}& \cdots & u_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & u_{nn}\end{array}\right)$

2.2 计算公式

第一行：$u_{1j}=a_{1j}$（$j=1,2,\dots ,n$）

第一列：$l_{i1}=a_{i1}/u_{11}$（$i=2,3,\dots ,n$）

一般地（$k=2,3,\dots ,n$）：

$u_{kj}=a_{kj}-{\sum }_{s=1}^{k-1}{l}_{ks}{u}_{sj}(j=k,k+1,\dots ,n)$

$l_{ik}=\frac{1}{u_{kk}}\left(a_{ik}-{\sum }_{s=1}^{k-1}{l}_{is}{u}_{sk}\right)(i=k+1,k+2,\dots ,n)$

2.3 完整示例

对 $A=\left(\begin{array}{ccc}2& 1& 1\\ 4& 3& 3\\ 8& 7& 9\end{array}\right)$ 进行 Doolittle 分解。

步骤1：$u_{11}=2$，$u_{12}=1$，$u_{13}=1$

$l_{21}=4/2=2$，$l_{31}=8/2=4$

步骤2：$u_{22}=3-2\times 1=1$，$u_{23}=3-2\times 1=1$

$l_{32}=(7-4\times 1)/1=3$

步骤3：$u_{33}=9-4\times 1-3\times 1=2$

$L=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 4& 3& 1\end{array}\right),U=\left(\begin{array}{ccc}2& 1& 1\\ 0& 1& 1\\ 0& 0& 2\end{array}\right)$

验证：$LU=\left(\begin{array}{ccc}2& 1& 1\\ 4& 3& 3\\ 8& 7& 9\end{array}\right)=A$

3. Crout 分解

3.1 定义

在 Crout 分解中，$L$ 为下三角矩阵，$U$ 为单位上三角矩阵（主对角线为1）：

$A=LU=\left(\begin{array}{cccc}{l}_{11}& 0& \cdots & 0\\ l_{21}& l_{22}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ l_{n1}& l_{n2}& \cdots & l_{nn}\end{array}\right)\left(\begin{array}{cccc}1& u_{12}& \cdots & u_{1n}\\ 0& 1& \cdots & u_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right)$

3.2 计算公式

第一列：$l_{i1}=a_{i1}$（$i=1,2,\dots ,n$）

第一行：$u_{1j}=a_{1j}/l_{11}$（$j=2,3,\dots ,n$）

一般地：

$l_{ik}=a_{ik}-{\sum }_{s=1}^{k-1}{l}_{is}{u}_{sk}(i=k,k+1,\dots ,n)$

$u_{kj}=\frac{1}{l_{kk}}\left(a_{kj}-{\sum }_{s=1}^{k-1}{l}_{ks}{u}_{sj}\right)(j=k+1,k+2,\dots ,n)$

4. LDU 分解

4.1 定义

将 $A$ 分解为 $A=LDU$，其中 $L$ 为单位下三角矩阵，$D$ 为对角矩阵，$U$ 为单位上三角矩阵。

4.2 与 LU 分解的关系

若 $A=LU$（Doolittle 分解），则 $A=LD{U}^{\prime }$，其中 $D=\text{diag}(u_{11},u_{22},\dots ,u_{nn})$，$U^{\prime }=D^{-1}U$。

5. LU 分解的应用

5.1 解线性方程组

$Ax=b$，$A=LU$：

1. 解 $Ly=b$（前代，$O(n^2)$）
2. 解 $Ux=y$（回代，$O(n^2)$）

分解本身需要 $O(n^3)$，但一旦分解完成，对不同的 $b$ 只需 $O(n^2)$。

5.2 求行列式

$|A|=|L|\cdot |U|=u_{11}{u}_{22}\cdots u_{nn}$（Doolittle 分解中 $|L|=1$）

5.3 求逆矩阵

$A^{-1}=U^{-1}{L}^{-1}$，分别解 $n$ 个三角形方程组。

6. Cholesky 分解

6.1 定义

若 $A$ 为正定矩阵，则 $A$ 可分解为：

$A=L{L}^T$

其中 $L$ 为下三角矩阵（对角线元素为正）。这称为 Cholesky 分解。

6.2 计算公式

$l_{kk}=\sqrt{a_{kk}-{\sum }_{s=1}^{k-1}{l}_{ks}^2}$

$l_{ik}=\frac{1}{l_{kk}}\left(a_{ik}-{\sum }_{s=1}^{k-1}{l}_{is}{l}_{ks}\right)(i=k+1,\dots ,n)$

6.3 示例

对 $A=\left(\begin{array}{cc}4& 2\\ 2& 5\end{array}\right)$ 进行 Cholesky 分解。

$l_{11}=2$，$l_{21}=2/2=1$，$l_{22}=\sqrt{5-1}=2$

$L=\left(\begin{array}{cc}2& 0\\ 1& 2\end{array}\right),L^T=\left(\begin{array}{cc}2& 1\\ 0& 2\end{array}\right)$

验证：$L{L}^T=\left(\begin{array}{cc}4& 2\\ 2& 5\end{array}\right)$

6.4 Cholesky 分解的优势

• 计算量约为 LU 分解的一半
• 数值稳定性好
• 只需存储 $L$，节省存储空间
• 正定性的数值验证