解线性方程组的迭代法优秀PPT.ppt

《解线性方程组的迭代法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《解线性方程组的迭代法优秀PPT.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、解线性方程组的迭代法现在学习的是第1页，共90页 第六章第六章 解线性方程组的迭代法解线性方程组的迭代法/*Iterative Method for Solving Linear Algebraic Systems*/求解求解迭代法迭代法从一个从一个初始向量初始向量出发出发,按照一定的按照一定的递推格式递推格式,产生逼近方程组的产生逼近方程组的近似解序列近似解序列。研究研究内容：内容：如何建立迭代格式？如何建立迭代格式？收敛速度？收敛速度？向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？现在学习的是第2页，共90页 直接法与迭代法各有优缺点直接法与迭代法各有优缺点直直接接法法由由于

2、于受受到到计计算算机机存存储储容容量量的的限限制制，一一般般来来说说，仅仅适适于于系系数数矩矩阵阵阶阶数数不不太太高高的的问问题题，其其工工作作量量较较小小，但但程程序较复杂。序较复杂。低低阶阶稠稠密密的的线线性性方方程程组组用用直直接接法法(如如高高斯斯消消去去法法和和三角分解法三角分解法)。迭迭代代法法主主要要用用于于某某些些系系数数矩矩阵阵稀稀疏疏且且阶阶数数较较高高的的问问题题，一一般般来来说说，程程序序较较为为简简单单，但但工工作作量量有有时时较较大大。大大型型稀稀疏疏非非带带状状的的线线性性方方程程组组(n(n很很大大,且且零零元元素素很很多多，如如偏偏微微方方程程数数值值解解产产

3、生生的的线线性性方方程程组组,n10,n104 4)，零零元元素素多多，适合用迭代法。适合用迭代法。实实际际计计算算时时，应应根根据据问问题题的的特特点点和和要要求求来来决决定定方方法法的取舍。的取舍。现在学习的是第3页，共90页考虑线性方程组考虑线性方程组也就是也就是 (1)将将(1)(1)化成等价形式化成等价形式 (2)现在学习的是第4页，共90页 当迭代公式产生的序列当迭代公式产生的序列 收敛到向收敛到向量量 ，即即 ，则称该迭代法，则称该迭代法收敛收敛，否则为否则为发散发散。？然后选取一个初始向量然后选取一个初始向量 ，按以下公式迭代计算，按以下公式迭代计算(3)称为称为单步定常单步定

4、常线性迭代法，线性迭代法，为为迭代矩阵迭代矩阵，为常数项。为常数项。现在学习的是第5页，共90页一、一、Jacobi迭代法迭代法(简称简称J法或法或简单简单迭代法迭代法)设设，从第，从第i个方程解个方程解出出xi得等价的方程组得等价的方程组Jacobi迭代法的迭代法的分量分量形式：形式：现在学习的是第6页，共90页Jacobi迭代法的计算过程如下：迭代法的计算过程如下：Whatifaii=0?迭代过程中，迭代过程中，A的元素的元素不改变，故可以不改变，故可以事先调整事先调整好好A使得使得aii 0，否则否则A不可逆不可逆。必须等必须等X(k)完全计算完全计算好了才能计算好了才能计算X(k+1)

5、，因此，因此需要需要两组向量两组向量存储。存储。A bit wasteful,isnt it?现在学习的是第7页，共90页将系数矩阵将系数矩阵分裂分裂为：为：其中其中A=-L-UD现在学习的是第8页，共90页其中其中 J迭代法的迭代法的矩阵矩阵形式：形式：现在学习的是第9页，共90页二、二、Gauss-Seidel迭代法迭代法(G-S迭代法迭代法)G-S迭代法是迭代法是J迭代法的一种迭代法的一种改进改进在在J迭代公式中，计算迭代公式中，计算 时，利用已经算出来的时，利用已经算出来的新的新的值，从而得到值，从而得到G-S迭代法。迭代法。G-S迭代法的迭代法的分量分量形式：形式：现在学习的是第10

6、页，共90页Gauss-Seidel迭代法的计算过程如下：迭代法的计算过程如下：现在学习的是第11页，共90页其中其中 G-S迭代法的迭代法的矩阵矩阵形式：形式：现在学习的是第12页，共90页例例1 1：利用利用Jacobi和和Gauss-Seidel迭代法求解方程组迭代法求解方程组解：解：从以上三个方程中分别解出从以上三个方程中分别解出现在学习的是第13页，共90页G-S迭迭代代格格式式Jacobi迭迭代代格格式式现在学习的是第14页，共90页计计算算结结果果Gauss-Seidel迭代法迭代法要求要求精度精度迭代迭代次数次数 0.001 5(0.9997916 0.9998479 1.00

7、00664)0.0001 7(0.9999929 0.9999949 1.0000022)0.00001 8(1.0000013 1.0000009 0.9999996)方方 程程 组组 的的 近近 似似 解解取初值取初值计计算算结结果果取初值取初值Jacobi迭代法迭代法要求要求精度精度迭代迭代次数次数 0.001 9(1.0002507 1.0000694 1.0002507)0.0001 10(0.9999541 1.0001253 0.9999541)0.00001 14(0.9999981 1.0000020 0.9999981)方方 程程 组组 的的 近近 似似 解解现在学习的是第

8、15页，共90页现在学习的是第16页，共90页引理引理迭代法迭代法 收收敛的充要条件是敛的充要条件是证明：证明：设迭代法设迭代法 收敛，则有收敛，则有三三、Jacobi和和Gauss-Seidel迭代法的收敛性分析迭代法的收敛性分析 收敛的充要条件与误差估计收敛的充要条件与误差估计现在学习的是第17页，共90页收敛的充要条件是收敛的充要条件是 。求解方程组求解方程组 的单步线性定常迭代法的单步线性定常迭代法（1）迭代法是否收敛取决于迭代矩阵的迭代法是否收敛取决于迭代矩阵的谱半径谱半径，与初，与初始向量和常数项无关始向量和常数项无关。（2）而对于同一个方程组，不同的迭代法对应的迭代而对于同一个方

9、程组，不同的迭代法对应的迭代矩阵的矩阵的谱半径谱半径一般不会相同，因而收敛性也一般不会相同，因而收敛性也不同。不同。上述定理说明：上述定理说明：现在学习的是第18页，共90页例例2 2：说明用说明用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：例例3 3：说明用说明用J法和法和G-S法求解下列方程组的收敛性：法求解下列方程组的收敛性：现在学习的是第19页，共90页例例2求解：求解：计算计算特征值特征值：J法不收敛法不收敛现在学习的是第20页，共90页G-S法的法的迭代迭代矩阵为矩阵为G-S法收敛法收敛现在学习的是第21页，共90页例例3求求解：解：计算计算特征值特征值：J

10、法收敛法收敛现在学习的是第22页，共90页G-S法的法的迭代迭代矩阵为矩阵为G-S法不收敛法不收敛计算计算特征值特征值：在例在例1中，中，G-S法收敛速度比法收敛速度比J法要高法要高例例2说明说明J 法发散时而法发散时而G-S法收敛，法收敛，但例但例3却说明却说明G-S法发散时而法发散时而J法却收敛法却收敛因此因此,不能说不能说G-S法比法比J法更好法更好现在学习的是第23页，共90页若迭代矩阵若迭代矩阵 的范数的范数 ，并假定，并假定的第的第k次迭代向量次迭代向量 与精确解与精确解 的误差满足：的误差满足：范数满足范数满足，则迭代法，则迭代法证明：证明：现在学习的是第24页，共90页代入前述

11、不等式即得。代入前述不等式即得。利用利用矩阵的范数判定迭代收敛只是一个充分条矩阵的范数判定迭代收敛只是一个充分条件，通常采用矩阵的件，通常采用矩阵的1-范数、范数、-范数来判定。范数来判定。现在学习的是第25页，共90页若迭代矩阵若迭代矩阵 的范数的范数 ，并假定，并假定的第的第k次迭代向量次迭代向量 与精确解与精确解 的误差满足：的误差满足：范数满足范数满足，则迭代法，则迭代法证明：证明：两边取范数即得。两边取范数即得。现在学习的是第26页，共90页如果如果 是对称矩阵，且有是对称矩阵，且有正正的对角元，则的对角元，则求解方程组求解方程组 的的J法收敛的充要条件是矩阵法收敛的充要条件是矩阵和

12、和 均为正定的，其中均为正定的，其中如果如果 是对称是对称正定正定矩阵，则矩阵，则求解方程组求解方程组 的的G-S法收敛。法收敛。从系数矩阵从系数矩阵A判断收敛的条件判断收敛的条件现在学习的是第27页，共90页设设 满足满足称称 为严格为严格对角占优对角占优矩阵矩阵如果如果 且至少有一个严格且至少有一个严格不等式成立，则称不等式成立，则称 为为弱对角占优弱对角占优矩阵。矩阵。现在学习的是第28页，共90页设设 ，如果能找到，如果能找到置换置换阵阵 ，使得，使得其中其中 与与 均为均为方方阵阵，称，称 为为可约可约的的否则称否则称 为为不可约不可约的的*Def每行每列只有一个元素是每行每列只有一

13、个元素是1,其余元素是零的方阵称为其余元素是零的方阵称为置换阵置换阵(或排列阵或排列阵).现在学习的是第29页，共90页例如：例如：矩阵矩阵是是可约可约的的若系数矩阵是若系数矩阵是可约可约的，则可通过的，则可通过行行与与列重排列重排化为化为上面上面(*)(*)式，从而可将方程组简化为式，从而可将方程组简化为低阶低阶方程组。方程组。现在学习的是第30页，共90页（可约可约矩阵的矩阵的等价等价定义）定义）设矩阵设矩阵 ，如果，如果存在存在 的两个非空子集的两个非空子集 和和 ，满足，满足使得使得则称矩阵则称矩阵可约，否则称可约，否则称不可约。不可约。例如：例如：矩阵矩阵现在学习的是第31页，共90

14、页矩阵矩阵不可约不可约设设 为为 严格严格对角占优或对角占优或不可约不可约对角对角占优，则占优，则，且，且 非奇异。非奇异。证明：证明：首先证明矩阵为严格首先证明矩阵为严格对角占优对角占优的情况（反证法）的情况（反证法）设矩阵设矩阵奇异，奇异，则方程组则方程组存在非零存在非零解解。不妨假设不妨假设，则由第则由第k个方程得：个方程得：现在学习的是第32页，共90页其次证明其次证明矩阵为矩阵为不可约不可约对角占优的情况对角占优的情况首先证明首先证明设设由条件：由条件：是是弱弱对角占优对角占优，即存在集合即存在集合与与 不可约不可约矛盾！矛盾！使得使得现在学习的是第33页，共90页下面证明下面证明

15、是是非奇异非奇异的：的：设设则存在则存在非零非零向量向量 满足满足则存在非空集合则存在非空集合否则否则与与 弱对角占优弱对角占优矛盾！矛盾！现在学习的是第34页，共90页且满足且满足与与 弱对角占优弱对角占优矛盾！矛盾！不可约不可约条件条件现在学习的是第35页，共90页设设 为为 严格严格对角占优或对角占优或不可约不可约对角对角占优占优的的对称对称矩阵，矩阵，且对角元素皆为且对角元素皆为正正，则，则 正定。正定。推论推论证明：证明：设设为矩阵为矩阵的特征值，则对于的特征值，则对于，注意到注意到与与同为同为严格严格对角占优或对角占优或不可约不可约对角占优对角占优则则，即即由由的任意性知，矩阵的任

16、意性知，矩阵的特征值均的特征值均大于零大于零，所以所以正定。正定。现在学习的是第36页，共90页若若 为为 严格严格对角占优或对角占优或不可约不可约对角对角占优的，占优的，则则Jacobi迭代和迭代和Gauss-Seidel迭代收敛迭代收敛。证明：证明：首先证明首先证明Jacobi迭代的收敛性（反证法）迭代的收敛性（反证法）因为因为 是是 严格严格对角占优或对角占优或不可约不可约对角对角占优，则占优，则设设 有一个特征值有一个特征值 ，满足，满足 ，则有，则有注意到注意到也为也为严格严格对角占优或对角占优或不可约不可约对角占优对角占优与与 是是 的特征值矛盾，从而所有特征值的绝对的特征值矛盾，

17、从而所有特征值的绝对值都小于值都小于1 1，故谱半径小于，故谱半径小于1 1，所以收敛。，所以收敛。现在学习的是第37页，共90页仅给出仅给出不可约不可约对角占优对角占优矩阵矩阵G-S法法的证明的证明只要证明只要证明 ，其中，其中设设 有一个特征值有一个特征值 ，满足，满足 ，且有，且有 由由 是是不可约不可约且且弱弱对角占优对角占优矩阵知：矩阵知：其次证明其次证明Gauss-Seidel迭代收敛的情况（反证法）迭代收敛的情况（反证法）现在学习的是第38页，共90页注意到注意到 和和 的零元素和的零元素和非零元素的非零元素的位置位置完全一样，故完全一样，故 是是不可约不可约也是也是弱弱对角占优

18、对角占优矩阵矩阵矛盾！矛盾！其中其中 为为J法的法的迭代迭代矩阵矩阵如果如果 为为严格对角占优严格对角占优矩阵，易证矩阵，易证现在学习的是第39页，共90页 迭代法的迭代法的收敛速度收敛速度：设迭代法设迭代法 收敛收敛，即，即上式说明：上式说明：可看作第可看作第k次迭代误差范数的次迭代误差范数的压缩率压缩率称之为迭代法称之为迭代法 的的平均收敛率平均收敛率。（/*Rate of Average Convergence*/）平均平均压压缩率缩率现在学习的是第40页，共90页上式说明：上式说明：最小最小迭代次数与迭代次数与 成反比成反比记记现在学习的是第41页，共90页称之为迭代法称之为迭代法 的

19、的渐进渐进收敛率，或者收敛率，或者渐进渐进收敛速度，简称收敛速度，简称收敛速度收敛速度。（/*Rate of Convergence*/）迭代次数的近似估计式迭代次数的近似估计式上式说明：谱半径上式说明：谱半径 越越小小，收敛速度越，收敛速度越快快。现在学习的是第42页，共90页设设 ，是是任意任意一种矩阵范数，则一种矩阵范数，则 证明：证明：因为因为对对令令所以所以时，时，现在学习的是第43页，共90页四、四、超松弛超松弛(SOR)迭代法迭代法/*Overrelaxation Iteration*/1、超松弛超松弛(SOR)迭代法迭代法思想思想类似于类似于G-S迭代法的改进方法，利用第迭代法

20、的改进方法，利用第k次次迭代值和第迭代值和第k+1次的次的G-S迭代值作迭代值作加权平均加权平均G-S迭代法的计算公式迭代法的计算公式：作作加权加权平均平均现在学习的是第44页，共90页 超松弛超松弛(SOR)迭代法的迭代法的分量分量形式：形式：其中其中 称为称为松弛松弛因子；因子；时即为时即为G-S迭代迭代现在学习的是第45页，共90页SOR迭代法的计算过程如下：迭代法的计算过程如下：现在学习的是第46页，共90页超松弛超松弛(SOR)迭代法的矩阵形式：迭代法的矩阵形式：迭代迭代矩阵矩阵其中其中 SOR迭代法的迭代法的迭代迭代矩阵：矩阵：记记现在学习的是第47页，共90页例例1 1：写出写出

21、SOR迭代法求解下列方程组的迭代格式迭代法求解下列方程组的迭代格式现在学习的是第48页，共90页解：解：SOR迭代法的迭代公式迭代法的迭代公式取取初始初始向量向量选取不同的选取不同的 值进行计算，值进行计算，结果结果见下见下表表现在学习的是第49页，共90页要求要求精度精度迭代迭代次数次数 0.001 12(3.0012790 3.9989342 -5.0002665)0.0001 16(3.0001952 3.9998374 -5.0000407)0.00001 21(3.0000186 3.9999845 -5.0000039)0.001 12(3.0020191 3.9982705 -5

22、.0004444)0.0001 18(3.0001673 3.9998567 -5.0000368)0.00001 23(3.0000210 3.9999820 -5.0000046)0.001 8(2.9997451 4.0000653 -4.9998924）0.0001 10(2.9999853 4.0000031 -4.9999935）0.00001 12(2.9999993 4.0000001 -4.9999996）0.001 13(3.0006104 4.0001741 -5.0007434)0.001 151(2.9995106 4.0017780 -5.0027919）方方 程程

23、 组组 的的 近近 似似 解解的值的值现在学习的是第50页，共90页 向后的向后的SOR迭代法：迭代法：记记SOR迭代法的迭代法的向量向量形式：形式：迭代迭代矩阵：矩阵：现在学习的是第51页，共90页向后向后SOR迭代法的迭代法的分量分量形式：形式：对称对称超松弛超松弛迭代法（迭代法（SSOR）：现在学习的是第52页，共90页例例2 2：写出写出下列方程组下列方程组向后的向后的SOR和和SSOR的迭代格式的迭代格式解：解：向后的向后的SOR迭代法的迭代格式迭代法的迭代格式现在学习的是第53页，共90页SSOR迭代法的迭代格式迭代法的迭代格式现在学习的是第54页，共90页2、SOR迭代法的收敛性

24、：迭代法的收敛性：其中其中对对 ，设其对角元皆非零，设其对角元皆非零，则对所有实数则对所有实数 ，有，有证明：证明：设设迭代迭代矩阵矩阵 的特征值为的特征值为现在学习的是第55页，共90页推论推论 如果求解方程组如果求解方程组 的的SOR法收敛，则法收敛，则设设 为对称为对称正定正定矩阵，且矩阵，且则求解方程组则求解方程组 的的SOR法收敛。法收敛。现在学习的是第56页，共90页证明：证明：迭代迭代矩阵矩阵设设 的任意特征值为的任意特征值为 ，相应的特征向量为，相应的特征向量为 ，则，则 上式两边与上式两边与 作作内积内积因为矩阵因为矩阵 正定正定，所以，所以 也也正定正定：现在学习的是第57

25、页，共90页记记则则分子分子减去分母：减去分母：现在学习的是第58页，共90页因为矩阵因为矩阵 正定正定，设设 为为对称对称矩阵，且所有对角元矩阵，且所有对角元，若求解方程组，若求解方程组 的的SOR法法收敛，则收敛，则 正定，且正定，且 。现在学习的是第59页，共90页设设 为为对称正定对称正定矩阵，且矩阵，且则求解方程组则求解方程组 的的SSOR法收敛。法收敛。例例3 3：分别用分别用J-和和SOR法法计算下列方程组，问：计算下列方程组，问：用用J-法计算该方程组，则收敛的法计算该方程组，则收敛的充要充要条件是条件是当当 满足满足 ，且，且 时，时，SOR法收敛。法收敛。满足满足现在学习的

26、是第60页，共90页五、五、共轭梯度共轭梯度法法/*Conjugate Gradient Method*/共轭梯度共轭梯度法法(CG算法算法)属于一种不需要确定任何参数的求解对属于一种不需要确定任何参数的求解对称正定线性方程组的迭代法，但如果不考虑计算过程的舍入称正定线性方程组的迭代法，但如果不考虑计算过程的舍入误差，误差，CG算法只用有限步就收敛于方程组的精确解。算法只用有限步就收敛于方程组的精确解。思想思想共轭梯度共轭梯度法是一种法是一种变分变分方法，将求解方程组方法，将求解方程组问题问题等价等价转化为一个转化为一个二次函数二次函数的的极值极值问题问题 在使用在使用SOR方法求解线性方程组

27、时，需要确定松驰因子，方法求解线性方程组时，需要确定松驰因子，只有系数矩阵具有较好的性质时，才有可能找到最佳松驰只有系数矩阵具有较好的性质时，才有可能找到最佳松驰因子，而且计算因子，而且计算最佳松驰因子最佳松驰因子时还需要求得对应时还需要求得对应Jacobi矩阵矩阵的谱半径，这常常是非常困难的。的谱半径，这常常是非常困难的。现在学习的是第61页，共90页1、与、与方程组等价的方程组等价的变分变分问题问题设设 为为对称对称正定正定矩阵，矩阵，其中其中定义定义二次二次函数函数现在学习的是第62页，共90页 二次二次函数函数 的基本的基本性质性质：对对设设 为为 的解，则的解，则，且对，且对 有有现

28、在学习的是第63页，共90页设设 对称对称正定正定，则，则 为为 的解的的解的充要条件是充要条件是证明：证明：必要性由上述性质必要性由上述性质易知，下证充分性：易知，下证充分性：定理说明：求解方程组的解等价于求上述定理说明：求解方程组的解等价于求上述二次二次函数的函数的最小值最小值。常用方法：。常用方法：迭代迭代解法解法如果如果则由极值的必要条件得则由极值的必要条件得现在学习的是第64页，共90页2、最速下降最速下降法法/*Steepest Descent Method*/思想思想最速下降法最速下降法是指每次沿着函数值是指每次沿着函数值 下降最快下降最快的方向寻找的方向寻找最小值点最小值点。而

29、函数值而函数值下降最快下降最快的方向是函数的的方向是函数的负梯度负梯度方向方向 几何几何意义：意义：等值线等值线现在学习的是第65页，共90页 最速下降最速下降法的实现过程法的实现过程选取初始向量选取初始向量，由，由二次二次函数函数 的基本性质的基本性质如果如果，则，则就是方程组的解；就是方程组的解；如果如果，则沿，则沿方向进行方向进行一维极小一维极小搜索：搜索：求求步长步长，使得，使得现在学习的是第66页，共90页现在学习的是第67页，共90页注意到注意到令令，从而完成第一次迭代。，从而完成第一次迭代。下面以下面以为为新新的初值，的初值，重复重复上述过程。上述过程。现在学习的是第68页，共9

30、0页 最速下降最速下降法的算法法的算法选取初值选取初值For k=0,1,2,如果如果，停止停止否则，进行下一次循环否则，进行下一次循环搜索方向是搜索方向是正交正交的：的：缺陷：收敛速度缺陷：收敛速度慢慢现在学习的是第69页，共90页引理引理 设设 的特征值为的特征值为 ,是是 的一个实系数多项式，则的一个实系数多项式，则其中其中 。证明：证明：设设 ，且满足，且满足则有：则有：现在学习的是第70页，共90页现在学习的是第71页，共90页证明：证明：由序列由序列 的构造性质得：的构造性质得：且有且有设设 的特征值为的特征值为 ,则由前述最速下降算法产生的序列则由前述最速下降算法产生的序列 满足

31、满足其中其中 。现在学习的是第72页，共90页记记 ，则对上式应用引理，得，则对上式应用引理，得现在学习的是第73页，共90页注意到注意到代入前式得代入前式得将不等式递推下去即得定理结论。将不等式递推下去即得定理结论。上述定理说明，当上述定理说明，当 时最速下降法收敛非常慢。时最速下降法收敛非常慢。现在学习的是第74页，共90页3、共轭梯度共轭梯度法法/*Conjugate-Gradient Method*/共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免需利用一阶导数信息，但

32、克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算了牛顿法需要存储和计算HesseHesse矩阵并求逆的缺点，共轭梯度法不矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一。优化最有效的算法之一。共轭梯度法最早是由共轭梯度法最早是由HestenesHestenes和和StiefleStiefle（19521952）提出来的，用于解）提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，正定系数矩阵的线性方程组，在这个基础上，FletcherFletcher和和Reeve

33、sReeves（19641964）首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩首先提出了解非线性最优化问题的共轭梯度法。由于共轭梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经阵存储，且有较快的收敛速度和二次终止性等优点，现在共轭梯度法已经广泛地应用与实际问题中，已经成为求解大型稀疏线性方程组最受欢迎的广泛地应用与实际问题中，已经成为求解大型稀疏线性方程组最受欢迎的一类方法。一类方法。共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共共轭梯度法是一个典型的共轭方向法，它的每一个搜索方向是互相共轭的，而这些搜索方向仅仅是负梯度方向与上一

34、次迭代的搜索方向的组合，轭的，而这些搜索方向仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此存储量少，计算方便。因此存储量少，计算方便。现在学习的是第75页，共90页设设 为为对称对称正定正定矩阵，矩阵，其中其中思想思想设设 为对称为对称正定正定矩阵，若矩阵，若 中向量中向量组组满足满足则称它是则称它是 中的一个中的一个 共轭共轭（正交正交）向量组。向量组。利用利用一维极小一维极小搜索方法确定一组搜索方法确定一组共轭共轭方向方向代替代替最速下降最速下降法中的法中的正交正交方向来进行迭代。方向来进行迭代。现在学习的是第76页，共90页 共轭梯度共轭梯度法的实现过程法的实现过程选取初始向量选取初

35、始向量，如何确定下一个搜索方向呢？如何确定下一个搜索方向呢？在过点在过点的由向量的由向量和和所张成的下列二维平所张成的下列二维平面内找出函数值下降最快的方向作为搜索方向面内找出函数值下降最快的方向作为搜索方向现在学习的是第77页，共90页、和和的几何意义的几何意义此时此时 在在 上可表示为上可表示为现在学习的是第78页，共90页由极值的必要条件得由极值的必要条件得其中其中 满足满足现在学习的是第79页，共90页取下一个搜索方向为取下一个搜索方向为沿该方向进行一维搜索得步长为沿该方向进行一维搜索得步长为记记下面以下面以为为新新的迭代值，的迭代值，重复重复上述过程即可。上述过程即可。现在学习的是第

36、80页，共90页一般地，设已经得到一般地，设已经得到，则第，则第k+1步迭代的计算公式为步迭代的计算公式为终止条件：终止条件：现在学习的是第81页，共90页同时注意到同时注意到现在学习的是第82页，共90页 共轭梯度共轭梯度法的算法法的算法选取初值选取初值For k=0,1,2,n计算计算计算计算如果如果，停止停止否则，计算否则，计算进行下一次迭代进行下一次迭代现在学习的是第83页，共90页最速下降法与共轭梯度法的比较：最速下降法与共轭梯度法的比较：最速下降法：搜索方向为目标函数负梯度方向，相邻两次最速下降法：搜索方向为目标函数负梯度方向，相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈

37、锯齿搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，故前几次迭代函数值下降较快，但以后的迭代下降越状，故前几次迭代函数值下降较快，但以后的迭代下降越来越慢，尤其在接近极值点时。所以，最速下降法常与其来越慢，尤其在接近极值点时。所以，最速下降法常与其它方法联合使用，即在迭代的第一步或前几步使用，当接它方法联合使用，即在迭代的第一步或前几步使用，当接近极小点时，改为用其它算法，以此加快收敛速度。近极小点时，改为用其它算法，以此加快收敛速度。共轭梯度法：第一步搜索沿共轭梯度法：第一步搜索沿负梯度方向，然后沿负梯度的负梯度方向，然后沿负梯度的共轭方向搜索，计算效率优于共轭方向搜索，计算效率优于最

38、速下降法，对初始点没有特最速下降法，对初始点没有特殊的要求，不需要计算二阶偏殊的要求，不需要计算二阶偏导数矩阵及其逆矩阵，计算量导数矩阵及其逆矩阵，计算量与最速下降法相当，适用于各与最速下降法相当，适用于各种规模的问题。种规模的问题。Conjugate GradientGradient现在学习的是第84页，共90页由由共轭梯度共轭梯度法得到的法得到的 满足性质：满足性质：Krylov(克雷洛夫克雷洛夫)子空间子空间现在学习的是第85页，共90页 定理表明：向量组定理表明：向量组 和和 分别是分别是Krylov子空间的正交基和子空间的正交基和共轭共轭正交基。因此，共轭正交基。因此，共轭梯度法最多

39、用梯度法最多用n步便可得到方程组的精确解。步便可得到方程组的精确解。由由共轭梯度共轭梯度法计算得到的法计算得到的 近似解满足近似解满足或或现在学习的是第86页，共90页解：解：易验证系数矩阵是对称正定的易验证系数矩阵是对称正定的.例：例：用用CG迭代法求解下列方程组迭代法求解下列方程组:Step1计算计算现在学习的是第87页，共90页Step2计算计算迭代结束迭代结束现在学习的是第88页，共90页解：解：易验证系数矩阵是对称正定的易验证系数矩阵是对称正定的.例：例：用用CG迭代法求解下列方程组迭代法求解下列方程组:3xStep1计算计算现在学习的是第89页，共90页Step2计算计算迭代结束迭代结束现在学习的是第90页，共90页