解正定线性方程组的CG方法省公开课一等奖全国示范课微课金奖

求解正定线性方程组共轭梯度法（CG方法）

林华堂、张卜元、吕迪第1页1.方法介绍共轭梯度法已经有五十多年历史,它最早是由Hestenes和Stiefel于1952年在求解线性方程组时提出,并由Fletcher和Reeves于1964年推广到非线性优化领域.后,Beale,Powell,Fletcher等著名优化教授对非线性共轭梯度法进行了深入研究,取得了十分优异结果.但几乎同时间世拟牛顿方法因为其良好计算表现以及丰富收敛性分析很快受到了青睐,从而在很长一段时间里共轭梯度法被研究者所忽略.近年来,伴随计算机飞速发展以及实际问题需要,大规模优化问题越来越受到重视,而共轭梯度法正是求解大规模问题一个主要方法.于是,共轭梯度法理论研究又受到人们关注.

第2页第3页第4页

共轭梯度法（ConjugateGradient）是介于最速下降法与牛顿法之间一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢缺点，又防止了牛顿法需要存放和计算Hesse矩阵并求逆缺点，共轭梯度法不但是处理大型线性方程组最有用方法之一，也是解大型非线性最优化最有效算法之一。在各种优化算法中，共轭梯度法是非常主要一个。其优点是所需存放量小，含有步收敛性，稳定性高，而且不需要任何外来参数。第5页2.方法理论与描述CG方法，它是一个极小化方法，对应于求一个二次函数极值。为了引出CG方法，下面介绍一些理论。2.1与方程组等价变分问题

（2.11）第6页则函数有以下性质：（1）对一切，有（2.12）（2）对一切,有（2.13）第7页（3）设为方程组（2.11）解，则对一切，有（2.14）则第8页定理1

设A对称正定，则为方程组（2.11）解充分必要条件是满足证实：设为方程组（2.11）解，由式（2.14）及A正定性，有。反之，若有使到达最小，则故由式（2.14）可知又因A正定，所以。证毕。

由上述定理，求解线性方程组等价于求解变分问题，即求最小。求解方法普通是结构一个向量序列｛｝,使。第9页2.2共轭梯度（CG）法定义设是任意给定一个初始点，从点出发沿某一要求方向，求函数在直线上极小点，设求得极小点为。再从点出发沿某一要求方向，求函数在直线上极小点，设求得极小点为。如此继续下去，普通地，从点出发沿某一要求方向，求函数在直线第10页上极小点。称为搜索方向。命题2对于已知上极小点为式中证实：记，欲确定系数使得一元函数时为极小。由式(2.13)得

第11页第12页注2在命题2中，余量命题2所得迭代公式（2.15）含有下降性第13页假如搜索方向为中一个A共轭向量系，即有性质（2.16）向量系，则称迭代法（2.15）为共轭梯度法（CG法）。用表示线性无关向量系张成子空间，即令第14页定理2从任意一点出发，得到点序列（2.17）充分必要条件是第15页第16页第17页第18页2.3共轭梯度法计算公式下面介绍共轭梯度法一个生成A共轭向量系详细方法。对任意初始向量,取第一个搜索方向为由式(2.15)计算:再计算。第19页令第20页第21页第22页例题

201x13010x2=1102x33解：取初始近似第23页第24页3.共轭梯度法特点建立在二次模型上，含有二次终止性．(2)一个有效算法，克服了最速下降法锯齿现象，又防止了牛顿法计算量大和局部收敛性缺点．(3)算法简