解正定线性方程组的CG方法.ppt

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