用「Schur补」理解「Cholesky分解」

Lingfeng2024-04-14

用「Schur补」理解「Cholesky分解」

1. Schur 补

1.1 定义

设 $M$ 为 $n\times n$ 的矩阵, 可分块为

M=\begin{pmatrix} A & B \\ C & D \end{pmatrix}

其中

A

为

k\times k

的矩阵,

D

为

(n-k)\times(n-k)

的矩阵.

假设 $A$ 是可逆的, 则 $M$ 相对于 $A$ 的 Schur 补定义为

S=D-CA^{-1}B

同理, 如果

D

是可逆的, 则

M

相对于

D

的 Schur 补为

S'=A-BD^{-1}C

1.2 性质

我们注意到, 设

L=\begin{pmatrix} I_{k} & -A^{-1}B \\ O & I_{n-k} \end{pmatrix}

此时

ML=\begin{pmatrix} A & B \\ C & D \end{pmatrix}\begin{pmatrix} I_{k} & -A^{-1}B \\ O & I_{n-k} \end{pmatrix}=\begin{pmatrix} A & O \\ C & D-CA^{-1}B \end{pmatrix} = \begin{pmatrix} A & O \\ C & S \end{pmatrix}

故显然 Schur 补有以下性质

\det(M)=\det(A)\cdot \det(S)

同理也有

\det(M)=\det(D)\cdot \det(S')

因此我们可以还得到推论: 如果已知

A

可逆, 则

M

可逆性与

A

的 Schur 补的可逆性相同.

同时, 如果 $M$ 也正定, 则容易证明 $M$ 关于任何一个主子块的 Schur 补也正定.

这是因为我们设

\begin{align*} M&=\begin{pmatrix} A & B \\ B^{T} & C \end{pmatrix} \\ P &= \begin{pmatrix} I_{k} & -A^{-1}B \\ O & I_{n-k} \end{pmatrix} \end{align*}

此时

\begin{align*} P^{T}MP&=\begin{pmatrix} I_{k} & O \\ -B^{T}A^{-1} & I_{n-k} \end{pmatrix}\begin{pmatrix} A & B \\ B^{T} & C \end{pmatrix}\begin{pmatrix} I_{k} & -A^{-1}B \\ O & I_{n-k} \end{pmatrix} \\ &=\begin{pmatrix} A & O \\ O & C-B^{T}A^{-1}B \end{pmatrix} \\ &=\begin{pmatrix} A & O \\ O & S \end{pmatrix} \end{align*} \tag{1}

因此

M

与

\begin{pmatrix} A & O \\ O & S\end{pmatrix}

合同, 因此

\begin{pmatrix} A & O \\ O & S\end{pmatrix}

也正定, 故不难得出

A

和

S

也正定. 故证毕(值得一提的是, 这里我们顺便证明了正定矩阵所有顺序主子式大于 0).

根据 $(1)$ , 我们还得到了一个重要的性质, 即当 $M$ 为对称矩阵时, $M$ 任一主子块与其 Schur 补组成的对角块矩阵与 $M$ 合同. 这便是我们理解 Cholesky 分解的关键.

Cholesky 分解本质上可以视为一种通过逐步“挖孔”并利用 Schur 补来简化问题的策略. 在每一步分解中, 选取矩阵的一个元素(如矩阵的首元素 $a_{11}$ )和相关行列(如对应的向量 $\boldsymbol{\alpha}^{T}$ 和 $\boldsymbol{\alpha}$ ), 相当于在矩阵中移除这一部分, 此时剩余部分正好构成首元素 $a_{11}$ 的 Schur 补. 而根据 Schur 补正交延续的性质, 便自然地变成了一种逐步递推关系.

用「Schur补」理解「Cholesky分解」

用「Schur补」理解「Cholesky分解」

1. Schur 补

1.1 定义

1.2 性质

2. Cholesky 分解

2.1 定义

2.2 证明

3. 总结

ON THIS PAGE