又到了矩阵分解时间。这次介绍的是Cholesky分解。这个方法只适用于符合厄米特矩阵、正定矩阵定义的矩阵。

算法原理

设A是一个n阶厄米特正定矩阵(Hermitian positive-definite matrix)。

Cholesky分解的目标是把A变成:

\[ A = LL^{T} \]

L是下三角矩阵。

推导过程

因为A是对称的矩阵，所以设A为：

\[ A = \left[ \begin{matrix} a_{11}&A_{21}^{T}\\ A_{21}&A_{22}\\ \end{matrix} \right] \]

(注意：细心观察此式子可以发现\(A_{21}\)是一个列向量，\(A_{22}\)是一个n-1阶的方阵)

设L：

\[ L = \left[ \begin{matrix} l_{11}&0\\ L_{21}&L_{22}\\ \end{matrix} \right] \]

则有:

\[ L^{T} = \left[ \begin{matrix} l_{11}&L_{21}^{T}\\ 0&L_{22}^{T}\\ \end{matrix} \right] \]

设\( A = LL^{T} \)，得到：

\[ \left[ \begin{matrix} a_{11}&A_{21}^{T}\\ A_{21}&A_{22}\\ \end{matrix} \right] = \left[ \begin{matrix} l_{11}&0\\ L_{21}&L_{22}\\ \end{matrix} \right] \left[ \begin{matrix} l_{11}&L_{21}^{T}\\ 0&L_{22}^{T}\\ \end{matrix} \right] \]

\[ = \left[ \begin{matrix} l_{11}^{2}&l_{11}L_{21}^{T}\\ l_{11}L_{21}&L_{21}L_{21}^{T}+L_{22}L_{22}^{T}\\ \end{matrix} \right] \]

其中，未知量是\( l_{11},L_{21},L_{22} \)，这3个未知量的求解公式是：

\[ l_{11} = \sqrt {a_{11}} \]

\[ L_{21} = \frac {1}{l_{11}}A_{21} \]

\[ L_{22}L_{22}^{T} = A_{22} - L_{21}L_{21}^{T} \]

显然，\( l_{11},L_{21} \)是易求的，而\( L_{22} \)的求解救有意思了。

观察可以发现，\( A_{22} - L_{21}L_{21}^{T} \)也很好求，\( A_{22} \)已知，\( L_{21}L_{21}^{T} \)是一个对角线矩阵，对角线上的元素只是一个平方，好求。

那么设\(A_{22}' = A_{22} - L_{21}L_{21}^{T} \)，则剩下的问题就是求:

\[ A_{22}' = L_{22}L_{22}^{T} \]

啊，这不也是Cholesky分解！被分解的矩阵是A的右下角的n-1阶子方阵！

所以这个算法具有递归性质。

附上一个实例：

设:

\[ A = \left[ \begin{matrix} 25&15&-5\\ 15&18&0\\ -5&0&11\\ \end{matrix} \right] = \left[ \begin{matrix} l_{11}&0&0\\ l_{21}&l_{22}&0\\ l_{31}&l_{32}&l_{33}\\ \end{matrix} \right] \left[ \begin{matrix} l_{11}&l_{21}&l_{31}\\ 0&l_{22}&l_{32}\\ 0&0&l_{33}\\ \end{matrix} \right] \]

根据上文的公式，有：

\[ l_{11} = \sqrt { a_{11} } = 5 \] \[ L_{21} = \frac {1}{l_{11}}A_{21} = \frac {1}{5} \left[ \begin{matrix} 15\\ -5\\ \end{matrix} \right] = \left[ \begin{matrix} 3\\ -1\\ \end{matrix} \right] \]

\[ A_{22} - L_{21}L_{21}^{T} = L_{22}L_{22}^{T} \]

\[ A_{22} - L_{21}L_{21}^{T} = L_{22}L_{22}^{T} \]

\[ \left[ \begin{matrix} 18&0\\ 0&11\\ \end{matrix} \right] - \left[ \begin{matrix} 3\\ -1\\ \end{matrix} \right] \left[ \begin{matrix} 3&-1\\ \end{matrix} \right] = \left[ \begin{matrix} l_{22}&0\\ l_{32}&l_{33}\\ \end{matrix} \right] \left[ \begin{matrix} l_{22}&l_{32}\\ 0&l_{33}\\ \end{matrix} \right] \]

\[ \left[ \begin{matrix} 9&3\\ 3&10\\ \end{matrix} \right] = \left[ \begin{matrix} l_{22}&0\\ l_{32}&l_{33}\\ \end{matrix} \right] \left[ \begin{matrix} l_{22}&l_{32}\\ 0&l_{33}\\ \end{matrix} \right] \]

(注意，这里已经是n-1阶的Cholesky分解)

\[ l_{22} = \sqrt { 9 } = 3 \] \[ l_{32} = \frac {1}{3}3 = 1 \] \[ 10 = l_{32}^{2} + l_{33}^{2} = 1 + l_{33}^{2} \] \[ l_{33} = \sqrt {10 - 1} = 3 \]

综上：

\[ A = \left[ \begin{matrix} 25&15&-5\\ 15&18&0\\ -5&0&11\\ \end{matrix} \right] = \left[ \begin{matrix} 5&0&0\\ 3&3&0\\ -1&1&3\\ \end{matrix} \right] \left[ \begin{matrix} 5&3&-1\\ 0&3&1\\ 0&0&3\\ \end{matrix} \right] \]

参考资料

(未经授权禁止转载)