专题进阶 · 数值算法推荐总顺序 · 第 115 / 148 课

利用对称正定结构分解 A=LLᵀ,解释正对角与平方根的来源。

先学会这些,再进入本课 LU 分解 矩阵乘法
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数值算法

Cholesky 分解Cholesky

对称正定矩阵可分解为 LLᵀ,利用结构节省存储与计算。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

利用对称正定结构分解 A=LLᵀ,解释正对角与平方根的来源。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

矩阵 A=[[4,2],[2,3]] 对称且正定,是否可以只保存一个三角因子来求解?

02一步步得到方法

正定是什么意思

实对称矩阵满足任意非零向量 x 都有 xᵀAx>0。几何上对应严格向上的二次型,没有平坦或向下方向。对称不等于正定,例如 [[1,2],[2,1]] 有负方向。

设 L 下三角且对角为正,将 LLᵀ 的元素逐项与 A 对齐。对角项满足 Lᵢᵢ²=Aᵢᵢ−ΣLᵢₖ²;非对角项满足 Lᵢⱼ=(Aᵢⱼ−ΣLᵢₖLⱼₖ)/Lⱼⱼ。

为什么通常不需要主元交换

对称正定矩阵的消元余块仍正定,因此精确算术下每个待开方对角量都为正,能持续分解。若输入不正定,或数值误差暴露近奇异情况,就可能出现非正待开方值。

求解时先 Ly=b,再 Lᵀx=y,分别前代与后代。用于协方差、最小化正定二次型和许多物理离散系统,但必须先确认模型确有正定性。

正定性保证每一步有正平方根

对称正定矩阵可分解为 A=LLᵀ,按列或按行扣除已知贡献后求对角线平方根,再求下面的系数。正定性保证精确算术下这些待开方量为正。

它比通用 LU 利用更多结构,只需存一半三角部分。若输入不对称、非正定或严重数值病态,不能仅把负数强行截成0继续计算;应诊断模型、尺度和数值误差。

03把一个小例子完全算清楚

A=[[4,2],[2,3]]。

步骤计算与状态为什么这样做
L₀₀sqrt(4)=2正对角约定
L₁₀2/2=1非对角公式
L₁₁sqrt(3−1²)=sqrt(2)减去已解释的贡献
重构[[2,0],[1,√2]]·其转置=A只需一个三角因子

窄屏可左右滑动表格,阅读完整计算与理由。

每个新元素都扣除已经由前面列解释的部分。

04为什么这个方法成立

  1. 按行列匹配 A=LLᵀ 得到递推公式。
  2. 正定性保证每一步 Schur 补正定,待开方值为正。
  3. 依赖只来自已完成列,逐项构造最终重构 A;正对角使因子唯一。

05把推导翻译成代码

Python · 可独立运行的教学实现

from math import sqrt
def cholesky(a):
    n = len(a)
    assert all(len(row)==n for row in a)
    if any(abs(a[i][j]-a[j][i])>1e-10 for i in range(n) for j in range(n)):
        raise ValueError("symmetric matrix required")
    l = [[0.0]*n for _ in range(n)]
    for i in range(n):
        for j in range(i+1):
            value = a[i][j]-sum(l[i][k]*l[j][k] for k in range(j))
            if i == j:
                if value <= 0: raise ArithmeticError("not positive definite")
                l[i][j] = sqrt(value)
            else:
                l[i][j] = value/l[j][j]
    return l

逐个理解关键决定

range(i+1)
只计算下三角,另一半由转置表达。
value <= 0
不满足正定分解条件时明确失败,不能对负值强行取绝对值开根。

06时间、空间与实现范围

稠密矩阵时间 O(n³),运算常数约为一般 LU 的一半;三角存储 O(n²)。

代码为清晰仍分配完整二维列表。真实库可只使用一半存储,数值阈值与正定判断需按尺度处理。

07改变条件,检查哪里会出错

只要对称就可以 Cholesky

对称但不正定的矩阵可能使某个平方根参数为负。

所有对称矩阵都可实数 Cholesky

对称但不正定仍可能出现负的开方项,正定条件不能省略。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

A=I 的 L 是什么?

需要一点提示

正对角的平方根。

查看解析与答案

仍为 I。

练习 2 · 边界与辨析

半正定矩阵一定能直接用本代码吗?

需要一点提示

可能存在零特征方向。

查看解析与答案

不一定,会出现零对角需要特殊处理;本接口要求严格正定。

练习 3 · 变式与迁移

为何不对失败的 value 取 abs 继续?

需要一点提示

等式是否仍成立?

查看解析与答案

那会改变分解对应矩阵,无法再保证 LLᵀ=A,掩盖输入或数值问题。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Driscoll 与 Braun · Fundamentals of Numerical Computation

理解之后,继续递进

继续当前专题:共轭梯度 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。