Cholesky Decomposition

原版文章请点击 Cholesky Decomposition

三角矩阵

三角矩阵首先是方阵，其次，如果这个方阵对角线上面或下面（不含对角线）的元素都为0的话，那么这个矩阵就被称为三角矩阵。如果是上面的元素都为0，则称之为下三角矩阵，反之则是上三角矩阵。

上 三 角 矩 阵 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ a 11 00 . . . 0 a 12 a 22 0 . . . 0 . . . . . . . . . . . . 0.. a 1 n a 2 n a 3 n . . . . a n n ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

下 三 角 矩 阵 ⎡ ⎣ ⎢ ⎢ ⎢ ⎢ ⎢ a 11 a 21 a 31 . . . a n 1 0 a 22 a 32 . . . a n 2 . . . 0.. . . . . . . . . . 000 . . . a n n ⎤ ⎦ ⎥ ⎥ ⎥ ⎥ ⎥

三角矩阵有一个非常好的性质，那就是在作为一个方程组的参数时，那么可以快速地解这个方程组，假设矩阵A是一个下三角矩阵，那么方程组 Ax=b ，可以很快地解出，解普通方程组节省很多时间，这个方程组的解具有如下形式

x 1 x 2 x 3 . . . x n = = = = b 1 a 11 b 2 - a 21 x 1 a 22 b 3 - a 31 x 1 - a 32 x 2 a 33 b n - \sum n - 1 i = 1 a n i x i a n n

Cholesky Descomposition

由于三角矩阵具有非常好的性质，因此我们在计算时，我们可以把一个矩阵分解成两个三角矩阵乘积的形式，从而可以利用三角矩阵的优点，但并不是任何矩阵都可以转化成三角矩阵形式的。在实数域，只有正定矩阵（positive defined matrix）才满足条件。假设矩阵A是堆成的正定矩阵，把A分解成如下形式就是Cholesky Decomposition,其中U为上三角矩阵，L为下三角矩阵。

A A = = U T U L L T

正定矩阵

首先我们需要知道什么是正定矩阵。首先正定矩阵是对称的，对称很容易理解，即矩阵A中的所有元素，有 aij=aji ，那么A必然是方阵；此外对于任何非零的向量z，正定矩阵A满足 zTAz>0 。正定矩阵还有如下性质：

正定矩阵是非奇异矩阵。假设A为正定矩阵，对于任意非零向量x，满足 $x T A x > 0$ 那么我们可以得到 $A x \neq 0$ 所以正定矩阵是非奇异矩阵。
对角线上的所有元素都是正的。令 ei 表示第i个元素为1，其余为0的单位向量，那么 $a i i = e T i A e i > 0$
正定矩阵的Schur补也是正定矩阵。对于正定矩阵 $A n = [a 11 a n 1 a T n 1 A n - 1]$ 其中 a11 为实数， an1 为向量， An−1 为方阵。 An 的Schur补为 $S = A n - 1 - 1 a 11 a n 1 a T n 1$ 令w为实数，v为长度为n-1的任意向量，由于 An 为正定矩阵，因此我们有 $[w, v T] A n [w, v T] T w 2 a 11 + w v T a n 1 + w a T n 1 v + v T A n - 1 v > > 00$ 要证明S为正定矩阵，只需要证明对于任意非零向量v， vTSv>0 即可，也就要证明 $v T A n - 1 v - 1 a 11 v T a n 1 a T n 1 v > 0$ 观察上面两个不等式发现，只需要令 $w 2 a 11 + w v T a n 1 + w a T n 1 v + v T A n - 1 v w 2 a 11 + 2 w v T a n 1 + 1 a 11 (v T a n 1) 2 w 2 + 2 v T a n 1 a 11 w + (( v T a n 1 ) a 11) 2 (w + v T a n 1 a 11) 2 w = = = = = v T A n - 1 v - 1 a 11 v T a n 1 a T n 1 v 000 - 1 a 11 v T a n 1$ 所以对任意的非零向量v，我们可以令 w=−1a11vTan1 ，根据 An 的性质，我们可以证明 vTSv>0 。因此，正定矩阵的Schur补也是正定矩阵。

为什么正定矩阵可以分成三角矩阵的乘积？

假设正定矩阵可以分解为两个三角矩阵的乘积。不妨令 An=LnLTn ，同时分别将 An 和 Ln 写作

A n L n = = [a 11 a n 1 a T n 1 A n - 1] [l 11 l n 1 0 L n - 1]

如果我们能证明下面的等式成立，那么我们就证明了正定矩阵可以分成了两个三角矩阵的乘积。

A n [a 11 a n 1 a T n 1 A n - 1] = = L n L T n [l 11 l n 1 0 L n - 1] [l 11 0 l T n 1 L T n - 1] = [l 211 l 11 l n 1 l 11 l T n 1 l n 1 l T n 1 + L n - 1 L T n - 1]

由于 An 是正定矩阵，而正定矩阵对角线上的元素都为正，因而 a11>0 ，所以我们得到

l 11 = a 11 - - - \sqrt

因为 an1=l11ln1 ，所以我们可以得到

l n 1 = 1 a 11 - - - \sqrt a n 1

至此，我们只需要证明 An−1=ln1lTn1+Ln−1LTn−1 ，既可以证明正定矩阵可以分解成三角矩阵的乘积，也就是证明

A n - 1 - l n 1 l T n 1 A n - 1 - 1 a 11 = = L n - 1 L T n - 1 L n - 1 L T n - 1

观察上面的等式，我们发现，只需要证明 An−1−1a11 是正定矩阵就可以了。而这个表达式恰好是矩阵 An 的Schur补，根据正定矩阵的性质，我们知道这个表达式也是正定矩阵。接着我们采用归纳证明，假设维度为n-1的正定矩阵可以分解成下三角矩阵和上三角矩阵的乘积，那么根据上面的分析，我们知道维度为n的正定矩阵也可以分解成下三角矩阵和上三角矩阵的乘积；当n=1时，显然可以分解成三角矩阵的乘积。因此我们证明了 An−1=ln1lTn1+Ln−1LTn−1 ，从而也就证明了Cholesky Decomposition。