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