第二章 线性方程组的直接方法(3)

这一讲，我们来学习平方根法。平方根法也是一种求解线性方程组的三角分解法。之前我们已经讲过了求解三角分解的Doolittle三角分解法，那么平方根法有什么区别呢？

2.5 平方根法

平方根法是用来适用于系数矩阵$A$是对称正定矩阵的，如果$A$为对称正定矩阵，则有唯一分解$A=LU$，且$u_{kk}>0$。那么我们可以将矩阵$U$继续分解，分解为一个对角矩阵和一个单位上三角矩阵的乘积：

$\left[\begin{matrix} u_{11} & u_{12} & ...& u_{1n} \\ & u_{22} & ... & u_{2n} \\ & & \ddots & \vdots \\ & & & u_{nn}\end{matrix}\right]= \left[\begin{matrix} u_{11} & & & \\ & u_{22} & & \\ & & \ddots & \\ & & & u_{nn}\end{matrix}\right]\left[\begin{matrix} 1 & \frac{u_{12}}{u_{11}} & ...& \frac{u_{1n}}{u_{11}} \\ & 1 & ... & \frac{u_{2n}}{u_{22}} \\ & & \ddots & \vdots \\ & & & 1\end{matrix}\right] = DM$

则有：$A=LDM$

又因为$A$是对称矩阵，那么我们又可以推出$(LDM)^T = M^TDL^T = LDM$，所以$M=L^T$，所以又可以进一步写成$A=LDM=LDL^T$。

因为$u_{kk}>0$，那么我们将对角矩阵$D$再进一步分解：

令$D = \left[\begin{matrix} \sqrt{u_{11}} & & & \\ & \sqrt{u_{22}} & & \\ & & \ddots & \\ & & & \sqrt{u_{nn}}\end{matrix}\right]\left[\begin{matrix} \sqrt{u_{11}} & & & \\ & \sqrt{u_{22}} & & \\ & & \ddots & \\ & & & \sqrt{u_{nn}}\end{matrix}\right] = D^{\frac{1}{2}}D^{\frac{1}{2}}$

则有$A=LD^{\frac{1}{2}}D^{\frac{1}{2}}L^T = (LD^{\frac{1}{2}})(LD^{\frac{1}{2}})^T=GG^T$，其中，$G=LD^{\frac{1}{2}}$

因此，正定对称矩阵$A$经过一系列分解，得到$A=GG^T$，称为对称正定矩阵的Cholesky分解。

那么，原来的$Ax=b$就转换为了$Gy=b$，$G^Tx=y$，这就是平方根法。

计算方法

若记$G = (g_{ij})$，则有：对$k=1,2,...,n$

$\begin{cases}g_{kk} = (a_{kk} - \sum^{k-1}_{m=1}g^2_{km})^{\frac{1}{2}} \\ g_{ik} = (a_{ik} - \sum^{k-1}_{m=1}g_{im}g_{km})\div g_{kk}, i =k+1,...,n\end{cases}$

求解顺序：先求$G$的都一列，再求第二列，以此类推。

解三角方程$Gy=b$，$G^Tx=y$，可得：

$\begin{cases} y_k = (b_k - \sum^{k-1}_{m=1}g_{km}y_m)\div g_{kk} \\ x_k = (y_k - \sum^{n}_{m=k+1}g_{mk}x_m)\div g_{kk} \end{cases}$

例：解线性方程组：

$\begin{cases} 4x_1 + 2x_2+4x_3 = 4 \\ 2x_1+10x_2-x_3=17 \\ 4x_1-x_2+6x_3=0 \end{cases}$

通过观察可知，这是一个正定对称矩阵，因此可以使用Cholesky分解。

解：

我们表示正定对称的系数矩阵$A$和$G$都可以只写出下三角元素

$\left[\begin{matrix}4 & & \\ 2 & 10 & \\ 4 & -1 & 6 \end{matrix}\right] \rightarrow \left[\begin{matrix}2 & & \\ 1 & 3 & \\ 2 & -1 & 1 \end{matrix}\right]$

所以：

$A = \left[\begin{matrix}2 & & \\ 1 & 3 & \\ 2 & -1 & 1 \end{matrix}\right]\left[\begin{matrix}2 & 1 & 2\\ & 3 & -1 \\ & & 1 \end{matrix}\right] = GG^T$

接下来求解三角方程，解方程$Gy=b$：

$\left[\begin{matrix}2 & & \\ 1 & 3 & \\ 2 & -1 & 1 \end{matrix}\right] \left[\begin{matrix} y_1 \\ y_2 \\ y_3 \end{matrix}\right] = \left[\begin{matrix} 4 \\ 17 \\ 0 \end{matrix}\right]$，得$\left[\begin{matrix} y_1 \\ y_2 \\ y_3 \end{matrix}\right] = \left[\begin{matrix} 2 \\ 5 \\ 1 \end{matrix}\right]$

再解$G^Tx=y$：

$\left[\begin{matrix}2 & 1 & 2\\ & 3 & -1 \\ & & 1 \end{matrix}\right]\left[\begin{matrix} x_1 \\ x_2 \\ x_3 \end{matrix}\right] = \left[\begin{matrix} 2 \\ 5 \\ 1 \end{matrix}\right]$，得$\left[\begin{matrix} x_1 \\ x_2 \\ x_3 \end{matrix}\right] = \left[\begin{matrix} -1 \\ 2 \\ 1 \end{matrix}\right]$

平方根法是求对称正定系数线性方程组的三角分解法，对称正定矩阵的Cholesky分解的计算量和存储量均约为一般矩阵的$LU$分解的一般。且Cholesky分解具有数值稳定性。