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

第四章第四章线性方程组迭代解法第1页第1页第四章目录第四章目录1 向量序列与矩阵序列极限向量序列与矩阵序列极限2 Jacobi迭代法迭代法3 GaussSeidel迭代法迭代法4 松驰法松驰法5 迭代法收敛条件及误差预计迭代法收敛条件及误差预计 5.1 矩阵谱半径矩阵谱半径 5.2 迭代法收敛条件迭代法收敛条件 5.3 误差预计误差预计6 非线性方程组迭代法非线性方程组迭代法 6.1 Newton法法 6.2 最速下降法最速下降法 第2页第2页第四章第四章 方程组迭代解法概述方程组迭代解法概述 这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法这一章讨论线性方程组另一类解法迭代迭代迭代迭代法法法法，由于迭代法能充足避免系数矩阵中零元存贮，由于迭代法能充足避免系数矩阵中零元存贮，由于迭代法能充足避免系数矩阵中零元存贮，由于迭代法能充足避免系数矩阵中零元存贮与计算，因此尤其适合用于求解系数矩阵阶数很与计算，因此尤其适合用于求解系数矩阵阶数很与计算，因此尤其适合用于求解系数矩阵阶数很与计算，因此尤其适合用于求解系数矩阵阶数很高而零元素又诸多（高而零元素又诸多（高而零元素又诸多（高而零元素又诸多（即大型稀疏即大型稀疏即大型稀疏即大型稀疏）线性方程组。）线性方程组。）线性方程组。）线性方程组。解线性方程组解线性方程组解线性方程组解线性方程组迭代法基本思想迭代法基本思想迭代法基本思想迭代法基本思想与解方程迭代法与解方程迭代法与解方程迭代法与解方程迭代法相同，首先将方程组相同，首先将方程组相同，首先将方程组相同，首先将方程组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页第3页迭代解法概述迭代解法概述(续）续）产生向量序列产生向量序列产生向量序列产生向量序列 x x(k k)，若此序列若此序列若此序列若此序列收敛于收敛于收敛于收敛于x x*，则有则有则有则有x x*=*=MxMx*+g+g，即即即即x x*为原方程组解。因此，为原方程组解。因此，为原方程组解。因此，为原方程组解。因此，可依据精度要求选择一个适当可依据精度要求选择一个适当可依据精度要求选择一个适当可依据精度要求选择一个适当x x(k k)（k k充足大时）充足大时）充足大时）充足大时）作为作为作为作为近似解近似解近似解近似解，这就是解线性方程组，这就是解线性方程组，这就是解线性方程组，这就是解线性方程组迭代法迭代法迭代法迭代法，上式称为上式称为上式称为上式称为迭代格式迭代格式迭代格式迭代格式，M M 称为称为称为称为迭代矩阵迭代矩阵迭代矩阵迭代矩阵，若序，若序，若序，若序列列列列 x x(k k)极限存在，称此迭代过程极限存在，称此迭代过程极限存在，称此迭代过程极限存在，称此迭代过程收敛收敛收敛收敛，不然称，不然称，不然称，不然称为为为为发散发散发散发散。第4页第4页1 向量序列与矩阵序列极限向量序列与矩阵序列极限 与求解方程类似，需要讨论与求解方程类似，需要讨论与求解方程类似，需要讨论与求解方程类似，需要讨论问题是问题是问题是问题是：如何建：如何建：如何建：如何建立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量立迭代公式，向量序列收敛条件是什么，若向量序列序列序列序列 x x(k)(k)收敛，如何进行误差预计？收敛，如何进行误差预计？收敛，如何进行误差预计？收敛，如何进行误差预计？1 向量序列与矩阵序列极限向量序列与矩阵序列极限 由于由于由于由于R Rn n中向量可与中向量可与中向量可与中向量可与R Rn n点建立一一相应关系，点建立一一相应关系，点建立一一相应关系，点建立一一相应关系，因此由点列收敛概念及向量范数等价性，可得因此由点列收敛概念及向量范数等价性，可得因此由点列收敛概念及向量范数等价性，可得因此由点列收敛概念及向量范数等价性，可得到到到到向量序列收敛概念向量序列收敛概念向量序列收敛概念向量序列收敛概念。定义定义定义定义1 1第5页第5页 向量序列与矩阵序列极限（续）向量序列与矩阵序列极限（续）n n维点列收敛一个等价描述是其相应坐标序列均维点列收敛一个等价描述是其相应坐标序列均维点列收敛一个等价描述是其相应坐标序列均维点列收敛一个等价描述是其相应坐标序列均收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。收敛，向量序列也有类似结论。定理定理定理定理1 1 第6页第6页矩阵序列收敛概念及定理定义定义定义定义2 2完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：完全类似地，能够定义矩阵序列收敛：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：定理定理定理定理2 2 第7页第7页2雅可比（Jacobi）迭代法设有设有设有设有n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：简记为：简记为：简记为：简记为：其系数矩阵其系数矩阵其系数矩阵其系数矩阵A A非奇异，不妨设非奇异，不妨设非奇异，不妨设非奇异，不妨设a aii ii 0(1,2,0(1,2,n n)可将上式可将上式可将上式可将上式改写为等价方程组：改写为等价方程组：改写为等价方程组：改写为等价方程组：第8页第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，如此继续下去，如此继续下去，如此继续下去，如此继续下去，就产生一个向量序列就产生一个向量序列就产生一个向量序列就产生一个向量序列 x x(k k)，按按按按（4-24-2）或或或或（4-34-3）格式迭代求解格式迭代求解格式迭代求解格式迭代求解办法称为办法称为办法称为办法称为雅可比（雅可比（雅可比（雅可比（JacobiJacobiJacobiJacobi）迭代法迭代法迭代法迭代法，又叫又叫又叫又叫简朴迭代法简朴迭代法简朴迭代法简朴迭代法。迭代式（迭代式（迭代式（迭代式（3-43-4）中）中）中）中B B 称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由（4-24-2）或或或或（4-34-3）得到，也可用系数矩阵得到，也可用系数矩阵得到，也可用系数矩阵得到，也可用系数矩阵A A来表示：来表示：来表示：来表示：若将系数矩阵若将系数矩阵若将系数矩阵若将系数矩阵A A分解为分解为分解为分解为A A=D D L L U U，其中：其中：其中：其中：第10页第10页Jacobi迭代法定义（续）式（式（式（式（4-54-5）为简朴迭代法矩阵形式）为简朴迭代法矩阵形式）为简朴迭代法矩阵形式）为简朴迭代法矩阵形式。第11页第11页Jacobi迭代法举例用用用用JacobiJacobi迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：例例例例1 1解解解解：由第一个方程解：由第一个方程解：由第一个方程解：由第一个方程解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页第12页Jacobi迭代法举例0 00.00000.00000.00000.00000.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.998112.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)=(11,12,13)T T，从从从从表表表表4-14-1能够看出，伴随能够看出，伴随能够看出，伴随能够看出，伴随迭代次数增长，迭代结果越来越靠近准确解。迭代次数增长，迭代结果越来越靠近准确解。迭代次数增长，迭代结果越来越靠近准确解。迭代次数增长，迭代结果越来越靠近准确解。第13页第13页3 高斯高斯塞德尔塞德尔(Gauss-Seidel)迭代法迭代法 JacobiJacobi迭代法长处是公式简朴，迭代矩阵容易得到，迭代法长处是公式简朴，迭代矩阵容易得到，它又称为同时替换法：在每一步迭代计算过程中，计算它又称为同时替换法：在每一步迭代计算过程中，计算x x(k k+1)+1)时是用时是用x x(k k)所有分量代入求所有分量代入求x x(k+1)(k+1)所有分量。因此所有分量。因此需同时保留两个近似解向量需同时保留两个近似解向量x x(k k)和和x x(k k+1)+1)。第14页第14页高斯塞德尔(Gauss-Seidel)迭代法续1第15页第15页Gauss-Seidel迭代法求解例例2 用用用用Gauss-SeidelGauss-Seidel迭代法求解例迭代法求解例迭代法求解例迭代法求解例1 1 解：解：解：解：Gauss-SeidelGauss-Seidel迭代格式为：迭代格式为：迭代格式为：迭代格式为：仍取仍取仍取仍取x x (0)(0)=(0,0,0)=(0,0,0)T T，计算结果见下表：计算结果见下表：计算结果见下表：计算结果见下表：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.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迭代收迭代收迭代收迭代收敛慢，甚至尚有敛慢，甚至尚有敛慢，甚至尚有敛慢，甚至尚有J Jacobiacobi迭代收敛，迭代收敛，迭代收敛，迭代收敛，Gauss-SeidelGauss-Seidel迭代发散情形。迭代发散情形。迭代发散情形。迭代发散情形。第16页第16页求例2中Gauss-Seidel法迭代阵M两种办法第17页第17页求例2中Gauss-Seidel法迭代阵M两种办法续1办法办法2：可按代入法求可按代入法求可按代入法求可按代入法求MM，以避免计算逆矩阵，在以避免计算逆矩阵，在以避免计算逆矩阵，在以避免计算逆矩阵，在Gauss-Gauss-SeidelSeidel迭代式迭代式迭代式迭代式（4-104-10）中，第中，第中，第中，第 二个式子中以第一个式子二个式子中以第一个式子二个式子中以第一个式子二个式子中以第一个式子代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为k k（能够无论常数）能够无论常数）能够无论常数）能够无论常数）：第18页第18页求例2中Gauss-Seidel法迭代阵M两种办法续2由于由于由于由于（4-104-10）第一式及第一式及第一式及第一式及（4-114-11），（4-124-12）右端上标均为右端上标均为右端上标均为右端上标均为k k，即即即即为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于JacobiJacobi迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代阵为：迭代阵为：迭代阵为：迭代阵为：第19页第19页4松驰法 通过引入参数，在通过引入参数，在通过引入参数，在通过引入参数，在Gauss-SeidelGauss-Seidel法基础上作适当修改，法基础上作适当修改，法基础上作适当修改，法基础上作适当修改，在不增长过多计算量条件下，可得到一个新，收敛在不增长过多计算量条件下，可得到一个新，收敛在不增长过多计算量条件下，可得到一个新，收敛在不增长过多计算量条件下，可得到一个新，收敛更快迭代法。更快迭代法。更快迭代法。更快迭代法。将将将将Gauss-SeidelGauss-Seidel迭代格式迭代格式迭代格式迭代格式（4-94-9）改写为改写为改写为改写为：第20页第20页松驰法（续）通过选择适当参数通过选择适当参数 使此迭代格式收敛更快。使此迭代格式收敛更快。称为称为松驰因子松驰因子，1时称时称为为超松驰法超松驰法，=1是是Gauss-Seidel迭代迭代，简称为简称为SOR法法（Successive Over-Relaxation）。）。第21页第21页SOR法迭代矩阵将将将将（4-134-13）代入代入代入代入（4-144-14）可得：可得：可得：可得：其矩阵其矩阵其矩阵其矩阵形式为：形式为：形式为：形式为：因此因此因此因此SORSOR法迭代矩阵为：法迭代矩阵为：法迭代矩阵为：法迭代矩阵为：第22页第22页用SOR法解线性方程组（例3）例例3 取取取取 =1.4=1.4,x x (0)(0)=(1,1,1)=(1,1,1)T T，用用用用SORSOR法解线性方程组法解线性方程组法解线性方程组法解线性方程组 第23页第23页例 3（续1）继续下去，计算结果下列：继续下去，计算结果下列：继续下去，计算结果下列：继续下去，计算结果下列：0 01.00001.00001.00001.00001.00001.00001 11.00001.00001.00001.00001.56001.56002 21.00001.00001.39201.39201.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)x x2 2(k k)x x3 3(k k)第24页第24页例 3（续2）因此，方程组近似解为因此，方程组近似解为因此，方程组近似解为因此，方程组近似解为:松驰因子选取对收敛速度影响极大，怎样选取使收敛速度加紧，或达到最快？这是非常主要，但又很困难，当前尚无可供实用计算最正确松驰因子方法，通常作法是采取试算法：即从同一初值出发，选不同松驰因子进行试算，迭代相同次数，来比较残量r(k)=bAx(k)大小，选取使r(k)最小（各分量总体相差最小）松驰因子。这么做较简朴，但比较有效。小结下列：小结下列：第25页第25页5迭代法收敛条件及误差预计5.1 矩阵谱半径矩阵谱半径 迭代法收敛性与迭代矩阵特性值相关：迭代法收敛性与迭代矩阵特性值相关：迭代法收敛性与迭代矩阵特性值相关：迭代法收敛性与迭代矩阵特性值相关：设设设设A A为为为为n n阶方阵，阶方阵，阶方阵，阶方阵，i i(i i=1,2,=1,2,，n n)为为为为A A特性值，特性值，特性值，特性值，称特性值模最大值为矩阵称特性值模最大值为矩阵称特性值模最大值为矩阵称特性值模最大值为矩阵A A谱半径，记为：谱半径，记为：谱半径，记为：谱半径，记为：定义定义定义定义3 3第26页第26页矩阵谱半径（续）矩阵谱半径与范数之间有下列关系：矩阵谱半径与范数之间有下列关系：矩阵谱半径与范数之间有下列关系：矩阵谱半径与范数之间有下列关系：设设设设x x为相应于特性值为相应于特性值为相应于特性值为相应于特性值 A A特性向量，则由：特性向量，则由：特性向量，则由：特性向量，则由：这个不等式对这个不等式对这个不等式对这个不等式对A A任何范数、任意特性值都成立，任何范数、任意特性值都成立，任何范数、任意特性值都成立，任何范数、任意特性值都成立，因此，可得矩阵因此，可得矩阵因此，可得矩阵因此，可得矩阵A A谱半径与谱半径与谱半径与谱半径与A A范数之间一个主要范数之间一个主要范数之间一个主要范数之间一个主要关系：关系：关系：关系：A A谱半径不超出谱半径不超出谱半径不超出谱半径不超出A A任一个范数任一个范数任一个范数任一个范数。即：。即：。即：。即：第27页第27页公式主要性阐明 它之因此主要是由于：它之因此主要是由于：它之因此主要是由于：它之因此主要是由于：(A A)难计算，而难计算，而难计算，而难计算，而|A A|、|A A|1 1计算容易，并且对于任意正数计算容易，并且对于任意正数计算容易，并且对于任意正数计算容易，并且对于任意正数 ，存在一个矩阵范数，存在一个矩阵范数，存在一个矩阵范数，存在一个矩阵范数很靠近很靠近很靠近很靠近 (A A)，使得成立：使得成立：使得成立：使得成立：对任意对任意对任意对任意n n 阶方阵阶方阵阶方阵阶方阵A A，普通不存在矩阵范数使普通不存在矩阵范数使普通不存在矩阵范数使普通不存在矩阵范数使 (A A)=|)=|A|A|，但若但若但若但若A A为对称矩阵为对称矩阵为对称矩阵为对称矩阵，则有：，则有：，则有：，则有：下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要下面结论对建立迭代法收敛条件十分主要 ：定理定理定理定理3 3第28页第28页定理3（续）证实：证实：证实：证实：第29页第29页5.2迭代法收敛条件证实：证实：证实：证实：定理定理定理定理4 4由由由由5.15.1 结果，能够得到下列收敛定理结果，能够得到下列收敛定理结果，能够得到下列收敛定理结果，能够得到下列收敛定理 ：对任意初始向量对任意初始向量对任意初始向量对任意初始向量x x(0)(0)和右端项和右端项和右端项和右端项g g，由迭代格式：由迭代格式：由迭代格式：由迭代格式：第30页第30页迭代法收敛条件（续1）推论推论推论推论1 1第31页第31页迭代法收敛条件（续2）推论推论推论推论2 2定理4表明，迭代法收敛是否只决定于迭代矩阵谱半径，与初始向量及方程组右端项无关。对同一方程组，因为不同迭代法其迭代矩阵不同，因此可能出现有方法收敛，有方法发散情形。第32页第32页两种迭代法举例例例例例4 4 讨论讨论讨论讨论JacobiJacobi迭代法与迭代法与迭代法与迭代法与Gauss-SeidelGauss-Seidel迭代法收敛性。迭代法收敛性。迭代法收敛性。迭代法收敛性。解：解：解：解：首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用推论推论推论推论1 1（充足条（充足条（充足条（充足条件）及件）及件）及件）及定理定理定理定理4 4（充足必要条件）进行讨论。（充足必要条件）进行讨论。（充足必要条件）进行讨论。（充足必要条件）进行讨论。对对对对JacobiJacobi迭代法：迭代法：迭代法：迭代法：第33页第33页例4（Jacobi迭代法续）第34页第34页例4（G-S迭代法续）对对对对G-SG-S迭迭迭迭代法：代法：代法：代法：第35页第35页两种迭代法阐明注注1：对对对对G-SG-S法法法法，为避免，为避免，为避免，为避免求逆阵求逆阵求逆阵求逆阵可按下面两个办法：可按下面两个办法：可按下面两个办法：可按下面两个办法：第36页第36页两种迭代法阐明（续）注注2：例例例例4 4也阐明也阐明也阐明也阐明0 0 2 2确实只是松驰法确实只是松驰法确实只是松驰法确实只是松驰法必要条件必要条件必要条件必要条件，而而而而非充足条件非充足条件非充足条件非充足条件，由于，由于，由于，由于G-SG-S法法法法即为即为即为即为 =1 1情形。情形。情形。情形。第37页第37页 定理定理定理定理4 4即使给出了判别迭代法收敛充要条件，但实际即使给出了判别迭代法收敛充要条件，但实际即使给出了判别迭代法收敛充要条件，但实际即使给出了判别迭代法收敛充要条件，但实际使用时很不以便，由于求逆矩阵和特性值难度并不亚于使用时很不以便，由于求逆矩阵和特性值难度并不亚于使用时很不以便，由于求逆矩阵和特性值难度并不亚于使用时很不以便，由于求逆矩阵和特性值难度并不亚于用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论1 1仅为充足条件。诸多仅为充足条件。诸多仅为充足条件。诸多仅为充足条件。诸多情况下如例情况下如例情况下如例情况下如例3 3，由推论，由推论，由推论，由推论1 1无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊方程组，从方程组本身出发给出几种惯用判别条件，方程组，从方程组本身出发给出几种惯用判别条件，方程组，从方程组本身出发给出几种惯用判别条件，方程组，从方程组本身出发给出几种惯用判别条件，而不必求迭代阵特性值或范数。而不必求迭代阵特性值或范数。而不必求迭代阵特性值或范数。而不必求迭代阵特性值或范数。直接用矩阵A鉴定敛散性且至少有一个且至少有一个且至少有一个且至少有一个 i i 值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则称称称称A A为为为为弱对角占优阵弱对角占优阵弱对角占优阵弱对角占优阵。若对所有。若对所有。若对所有。若对所有 i i，上式中不等号均上式中不等号均上式中不等号均上式中不等号均严格成立，则称严格成立，则称严格成立，则称严格成立，则称A A为为为为严格对角占优阵严格对角占优阵严格对角占优阵严格对角占优阵。定义定义定义定义4 4第38页第38页直接用矩阵A鉴定敛散性（续）为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，JacobiJacobi迭代法与迭代法与迭代法与迭代法与G G-S S迭代法均收敛。迭代法均收敛。迭代法均收敛。迭代法均收敛。又如例又如例又如例又如例3 3中中中中，系数矩阵：，系数矩阵：，系数矩阵：，系数矩阵：为非严格对角占优，但为非严格对角占优，但为非严格对角占优，但为非严格对角占优，但A A为对称正定矩阵，且为对称正定矩阵，且为对称正定矩阵，且为对称正定矩阵，且 =1.4=1.4 松驰法收敛。松驰法收敛。松驰法收敛。松驰法收敛。如例如例如例如例1 1中中中中，线性方程组系数矩阵：，线性方程组系数矩阵：，线性方程组系数矩阵：，线性方程组系数矩阵：设有线性方程组设有线性方程组设有线性方程组设有线性方程组AxAx=b b，下列结论成立：下列结论成立：下列结论成立：下列结论成立：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为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛 0 0 2 2。第39页第39页三种迭代法鉴定敛散性举例解：解：解：解：能够总结，讨论迭代法收敛性，应首先从能够总结，讨论迭代法收敛性，应首先从能够总结，讨论迭代法收敛性，应首先从能够总结，讨论迭代法收敛性，应首先从A A出发讨出发讨出发讨出发讨论其是否含有主对角占优或对称正定性；另一方面对迭代法论其是否含有主对角占优或对称正定性；另一方面对迭代法论其是否含有主对角占优或对称正定性；另一方面对迭代法论其是否含有主对角占优或对称正定性；另一方面对迭代法迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于1 1；最后利用迭代阵谱；最后利用迭代阵谱；最后利用迭代阵谱；最后利用迭代阵谱半径讨论（这是充足必要条件）。半径讨论（这是充足必要条件）。半径讨论（这是充足必要条件）。半径讨论（这是充足必要条件）。例例例例5 5第40页第40页例5(续）对对对对JacobiJacobi迭代法，其迭代阵容易由迭代法，其迭代阵容易由迭代法，其迭代阵容易由迭代法，其迭代阵容易由A A直接得到：直接得到：直接得到：直接得到：第41页第41页例例6解解解解JacobiJacobi迭代阵为：迭代阵为：迭代阵为：迭代阵为：例例例例6 6第42页第42页G-S迭代迭代阵为：阵为：第43页第43页两点注释 注注注注1 1：值得注意是，改变方程组中方程值得注意是，改变方程组中方程值得注意是，改变方程组中方程值得注意是，改变方程组中方程顺序，即将系数矩阵进行行互换，顺序，即将系数矩阵进行行互换，顺序，即将系数矩阵进行行互换，顺序，即将系数矩阵进行行互换，会改变迭代法收会改变迭代法收会改变迭代法收会改变迭代法收敛性，比如，设有方程组敛性，比如，设有方程组敛性，比如，设有方程组敛性，比如，设有方程组Ax Ax=b b，其中：其中：其中：其中：两点注释两点注释第44页第44页两点注释（续）注2：在利用迭代阵范数鉴定收敛时（推论1），只要迭代阵范数小于1，即可判定其收敛性，但当|1时，则无法鉴定，还需利用谱半径作最终鉴定，而且，由于不同范数其值不同，可能会出现某一个范数小于1但很靠近于1（收敛），这时另一个范数可能会大于1（无法鉴定）情况，如设Ax=b，其中（见下）:第45页第45页5.3误差预计定理定理定理定理5 5证实证实第46页第46页定理5（续）利用利用利用利用定理定理定理定理5 5 对对对对例例例例1 1，若给出，若给出，若给出，若给出 =10=10 4 4，即要求各分量，即要求各分量，即要求各分量，即要求各分量误差绝对值不超出误差绝对值不超出误差绝对值不超出误差绝对值不超出1010 4 4，则由于：，则由于：，则由于：，则由于：式式式式（4-204-20）惯用于事后预计误差，即在实际计算时，利用惯用于事后预计误差，即在实际计算时，利用惯用于事后预计误差，即在实际计算时，利用惯用于事后预计误差，即在实际计算时，利用相邻两次迭代值之差是否达到精度要求作为停机原则。相邻两次迭代值之差是否达到精度要求作为停机原则。相邻两次迭代值之差是否达到精度要求作为停机原则。相邻两次迭代值之差是否达到精度要求作为停机原则。这表明需要迭代这表明需要迭代这表明需要迭代这表明需要迭代1313次才干确保各分量绝对误差不超出次才干确保各分量绝对误差不超出次才干确保各分量绝对误差不超出次才干确保各分量绝对误差不超出1010-4-4。第47页第47页迭代改进法无论是用直接法还是用迭代法求得病态方程组计算解,当精度不抱负时，能够使用迭代改进办法进行处理，即使用迭代改进法 此法惯用于解不十分严重病态方程组。迭代改进法：迭代改进法：（2）也可与直接法结合进行直接求解。（1）可用于改进已求得近似争精度，1.对Ax=b用列主元消元法，分解法均可，分解法（选主分解法（选主元）最好。元）最好。即：即：详细环节为：详细环节为：第48页第48页迭代改进法（续1）2.求x(1)修正量z(1)：先求然后由即可即可解。而就是近似解x(1)改进解改进解.这是由于有：这是由于有：3.可继续下去：再求第49页第49页迭代改进法（续2）例例1：与准确解若用Gauss消元法求解（取五位有效数字）比较，相差太远。第50页第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页第51页迭代改进法（续4）例例2Hilbert 阵阵较准确解为若用列主元法求得近似解：对x(1)用迭代改进法进行改进：先求第52页第52页迭代改进法（续5）用Doolittle分解法求解x(3)显然已含有四位有效数字可计算可继续求：并由Dolittle分解法解可得第53页第53页6非线性方程组解法非线性方程组普通形式为：非线性方程组普通形式为：非线性方程组普通形式为：非线性方程组普通形式为：这一节讨论它求解办法，主要是迭代解法（由于这一节讨论它求解办法，主要是迭代解法（由于这一节讨论它求解办法，主要是迭代解法（由于这一节讨论它求解办法，主要是迭代解法（由于除了极为特殊非线性方程组以外，类似于线性方程组除了极为特殊非线性方程组以外，类似于线性方程组除了极为特殊非线性方程组以外，类似于线性方程组除了极为特殊非线性方程组以外，类似于线性方程组直接解法几乎是不也许），并且这里简介迭代解直接解法几乎是不也许），并且这里简介迭代解直接解法几乎是不也许），并且这里简介迭代解直接解法几乎是不也许），并且这里简介迭代解法都采用线性化办法构成各种形式迭代格式，只介法都采用线性化办法构成各种形式迭代格式，只介法都采用线性化办法构成各种形式迭代格式，只介法都采用线性化办法构成各种形式迭代格式，只介绍办法，不讨论收敛性。绍办法，不讨论收敛性。绍办法，不讨论收敛性。绍办法，不讨论收敛性。其中：其中：其中：其中：x xi i是实变量，是实变量，是实变量，是实变量，f fi i 是是是是x xi i 非非非非线性实函数线性实函数线性实函数线性实函数(i 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页第54页非线性方程组解法（续）选取一组初值选取一组初值x1(0)，x2(0)，xn(0)代入迭代代入迭代格式，可得向量序列格式，可得向量序列x(k)，并且普通有，若并且普通有，若x(k)收敛，只要收敛，只要gi连续，则收敛到原方程组连续，则收敛到原方程组解（向量形式：解（向量形式：x=g(x)，x(k+1)=g(x(k)）。）。普通办法：将上述方程组改写等价形式：普通办法：将上述方程组改写等价形式：普通办法：将上述方程组改写等价形式：普通办法：将上述方程组改写等价形式：下面主要简介下面主要简介Newton法法 ，只简介基本办法。只简介基本办法。只简介基本办法。只简介基本办法。第55页第55页此式可展为：此式可展为：此式可展为：此式可展为：6.1Newton法按上述过程求按上述过程求按上述过程求按上述过程求F F(x x)=0)=0近似近似近似近似解办法称为解办法称为解办法称为解办法称为Newton法法 。第56页第56页第57页第57页Newton法详细做法用用Newton法详细做时：法详细做时：每迭代一次，即要解一个线性方程组（即Newton方程组）,而且每次系数矩阵F(x(k)不同。能够证实：Newton法含有二阶收敛速度。控制结束：对预先给定精度：第58页第58页两个方程情况下Newton法两个方程情况，加深理解两个方程情况，加深理解Newton法：法：第59页第59页两个方程情况下Newton法举例NewtonNewton方程组方程组方程组方程组 F F(x x)在在在在x x(0)(0)处取值，处取值，处取值，处取值，F F (x x)在在在在x x(0)(0)取值得：取值得：取值得：取值得：同单个方程同单个方程同单个方程同单个方程NwetonNweton法同样：解非线性方程组法同样：解非线性方程组法同样：解非线性方程组法同样：解非线性方程组NewtonNewton法：法：法：法：收敛快，形式简朴，格式固定。收敛快，形式简朴，格式固定。收敛快，形式简朴，格式固定。收敛快，形式简朴，格式固定。但同时也：但同时也：但同时也：但同时也：1.1.对初值要求高；对初值要求高；对初值要求高；对初值要求高；2.2.迭代一次，需计算迭代一次，需计算迭代一次，需计算迭代一次，需计算n n+n n2 2个函数值及导数值；个函数值及导数值；个函数值及导数值；个函数值及导数值；3.3.求解一个求解一个求解一个求解一个n n阶非线性方程组，计算量较大。阶非线性方程组，计算量较大。阶非线性方程组