Cholesky 分解 | Codeboy's Blog

形式陈述

若 $A\in\mathbb F^{n\times n}$ 是Hermitian 正定矩阵，则存在唯一的下三角矩阵 $L$ ，其对角元均为正实数，并满足

A=LL^*.

这里 $L^*$ 表示共轭转置；实数情形即 $A=LL^{\mathsf T}$ 。正对角的约定排除了任意改列符号或复相位的自由度。逐列比较矩阵元素得到递推

l_{jj} = \sqrt{a_{jj}-\sum_{k=1}^{j-1}|l_{jk}|^2},

以及对 $i>j$ ，

l_{ij} = \frac{a_{ij}-\sum_{k=1}^{j-1}l_{ik}\overline{l_{jk}}} {l_{jj}}.

其存在性可按消去步骤理解：第一步取 $l_{11}=\sqrt{a_{11}}>0$ ，消去第一列后，剩余问题的矩阵是右下子块减去已消去第一列所贡献的秩一项，这个矩阵称为 Schur 补。正定矩阵的这一 Schur 补仍然正定，于是同一步骤可以递归完成。每个正平方根和后续除法又都被先前数据唯一确定，这给出唯一性的证明思路。正定性因此保证精确算术中每个被开方数严格为正，无需通用 LU 的行主元。反过来，递推若在精确算术中得到非正主元，就证明输入不是正定矩阵。

实稠密 Cholesky 分解约需 $n^3/3$ 次浮点运算，只存一个三角因子；相比通用 LU 的约 $2n^3/3$ ，它利用 Hermitian 结构节省近一半工作和存储。求解 $Ax=b$ 时执行

Ly=b,\qquad L^*x=y,

即两次三角求解。输入是声明为 Hermitian 的矩阵，输出是 $L$ 或明确的非正定失败；完成时应确认所有对角元有限且为正，并用因子重构误差或求解残差核对结果。

在没有溢出等异常且算法成功完成时，标准实现的计算因子满足后向误差关系

A+\Delta A=\widehat L\widehat L^*, \qquad \|\Delta A\|_2\le c_n u\,\|A\|_2,

这里 $u$ 是单位舍入误差， $c_n$ 是依赖维数和实现的常数；这一界在标准浮点误差分析的条件下成立。若矩阵非常接近半正定边界，舍入可能让理论上很小的正主元变成非正；这既是数值诊断，也提示条件性差，不能通过随意取绝对值把失败藏起来。

直觉

正定矩阵给每个非零方向分配正能量。Cholesky 因子把这份耦合能量改写成普通 Euclidean 长度：

x^*Ax=x^*LL^*x=\|L^*x\|_2^2.

递推每一步从当前对角能量中扣除已经由前面列解释的部分，剩余严格为正，才产生新的独立方向。零剩余表示新方向没有能量，不再正定；负剩余则暴露不定性。

例子与边界

矩阵

A=\begin{pmatrix}4&2\\2&3\end{pmatrix}

的顺序主子式为 $4$ 与 $8$ ，所以正定。递推给出

L= \begin{pmatrix} 2&0\\ 1&\sqrt2 \end{pmatrix}, \qquad LL^{\mathsf T}=A.

具体地，第一列由 $l_{11}=\sqrt4=2$ 、 $l_{21}=2/2=1$ 得到，第二个对角元为 $\sqrt{3-1^2}=\sqrt2$ 。若要求解 $Ax=(6,5)^{\mathsf T}$ ，先由 $2y_1=6$ 、 $y_1+\sqrt2y_2=5$ 得 $y=(3,\sqrt2)^{\mathsf T}$ ，再回代得 $x_2=1$ 、 $x_1=1$ 。分解只做一次，更换右端时只需重复这两次三角求解。

半正定矩阵

\begin{pmatrix}1&1\\1&1\end{pmatrix}

在第二步产生零主元，标准正定 Cholesky 应报告不满足正定要求。它仍可写成 $LL^{\mathsf T}$ ，例如 $L=\begin{pmatrix}1&0\\1&0\end{pmatrix}$ ，但已不满足本定理的正对角条件。对称不定矩阵 $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ 则产生负的第二被开方数。仅仅“矩阵对称”绝不足以调用本算法，半正定、近半正定和对称不定必须分别处理。

Gram 矩阵 $B^*B$ 总是半正定，只有 $B$ 满列秩时才正定。虽然这使正规方程能够形式上使用 Cholesky，但显式形成 $B^*B$ 会把 $2$ -范数条件数平方；因此最小二乘的默认计算路线仍是 QR 或 SVD，而不是“正规方程加 Cholesky”。

推论与应用

Cholesky 是正定线性系统、Gaussian 过程协方差、二次优化和能量离散中的标准直接分解。它还为共轭梯度法提供正定几何，并可作为检查输入是否数值上远离半正定边界的实用信号。

不完全 Cholesky在固定模式内保留部分填充，用作稀疏迭代法的预条件器。丢弃更新后，正定输入也可能产生非正主元；它必须报告失败，不能沿用本页精确分解的存在性结论。半正定秩亏问题可采用带主元或秩揭示变体，但不能把标准正定算法的唯一性和稳定结论原样搬过去。

在Hermitian 正定广义特征问题 $Ax=\lambda Bx$ 中，对度量矩阵 $B=LL^*$ 做 Cholesky，便可用 $y=L^*x$ 把问题化为 $L^{-1}AL^{-*}y=\lambda y$ 。三角求解方向及 $B$ -正交性一起核对，才能把普通谱算法的输出正确恢复到原坐标。

参考资料

Gene H. Golub and Charles F. Van Loan, Matrix Computations, 4th ed., Johns Hopkins University Press, 2013, §4.2.
Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, 2002, Ch. 10.
Nicholas J. Higham, “What Is a Cholesky Factorization?”, author’s article, 2020; existence, cost, and finite-precision breakdown.

形式陈述 ​

反向链接

形式陈述