Cholesky分解

学习笔记

---

Cholesky分解
Cholesky分解目标是将正定厄密特阵A分解为:

$$A = LL^T$$

推导过程
因为A是对称阵，所以设A为:

$$A = \begin{bmatrix} a_{11} & A^T_{21} \\ A_{21} & A_{22} \end{bmatrix}$$
注意，$A_{21}$是一个列向量，$A_{22}$是一个$n-1$阶方阵

设L:

$$L = \begin{bmatrix} l_{11} & 0 \\ L_{21} & L_{22} \end{bmatrix}$$
有
$$L^T = \begin{bmatrix} l_{11} & L^T_{21} \\ 0 & L_{22} \end{bmatrix}$$
由$A = LL^T$可以得到：
$$\begin{bmatrix} a_{11} & A^T_{21} \\ A_{21} & A_{22} \end{bmatrix} = \begin{bmatrix} l_{11} & 0 \\ L_{21} & L_{22} \end{bmatrix} \begin{bmatrix} l_{11} & L^T_{21} \\ 0 & L^T_{22} \end{bmatrix} \\ = \begin{bmatrix} l^2_{11} & l_{11}L^T_{21} \\ l_{11}L_{21} & L_{21}L^T_{21} + L_{22}L^T_{22} \end{bmatrix}$$
其中需要求解的是$l_{11}, L_{21}, L_{22}$，由上述公式可以得到三个未知量的求解公式为：
$$\begin{align} l_{11} & = \sqrt{a_{11}} \tag 1 \\ L_{21} & = \frac{1}{l_{11}}A_{21} \tag 2 \\ L_{22}L^T_{22} & = A_{22} - L_{21}L^T_{21} \tag 3\\ \end{align}$$

显然，$l_{11}$和$L_{21}$都是易求的。
$l_{11}$显而易见。可以发现，$A_{22}-L_{21}L^T_{21}$也好求，$A_{22}$已知，$L_{21}L^T_{21}$是一个对称矩阵，对角线上的元素都是平方，容易求解。
那么设公式$\ref{3}$中右边为$A'_{22}$。那么，可以得到：

$$A'_{22} = L_{22}L^T_{22}$$
可以发现，这又是一个Cholesky分解，在进行上述推导，最终可以解得矩阵$L$。

参考：
http://www.qiujiawei.com/linear-algebra-11/
http://www.cnblogs.com/vivounicorn/archive/2011/03/22/1991479.html