科列斯基分解

科列斯基分解（Cholesky decomposition，也译乔列斯基分解）把实对称正定矩阵写成 $A=L{L}^{𝖳}$，其中 $L$ 是对角元严格为正的下三角矩阵。复数情形将对称换为厄米、转置换为共轭转置。它把一个正定线性方程组拆成两次三角求解，也给出二次型是平方和的表示。

考虑教学矩阵 $$A=\left(\begin{array}{ccc}4& 2& 2\\ 2& 5& -1\\ 2& -1& 3\end{array}\right).$$ 要找下三角 $L$，不需要猜九个元素；上三角的三个位置已经固定为零，剩下六个数可按列依次确定。

从矩阵乘积读出递推式

写 $L=({\ell }_{ij})$，约定 ${\ell }_{ij}=0$ 当 $i<j$。乘积的第 $(i,j)$ 项为 $$a_{ij}=\sum _{k=1}^{min(i,j)}{\ell }_{ik}{\ell }_{jk}.$$ 第 $j$ 列之前的列已知时，对角等式决定 $${\ell }_{jj}=\sqrt{a_{jj}-\sum _{k<j}{\ell }_{jk}^2},$$ 选择正平方根；该列下面的元素则由 $${\ell }_{ij}=\frac{a_{ij}-\sum _{k<j}{\ell }_{ik}{\ell }_{jk}}{{\ell }_{jj}}(i>j)$$ 确定。分子减去前面各列已贡献的部分，余下的乘积只有 ${\ell }_{ij}{\ell }_{jj}$，因此这一步可以除以已经得到的正对角元。

原例第一列是 ${\ell }_{11}=2$、${\ell }_{21}={\ell }_{31}=1$。第二列先取 ${\ell }_{22}=\sqrt{5-1}=2$，再取 ${\ell }_{32}=(-1-1)/2=-1$。最后 ${\ell }_{33}=\sqrt{3-1-1}=1$，所以 $$L=\left(\begin{array}{ccc}2& 0& 0\\ 1& 2& 0\\ 1& -1& 1\end{array}\right).$$ 核验非对角元时，第二行与第三行的内积为 $1\cdot 1+2\cdot (-1)=-1$，恰与 $a_{23}$ 相同；不能把负的非对角元误当成非正定的证据。

每列先求正对角元，再向下更新；不同颜色对应不同的已知列。

正定性保证递推不会中断

定理　每个实对称正定矩阵都有唯一的、对角元为正的科列斯基分解。

先证明存在。对阶数归纳，一阶情形为正数开平方。高阶时把矩阵分块为 $$A=\left(\begin{array}{cc}a& w^{𝖳}\\ w& B\end{array}\right),a>0.$$ 第一列必须为 $(\sqrt{a},w/\sqrt{a}{)}^{𝖳}$。扣掉它对右下块的贡献，剩下 $S=B-w{w}^{𝖳}/a$。对任意非零向量 $z$，取 $x=(-w^{𝖳}z/a,z{)}^{𝖳}$，直接展开得到 $$z^{𝖳}Sz=x^{𝖳}Ax>0.$$ 故 $S$ 仍正定。按归纳假设 $S=M{M}^{𝖳}$，于是 $$L=\left(\begin{array}{cc}\sqrt{a}& 0\\ w/\sqrt{a}& M\end{array}\right)$$ 满足 $L{L}^{𝖳}=A$。这也说明每一步的剩余对角量都严格为正。至于唯一性，第一列由 $a,w$ 和正平方根唯一确定，剩余分解又由同一归纳过程唯一确定，故全部列唯一。

反向若 $A=L{L}^{𝖳}$ 且 $L$ 的对角元非零，则对非零 $x$，$L^{𝖳}x\ne 0$，因此 $x^{𝖳}Ax=\Vert L^{𝖳}x{\Vert }_2^2>0$。这证明了分解条件与正定性的对应，而不只是递推公式恰好能运行。

三角求解与平方和

求 $Ax=b$ 时先解 $Ly=b$，再解 $L^{𝖳}x=y$。原例取 $b=(6,-5,9{)}^{𝖳}$，前代依次得到 $y_1=3$、$y_2=(-5-3)/2=-4$、$y_3=9-3-4=2$。回代得到 $x_3=2$、$x_2=(-4+2)/2=-1$、$x_1=(3+1-2)/2=1$。代回原式即为 $A(1,-1,2{)}^{𝖳}=(6,-5,9{)}^{𝖳}$。

同一分解还给出 $$x^{𝖳}Ax=(2x_1+x_2+x_3{)}^2+(2x_2-x_3{)}^2+x_3^2.$$ 三个平方同时为零时，先由最后一项得到 $x_3=0$，再依次得到 $x_2=x_1=0$，与正定性吻合。

作为变式，把 $a_{33}$ 从三改为二，最后一个对角量成为零。新矩阵只有半正定，递推的正对角约定不再适用；向量 $(-3,2,4{)}^{𝖳}$ 使上述前两个平方均为零，新二次型等于零。半正定情形可以有零对角因子，但须另行处理零主元，不能在下一步继续除以零。

可运行的实数实现

下面接受有限实数构成的方阵，要求转换为浮点数后严格对称，返回新的下三角列表，不改写输入；发现非正主元就报错。空矩阵返回空列表。它对应上面的数学递推，未实现针对病态数据的误差认证。

Python 3

from math import isfinite, sqrt

def cholesky(source):
    a = [list(map(float, row)) for row in source]
    n = len(a)
    if any(len(row) != n for row in a):
        raise ValueError("matrix must be square")
    if any(not isfinite(x) for row in a for x in row):
        raise ValueError("entries must be finite")
    if any(a[i][j] != a[j][i] for i in range(n) for j in range(i)):
        raise ValueError("matrix must be symmetric")
    lower = [[0.0] * n for _ in range(n)]
    for j in range(n):
        pivot = a[j][j] - sum(lower[j][k] ** 2 for k in range(j))
        if pivot <= 0:
            raise ValueError("nonpositive pivot")
        lower[j][j] = sqrt(pivot)
        for i in range(j + 1, n):
            residual = a[i][j] - sum(lower[i][k] * lower[j][k]
                                     for k in range(j))
            lower[i][j] = residual / lower[j][j]
    return lower

a = [[4, 2, 2], [2, 5, -1], [2, -1, 3]]
assert cholesky(a) == [[2.0, 0.0, 0.0], [1.0, 2.0, 0.0], [1.0, -1.0, 1.0]]
assert cholesky([]) == []
for bad in ([[1, 1], [1, 1]], [[1, 2], [2, 1]], [[1, 0], [1, 1]]):
    try:
        cholesky(bad)
    except ValueError:
        pass
    else:
        raise AssertionError("invalid input accepted")
print("all checks passed")

每轮正确得到第 $j$ 列，因为所有求和只使用已经确定的列；存在性证明保证精确算术下的正定输入不会遇到非正主元。三重求和总计 $O(n^3)$ 时间，输出与副本需 $O(n^2)$ 空间；分解完成后，每次三角求解为 $O(n^2)$。浮点消去可能使很小的正主元被舍入为非正，因此程序报错不是关于原始精确数据的独立正定性证明；实际库会结合误差分析与数据尺度使用该算法。