求解线性方程组的迭代解法市公开课一等奖百校联赛特等奖课件.pptx

《求解线性方程组的迭代解法市公开课一等奖百校联赛特等奖课件.pptx》由会员分享，可在线阅读，更多相关《求解线性方程组的迭代解法市公开课一等奖百校联赛特等奖课件.pptx（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章线性方程组迭代解法第1页第四章目录第四章目录1 向量序列与矩阵序列极限向量序列与矩阵序列极限2 Jacobi迭代法迭代法3 GaussSeidel迭代法迭代法4 松驰法松驰法5 迭代法收敛条件及误差预计迭代法收敛条件及误差预计 5.1 矩阵谱半径矩阵谱半径 5.2 迭代法收敛条件迭代法收敛条件 5.3 误差预计误差预计6 非线性方程组迭代法非线性方程组迭代法 6.1 Newton法法 6.2 最速下降法最速下降法 第2页第四章第四章 方程组迭代解法概述方程组迭代解法概述 这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法这一章讨论线性方程组另

2、一类解法迭代迭代迭代迭代法法法法，因为迭代法能充分防止系数矩阵中零元存贮，因为迭代法能充分防止系数矩阵中零元存贮，因为迭代法能充分防止系数矩阵中零元存贮，因为迭代法能充分防止系数矩阵中零元存贮与计算，所以尤其适合用于求解系数矩阵阶数很与计算，所以尤其适合用于求解系数矩阵阶数很与计算，所以尤其适合用于求解系数矩阵阶数很与计算，所以尤其适合用于求解系数矩阵阶数很高而零元素又很多（高而零元素又很多（高而零元素又很多（高而零元素又很多（即大型稀疏即大型稀疏即大型稀疏即大型稀疏）线性方程组。）线性方程组。）线性方程组。）线性方程组。解线性方程组解线性方程组解线性方程组解线性方程组迭代法基本思想迭代法基本

3、思想迭代法基本思想迭代法基本思想与解方程迭代法与解方程迭代法与解方程迭代法与解方程迭代法相同，首先将方程组相同，首先将方程组相同，首先将方程组相同，首先将方程组AxAx=b b化为化为化为化为等价等价等价等价方程组方程组方程组方程组x x=MxMx +g g，其中其中其中其中MM为为为为n n 阶方阵，阶方阵，阶方阵，阶方阵，b b=(=(b b1 1,b b2 2,b bn n)T T，g g R Rn n，任取初始向量任取初始向量任取初始向量任取初始向量x x(0)(0)R Rn n，代入迭代公式：代入迭代公式：代入迭代公式：代入迭代公式：第3页迭代解法概述迭代解法概述(续）续）产生向量序

4、列产生向量序列产生向量序列产生向量序列 x x(k k)，若此序列若此序列若此序列若此序列收敛于收敛于收敛于收敛于x x*，则有则有则有则有x x*=*=MxMx*+g+g，即即即即x x*为原方程组解。所以，为原方程组解。所以，为原方程组解。所以，为原方程组解。所以，可依据精度要求选择一个适当可依据精度要求选择一个适当可依据精度要求选择一个适当可依据精度要求选择一个适当x x(k k)（k k充分大时）充分大时）充分大时）充分大时）作为作为作为作为近似解近似解近似解近似解，这就是解线性方程组，这就是解线性方程组，这就是解线性方程组，这就是解线性方程组迭代法迭代法迭代法迭代法，上式称为上式称为

5、上式称为上式称为迭代格式迭代格式迭代格式迭代格式，M M 称为称为称为称为迭代矩阵迭代矩阵迭代矩阵迭代矩阵，若序，若序，若序，若序列列列列 x x(k k)极限存在，称此迭代过程极限存在，称此迭代过程极限存在，称此迭代过程极限存在，称此迭代过程收敛收敛收敛收敛，不然称，不然称，不然称，不然称为为为为发散发散发散发散。第4页1 向量序列与矩阵序列极限向量序列与矩阵序列极限 与求解方程类似，需要讨论与求解方程类似，需要讨论与求解方程类似，需要讨论与求解方程类似，需要讨论问题是问题是问题是问题是：怎样建：怎样建：怎样建：怎样建立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什

6、么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量序列序列序列序列 x x(k)(k)收敛，怎样进行误差预计？收敛，怎样进行误差预计？收敛，怎样进行误差预计？收敛，怎样进行误差预计？1 向量序列与矩阵序列极限向量序列与矩阵序列极限 因为因为因为因为R Rn n中向量可与中向量可与中向量可与中向量可与R Rn n点建立一一对应关系，点建立一一对应关系，点建立一一对应关系，点建立一一对应关系，所以由点列收敛概念及向量范数等价性，可得所以由点列收敛概念及向量范数等价性，可得所以由点列收敛概念及向量范数等价性，可得所以由点列收敛概念及向量范数等价性，可得到到

7、到到向量序列收敛概念向量序列收敛概念向量序列收敛概念向量序列收敛概念。定义定义定义定义1 1第5页 向量序列与矩阵序列极限（续）向量序列与矩阵序列极限（续）n n维点列收敛一个等价描述是其对应坐标序列均维点列收敛一个等价描述是其对应坐标序列均维点列收敛一个等价描述是其对应坐标序列均维点列收敛一个等价描述是其对应坐标序列均收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。定理定理定理定理1 1 第6页矩阵序列收敛概念及定理定义定义定义定义2 2完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵

8、序列收敛：完全类似地，能够定义矩阵序列收敛：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：定理定理定理定理2 2 第7页2雅可比（Jacobi）迭代法设有设有设有设有n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：简记为：简记为：简记为：简记为：其系数矩阵其系数矩阵其系数矩阵其系数矩阵A A非奇异，不妨设非奇异，不妨设非奇异，不妨设非奇异，不妨设a aii ii 0(1,2,0(1,2,n n)可将上式可将上式可将上式可将上式改写为等价方程组：改写为等价方程组：改写为等价方程组：改写为等价方程组：第8页雅可比（Jacobi）迭代法（续）也

9、可写作为：也可写作为：也可写作为：也可写作为：可简记为：可简记为：可简记为：可简记为：由此可建立迭代格式：由此可建立迭代格式：由此可建立迭代格式：由此可建立迭代格式：第9页Jacobi迭代法定义 选取初始向量选取初始向量选取初始向量选取初始向量x x(0)(0)代入代入代入代入（4-44-4）右端，可得右端，可得右端，可得右端，可得x x(1)(1)=BxBx(0)(0)+g g，再将再将再将再将x x(1)(1)代入代入代入代入（4-44-4）右端，可得右端，可得右端，可得右端，可得x x(2)(2)=BxBx(1)(1)+g g，如此继续下去，如此继续下去，如此继续下去，如此继续下去，就产

10、生一个向量序列就产生一个向量序列就产生一个向量序列就产生一个向量序列 x x(k k)，按按按按（4-24-2）或或或或（4-34-3）格式迭代求解格式迭代求解格式迭代求解格式迭代求解方法称为方法称为方法称为方法称为雅可比（雅可比（雅可比（雅可比（JacobiJacobiJacobiJacobi）迭代法迭代法迭代法迭代法，又叫又叫又叫又叫简单迭代法简单迭代法简单迭代法简单迭代法。迭代式（迭代式（迭代式（迭代式（3-43-4）中）中）中）中B B 称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由（4-24-2）或或或或（4-34-3）得到，也可用系

11、数矩阵得到，也可用系数矩阵得到，也可用系数矩阵得到，也可用系数矩阵A A来表示：来表示：来表示：来表示：若将系数矩阵若将系数矩阵若将系数矩阵若将系数矩阵A A分解为分解为分解为分解为A A=D D L L U U，其中：其中：其中：其中：第10页Jacobi迭代法定义（续）式（式（式（式（4-54-5）为简单迭代法矩阵形式）为简单迭代法矩阵形式）为简单迭代法矩阵形式）为简单迭代法矩阵形式。第11页Jacobi迭代法举例用用用用JacobiJacobi迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：例例例例1 1解解解解：由第一个方程解：由第一个方程解：由

12、第一个方程解：由第一个方程解x x1 1，第二个方程解第二个方程解第二个方程解第二个方程解x x2 2，第三第三第三第三个方程解个方程解个方程解个方程解x x3 3得得得得JoacbiJoacbi迭代格式为：迭代格式为：迭代格式为：迭代格式为：继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表4-14-1：取取取取x x(0)(0)=(0,0,0)=(0,0,0)T T代入迭代式代入迭代式代入迭代式代入迭代式（4-64-6）或或或或（4-74-7）得：得：得：得：第12页Jacobi迭代法举例0 00.00000.00000.00000.0

13、0000.00000.00001 17.7.8.30008.30008.40008.40002 29.71009.710010.700010.700011.500011.50003 310.570010.570011.570011.570012.482012.48204 410.853510.853511.853411.853412.828212.82825 510.951010.951011.951011.951012.941412.94146 610.983410.983411.983411.983412.950412.95047 710.994410.994411.998111.9981

14、12.993412.99348 810.998110.998111.994111.994112.997812.99789 910.999410.999411.999411.999412.999212.9992表表表表4-14-1k k x x1 1(k k)x x2 2(k k)x x3 3(k k)迭代迭代迭代迭代9 9次次次次，得近似解，得近似解，得近似解，得近似解x x(9)(9)=(10.9994,11.9994,12,9992)=(10.9994,11.9994,12,9992)T T，此此此此方程组准确解为方程组准确解为方程组准确解为方程组准确解为x x=(11,12,13)=(1

15、1,12,13)T T，从从从从表表表表4-14-1能够看出，伴随能够看出，伴随能够看出，伴随能够看出，伴随迭代次数增加，迭代结果越来越靠近准确解。迭代次数增加，迭代结果越来越靠近准确解。迭代次数增加，迭代结果越来越靠近准确解。迭代次数增加，迭代结果越来越靠近准确解。第13页3 高斯高斯塞德尔塞德尔(Gauss-Seidel)迭代法迭代法 JacobiJacobi迭代法优点是公式简单，迭代矩阵轻易得到，迭代法优点是公式简单，迭代矩阵轻易得到，它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算x x(k k+1)+1)时是用时是用x x(k k)全部

16、分量代入求全部分量代入求x x(k+1)(k+1)全部分量。所以全部分量。所以需同时保留两个近似解向量需同时保留两个近似解向量x x(k k)和和x x(k k+1)+1)。第14页高斯塞德尔(Gauss-Seidel)迭代法续1第15页Gauss-Seidel迭代法求解例例2 用用用用Gauss-SeidelGauss-Seidel迭代法求解例迭代法求解例迭代法求解例迭代法求解例1 1 解：解：解：解：Gauss-SeidelGauss-Seidel迭代格式为：迭代格式为：迭代格式为：迭代格式为：仍取仍取仍取仍取x x (0)(0)=(0,0,0)=(0,0,0)T T，计算结果见下表：计算

17、结果见下表：计算结果见下表：计算结果见下表：0 00.00000.00000.00000.00000.00000.00001 17.7.9.02009.020011.644011.64402 210.430810.430811.671911.671912.820512.82053 310.931310.931311.957211.957212.977812.97784 410.991310.991311.994711.994712.997212.99725 510.998910.998911.999311.999312.999612.99966 610.999910.999911.999911

18、.999913.000013.0000k xk x1 1(k k)x x2 2(k k)x x3 3(k k)表表表表4-24-2 显然，用显然，用显然，用显然，用Gauss-SeidelGauss-Seidel 迭代法比迭代法比迭代法比迭代法比J Jacobiacobi迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论在多数情况下是成立，但也有在多数情况下是成立，但也有在多数情况下是成立，但也有在多数情况下是成立，但也有Gauss-SeidelGauss-Seidel迭代比迭代比迭代比迭代比JacuobiJacuobi迭代收迭代收迭代收迭代收敛慢，甚至还

19、有敛慢，甚至还有敛慢，甚至还有敛慢，甚至还有J Jacobiacobi迭代收敛，迭代收敛，迭代收敛，迭代收敛，Gauss-SeidelGauss-Seidel迭代发散情形。迭代发散情形。迭代发散情形。迭代发散情形。第16页求例2中Gauss-Seidel法迭代阵M两种方法第17页求例2中Gauss-Seidel法迭代阵M两种方法续1方法方法2：可按代入法求可按代入法求可按代入法求可按代入法求MM，以防止计算逆矩阵，在以防止计算逆矩阵，在以防止计算逆矩阵，在以防止计算逆矩阵，在Gauss-Gauss-SeidelSeidel迭代式迭代式迭代式迭代式（4-104-10）中，第中，第中，第中，第 二

20、个式子中以第一个式子二个式子中以第一个式子二个式子中以第一个式子二个式子中以第一个式子代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为k k（能够不论常数）能够不论常数）能够不论常数）能够不论常数）：第18页求例2中Gauss-Seidel法迭代阵M两种方法续2因为因为因为因为（4-104-10）第一式及第一式及第一式及第一式及（4-114-11），（4-124-12）右端上标均为右端上标均为右端上标均为右端上标均为k k，即即即即为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类

21、似于JacobiJacobi迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代阵为：迭代阵为：迭代阵为：迭代阵为：第19页4松驰法 经过引入参数，在经过引入参数，在经过引入参数，在经过引入参数，在Gauss-SeidelGauss-Seidel法基础上作适当修改，法基础上作适当修改，法基础上作适当修改，法基础上作适当修改，在不增加过多计算量条件下，可得到一个新，收敛在不增加过多计算量条件下，可得到一个新，收敛在不增加过多计算量条件下，可得到一个新，收敛在不增加过多计算量条件下，可得到一个新，收敛更加快迭代法。更加快迭代法。更加快迭代法。更加快迭代法。将将将将G

22、auss-SeidelGauss-Seidel迭代格式迭代格式迭代格式迭代格式（4-94-9）改写为改写为改写为改写为：第20页松驰法（续）经过选择适当参数经过选择适当参数 使此迭代格式收敛更加快。使此迭代格式收敛更加快。称为称为松驰因子松驰因子，1时称时称为为超松驰法超松驰法，=1是是Gauss-Seidel迭代迭代，简称为简称为SOR法法（Successive Over-Relaxation）。）。第21页SOR法迭代矩阵将将将将（4-134-13）代入代入代入代入（4-144-14）可得：可得：可得：可得：其矩阵其矩阵其矩阵其矩阵形式为：形式为：形式为：形式为：所以所以所以所以SORSO

23、R法迭代矩阵为：法迭代矩阵为：法迭代矩阵为：法迭代矩阵为：第22页用SOR法解线性方程组（例3）例例3 取取取取 =1.4=1.4,x x (0)(0)=(1,1,1)=(1,1,1)T T，用用用用SORSOR法解线性方程组法解线性方程组法解线性方程组法解线性方程组 第23页例 3（续1）继续下去，计算结果以下：继续下去，计算结果以下：继续下去，计算结果以下：继续下去，计算结果以下：0 01.00001.00001.00001.00001.00001.00001 11.00001.00001.00001.00001.56001.56002 21.00001.00001.39201.39201

24、.61841.61843 31.27441.27441.46821.46821.64061.64064 41.21801.21801.41361.41361.59341.59345 51.20231.20231.39161.39161.60681.60686 61.19321.19321.40341.40341.60071.60077 71.20511.20511.40271.40271.60161.60168 81.19991.19991.40001.40001.59941.59949 91.1.1.39961.39961.60011.6001表表表表4-34-3k k x x1 1(k k

25、)x x2 2(k k)x x3 3(k k)第24页例 3（续2）所以，方程组近似解为所以，方程组近似解为所以，方程组近似解为所以，方程组近似解为:松驰因子松驰因子松驰因子松驰因子 选取对收敛速度影响极大，怎样选取选取对收敛速度影响极大，怎样选取选取对收敛速度影响极大，怎样选取选取对收敛速度影响极大，怎样选取 使使使使收敛速度加紧，或到达最快？这是非常主要，但又收敛速度加紧，或到达最快？这是非常主要，但又收敛速度加紧，或到达最快？这是非常主要，但又收敛速度加紧，或到达最快？这是非常主要，但又很困难很困难很困难很困难，当前尚无可供实用计算最正确松驰因子方法，通常作法是当前尚无可供实用计算最正确

26、松驰因子方法，通常作法是当前尚无可供实用计算最正确松驰因子方法，通常作法是当前尚无可供实用计算最正确松驰因子方法，通常作法是采取采取采取采取试算法：试算法：试算法：试算法：即从同一初值出发，选不一样松驰因子进行即从同一初值出发，选不一样松驰因子进行即从同一初值出发，选不一样松驰因子进行即从同一初值出发，选不一样松驰因子进行试算，迭代相同次数，来比较残量试算，迭代相同次数，来比较残量试算，迭代相同次数，来比较残量试算，迭代相同次数，来比较残量r r (k)(k)=b b AxAx(k k)大小，大小，大小，大小，选取使选取使选取使选取使r r(k k)最小（各分量总体相差最小）松驰因子。这么最小

27、（各分量总体相差最小）松驰因子。这么最小（各分量总体相差最小）松驰因子。这么最小（各分量总体相差最小）松驰因子。这么做较简单，但比较有效。做较简单，但比较有效。做较简单，但比较有效。做较简单，但比较有效。小结以下：小结以下：第25页5迭代法收敛条件及误差预计5.1 矩阵谱半径矩阵谱半径 迭代法收敛性与迭代矩阵特征值相关：迭代法收敛性与迭代矩阵特征值相关：迭代法收敛性与迭代矩阵特征值相关：迭代法收敛性与迭代矩阵特征值相关：设设设设A A为为为为n n阶方阵，阶方阵，阶方阵，阶方阵，i i(i i=1,2,=1,2,，n n)为为为为A A特征值，特征值，特征值，特征值，称特征值模最大值为矩阵称特

28、征值模最大值为矩阵称特征值模最大值为矩阵称特征值模最大值为矩阵A A谱半径，记为：谱半径，记为：谱半径，记为：谱半径，记为：定义定义定义定义3 3第26页矩阵谱半径（续）矩阵谱半径与范数之间有以下关系：矩阵谱半径与范数之间有以下关系：矩阵谱半径与范数之间有以下关系：矩阵谱半径与范数之间有以下关系：设设设设x x为对应于特征值为对应于特征值为对应于特征值为对应于特征值 A A特征向量，则由：特征向量，则由：特征向量，则由：特征向量，则由：这个不等式对这个不等式对这个不等式对这个不等式对A A任何范数、任意特征值都成立，任何范数、任意特征值都成立，任何范数、任意特征值都成立，任何范数、任意特征值都

29、成立，所以，可得矩阵所以，可得矩阵所以，可得矩阵所以，可得矩阵A A谱半径与谱半径与谱半径与谱半径与A A范数之间一个主要范数之间一个主要范数之间一个主要范数之间一个主要关系：关系：关系：关系：A A谱半径不超出谱半径不超出谱半径不超出谱半径不超出A A任一个范数任一个范数任一个范数任一个范数。即：。即：。即：。即：第27页公式主要性说明 它之所以主要是因为：它之所以主要是因为：它之所以主要是因为：它之所以主要是因为：(A A)难计算，而难计算，而难计算，而难计算，而|A A|、|A A|1 1计算轻易，而且对于任意正数计算轻易，而且对于任意正数计算轻易，而且对于任意正数计算轻易，而且对于任意

30、正数 ，存在一个矩阵范数，存在一个矩阵范数，存在一个矩阵范数，存在一个矩阵范数很靠近很靠近很靠近很靠近 (A A)，使得成立：使得成立：使得成立：使得成立：对任意对任意对任意对任意n n 阶方阵阶方阵阶方阵阶方阵A A，普通不存在矩阵范数使普通不存在矩阵范数使普通不存在矩阵范数使普通不存在矩阵范数使 (A A)=|)=|A|A|，但若但若但若但若A A为对称矩阵为对称矩阵为对称矩阵为对称矩阵，则有：，则有：，则有：，则有：下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要 ：定理定理定理定理3 3第2

31、8页定理3（续）证实：证实：证实：证实：第29页5.2迭代法收敛条件证实：证实：证实：证实：定理定理定理定理4 4由由由由5.15.1 结果，能够得到以下收敛定理结果，能够得到以下收敛定理结果，能够得到以下收敛定理结果，能够得到以下收敛定理 ：对任意初始向量对任意初始向量对任意初始向量对任意初始向量x x(0)(0)和右端项和右端项和右端项和右端项g g，由迭代格式：由迭代格式：由迭代格式：由迭代格式：第30页迭代法收敛条件（续1）推论推论推论推论1 1第31页迭代法收敛条件（续2）推论推论推论推论2 2 定理定理定理定理4 4表明，迭代法收敛是否只决定于迭代矩阵表明，迭代法收敛是否只决定于迭

32、代矩阵表明，迭代法收敛是否只决定于迭代矩阵表明，迭代法收敛是否只决定于迭代矩阵谱半径，与初始向量及方程组右端项无关。谱半径，与初始向量及方程组右端项无关。谱半径，与初始向量及方程组右端项无关。谱半径，与初始向量及方程组右端项无关。对同一方程组，因为不一样迭代法其迭代矩阵不一样，对同一方程组，因为不一样迭代法其迭代矩阵不一样，对同一方程组，因为不一样迭代法其迭代矩阵不一样，对同一方程组，因为不一样迭代法其迭代矩阵不一样，所以可能出现有方法收敛，有方法发散情形。所以可能出现有方法收敛，有方法发散情形。所以可能出现有方法收敛，有方法发散情形。所以可能出现有方法收敛，有方法发散情形。第32页两种迭代法

33、举例例例例例4 4 讨论讨论讨论讨论JacobiJacobi迭代法与迭代法与迭代法与迭代法与Gauss-SeidelGauss-Seidel迭代法收敛性。迭代法收敛性。迭代法收敛性。迭代法收敛性。解：解：解：解：首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用推论推论推论推论1 1（充分条（充分条（充分条（充分条件）及件）及件）及件）及定理定理定理定理4 4（充分必要条件）进行讨论。（充分必要条件）进行讨论。（充分必要条件）进行讨论。（充分必要条件）进行讨论。对对对对JacobiJacobi迭代法：迭代法：迭代法：迭代法：第33页

34、例4（Jacobi迭代法续）第34页例4（G-S迭代法续）对对对对G-SG-S迭迭迭迭代法：代法：代法：代法：第35页两种迭代法说明注注1：对对对对G-SG-S法法法法，为防止，为防止，为防止，为防止求逆阵求逆阵求逆阵求逆阵可按下面两个方法：可按下面两个方法：可按下面两个方法：可按下面两个方法：第36页两种迭代法说明（续）注注2：例例例例4 4也说明也说明也说明也说明0 0 2 2确实只是松驰法确实只是松驰法确实只是松驰法确实只是松驰法必要条件必要条件必要条件必要条件，而而而而非充分条件非充分条件非充分条件非充分条件，因为，因为，因为，因为G-SG-S法法法法即为即为即为即为 =1 1情形。情

35、形。情形。情形。第37页 定理定理定理定理4 4即使给出了判别迭代法收敛充要条件，但实际即使给出了判别迭代法收敛充要条件，但实际即使给出了判别迭代法收敛充要条件，但实际即使给出了判别迭代法收敛充要条件，但实际使用时很不方便，因为求逆矩阵和特征值难度并不亚于使用时很不方便，因为求逆矩阵和特征值难度并不亚于使用时很不方便，因为求逆矩阵和特征值难度并不亚于使用时很不方便，因为求逆矩阵和特征值难度并不亚于用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论1 1仅为充分条件。很多仅为充分条件。很多仅为充分条件。很多仅为充分条件。很多情

36、况下如例情况下如例情况下如例情况下如例3 3，由推论，由推论，由推论，由推论1 1无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊方程组，从方程组本身出发给出几个惯用判别条件，方程组，从方程组本身出发给出几个惯用判别条件，方程组，从方程组本身出发给出几个惯用判别条件，方程组，从方程组本身出发给出几个惯用判别条件，而无须求迭代阵特征值或范数。而无须求迭代阵特征值或范数。而无须求迭代阵特征值或范数。而无须求迭代阵特征值或范数。直接用矩阵A判定敛散性且最少有一个且最少有一个且最少有一个且最少有一个 i i 值，使上式中不等号严格

37、成立，则值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则称称称称A A为为为为弱对角占优阵弱对角占优阵弱对角占优阵弱对角占优阵。若对全部。若对全部。若对全部。若对全部 i i，上式中不等号均上式中不等号均上式中不等号均上式中不等号均严格成立，则称严格成立，则称严格成立，则称严格成立，则称A A为为为为严格对角占优阵严格对角占优阵严格对角占优阵严格对角占优阵。定义定义定义定义4 4第38页直接用矩阵A判定敛散性（续）为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，JacobiJacobi迭代法与迭代法与迭代法与迭代法与G G-S

38、S迭代法均收敛。迭代法均收敛。迭代法均收敛。迭代法均收敛。又如例又如例又如例又如例3 3中中中中，系数矩阵：，系数矩阵：，系数矩阵：，系数矩阵：为非严格对角占优，但为非严格对角占优，但为非严格对角占优，但为非严格对角占优，但A A为对称正定矩阵，且为对称正定矩阵，且为对称正定矩阵，且为对称正定矩阵，且 =1.4=1.4 松驰法收敛。松驰法收敛。松驰法收敛。松驰法收敛。如例如例如例如例1 1中中中中，线性方程组系数矩阵：，线性方程组系数矩阵：，线性方程组系数矩阵：，线性方程组系数矩阵：设有线性方程组设有线性方程组设有线性方程组设有线性方程组AxAx=b b，以下结论成立：以下结论成立：以下结论成

39、立：以下结论成立：1.1.若若若若A A为严格对角占优阵，则为严格对角占优阵，则为严格对角占优阵，则为严格对角占优阵，则JacobiJacobi迭代法与迭代法与迭代法与迭代法与G G-S S法均收敛；法均收敛；法均收敛；法均收敛；2.2.若若若若A A为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，0 0 1 1，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；3.3.若若若若A A为对称正定矩阵，为对称正定矩阵，为对称正定矩阵，为对称正定矩阵，0 0 2 2，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；若若若若A A为对称正定阵，松驰法

40、收敛为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛 0 0 2 2。第39页三种迭代法判定敛散性举例解：解：解：解：能够总结，讨论迭代法收敛性，应首先从能够总结，讨论迭代法收敛性，应首先从能够总结，讨论迭代法收敛性，应首先从能够总结，讨论迭代法收敛性，应首先从A A出发讨出发讨出发讨出发讨论其是否含有主对角占优或对称正定性；其次对迭代法论其是否含有主对角占优或对称正定性；其次对迭代法论其是否含有主对角占优或对称正定性；其次对迭代法论其是否含有主对角占优或对称正定性；其次对迭代法迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是

41、否有范数小于1 1；最终利用迭代阵谱；最终利用迭代阵谱；最终利用迭代阵谱；最终利用迭代阵谱半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。例例例例5 5第40页例5(续）对对对对JacobiJacobi迭代法，其迭代阵轻易由迭代法，其迭代阵轻易由迭代法，其迭代阵轻易由迭代法，其迭代阵轻易由A A直接得到：直接得到：直接得到：直接得到：第41页例例6解解解解JacobiJacobi迭代阵为：迭代阵为：迭代阵为：迭代阵为：例例例例6 6第42页G-S迭代迭代阵为：阵为：第43页两点注释 注注注注1 1：值得注意是，改变方程组中

42、方程值得注意是，改变方程组中方程值得注意是，改变方程组中方程值得注意是，改变方程组中方程次序，即将系数矩阵进行行交换，次序，即将系数矩阵进行行交换，次序，即将系数矩阵进行行交换，次序，即将系数矩阵进行行交换，会改变迭代法收会改变迭代法收会改变迭代法收会改变迭代法收敛性，比如，设有方程组敛性，比如，设有方程组敛性，比如，设有方程组敛性，比如，设有方程组Ax Ax=b b，其中：其中：其中：其中：两点注释两点注释第44页两点注释（续）注注注注2 2：在利用迭代阵范数判定收敛时（推论在利用迭代阵范数判定收敛时（推论在利用迭代阵范数判定收敛时（推论在利用迭代阵范数判定收敛时（推论1 1），只要），只要

43、），只要），只要迭代阵范数小于迭代阵范数小于迭代阵范数小于迭代阵范数小于1 1，即可判，即可判，即可判，即可判 定其收敛性，但当定其收敛性，但当定其收敛性，但当定其收敛性，但当|1|1时时时时，则无法判定，还需利用谱半径作最终判定，而且，由，则无法判定，还需利用谱半径作最终判定，而且，由，则无法判定，还需利用谱半径作最终判定，而且，由，则无法判定，还需利用谱半径作最终判定，而且，由于不一样范数其值不一样，可能会出现某一个范数小于于不一样范数其值不一样，可能会出现某一个范数小于于不一样范数其值不一样，可能会出现某一个范数小于于不一样范数其值不一样，可能会出现某一个范数小于1 1但很靠近于但很靠近

44、于但很靠近于但很靠近于1 1（收敛），（收敛），（收敛），（收敛），这时另一个范数可能会大于这时另一个范数可能会大于这时另一个范数可能会大于这时另一个范数可能会大于1 1（无法判定）情况，如设（无法判定）情况，如设（无法判定）情况，如设（无法判定）情况，如设AxAx=b b，其中（见下）其中（见下）其中（见下）其中（见下）:第45页5.3误差预计定理定理定理定理5 5证实证实第46页定理5（续）利用利用利用利用定理定理定理定理5 5 对对对对例例例例1 1，若给出，若给出，若给出，若给出 =10=10 4 4，即要求各分量，即要求各分量，即要求各分量，即要求各分量误差绝对值不超出误差绝对值不超

45、出误差绝对值不超出误差绝对值不超出1010 4 4，则因为：，则因为：，则因为：，则因为：式式式式（4-204-20）惯用于事后预计误差，即在实际计算时，利用惯用于事后预计误差，即在实际计算时，利用惯用于事后预计误差，即在实际计算时，利用惯用于事后预计误差，即在实际计算时，利用相邻两次迭代值之差是否到达精度要求作为停机标准。相邻两次迭代值之差是否到达精度要求作为停机标准。相邻两次迭代值之差是否到达精度要求作为停机标准。相邻两次迭代值之差是否到达精度要求作为停机标准。这表明需要迭代这表明需要迭代这表明需要迭代这表明需要迭代1313次才能确保各分量绝对误差不超出次才能确保各分量绝对误差不超出次才能

46、确保各分量绝对误差不超出次才能确保各分量绝对误差不超出1010-4-4。第47页迭代改进法不论是用直接法还是用迭代法求得病态方程组计算解,当精度不理想时，能够使用迭代改进方法进行处理，即使用迭代改进法 此法惯用于解不十分严重病态方程组。迭代改进法：迭代改进法：（2）也可与直接法结合进行直接求解。（1）可用于改进已求得近似争精度，1.对Ax=b用列主元消元法，分解法均可，分解法（选主分解法（选主元）最好。元）最好。即：即：详细步骤为：详细步骤为：第48页迭代改进法（续1）2.求x(1)修正量z(1)：先求然后由即可即可解。而就是近似解x(1)改进解改进解.这是因为有：这是因为有：3.可继续下去：

47、再求第49页迭代改进法（续2）例例1：与准确解若用Gauss消元法求解（取五位有效数字）比较，相差太远。第50页迭代改进法（续3）若用迭代改进法：若用迭代改进法：K 0 0 0 0 0 1 9.9773 6.9786 0.0063242 0.0027559 2 8.1665 5.7110 0.00028017 0.0015411 3 8.4954 5.94130.000127740.0038975 4 8.4356 5.89940.000240940.000072077第51页迭代改进法（续4）例例2Hilbert 阵阵较准确解为若用列主元法求得近似解：对x(1)用迭代改进法进行改进：先求第5

48、2页迭代改进法（续5）用Doolittle分解法求解x(3)显然已含有四位有效数字可计算可继续求：并由Dolittle分解法解可得第53页6非线性方程组解法非线性方程组普通形式为：非线性方程组普通形式为：非线性方程组普通形式为：非线性方程组普通形式为：这一节讨论它求解方法，主要是迭代解法（因为这一节讨论它求解方法，主要是迭代解法（因为这一节讨论它求解方法，主要是迭代解法（因为这一节讨论它求解方法，主要是迭代解法（因为除了极为特殊非线性方程组以外，类似于线性方程组除了极为特殊非线性方程组以外，类似于线性方程组除了极为特殊非线性方程组以外，类似于线性方程组除了极为特殊非线性方程组以外，类似于线性方

49、程组直接解法几乎是不可能），而且这里介绍迭代解直接解法几乎是不可能），而且这里介绍迭代解直接解法几乎是不可能），而且这里介绍迭代解直接解法几乎是不可能），而且这里介绍迭代解法都采取线性化方法组成各种形式迭代格式，只介法都采取线性化方法组成各种形式迭代格式，只介法都采取线性化方法组成各种形式迭代格式，只介法都采取线性化方法组成各种形式迭代格式，只介绍方法，不讨论收敛性。绍方法，不讨论收敛性。绍方法，不讨论收敛性。绍方法，不讨论收敛性。其中：其中：其中：其中：x xi i是实变量，是实变量，是实变量，是实变量，f fi i 是是是是x xi i 非非非非线性实函数线性实函数线性实函数线性实函数(i

50、 i=1=1，2 2，n n)可可可可记为记为记为记为x x=(=(x x1 1，x x2 2，x xn n)T T，F F(x x)=()=(f f1 1(x x)，f f2 2(x x)，f fn n(x x)T T，上述方程组上述方程组上述方程组上述方程组又可记为：又可记为：又可记为：又可记为：F(x)=0第54页非线性方程组解法（续）选取一组初值选取一组初值x1(0)，x2(0)，xn(0)代入迭代代入迭代格式，可得向量序列格式，可得向量序列x(k)，而且普通有，若而且普通有，若x(k)收敛，只要收敛，只要gi连续，则收敛到原方程组连续，则收敛到原方程组解（向量形式：解（向量形式：x=