JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Cholesky 与 LDL^T:对称性的回报

当 A 是对称正定矩阵时,LU 有一半是冗余的。Cholesky 把它扔掉——A = LL^T——换来两倍速度和一次免费的正定性检验。

对称性该换来好处

实践中出现的许多矩阵——协方差矩阵、最小二乘的法方程 A^T A、物理中的刚度矩阵——都是对称且正定的(SPD):A = A^T,且对每个非零 x 都有 x^T A x > 0。在这样的矩阵上跑通用 LU 是浪费,因为 L 与 U 除一个对角缩放外互为镜像。分解应当体现这种对称性,而非忽视它。

Cholesky 分解正是这样做的:它把 A 写成 A = LL^T,其中 L 为下三角且对角元*为正*。一个三角因子加上它的转置就承载了全部信息——无需单独的 U,也无需选主元,因为正定性保证主元始终为正。它是整个稠密线性代数中最高效、最稳定的分解,只要你能证明 A 是 SPD,就该选用它。

逐列计算它

Cholesky 有一个干净的递归配方。把 LL^T 的元素与 A 匹配:(1,1)元强制 L_11 = sqrt(A_11);L 第一列的其余部分是 A 的第一列除以 L_11;然后从剩余块中减去该列的外积,再重复。每个对角步都取一次平方根——若根号下某个值变为非正,则 A *不是*正定的。这个失败本身就是一项特性。

A = [ 4   12  -16 ;        L = [  2   0   0 ;
      12  37  -43 ;              6   1   0 ;
     -16 -43   98 ]            -8   5   3 ]

# L_11 = sqrt(4) = 2
# L_21 = 12/2 = 6 ,  L_31 = -16/2 = -8
# L_22 = sqrt(37 - 6^2) = sqrt(1) = 1
# L_32 = (-43 - (-8)(6)) / 1 = 5
# L_33 = sqrt(98 - (-8)^2 - 5^2) = sqrt(9) = 3
# check: L @ L^T == A
一个完整算出的 3x3 Cholesky;每个对角步都取实平方根,因为 A 是 SPD。

在对角元为正的约束下,Cholesky 是唯一的——恰好存在一个这样的 L。对比 LU,那里你得按惯例把 L 的对角线固定为 1;而这里 A 的正定性免费完成了这个固定。这是由结构*赢得*的唯一性,而非人为规定的。

LDL^T:免开方的 Cholesky

平方根略微昂贵,且对*非*正定的对称矩阵(不定情形,在优化中很常见)无定义。LDL^T 分解同时绕开这两个问题:把 A 写成 A = LDL^T,其中 L 是单位下三角、D 是对角矩阵。D 中的符号现在记录不定性,而不会让算法崩溃——按Sylvester 惯性定律,D 上正、负、零元的个数是 A 的一个不变量。