矩阵分析之 实矩阵分解（3）Cholesky分解

前言

上篇写了LU和PLU分解。对于任意可逆方阵都可以进行LU分解和PLU分解，并且PLU分解的稳定性优于LU分解。本次的Cholesky分解实际上是LU分解的特例。

Cholesky分解（LLT分解）

当方阵 A A A是对称正定矩阵时，可以进行Cholesky分解： A = L L T A=LL^T A=LLT Cholesky分解的结果是唯一的。

证明： A = L ~ U , L ~ 是 单 位 下 三 角 矩 阵 , U 是 上 三 角 矩 阵 U = Λ U ~ U ~ 是 单 位 上 三 角 矩 阵 ， Λ 是 对 角 矩 阵 A = A T A = L ~ Λ U ~ A T = U ~ T Λ L ~ T L ~ Λ U ~ = U ~ T Λ L ~ T L ~ Λ = U ~ T Λ L ~ T U ~ − 1 ( U ~ T ) − 1 L ~ = Λ L ~ T U ~ − 1 Λ − 1 左 边 单 位 下 三 角 矩 阵 ， 右 边 是 上 三 角 矩 阵 两 边 相 等 ， 则 两 边 都 是 单 位 矩 阵 ( U ~ T ) − 1 L ~ = E L ~ = U ~ T A = L ~ Λ L ~ T Λ 可 看 作 一 个 二 次 型 的 标 准 型 矩 阵 由 于 A 正 定 ， Λ 对 角 元 素 大 于 0 ， 将 Λ 分 解 Λ = Λ ~ Λ ~ T = d i a g ( λ 1 , λ 2 , … , λ n ) Λ ~ = d i a g ( λ 1 , λ 2 , … , λ n ) A = L ~ Λ L ~ T = L ~ Λ ~ Λ ~ T L ~ T = L ~ Λ ~ ( L ~ Λ ~ ) T = L L T A=\tilde LU, \\ \tilde L是单位下三角矩阵,U是上三角矩阵\\ U=\Lambda \tilde U \\ \tilde U是单位上三角矩阵，\Lambda是对角矩阵 \\ \quad \\ A=A^T \\ A=\tilde L\Lambda \tilde U \\ A^T = \tilde U^T\Lambda \tilde L^T \\ \tilde L\Lambda \tilde U = \tilde U^T\Lambda \tilde L^T \\ \tilde L\Lambda = \tilde U^T\Lambda \tilde L^T \tilde U^{-1} \\ (\tilde U^T)^{-1}\tilde L =\Lambda \tilde L^T \tilde U^{-1}\Lambda^{-1} \\ \quad \\ 左边单位下三角矩阵，右边是上三角矩阵 \\ 两边相等，则两边都是单位矩阵 \\ \quad \\ (\tilde U^T)^{-1}\tilde L=E \\ \tilde L = \tilde U^T \\ A=\tilde L\Lambda \tilde L^T \\ \quad \\ \Lambda可看作一个二次型的标准型矩阵\\ 由于A正定，\Lambda对角元素大于0，将\Lambda分解 \\ \quad \\ \Lambda = \tilde \Lambda \tilde \Lambda^T=diag(\lambda_1,\lambda_2,\dots,\lambda_n) \\ \tilde \Lambda = diag(\sqrt \lambda_1,\sqrt \lambda_2,\dots,\sqrt \lambda_n) \\ A=\tilde L\Lambda \tilde L^T=\tilde L\tilde \Lambda \tilde \Lambda^T \tilde L^T=\tilde L\tilde \Lambda(\tilde L\tilde \Lambda)^T=LL^T \\ A=L~U,L~是单位下三角矩阵,U是上三角矩阵U=ΛU~U~是单位上三角矩阵，Λ是对角矩阵A=ATA=L~ΛU~AT=U~TΛL~TL~ΛU~=U~TΛL~TL~Λ=U~TΛL~TU~−1(U~T)−1L~=ΛL~TU~−1Λ−1左边单位下三角矩阵，右边是上三角矩阵两边相等，则两边都是单位矩阵(U~T)−1L~=EL~=U~TA=L~ΛL~TΛ可看作一个二次型的标准型矩阵由于A正定，Λ对角元素大于0，将Λ分解Λ=Λ~Λ~T=diag(λ1​,λ2​,…,λn​)Λ~=diag(λ ​1​,λ ​2​,…,λ ​n​)A=L~ΛL~T=L~Λ~Λ~TL~T=L~Λ~(L~Λ~)T=LLT 因为LU矩阵分解获得的单位下三角矩阵是唯一的，因此 L ~ , Λ , U ~ \tilde L,\Lambda,\tilde U L~,Λ,U~是唯一的，则Cholesky分解得到的 L L L也是唯一的。

Cholesky分解同PLU分解稳定性相似，比LU分解稳定，计算速度快于LU和PLU分解。

改进的Cholesky分解（LDLT分解）

从上面的证明中可以看出，如果矩阵 A A A不是正定的，则 Λ \Lambda Λ并不能进行Cholesky分解。

如果 A A A是可逆对称矩阵，那么可以进行LDLT分解： A = L D L T A=LDL^T A=LDLT LDLT分解的结果也是唯一的，证法与Cholesky的证明类似，在这就不多写了。

可以看出，不把 Λ \Lambda Λ分解时的Cholesky分解形式和LDLT分解是一样的，因此LDLT实际上就是去除了开方操作的Cholesky算法。

LDLT算法的计算复杂度和稳定性与Cholesky算法相同。