解正定线性方程组的CG方法完整

1、1求解正定线性方程组的共轭梯度法求解正定线性方程组的共轭梯度法（CG方法）方法） 林华堂、张卜元、吕迪21.方法简介n 共轭梯度法已有五十多年的历史,它最早是由Hestenes和Stiefel于1952年在求解线性方程组时提出的,并由Fletcher和Reeves于1964年推广到非线性优化领域.后,Beale,Powell,Fletcher等著名的优化专家对非线性共轭梯度法进行了深入研究,取得了十分优秀的成果.但几乎同时间世的拟牛顿方法由于其良好的计算表现以及丰富的收敛性分析很快受到了青睐,从而在很长一段时间里共轭梯度法被研究者所忽视.近年来,随着计算机的飞速发展以及实际问题的需要,大规模优

2、化问题越来越受到重视,而共轭梯度法正是求解大规模问题的一种主要方法.于是,共轭梯度法的理论研究又受到人们的关注. 345n 共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定性高，而且不需要任何外来参数。62.方法理论与描述nCG方法，它是一种极小化方法，对应于求一个

3、二次函数的极值。n为了引出CG方法，下面介绍一些理论。n2.1与方程组等价的变分问题n n n （2.112.11）bAxARbRAnn对称正定，考虑方程组设,n),(,21:nxbxAxxRR）（）（为定义二次函数7n则函数 有如下性质：n（1）对一切 ，有n （2.12）n（2）对一切 ,有n （2.13）nRx bAxxgrad)(RRyxn,),(2),()(),(),(21)2yAyaybAxxyxbyxyxAyx（8n（3）设 为方程组（2.11）的解，则对一切 ，有n （2.14）n则xnRx），（）（）（xxxxAxx21),(21),(21),(),(21)(),(21)(,

4、11111xAxbAbbAbbAbAAxbxAxxbAx所以证明：因为)()(),(21),(),(21),(21xxxAxxAxxAxxxxxA9n定理定理1 设设A对称正定，则对称正定，则 为方程组（为方程组（2.11）解的充分必要条件是）解的充分必要条件是 n 满足满足n证明：设 为方程组（2.11）的解， 由式（2.14）及A的正定性，有 。n 反之，若有 使 达到最小，则n 故由式（2.14）可知n 又因A正定，所以 。证毕。n 由上述定理，求解线性方程组由上述定理，求解线性方程组 等价于求解变分问题，即求等价于求解变分问题，即求n 最小。求解的方法一般是构造一个向量序列最小。求解的

5、方法一般是构造一个向量序列 ,n 使使 。xx)(min)(xxnRxx最小。使即)(, 0)()(xxxxxx)(x。所以。又0)()(),()()()(xxxxxx0)()( 2),(xxxxxxAxxbAx)(xRxn，使kx)(min)(xxk102.2共轭梯度（CG）法的定义n设 是任意给定的一个初始点，从点 出发沿某一规定的方向 ，求函数 在直线 n上的极小点，设求得的极小点为 。再从点 出发沿某一规定的方向 ，求函数 在直线 n上的极小点，设求得的极小点为 。如此继续下去，一般地，从 点 出发沿某一规定的方向 ，求函数 在直线0 x0 x0p)(x00tpxx1x1x1p)(x1

6、1tpxx2xkxkp)(xkktpxx11n上的的极小点 。称 为搜索方向。n命题2 对于已知的 n上的极小点 为 n式中n证明：记 ，欲确定系数 使得一元函数 时为极小。由式(2.13)得 1kxkp在直线函数)(),0(,xppxkkkkktpxx1kxkkkkpxx1bAxrApprkkkkTk,p-Tkk)()(kktpxtfkktf当12),(2),()()(2kkkkkpAptpbAxtxtf得由, 0)( tfkTkkTkkTkkTkkAppprApppbAxat)(极小。从而时，因此又由于)(),0(0tfatpAppfkkkTk kkkkpxx1证毕。13n注注2 在命题2

7、中，余量 命题2所得的迭代公式n （2.15） n具有下降性。)(kkkxgradbAxrkTkkTkkkkkkAppprpxx1)()(1kkxx14n如果搜索方向n为 中的一个A共轭向量系，即有性质n （2.16）n的向量系 ，则称迭代法（2.15）为共轭梯度法（CG法）。n 用 表示线性无关的向量系 张成的子空间，即n令,210pppnR0jTiApp)(ji),2, 1 ,0(0,kppkk且kLkp1210,kkppppspanL。kkLuuxxS015n定理定理2 从任意一点 出发，得到的点序列n （2.17）n的充分必要条件是0 x具有性质,21xx)(min)(0uxxk)(L

8、ku正交，即和且余量kkkkLrSx 0),(urk)(kLu)18.2(零，从而有沿任一方向导数必须为在极小点，因此上的在为二次函数表明，必要性。式证明：kkkxxSxx)()()17. 2() 1 (0),(),(uruxgradkk)(kLu 令充分性。任取,)2(kSxkkkkuxxuxxxxx00,16于是则其中,kkkkuuxLuu),(21),()()(kkkkkxAxxrxx得由)18.2(0),(),(),(kkkkkururxr。证毕。故有正定，又因)()(,0),(kkkxxxAxA要结论：可得到共轭梯度法的重由定理23定理 。满足式列由共轭梯度法得到的点)17. 2(k

9、x正交。事实上有和且余量只需证明证明：由定理kkkkLrSx 2kikiikkkkkkkkkSpxppxpxx1001122211117有因为对任意, 1, 1 , 0kj0)()()()(),(001000000100100rprpAprprpbAxprprprpApprpApprpAprpbAxpprTjTjijiiTjTjjTjTjjTjTjjTjjTjiTjkiiTjikiiTjkTjjk正交。证毕。和所以kkLr184定理的解。步便得到方程组共轭梯度法至多进行)11. 2(n因此无关，共轭向量系，必为线性为非零的而知和定理证明：由定理Apppniprnin110,),1, 1 , 0

10、(0),(320bAxrnn的解。证毕。一定是方程组故)11. 2(nx192.3共轭梯度法的计算公式n下面介绍共轭梯度法一种生成A共轭向量系 的具体方法。n 对任意初始向量 ,取第一个搜索方向 为n由式(2.15)计算 :n再计算 。 ip0 x)(000bAxrp0p1x000000001AppprpxxTTbAxr11。方向张成的空间中搜索、于是可在因此而1010101,prrrrpr20n令0010011prrrp共轭，则为与要使App100)(000101ApprAppTT从而得到),/(),(00010AppApr:)15. 2(2x计算再由式111111112AppprpxxTT

11、21再计算bAxr22令1122prp共轭，必须为与要使App210)(111212ApprAppTT从而得到),/(),(11121AppApr算依此类推，一般地，计bAxrkk11否则，令的解，停止计算为方程组则若;)11. 2(, 011kkxrkkkkprp1122共轭，必须为与要使Appkk 1),/(),(1kkkkkAppApr的计算公式：这样便得到共轭梯度法，取给定初始近似向量0 x)(000bAxrp计算对于, 2 , 1 , 0kkkkkkkkkkkkkkkkkkkkTkkTkkprpAppAprAprbAxrpxxApppr111111),/(),(的解，停止计算。为方程

12、组则计算过程中，若)11. 2(, 011kkxr23例题n 2 0 1 x1 3n 0 1 0 x2 = 1n 1 0 2 x3 3n解：取初始近似，则Tx)0 , 0 , 0(0TbAxr)3, 1, 3(00Trp)3 , 1 , 3(00计算得对于, 0k55,)9 , 1 , 9(000AppApTT因此TTTpxxApppr) 3 , 1 , 3(5519,5519-00010000024TTprpAppAprAprbAxr) 1,18, 1(551145572),/(),() 1 , 6, 1 (5562001120001000011计算得对于, 1k323112155196,) 1, 6 , 1(551918AppApTT因此TTTpxxApppr) 1 , 1 , 1 (19355-111211111，022bAxr。组的解故两次迭代变得到方程Tx) 1 , 1 , 1 (2253.共轭梯度法的特点建立在二次模型上，具有二次终止性(2) 一种有效的算法，克服了最速下降法的锯齿现象，又避免了牛顿法的计算量大和局部收敛性的缺点(3)算法简单，易于编程，无需计算二阶导数，存储空间小等优点，是求解中等规模优化问题的主要方法 理论上CG方法经过有限步迭代便可得到方