Cholesky分解、乔列斯基分解-Toy模板网

这篇具有很好参考价值的文章主要介绍了Cholesky分解、乔列斯基分解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、简介

1.1 定理

Cholesky分解法 又叫 平方根法，是一种分解 正定Hermite矩阵 (即 $\boldsymbol A = \boldsymbol A^\mathrm H$ ) 的方法，以下我用实数域 (即对称正定阵 $\boldsymbol A = \boldsymbol A^\mathrm T$ ) 来说明。

定理：若矩阵 $\boldsymbol A \in \mathbb R^{n\times n}$ 正定，且 $\boldsymbol A=\boldsymbol A^{\mathrm T}$ ，则存在唯一下三角矩阵 $\boldsymbol L \in \mathbb R^{n\times n}$ ，使得：
$\boldsymbol A = \boldsymbol L\boldsymbol L^{\mathrm T}$

证明：（暂略，有时间补）

1.2 分解方法

记:
$\boldsymbol A= \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \\ \end{pmatrix} \\ ~ \\ \boldsymbol L= \begin{pmatrix} l_{11} & \\ l_{21} & l_{22} \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \dots & l_{nn} \\ \end{pmatrix} ~~ \boldsymbol L^\mathrm T= \begin{pmatrix} l_{11} & l_{21} & \dots & l_{n1} \\ & l_{22} & \dots & l_{n2} \\ & & \ddots & \vdots \\ & & & l_{nn} \\ \end{pmatrix}$

那么：
$\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \\ \end{pmatrix}= \begin{pmatrix} l_{11} & \\ l_{21} & l_{22} \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \dots & l_{nn} \\ \end{pmatrix} \begin{pmatrix} l_{11} & l_{21} & \dots & l_{n1} \\ & l_{22} & \dots & l_{n2} \\ & & \ddots & \vdots \\ & & & l_{nn} \\ \end{pmatrix} \\ ~ \\ =\begin{pmatrix} l_{11}^2 & \dots & \dots & \dots & \dots \\ l_{11}l_{21} & l_{21}^2+l_{22}^2 & \dots & \dots & \dots \\ l_{11}l_{31} & l_{31}l_{21}+l_{32}l_{22} & l_{31}^2+l_{32}^2+l_{33}^2 & \dots & \dots \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ l_{11}l_{n1} & l_{n1}l_{21}+l_{n2}l_{22} & l_{n1}l_{31}+l_{n2}l_{32}+l_{n3}l_{33} & \dots & \displaystyle\sum_{i=1}^nl_{ni}^2 \\ \end{pmatrix}$

由于 $\boldsymbol A$ 是对称矩阵，所以我们只看下三角：
$\begin{pmatrix} \textcolor{#FF0000}{a_{11}} \\ \textcolor{#FF0000}{a_{21}} & \textcolor{#DFCC00}{a_{22}} \\ \textcolor{#FF0000}{a_{31}} & \textcolor{#DFCC00}{a_{32}} & \textcolor{#00CC00}{a_{33}} \\ \textcolor{#FF0000}{\vdots} & \textcolor{#DFCC00}{\vdots} & \textcolor{#00CC00}{\vdots} & \textcolor{#0099FF}{\ddots} \\ \textcolor{#FF0000}{a_{n1}} & \textcolor{#DFCC00}{a_{n2}} & \textcolor{#00CC00}{a_{n3}} & \textcolor{#0099FF}{\dots} & \textcolor{#BB00FF}{a_{nn}} \\ \end{pmatrix}= \begin{pmatrix} \textcolor{#FF0000}{l_{11}^2} \\ \textcolor{#FF0000}{l_{11}l_{21}} & \textcolor{#DFCC00}{l_{21}^2+l_{22}^2} \\ \textcolor{#FF0000}{l_{11}l_{31}} & \textcolor{#DFCC00}{l_{31}l_{21}+l_{32}l_{22}} & \textcolor{#00CC00}{l_{31}^2+l_{32}^2+l_{33}^2} \\ \textcolor{#FF0000}{\vdots} & \textcolor{#DFCC00}{\vdots} & \textcolor{#00CC00}{\vdots} & \textcolor{#0099FF}{\ddots} \\ \textcolor{#FF0000}{l_{11}l_{n1}} & \textcolor{#DFCC00}{l_{n1}l_{21}+l_{n2}l_{22}} & \textcolor{#00CC00}{l_{n1}l_{31}+l_{n2}l_{32}+l_{n3}l_{33}} & \textcolor{#0099FF}{\dots} & \textcolor{#BB00FF}{\displaystyle\sum_{i=1}^nl_{ni}^2} \\ \end{pmatrix}$

按照从左到右 (红黄绿蓝紫) 的顺序，逐列对应元素计算，便可将所有 $\boldsymbol L$ 的元素 $l_{ij}$ 求出来

二、应用

2.1 线性方程求解

对于线性方程组 $\boldsymbol A\boldsymbol X=\boldsymbol B$ ，其中 $\boldsymbol A \in \mathbb R^{n\times n}$ 正定，且 $\boldsymbol A=\boldsymbol A^{\mathrm T}$ ，那么求解方程可以使用 Cholesky分解：

对矩阵 $\boldsymbol A$ 进行 Cholesky分解得， $\boldsymbol A = \boldsymbol L\boldsymbol L^{\mathrm T}$ ，则原方程化为 $\boldsymbol L\boldsymbol L^{\mathrm T}\boldsymbol X=\boldsymbol B$
令 $\boldsymbol L^{\mathrm T}\boldsymbol X=\boldsymbol Y$ ，此时，解下三角方程 $\boldsymbol L\boldsymbol Y=\boldsymbol B$ ，求得 $\boldsymbol Y$
解上三角方程 $\boldsymbol L^{\mathrm T}\boldsymbol X=\boldsymbol Y$ ，求得 $\boldsymbol X$

通过 Cholesky分解将普通线性方程求解改为两次简单的三角阵方程组求解，降低计算复杂度。

2.2 求逆矩阵

三角矩阵的逆比较好求，从而可以很快求出原矩阵的逆。

三、扩展Cholesky分解

3.1 简介

从 1.2 节可以知道，矩阵 $\boldsymbol L$ 对角线上的元素在计算时，都需要开方操作，增加计算量的同时还可能损失精度。引进一种 Cholesky的扩展分解方法：
$\boldsymbol A = \boldsymbol L\boldsymbol D\boldsymbol L^{\mathrm T}$

证明：
我们已知，正定对称阵 $\boldsymbol A$ 可以分解为： $\boldsymbol A = \boldsymbol L\boldsymbol L^{\mathrm T}$

而 $\boldsymbol L$ 可以写成：

$\begin{aligned} \boldsymbol L &=\begin{pmatrix} l_{11} & \\ l_{21} & l_{22} \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \dots & l_{nn} \\ \end{pmatrix} \\ ~ \\ &=\begin{pmatrix} 1 & \\ l_{21}/l_{11} & 1 \\ \vdots & \vdots & \ddots \\ l_{n1}/l_{11} & l_{n2}/l_{22} & \dots & 1 \\ \end{pmatrix} \begin{pmatrix} l_{11} & \\ & l_{22} \\ & & \ddots \\ & & & l_{nn} \\ \end{pmatrix} \\ ~ \\ &\overset{\mathrm{def}}{=}\boldsymbol L_1 \boldsymbol \Lambda \end{aligned}$

同理 $\boldsymbol L^\mathrm T = \boldsymbol \Lambda\boldsymbol L_1^\mathrm T$

那么 $\boldsymbol A = \boldsymbol L\boldsymbol L^{\mathrm T}=\boldsymbol L_1\boldsymbol \Lambda^2\boldsymbol L_1^{\mathrm T} = \boldsymbol L_1\boldsymbol D\boldsymbol L_1^{\mathrm T}$

3.2 分解方法

记:
$\boldsymbol A= \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \\ \end{pmatrix} \\ ~ \\ \boldsymbol L= \begin{pmatrix} 1 & \\ l_{21} & 1 \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \dots & 1 \\ \end{pmatrix} ~~ \boldsymbol L^\mathrm T= \begin{pmatrix} 1 & l_{21} & \dots & l_{n1} \\ & 1 & \dots & l_{n2} \\ & & \ddots & \vdots \\ & & & 1 \\ \end{pmatrix} ~~ \boldsymbol D= \begin{pmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & d_n \\ \end{pmatrix}$

那么：
$\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \dots & a_{nn} \\ \end{pmatrix}= \begin{pmatrix} 1 & \\ l_{21} & 1 \\ \vdots & \vdots & \ddots \\ l_{n1} & l_{n2} & \dots & 1 \\ \end{pmatrix} \begin{pmatrix} d_1 & & & \\ & d_2 & & \\ & & \ddots & \\ & & & d_n \\ \end{pmatrix} \begin{pmatrix} 1 & l_{21} & \dots & l_{n1} \\ & 1 & \dots & l_{n2} \\ & & \ddots & \vdots \\ & & & 1 \\ \end{pmatrix} \\ ~ \\ =\begin{pmatrix} d_1 & \dots & \dots & \dots & \dots \\ d_1l_{21} & d_1l_{21}^2+d_2 & \dots & \dots & \dots \\ d_1l_{31} & d_1l_{31}l_{21}+l_{32}l_{22} & d_1l_{31}^2+d_2l_{32}^2+d_3 & \dots & \dots \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ d_1l_{n1} & d_1l_{n1}l_{21}+d_2l_{n2} & d_1l_{n1}l_{31}+d_2l_{n2}l_{32}+d_3l_{n3} & \dots & \displaystyle d_n+\sum_{i=1}^{n-1}d_il_{ni}^2 \\ \end{pmatrix}$