共轭梯度法及其基本性质

预备知识

定义1 设word/media/image1.gif是对称正定矩阵。称word/media/image2.gif是A-共轭的，是指

word/media/image3.gif

性质1 设有word/media/image4.gif是彼此共轭的word/media/image5.gif维向量，即

word/media/image6.gif

则word/media/image7.gif一定是线性无关的。

［证明］若有一组数word/media/image8.gif满足

word/media/image9.gif

则对一切word/media/image10.gif一定有

word/media/image11.gif

注意到word/media/image12.gif，由此得出：word/media/image13.gif即所有的word/media/image14.gif＝０．因此，word/media/image7.gif是线性无关的．

性质２　设向量word/media/image15.gif是线性无关的向量组，则可通过它们的线性组合得出一组向量word/media/image7.gif，而word/media/image7.gif是两两共轭的．

［证明］我们用构造法来证实上面的结论．

Ｓ０：取word/media/image16.gif；

Ｓ１：令word/media/image17.gif，取word/media/image18.gif．

……

Ｓm：令

word/media/image19.gif

取　

word/media/image20.gif

容易验证：word/media/image7.gif符合性质２的要求．

性质３设word/media/image7.gif是两两Ａ－共轭的，word/media/image21.gif是任意指定的向量，那么从word/media/image22.gif出发，逐次沿方向word/media/image7.gif搜索求word/media/image23.gif的极小值，所得序列word/media/image24.gif，满足：

word/media/image25.gif．

［证明］由下山算法可知，从word/media/image26.gif出发，沿word/media/image27.gif方向搜索，获得

word/media/image28.gif

从而

word/media/image29.gif

性质４设word/media/image30.gif是两两Ａ共轭的，则从任意指定的word/media/image21.gif出发，依次沿word/media/image30.gif搜索，所得序列word/media/image31.gif满足：

（１）word/media/image32.gifword/media/image33.gif

（２）word/media/image34.gif，其中word/media/image35.gif是方程组(5.1.1)的解．

［证明］（１）是性质３的直接推论，显然成立．

（２）由于word/media/image30.gif是两两Ａ共轭的，故word/media/image30.gif是线性无关的．所以对于向量word/media/image36.gif可用word/media/image30.gif线性表出，即存在一组数word/media/image37.gif使

word/media/image38.gif

由于word/media/image39.gif及word/media/image40.gif，得出

word/media/image41.gif，

于是word/media/image42.gif，再由word/media/image43.gif得出

word/media/image44.gif

于是word/media/image45.gif，与得出word/media/image46.gif一样地，我们可以陆续得出：

word/media/image47.gif

对比word/media/image35.gif和word/media/image48.gif的表达式可知，word/media/image49.gif

证明完毕

性质４是性质３的直接推论．但它给出了一种求（５.１.１）的算法，这种算法称之为共轭方向法．结合性质２，我们可以得到如下的性质５．

性质５设word/media/image50.gif是word/media/image51.gif上的一组线性无关的向量，则从任意指定的word/media/image21.gif出发，按以下迭代产生的序列word/media/image31.gif：

Ｓ１：取word/media/image16.gif，word/media/image52.gif，word/media/image53.gif；

Ｓ２：计算word/media/image54.gif，取word/media/image55.gif；

计算word/media/image56.gif，得出word/media/image57.gif；

如此进行下去，直到第n步：

Ｓn：计算word/media/image58.gif取word/media/image59.gif

计算word/media/image60.gif，得出word/media/image61.gif．

显然：word/media/image49.gif

根据性质４可知，不论采用什么方法，只要能够构造word/media/image5.gif个两两Ａ共轭的向量作为搜索方向，从任一初始向量出发，依次沿两两Ａ共轭的方向进行搜索，经word/media/image5.gif步迭代后，便可得到正定方程组word/media/image62.gif的解．

共轭梯度法

算法步骤如下：

［预置步］任意word/media/image63.gif，计算word/media/image64.gif，并令取：word/media/image65.gif指定算法终止常数word/media/image66.gif，置word/media/image67.gif，进入主步；

［主步］（１）如果word/media/image68.gif，终止算法，输出word/media/image69.gif；否则下行；

（２）计算：word/media/image70.gif

（３）计算：word/media/image71.gif

（４）置word/media/image72.gif，转入（１）．

定理５.2.1　由共轭梯度法得到的向量组word/media/image73.gif和word/media/image74.gif具有如下性质：

（１）word/media/image75.gif

（２）word/media/image76.gif

（３）word/media/image77.gif

（４）word/media/image78.gif，其中

word/media/image79.gif            （5.2.1）

通常称之为Krylov子空间．

［证明］用归纳法．当word/media/image80.gif时，因为

word/media/image81.gif，

word/media/image82.gif

word/media/image83.gif

因此定理的结论成立．现在假设定理的结论对word/media/image84.gif成立，我们来证明其对word/media/image85.gif也成立．

利用等式word/media/image86.gif及归纳假设，有

word/media/image87.gif

又由于

word/media/image88.gif，

故定理的结论（１）对word/media/image85.gif成立．

利用归纳假定有

word/media/image89.gif

而由（１）所证知，word/media/image90.gif与上述子空间正交，从而有定理的结论（２）对word/media/image85.gif也成立．

利用等式

word/media/image91.gif　和　word/media/image92.gif，

并利用归纳法假定和（２）所证之结论，就有

word/media/image93.gif．

成立；而由word/media/image94.gif的定义得

word/media/image95.gif

这样，定理的结论（３）对word/media/image85.gif也成立．

由归纳法假定知

word/media/image96.gif

进而

word/media/image97.gif

于是

word/media/image98.gif

再注意到（２）和（３）所证的结论表明，向量组word/media/image99.gif和word/media/image100.gif都是线性无关的，因此定理的结论（４）对word/media/image85.gif同样成立．

定理证毕

定理5.2.1表明，向量word/media/image101.gif和word/media/image102.gif分别是Krylov子空间word/media/image103.gif的正交基和共轭正交基．由此可见，共轭梯度法最多word/media/image5.gif步便可得到方程组的解word/media/image35.gif．因此，理论上来讲，共轭梯度法是直接法．

定理5.2.2　用共轭梯度法计算得到的近似解word/media/image26.gif满足

word/media/image104.gif             （5.2.２）

或

word/media/image105.gif       （5.2.３）

其中word/media/image106.gif，word/media/image35.gif是方程组word/media/image62.gif的解，word/media/image107.gif是由（5.2.1）所定义的Krylov子空间．

证明　注意到：word/media/image108.gif，则（5.2.2）和(5.2.3)是等价的，因此我们下面只证明(5.2.3)成立．

假定共轭梯度法计算到word/media/image109.gif步出现word/media/image110.gif，那么有

word/media/image111.gif

此外，对计算过程中的任一步word/media/image112.gif，有

word/media/image113.gif

设word/media/image114.gif是属于word/media/image115.gif的任一向量，则由定理5.2.1的（４）知，word/media/image114.gif可以表示为

word/media/image116.gif，

于是

word/media/image117.gif

而

word/media/image118.gif，

再利用定理5.2.1的（３）就可以推出

word/media/image119.gif

于是定理得证．

定理证毕

由定理5.2.1，我们容易得出

word/media/image120.gif

word/media/image121.gif

由此可得

word/media/image122.gif                        (5.2.4)

另外，从理论上讲，该迭代法经word/media/image5.gif次迭代，便能得到精确解．但考虑到计算误差，可以作为无限迭代算法进行计算，直到word/media/image123.gif为止．

从而，我们得到如下实用的共轭梯度算法：

［预置步］任意word/media/image63.gif，计算word/media/image64.gif，并令取：word/media/image65.gif指定算法终止常数word/media/image66.gif，置word/media/image67.gif，进入主步；

［主步］（１）计算：word/media/image124.gif，word/media/image86.gif

（２）如果word/media/image125.gif，转入（3）．否则，终止算法，输出计算结果word/media/image126.gif

（３）计算：word/media/image127.gif

（４）置word/media/image72.gif，转入（1）

注：在算法［主步］中，引入变量word/media/image128.gif，word/media/image129.gif及word/media/image130.gif，可以简化计算。

结合程序设计的特点，共轭梯度法可改为如下实用形式：

算法５·３·１（解对称正定方程组：实用共轭梯度法）

word/media/image131.gif；

word/media/image132.gif

whileword/media/image133.gif and word/media/image134.gif

word/media/image135.gif

if word/media/image80.gif

word/media/image136.gif

else

word/media/image137.gif

end

word/media/image138.gif

end

共轭梯度法作为一种实用的迭代法，它主要有下面的优点：

算法中，系数矩阵Ａ的作用仅仅是用来由已知向量word/media/image139.gif产生向量word/media/image140.gif，这不仅可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量word/media/image139.gif产生向量word/media/image140.gif又十分方便的应用问题是很有益的；

不需要预先估计任何参数就可以计算，这一点不像ＳＯＲ等；

每次迭代所需的计算，主要是向量之间的运算，便于并行化。

5.2.3 收敛性分析

将共轭梯度法作为一种迭代法，它的收敛性怎样呢？这是本节下面主要讨论的问题：

定理５.2.3　如果word/media/image141.gif而且word/media/image142.gif，则共轭梯度法至多迭代word/media/image143.gif步即可得到方程组的精确解。

证明　注意到word/media/image142.gif蕴含着子空间

word/media/image144.gif

的维数不会超过word/media/image143.gif，由定理５.2.1即知定理的结论成立。

定理证毕

定理5·2·3表明，若线性方程组（5·1·1）的系数矩阵与单位相关一个秩word/media/image145.gif的矩阵，而且word/media/image145.gif很小时，则共轭梯度法将会收敛得很快。

定理5·2·4 用共轭梯度法求得的word/media/image26.gif有如下的误差估计

word/media/image146.gif               （5·2·5）

其中word/media/image147.gif

证明由定理5·2·1可知，对任意的word/media/image148.gif，有

word/media/image149.gif

记word/media/image150.gif，则word/media/image151.gif是常数项为1的word/media/image84.gif次实系数多项式。令word/media/image33.gifword/media/image152.gif为所有常数项为1的次数不超过word/media/image84.gif的实系数多项式的全体，则由定理5·2·2和引理5·1·1得

word/media/image153.gif

其中word/media/image154.gif是word/media/image155.gif的特征值。由Chebyshev多项式逼近定理及Chebyshev多项式的性质，定义在[-1，1]区间上的word/media/image84.gif次Chebyshev多项式：word/media/image156.gif是所有常数项为1的次数不超过word/media/image84.gif的实系数多项式中，在[-1，1]上与“0”的偏差值最小的多项式。且偏差值为1，对应的交错点组为：word/media/image157.gif。因此，多项式

word/media/image158.gif

是word/media/image152.gif中在word/media/image159.gif上与“0”的偏差值最小的多项式。即

word/media/image160.gif

于是，我们有

word/media/image161.gif

因此，定理得证。

定理证毕

虽然定理5·2·5所给出的估计是十分粗糙的，而且实际计算时其收敛速度往往要比这个估计快得多，但是它却提示了共轭梯度法的一个重要的性质：只要线性方程组（5·1·1）的系数矩阵是十分良态的（即word/media/image162.gif），则共轭梯度法就会收敛的很快。

共轭梯度法及其基本性质