11. Cholesky分解

数值分析



周维祺

实对称矩阵:A=ATA=A^T

ATA^T是AA的转置

实对称矩阵的元素关于主对角线对称，例：

(123214341)\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 4 \\ 3 & 4 & 1 \end{pmatrix}

LDLLDL分解

  • 若AA可逆，作AA的三角分解A=LUA=LU，其中LL的主对角线元素都是11

  • 上式可进一步写作A=LDVA=LDV，其中DD是对角阵，VV是主对角线元素都为11的上三角阵

  • 若AA实对称，则有A=AT=VTDLTA=A^T=V^TDL^T，其中VTV^T是主对角线元素都为11的下三角阵，DLTDL^T是上三角阵

  • 由三角分解的唯一性得VT=LV^T=L

LDLLDL分解：A=LDLTA=LDL^T

其中AA实对称、可逆，LL是主对角线元素都为11的下三角阵，DD是对角阵

练习

求(11010−10−10)\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & -1 \\ 0 & -1 & 0 \end{pmatrix}的LDLLDL分解

Rn\mathbb R^n上的内积

  • x⃗=(x1,…,xn)∈Rn\vec x=(x_1,\ldots,x_n)\in\mathbb R^n，y⃗=(y1,…,yn)∈Rn\vec y=(y_1,\ldots,y_n)\in\mathbb R^n

  • 内积：Rn×Rn→R\mathbb R^n\times\mathbb R^n\to\mathbb R，(x⃗,y⃗)=x1y1+…+xnyn(\vec x,\vec y)=x_1y_1+\ldots+x_ny_n

  • 也记作x⃗⋅y⃗\vec x\cdot \vec y, ⟨x⃗,y⃗⟩\langle\vec x,\vec y\rangle

练习

  • 给定 A=(a11a12a13a21a22a23a31a32a33)A=\begin{pmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{pmatrix}，x⃗=(x1x2x3)\vec x=\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}, y⃗=(y1y2y3)\vec y=\begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix}

  • 计算y⃗TAx⃗\vec y^TA\vec x

  • 计算(Ax⃗,y⃗)(A\vec x,\vec y)和(x⃗,ATy⃗)(\vec x,A^T\vec y)

一般地，有

y⃗TAx⃗=(Ax⃗,y⃗)=(x⃗,ATy⃗)=∑i,j=1nAijyixj\vec y^TA\vec x=(A\vec x,\vec y)=(\vec x,A^T\vec y)=\sum_{i,j=1}^nA_{ij}y_ix_j

正定矩阵

称n×nn\times n矩阵AA正定，若对任意nn维向量x⃗\vec x都有

(Ax⃗,x⃗)≥0,(A\vec x,\vec x)\ge0,

且等号仅在x⃗=0\vec x=0时成立

练习

证明正定矩阵是可逆矩阵

练习

设DD是实对角阵，且正定，证明DD主对角线上每个元素都大于00

Cholesky分解

  • 设AA实对称且正定，则有LDLLDL分解: A=LDLTA=LDL^T

  • 对任意非零向量x⃗\vec x，有(DLTx⃗,LTx⃗)=(LDLTx⃗,x⃗)>0(DL^T\vec x,L^T\vec x)=(LDL^T\vec x,\vec x)>0
    (思考：为什么)

  • ⇒D\Rightarrow D正定 (思考：为什么)

Cholesky分解

  • DD中每个元素都非负，记D\sqrt D为将DD中每个元素开平方根所得的矩阵

  • DD对角阵⇒\Rightarrow D=DDD=\sqrt D\sqrt D，且(D)T=D(\sqrt D)^T=\sqrt D

  • A=LDLT=LD⏟L′DLT⏟(L′)TA=LDL^T=\underbrace{L\sqrt{D}}_{L'}\underbrace{\sqrt{D}L^T}_{(L')^T}

Cholesky分解: A=LLTA=LL^T

AA实对称正定

练习

求(110132025)\begin{pmatrix} 1 & 1 & 0 \\ 1 & 3 & 2 \\ 0 & 2 & 5 \end{pmatrix}的Cholesky分解

小结

  • 对称矩阵的LDLLDL分解

  • 内积(Ax,y)(Ax,y)的几种公式

  • 正定矩阵及其相关性质

  • 实对称正定矩阵的Cholesky分解