【数值算法】共轭梯度法（二）-预处理共轭梯度法

在之前的文章【数值算法】共轭梯度法求解线性方程组中，我们指出，共轭梯度法是求解对称正定系数的线性方程组的极为有效的方法，并且指出：对于n阶线性方程组，通常最多n+1次迭代可以获得收敛。在实际的有限元开发实践中，需要求解的经常是非常大，极端大的线性方程组，此时，采用共轭梯度法，有时可能需要上万次的迭代才能收敛，虽然每次收敛的计算量并不大，但是整体求解也会花费较多时间。

实际上，共轭梯度法能否快速收敛与系数矩阵A密切相关。文献【1】指出，对于共轭梯度法存在以下定理：

如果A=I+B为nxn的对称正定矩阵，且rank（B）=r，则共轭梯度法至多r+1步收敛。其中I指单位矩阵，rank是矩阵的秩。

从该定理可知，共轭梯度法能否快速收敛，主要取决于“A”是否“接近于”单位矩阵。特别地，当A就是单位矩阵时，rank(B)=0，此时一步即可收敛，当然这是很显然的。

基于上述定理，多种基于共轭梯度法法衍生的预处理共轭梯度法（PCG）得以广泛地应用。具体来说，实际过程如下：

假设要求解的方程是

预处理共轭梯度法的思想是求解

其中，

并且，C为对称正定矩阵，且使得 是良态（即尽量“接近”于单位矩阵）。如果定义

结合原始的共轭梯度法，可以得到以下的预处理共轭梯度法（PCG）：

从上述算法中可以看出，其主要改动是需要首先求解

这一预处理方程，得到Zk的值后再代替原来的rk进行运算。采用不同的M，当然就会得到不同的Zk，最终影响共轭梯度法的收敛性。很显然，对于整个原始方程的PCG求解效率来说，首先这个预处理方程需要比较容易求解，否则求解该预处理方程就已经花费了较多时间，则整个原始方程求解效率自然不会高。其次，M的选取需要确实能够减少迭代步数。这两方面在实际中往往是冲突的，例如，假设M取为简单的单位矩阵，则Zk就是rk，几乎不需要求解，此时PCG共轭梯度法就退化为普通的共轭梯度法，预处理相当于未生效；假设M取原始系数矩阵A，则很显然，一步迭代就能得到最终解，但是求解该预处理方程，本质上就和求解原始方程无二。

在实践中，尤其是有限元程序开发中，常见的M的选取至少有两种：对角线预处理和不完备的Cholesky预处理。

（1）对角线预处理：对角线预处理指的就是M矩阵为原始系数矩阵A的对角线矩阵。在知名的开源有限元软件FEAPpv中，就是采用的这种方法进行共轭梯度法预处理。一般情况下，这种方法求解预处理方程十分简单，但是通常对于系数矩阵严格对角占优（即对角线元素大于该行其他元素之和）的情况下才比较有效。例如之前文章中待求解的系数矩阵为：

该矩阵并不严格对角占优，采用对角线预处理共轭梯度法求解结果如下：

采用对角线预处理，迭代次数并无太多改善。

但是如果系数矩阵A的对角线扩大10倍：

采用共轭梯度法求解：

而采用对角线预处理共轭梯度法求解：

      采用对角线预处理共轭梯度法仅需4次迭代即获得收敛结果。

（2）不完备的Cholesky分解预处理

    不完备的Cholesky分解预处理指的是对系数矩阵A进行不完备的Cholesky分解。常规的Cholesky分解如下：

    其中,A是正定矩阵，L是下三角矩阵。而在不完备的Cholesky预处理共轭梯度法中，也是对A进行此分解，但是仅对于A中非0元素进行分解，A中的0元素在L中依然是0，或者甚至是求解过程中只在内存中存取A的非0元素。

   求得系数矩阵A的不完备的下三角矩阵L后，

   令

    再采用预处理共轭梯度法的具体算法获得最终解。当然，由于L是下三角矩阵，因此预处理方程一般通过两次“回代”（参考本公众号文章[数值算法与编程]高斯消去法的回代部分）即可求解。

    以之前的文章共轭梯度法中的原始方程求解为例，采用不完备Cholesky分解预处理求解如下：

    

    仅需3次迭代，即获得收敛解，而原来的常规共轭梯度法需要9次迭代。并且，matlab计算结果如下：

    通过对比不难看出，虽然仅仅是3次迭代，但是已经具备较高的求解精度。

    在实际开发中，共轭梯度法还有较多的发挥空间，比如，比如，知名有限元大师Thomas J.R. Hughes在1983年创立了一种基于共轭梯度法的element by element算法，这种方法不需要组装整体刚度矩阵，而是通过逐个单元进行求解，求解效率很高，且由于不需要组装整体刚度矩阵，计算过程中的内存需求显著减少，并且免去了常规的采用稀疏矩阵存储有限元刚度矩阵的组装过程，实际上，相较于常规的矩阵，对于CSR，CSC等格式的有限元整体刚度稀疏矩阵组装，并不是一件十分容易的事情。以上，就是共轭梯度法（二）之预处理共轭梯度法的全部内容，感谢您的阅读！

【完】

==================================================================================

参考文献：

     【1】《矩阵计算》，Gene H Golub，Charles F. Van Loan

==================================================================================

     

   欢迎关注公众号 有限元术