正定矩阵的Cholesky分解
2012-06-22 13:39阅读：
1、为什么要进行矩阵分解
个人认为，首先，当数据量很大时，将一个矩阵分解为若干个矩阵的乘积可以大大降低存储空间；其次，可以减少真正进行问题处理时的计算量，毕竟算法扫描的元素越少完成任务的速度越快，这个时候矩阵的分解是对数据的一个预处理；再次，矩阵分解可以高效和有效的解决某些问题；最后，矩阵分解可以提高算法数值稳定性，关于这一点可以有进一步的说明，
借用一个上学时老师给的例子：
有方程组：
![\begin{equation}
\begin{cases}
5x_1+7x_2=0.7\\
7x_1+10x_2=1
\end{cases}
\end{equation}]( "正定矩阵的Cholesky分解")
令
![A=
\begin{pmatrix}
5 & 7 \\
7 & 10
\end{pmatrix}]( "正定矩阵的Cholesky分解")
，
![x=
\begin{pmatrix}
x_1 \\
x_2
\end{pmatrix}]( "正定矩阵的Cholesky分解")
，
![b=
\begin{pmatrix}
0.7\\
1
\end{pmatrix}]( "正定矩阵的Cholesky分解")
解方程组可得：
![x=
\begin{pmatrix}
0.0 \\
0.1
\end{pmatrix}]( "正定矩阵的Cholesky分解")
现在对b进行微小扰动：
![b=
\begin{pmatrix}
0.69 \\
1.01
\end{pmatrix}]( "正定矩阵的Cholesky分解")
，扰动项为：
![\begin{pmatrix}
-0.01 \\
0.01
\end{pmatrix}]( "正定矩阵的Cholesky分解")
此时相应的解为：
![x=
\begin{pmatrix}
-0.17 \\
0.22
\end{pmatrix}]( "正定矩阵的Cholesky分解")
。
这个例子说明，当方程组常数项发生微小变动的时候会导致求出的结果差别相当大，而导致这种差别的并不是求解方法，而是方程组系数矩阵本身的问题，这会给我们解决问题带来很大危害，例如，我们在用计算机求解这类问题时难以避免在计算当中出现舍入误差，如果矩阵本身性质不好会直接导致所答非所问。
对常数向量b和矩阵A进行一个简单的扰动分析：
1)、扰动b，原方程组为：
(式子1)，（
，A非奇异）
扰动后为：
=b+/delta+b "正定矩阵的Cholesky分解")
(式子2)
把式子1带入式子2得：
，用2-范式来衡量这种变化得：
，由于
，于是得到：
![\frac{||\delta x||}{||x||}=\frac{||A^{-1}\delta b||}{||x||}\leq \frac{||A^{-1}||||\delta b||}{||x||}]( "正定矩阵的Cholesky分解")
而利用式子1同理可得
![||x||\geq\frac{||b||}{||A||}]( "正定矩阵的Cholesky分解")
，整理后得：
![\frac{||\delta x||}{||x||}\leq \frac{||A||\quad ||A^{-1}||\quad ||\delta b||}{||b||}]( "正定矩阵的Cholesky分解")
，可见b的扰动对解的影响由
![||A||\quad ||A^{-1}||]( "正定矩阵的Cholesky分解")
决定。
2)、扰动A，扰动后为：
(x+/delta+x)=b "正定矩阵的Cholesky分解")
(式子3)，（
，A非奇异）
稍微做一下变换：
+/delta+Ax+/delta+A/delta+x=b "正定矩阵的Cholesky分解")
把式子1带入后得到：
![\delta x=A^{-1}(-\delta Ax-\delta A\delta x)]( "正定矩阵的Cholesky分解")
对两边同时取2-范式有：
![||\delta x||=||A^{-1}(-\delta Ax-\delta A\delta x)|| \leq ||A^{-1}||\quad ||\delta Ax|| \quad ||\delta A|| \quad ||\delta x||]( "正定矩阵的Cholesky分解")
于是有：
![||\delta x||=||A^{-1}(-\delta Ax-\delta A\delta x)|| \leq ||A^{-1}||\quad ||\delta A||\quad||x|| \quad ||\delta A|| \quad ||\delta x||]( "正定矩阵的Cholesky分解")
，整理一下就是：
![\frac{||\delta x||}{||x||}\leq \frac{||A^{-1}|| \quad ||A||\frac{||\delta A||}{||A||}}{1-||A^{-1}|| \quad ||A||\frac{||\delta A||}{||A||}}]( "正定矩阵的Cholesky分解")
，A的扰动对解的影响依然是由
![||A||\quad ||A^{-1}||]( "正定矩阵的Cholesky分解")
决定。
3)、对于同时扰动A和b的情况偶就不推了，最后的结果依然是，扰动对解的影响依然由
![||A||\quad ||A^{-1}||]( "正定矩阵的Cholesky分解")
决定。
定义矩阵的条件数
![cond(A)=||A||||A^{-1}||]( "正定矩阵的Cholesky分解")
来描述矩阵的病态程度，一般认为条件数小于100为良态，条件数在100到1000之间为中等程度的病态，条件数超过1000存在严重病态。以上面的矩阵A为例，采用
2-范数表示的条件数为：
=222.9955 "正定矩阵的Cholesky分解")
，看来矩阵处于中等病态程度。
矩阵其实就是一个给定的线性变换，特征向量描述了这个线性变换的主要方向，而特征值描述了一个特征向量的长度在该线性变换下缩放的比例，有关特征值和特征向量的相关概念可查看
http://en.wikipedia.org/wiki/Eigenvalues_and_eigenvectors，对开篇的例子进一步观察发现，A是个对称正定矩阵，A的特征值分别为
：14.93303437 和
：0.06696563，两个特征值在数量级上相差很大，这意味着b发生扰动时，向量x在这两个特征向量方向上的移动距离是相差很大的——对于
对应的特征向量只需要微小的移动就可到达b的新值，而对于
，由于它比起
太小了，因此需要x做大幅度移动才能到达b的新值，于是悲剧就发生了……………..。
关于矩阵可以有以下各种分解方式，①矩阵的三角分解（Cholesky分解、LU分解等），②矩阵的正交三角分解(QR分解等)，③矩阵的满秩分解，④矩阵的奇异值分解(SVD)(关于SVD可以查看高人
LeftNotEasy的
http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html#2038925一文以及他提供的参考资料)。
再看矩阵A，它是个对称正定矩阵，对这种矩阵都可以进行Cholesky分解，也就是将矩阵A分解为：
![A=L\quad L^T]( "正定矩阵的Cholesky分解")
，其中
为一个下三角矩阵，具体操作随后讨论，回头看方程组
，它就变成了：
![Ax=L\quad L^T\quad x=b]( "正定矩阵的Cholesky分解")
，
将它看成两个方程组：
和
![L^Tx=y]( "正定矩阵的Cholesky分解")
，其中：
![L=
\begin{pmatrix}
2.236068 & 0.000000\\
3.1304952 & 0.4472136
\end{pmatrix}]( "正定矩阵的Cholesky分解")
，特征值为
：2.2360680和
：0.4472136
此时采用
2-范数表示的条件数为
=5 "正定矩阵的Cholesky分解")
，显然上面这两个方程组也都是良态的且只需要存储矩阵
的下三角部分即可，矩阵分解的优点可见一斑。
2、实正定Hermit矩阵的完全Cholesky分解
设矩阵A有如下形式：
![A=
\begin{pmatrix}
a_{1,1} & b_1^*\\
b_1&B^1\\
\end{pmatrix}]( "正定矩阵的Cholesky分解")
借用
http://en.wikipedia.org/wiki/Cholesky_decomposition中的推导：
令
![A^{(1)}:=A]( "正定矩阵的Cholesky分解")
，在第i次迭代时有：
![A^{(i)}=
\begin{pmatrix}
I_{i-1}&0&0\\
0&a_{i,i}&b_i^*\\
0&b_i&B^{(i)}
\end{pmatrix}]( "正定矩阵的Cholesky分解")
，其中
![I_{i-1}]( "正定矩阵的Cholesky分解")
为i-1维单位矩阵
定义矩阵
：
