《解正定线性方程组的CG方法课件》由会员分享，可在线阅读，更多相关《解正定线性方程组的CG方法课件（25页珍藏版）》请在金锄头文库上搜索。
1、求解正定线性方程组的共轭梯度法求解正定线性方程组的共轭梯度法（CG方法）方法） 林华堂、张卜元、吕迪解正定线性方程组的CG方法1.方法简介n 共轭梯度法已有五十多年的历史,它最早是由Hestenes和Stiefel于1952年在求解线性方程组时提出的,并由Fletcher和Reeves于1964年推广到非线性优化领域.后,Beale,Powell,Fletcher等著名的优化专家对非线性共轭梯度法进行了深入研究,取得了十分优秀的成果.但几乎同时间世的拟牛顿方法由于其良好的计算表现以及丰富的收敛性分析很快受到了青睐,从而在很长一段时间里共轭梯度法被研究者所忽视.近年来,随着计算机的飞速发展以及实
2、际问题的需要,大规模优化问题越来越受到重视,而共轭梯度法正是求解大规模问题的一种主要方法.于是,共轭梯度法的理论研究又受到人们的关注. 解正定线性方程组的CG方法解正定线性方程组的CG方法解正定线性方程组的CG方法n 共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。 在各种优化算法中，共轭梯度法是非常重要的一种。其优点是所需存储量小，具有步收敛性，稳定
3、性高，而且不需要任何外来参数。解正定线性方程组的CG方法2.方法理论与描述nCG方法，它是一种极小化方法，对应于求一个二次函数的极值。n为了引出CG方法，下面介绍一些理论。n2.1与方程组等价的变分问题n n n （2.112.11）解正定线性方程组的CG方法n则函数 有如下性质：n（1）对一切 ，有n （2.12）n（2）对一切 ,有n （2.13）解正定线性方程组的CG方法n（3）设 为方程组（2.11）的解，则对一切 ，有n （2.14）n则解正定线性方程组的CG方法n定理定理1 设设A对称正定，则对称正定，则 为方程组（为方程组（2.11）解的充分必要条件是）解的充分必要条件是 n 满
4、足满足n证明：设 为方程组（2.11）的解， 由式（2.14）及A的正定性，有 。n 反之，若有 使 达到最小，则n 故由式（2.14）可知n 又因A正定，所以 。证毕。n 由上述定理，求解线性方程组由上述定理，求解线性方程组 等价于求解变分问题，即求等价于求解变分问题，即求n 最小。求解的方法一般是构造一个向量序列最小。求解的方法一般是构造一个向量序列 ,n 使使 。解正定线性方程组的CG方法2.2共轭梯度（CG）法的定义n设 是任意给定的一个初始点，从点 出发沿某一规定的方向 ，求函数 在直线 n上的极小点，设求得的极小点为 。再从点 出发沿某一规定的方向 ，求函数 在直线 n上的极小点，
5、设求得的极小点为 。如此继续下去，一般地，从 点 出发沿某一规定的方向 ，求函数 在直线解正定线性方程组的CG方法n上的的极小点 。称 为搜索方向。n命题2 对于已知的 n上的极小点 为 n式中n证明：记 ，欲确定系数 使得一元函数 时为极小。由式(2.13)得 解正定线性方程组的CG方法解正定线性方程组的CG方法n注注2 在命题2中，余量 命题2所得的迭代公式n （2.15） n具有下降性解正定线性方程组的CG方法n如果搜索方向n为 中的一个A共轭向量系，即有性质n （2.16）n的向量系 ，则称迭代法（2.15）为共轭梯度法（CG法）。n 用 表示线性无关的向量系 张成的子空间，即n令解正
6、定线性方程组的CG方法n定理定理2 从任意一点 出发，得到的点序列n （2.17）n的充分必要条件是解正定线性方程组的CG方法解正定线性方程组的CG方法解正定线性方程组的CG方法解正定线性方程组的CG方法2.3共轭梯度法的计算公式n下面介绍共轭梯度法一种生成A共轭向量系 的具体方法。n 对任意初始向量 ,取第一个搜索方向 为n由式(2.15)计算 :n再计算 。解正定线性方程组的CG方法n令解正定线性方程组的CG方法解正定线性方程组的CG方法解正定线性方程组的CG方法例题n 2 0 1 x1 3n 0 1 0 x2 = 1n 1 0 2 x3 3n解：取初始近似解正定线性方程组的CG方法解正定线性方程组的CG方法3.共轭梯度法的特点(1)建立在二次模型上，具有二次终止性(2) 一种有效的算法，克服了最速下降法的锯齿现象，又避免了牛顿法的计算量大和局部收敛性的缺点(3)算法简单，易于编程，无需计算二阶导数，存储空间小等优点，是求解中等规模优化问题的主要方法 理论上CG方法经过有限步迭代便可得到方程组的准确解，因此CG法本质上是一种直接方法。在实际问题（特别是大型方程组）的计算中，由于舍入误差的存在，很难在有限步得到准确解，且其计算公式具有迭代格式的特点，因此被作为一种迭代法使用。解正定线性方程组的CG方法
