03 Cholesky、LDL* 与矩阵结构

1. 正定矩阵可以“开平方”

若 $A=A^{\ast }\succ 0$，则存在唯一的上三角矩阵 $R$，其对角元为正且

$$A=R^{\ast }R.$$

这就是 Cholesky 分解。其计算量约为 $\frac{1}{3}{n}^3$，只有通用 LU 的一半，并且无需选主元。

递推公式来自逐项比较 $A=R^{\ast }R$：

$$r_{kk}=\sqrt{a_{kk}-\sum _{j<k}|r_{jk}{|}^2},$$$$r_{ki}=\frac{a_{ki}-\sum _{j<k}\overline{r_{jk}}{r}_{ji}}{r_{kk}},i>k.$$

根号中的量应为正；若在远大于舍入误差的尺度上变成非正，说明矩阵并非正定或数据存在严重问题。

2. LDL* 分解

把 Cholesky 的对角缩放单独抽出，可写

$$A=LD{L}^{\ast },$$

其中 $L$ 为单位下三角矩阵。对 Hermite 不定矩阵，需要对称选主元并允许 $D$ 含 $1\times 1$ 或 $2\times 2$ 块：

$$PA{P}^{\ast }=LD{L}^{\ast }.$$

这既保持对称结构，又避免对负数开平方。

3. 带状矩阵

若 $a_{ij}=0$ 当 $|i-j|>b$，称半带宽为 $b$。在不选主元的 Cholesky 中，带状结构会被保留，存储量约为 $O(nb)$，计算量约为 $O(n{b}^2)$。

结构优势不是抽象常数：当 $b\ll n$ 时，它决定一个问题能否被实际求解。

4. 稀疏矩阵与填充

稀疏分解中，原来的零元素可能在消元时变成非零，称为填充。数值选主元关心稳定性；稀疏排序还要控制填充。二者目标不同，实际软件往往先做重排序，再做带选主元的数值分解。

稀疏 Cholesky 的图解释：消去一个变量会让其相邻节点形成团。好的消元顺序试图减小这种新连接。

5. Cholesky QR 的代价

对满列秩 $A$，可先形成

$$A^{\ast }A=R^{\ast }R,Q=A{R}^{-1}.$$

数学上得到 QR 分解，但形成 $A^{\ast }A$ 会把条件数平方：

$${\kappa }_2(A^{\ast }A)={\kappa }_2(A{)}^2.$$

因此 Cholesky QR 很快，却可能在病态问题上严重丧失正交性。它适合条件良好的高性能场景，不是 Householder QR 的无条件替代品。

6. 选择指南

矩阵类型	首选分解	备注
一般方阵	部分选主元 LU	通用可靠
Hermite 正定	Cholesky	更快、存储更少
Hermite 不定	带对称选主元的 $LD{L}^{\ast }$	保持对称结构
带状/稀疏正定	结构化稀疏 Cholesky	先考虑排序与填充

7. 存在性为何与正定性等价

把 $A$ 分块为

$$A=\left(\begin{array}{cc}{a}_{11}& a_{12}^{\ast }\\ a_{12}& A_{22}\end{array}\right).$$

正定性给出 $a_{11}>0$，并且 Schur 补

$$S=A_{22}-\frac{a_{12}{a}_{12}^{\ast }}{a_{11}}$$

仍然正定。递归地对 $S$ 做 Cholesky 即证明存在性；正对角约定又保证唯一性。反过来，若 $A=R^{\ast }R$ 且 $R$ 非奇异，则 $x^{\ast }Ax=\parallel Rx{\parallel }_2^2>0$。

这个证明也解释了算法中的开方量为什么理论上为正：它正是连续 Schur 补的首个主元。

8. 数值稳定性与失败诊断

标准 Cholesky 对正定矩阵是后向稳定的，计算结果满足

$$A+\mathrm{\Delta }A={\hat{R}}^{\ast }\hat{R},|\mathrm{\Delta }A|\lesssim {\gamma }_{n+1}|{\hat{R}}^{\ast }||\hat{R}|.$$

若开方量略小于零，可能是舍入误差；若明显为负，则矩阵不是正定、输入未严格对称，或条件极差。不要简单取绝对值继续计算，那会掩盖模型错误。合理做法是先检查对称性和最小特征值尺度，或改用带主元的 $LD{L}^{\ast }$。

9. 从非分块到分块 Cholesky

分块写成

$$A=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{12}^{\ast }& A_{22}\end{array}\right).$$

先求 $A_{11}=R_{11}^{\ast }{R}_{11}$，再解

$$R_{11}^{\ast }{R}_{12}=A_{12},$$

最后更新

$$A_{22}\leftarrow A_{22}-R_{12}^{\ast }{R}_{12}.$$

最后一步是对称秩-$k$ 更新，可由高效 Level-3 BLAS 完成。选择合适块大小能让活动数据进入缓存；块太小无法复用数据，块太大则内部面板分解拖慢速度。

10. 对称重排序与稀疏填充

对稀疏正定矩阵应使用同一个置换同时重排行和列：

$$PA{P}^T=L{L}^T.$$

常见策略包括近似最小度排序和嵌套剖分。它们不改变方程本身，只改变消元图，从而显著影响填充量、并行度和内存峰值。对于 PDE 网格，嵌套剖分利用几何或图分隔器把远离的子域分开处理。

11. 自检

• [ ] 能说明 Cholesky 为何比 LU 少一半主项运算量。
• [ ] 知道不定矩阵为什么需要 $2\times 2$ 主元块。
• [ ] 能用带宽估算存储和运算量。
• [ ] 能解释 Cholesky QR 为什么会平方条件数。
• [ ] 能用 Schur 补证明 Cholesky 存在性。
• [ ] 知道分块 Cholesky 的主要矩阵更新是什么。

下一章：正交变换与 QR 分解。