【转载】Cholesky分解及一个例子

原网址：https://blog.csdn.net/qq_41564404/article/details/88085073

文字来源：

1. C.E. Rasmussen & K.I. Williams, Gaissian Processes for Machine Learning,MIT
2. 计算机科学计算，高等教育出版社，张宏伟 等

---

定义： cholesky分解是一种将任意n阶对称正定矩阵A分解成下三角矩阵L的一种方法：

$LL^T = A$

其中，L称为Cholesky因子。如果L的对角元均为正数，则L是唯一确定的。

Cholesky分解对于解决带有对称正定系数矩阵A的线性问题非常有效。在计算机中，直接求解$A\mathbf x=\mathbf b$=b时间复杂度是很高的（Gauss消元法求解是$O(n3)$ ），用cholesky法对A提前变换之后再计算会有效降低复杂度。计算方法如下：

$Ax=b \rightarrow LL^T x =b$

等价于：

$\left\{\begin{array}{l} L y=b \\ L^{T} x=y \end{array}\right.$

令

$\left(\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ a_{21} & a_{22} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n 1} & a_{n 2} & \cdots & a_{n n} \end{array}\right)=\left(\begin{array}{cccc} l_{11} & & & \\ l_{21} & l_{22} & & \\ \vdots & \vdots & \ddots & \\ l_{n 1} & l_{n 2} & \dots & l_{n n} \end{array}\right)\left(\begin{array}{cccc} l_{11} & l_{12} & \cdots & l_{1 n} \\ & l_{22} & \cdots & l_{2 n} \\ & & \ddots & \vdots \\ & & & l_{n n} \end{array}\right)$

则

$a_{i j}=\sum_{k=1}^{j-1} l_{i k} l_{j k}+l_{i j} l_{j j}, \quad i=j, j+1, \cdots, n$

则有

$l_{j j}=\left(a_{j j}-\sum_{k=1}^{j-1} l_{j k}^{2}\right)^{\frac{1}{2}}$

$l_{i j}=\left(a_{i j}-\sum_{k=1}^{j-1} l_{i k} l_{j k}\right) / l_{j j}, \quad i=j+1, j+2, \cdots, n$

计算次序为$l_{11},l_{21},\dots,l_{n1},l_{22},l_{32},\dots,l_{n2},\dots,l_{nn}$

注意，正定对称矩阵的行列式可以由下式得出：

$|A|= \prod_{i=1}^nL_{ii}^2$

或者

$log|A| = 2\sum_{i=1}^nlogL_{ii}$

其中，$L$是由A得出的$Cholesky$因子。