求解线性方程组的迭代解法

《求解线性方程组的迭代解法》由会员分享，可在线阅读，更多相关《求解线性方程组的迭代解法（65页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章线性方程组迭代解法第四章目录第四章目录1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限2 Jacobi迭代法迭代法3 GaussSeidel迭代法迭代法4 松驰法松驰法5 迭代法的收敛条件及误差估计迭代法的收敛条件及误差估计 5.1 矩阵的谱半径矩阵的谱半径 5.2 迭代法的收敛条件迭代法的收敛条件 5.3 误差估计误差估计6 非线性方程组迭代法非线性方程组迭代法 6.1 Newton法法 6.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，代入迭代公式：代

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) ) 极限存在，称此迭代过程极限存在，称此迭代过程极限存在，称此迭代过程极限存在，称此迭代过程收敛收敛收敛收敛，否则称，否则称，否则称，否则称为为为为发散发散发散发散。 1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限 与求解方程类似，需要讨论的与求解方程类似，需要讨论的与求解方程类似

6、，需要讨论的与求解方程类似，需要讨论的问题是问题是问题是问题是：如何建：如何建：如何建：如何建立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量序列序列序列序列 x x(k)(k) 收敛，如何进行误差估计？收敛，如何进行误差估计？收敛，如何进行误差估计？收敛，如何进行误差估计？ 1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限 由于由于由于由于R Rn n中的向量可与中的向量可与中的向量可与中的向量可与R Rn n的点建立一一对应关系，的点建立一一对应关系，的点建立

7、一一对应关系，的点建立一一对应关系，因此由点列的收敛概念及向量范数的等价性，可得因此由点列的收敛概念及向量范数的等价性，可得因此由点列的收敛概念及向量范数的等价性，可得因此由点列的收敛概念及向量范数的等价性，可得到到到到向量序列的收敛概念向量序列的收敛概念向量序列的收敛概念向量序列的收敛概念。定义定义定义定义1 1 向量序列与矩阵序列的极限（续）向量序列与矩阵序列的极限（续） n n维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均收敛，向量序列也有类似的结论。收敛，向量序列也

8、有类似的结论。收敛，向量序列也有类似的结论。收敛，向量序列也有类似的结论。 定理定理定理定理1 1 矩阵序列的收敛概念及定理定义定义定义定义2 2完全类似地，可以定义矩阵序列的收敛：完全类似地，可以定义矩阵序列的收敛：完全类似地，可以定义矩阵序列的收敛：完全类似地，可以定义矩阵序列的收敛：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：与向量序列类似，也有：定理定理定理定理2 2 2雅可比（Jacobi）迭代法设有设有设有设有n n阶线性方程组：阶线性方程组：阶线性方程组：阶线性方程组：简记为：简记为：简记为：简记为：其系数矩阵其系数矩阵其系数矩阵其系数矩阵A A非奇异，不妨

9、设非奇异，不妨设非奇异，不妨设非奇异，不妨设a aii ii 0 (1,2, 0 (1,2,n n) )可将上式可将上式可将上式可将上式改写为等价方程组：改写为等价方程组：改写为等价方程组：改写为等价方程组：雅可比（Jacobi）迭代法（续）也可写作为：也可写作为：也可写作为：也可写作为：可简记为：可简记为：可简记为：可简记为：由此可建立迭代格式：由此可建立迭代格式：由此可建立迭代格式：由此可建立迭代格式：Jacobi迭代法定义 选取初始向量选取初始向量选取初始向量选取初始向量x x(0)(0)代入代入代入代入（4-44-4）右端，可得右端，可得右端，可得右端，可得x x(1) (1) = =

10、 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）迭代

11、法迭代法迭代法迭代法，又叫又叫又叫又叫简单迭代法简单迭代法简单迭代法简单迭代法。 迭代式（迭代式（迭代式（迭代式（3-43-4）中的）中的）中的）中的B B 称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由称为迭代矩阵，它可直接由（4-24-2）或或或或（4-34-3）得到，也可用系数矩阵得到，也可用系数矩阵得到，也可用系数矩阵得到，也可用系数矩阵A A来表示：来表示：来表示：来表示：若将系数矩阵若将系数矩阵若将系数矩阵若将系数矩阵A A分解为分解为分解为分解为A A = = D D L L U U，其中：其中：其中：其中： Jacobi迭代法定义（续）式（式（式（式（

12、4-54-5）为简单迭代法的矩阵形式）为简单迭代法的矩阵形式）为简单迭代法的矩阵形式）为简单迭代法的矩阵形式。Jacobi迭代法举例用用用用JacobiJacobi迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组：迭代法求解线性方程组： 例例例例1 1解解解解：由第一个方程解：由第一个方程解：由第一个方程解：由第一个方程解x x1 1，第二个方程解第二个方程解第二个方程解第二个方程解x x2 2，第三第三第三第三个方程解个方程解个方程解个方程解x x3 3得得得得JoacbiJoacbi迭代格式为：迭代格式为：迭代格式为：迭代格式为： 继续迭代下去，迭代结果见表继续迭代下去，迭

13、代结果见表继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表4-14-1：取取取取x x(0)(0) = (0,0,0) = (0,0,0)T T代入迭代式代入迭代式代入迭代式代入迭代式（4-64-6）或或或或（4-74-7）得：得：得：得：Jacobi迭代法举例0 00.00000.00000.00000.00000.00000.00001 17.20007.20008.30008.30008.40008.40002 29.71009.710010.700010.700011.500011.50003 310.570010.570011.570011.570012.482012.48204

14、 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

15、 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可以看出，随可以看出，随可以看出，随可以看出，随着迭代次数的增加，迭代结果越来越接近精确解。着迭代次数的增加，迭代结果越来越接近精确解。着迭代次数的增加，迭代结果越来越

16、接近精确解。着迭代次数的增加，迭代结果越来越接近精确解。 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)。 高斯

17、塞德尔(Gauss-Seidel)迭代法续1Gauss-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.20007.20009.02009.020011.6

18、44011.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 显然，

19、用显然，用显然，用显然，用Gauss-SeidelGauss-Seidel 迭代法比迭代法比迭代法比迭代法比J Jacobiacobi迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论迭代法收敛快，这个结论在多数情况下是成立的，但也有在多数情况下是成立的，但也有在多数情况下是成立的，但也有在多数情况下是成立的，但也有Gauss-SeidelGauss-Seidel迭代比迭代比迭代比迭代比JacuobiJacuobi迭代收迭代收迭代收迭代收敛慢，甚至还有敛慢，甚至还有敛慢，甚至还有敛慢，甚至还有J Jacobiacobi迭代收敛，迭代收敛，迭代收敛，迭代收敛，Gauss-Seid

20、elGauss-Seidel迭代发散的情形。迭代发散的情形。迭代发散的情形。迭代发散的情形。 求例2中的Gauss-Seidel法的迭代阵M的两种方法求例2中的Gauss-Seidel法的迭代阵M的两种方法续1方法方法2：可按代入法求可按代入法求可按代入法求可按代入法求MM，以避免计算逆矩阵，在以避免计算逆矩阵，在以避免计算逆矩阵，在以避免计算逆矩阵，在Gauss-Gauss-SeidelSeidel迭代式迭代式迭代式迭代式（4-104-10）中，第中，第中，第中，第 二个式子中的以第一个式子二个式子中的以第一个式子二个式子中的以第一个式子二个式子中的以第一个式子代替。可将第二式右端上标都化为

21、代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为k k（可以不管常数）可以不管常数）可以不管常数）可以不管常数）：求例2中的Gauss-Seidel法的迭代阵M的两种方法续2由于由于由于由于（4-104-10）第一式及第一式及第一式及第一式及（4-114-11），（4-124-12）的右端上标均为的右端上标均为的右端上标均为的右端上标均为k k ，即即即即为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于为同时替换迭代式，类似于JacobiJacobi迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得迭代法可直接由它们得

22、迭代阵为：迭代阵为：迭代阵为：迭代阵为： 4松驰法 通过引入参数，在通过引入参数，在通过引入参数，在通过引入参数，在Gauss-SeidelGauss-Seidel法的基础上作适当修改，法的基础上作适当修改，法的基础上作适当修改，法的基础上作适当修改，在不增加过多的计算量的条件下，可得到一种新的，收敛在不增加过多的计算量的条件下，可得到一种新的，收敛在不增加过多的计算量的条件下，可得到一种新的，收敛在不增加过多的计算量的条件下，可得到一种新的，收敛更快的迭代法。更快的迭代法。更快的迭代法。更快的迭代法。 将将将将Gauss-SeidelGauss-Seidel迭代格式迭代格式迭代格式迭代格式（

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

24、解线性方程组（例3）例例3 取取取取 =1.4=1.4, ,x x (0)(0) = (1,1,1) = (1,1,1)T T，用用用用SORSOR法解线性方程组法解线性方程组法解线性方程组法解线性方程组 例 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.4

25、6821.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.20001.20001.39961.39961.60011.6001表表表表4-34-3k k x x1 1( (k k) ) x x2 2( (k k) ) x x3

26、3( (k k) ) 例 3 （续2）所以，方程组近似解为所以，方程组近似解为所以，方程组近似解为所以，方程组近似解为: : 松驰因子松驰因子松驰因子松驰因子 的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取的选取对收敛速度影响极大，如何选取 使收敛速度加快，或达到最快？这是非常重要的，但又使收敛速度加快，或达到最快？这是非常重要的，但又使收敛速度加快，或达到最快？这是非常重要的，但又使收敛速度加快，或达到最快？这是非常重要的，但又很很很很困难困难困难困难，目前尚无可供实用的计算最佳松驰因子的办法，通，目前尚无可供实用的计算最佳松驰因子的办

27、法，通，目前尚无可供实用的计算最佳松驰因子的办法，通，目前尚无可供实用的计算最佳松驰因子的办法，通常的作法是采用常的作法是采用常的作法是采用常的作法是采用试算法：试算法：试算法：试算法：即从同一初值出发，选不同的松即从同一初值出发，选不同的松即从同一初值出发，选不同的松即从同一初值出发，选不同的松驰因子进行试算，迭代相同的次数，来比较残量驰因子进行试算，迭代相同的次数，来比较残量驰因子进行试算，迭代相同的次数，来比较残量驰因子进行试算，迭代相同的次数，来比较残量r r (k)(k) = = b b AxAx( (k k) ) 的大小，选取使的大小，选取使的大小，选取使的大小，选取使r r( (

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

29、 = 1,2,，n n) )为为为为A A的特征值，的特征值，的特征值，的特征值，称特征值模的最大值为矩阵称特征值模的最大值为矩阵称特征值模的最大值为矩阵称特征值模的最大值为矩阵A A的谱半径，记为：的谱半径，记为：的谱半径，记为：的谱半径，记为：定义定义定义定义3 3矩阵的谱半径（续） 矩阵的谱半径与范数之间有如下关系：矩阵的谱半径与范数之间有如下关系：矩阵的谱半径与范数之间有如下关系：矩阵的谱半径与范数之间有如下关系： 设设设设x x为对应于特征值为对应于特征值为对应于特征值为对应于特征值 的的的的A A的特征向量，则由：的特征向量，则由：的特征向量，则由：的特征向量，则由： 这个不等式对

30、这个不等式对这个不等式对这个不等式对A A的任何范数、任意特征值都成立，的任何范数、任意特征值都成立，的任何范数、任意特征值都成立，的任何范数、任意特征值都成立，因此，可得矩阵因此，可得矩阵因此，可得矩阵因此，可得矩阵A A的谱半径与的谱半径与的谱半径与的谱半径与A A的范数之间的一个重要的范数之间的一个重要的范数之间的一个重要的范数之间的一个重要关系：关系：关系：关系：A A的谱半径不超过的谱半径不超过的谱半径不超过的谱半径不超过A A的任一种范数的任一种范数的任一种范数的任一种范数。即：。即：。即：。即： 公式的重要性说明 它之所以重要是因为：它之所以重要是因为：它之所以重要是因为：它之所

31、以重要是因为： ( (A A) )难计算，而难计算，而难计算，而难计算，而| |A A| | 、 | |A A| |1 1计算容易，并且对于任意正数计算容易，并且对于任意正数计算容易，并且对于任意正数计算容易，并且对于任意正数 ，存在一种矩阵范数，存在一种矩阵范数，存在一种矩阵范数，存在一种矩阵范数很接近很接近很接近很接近 ( (A A) )，使得成立：使得成立：使得成立：使得成立： 对任意对任意对任意对任意n n 阶方阵阶方阵阶方阵阶方阵A A，一般不存在矩阵范数使一般不存在矩阵范数使一般不存在矩阵范数使一般不存在矩阵范数使 ( (A A) =|) =|A|A|，但若但若但若但若A A为对称

32、矩阵为对称矩阵为对称矩阵为对称矩阵，则有：，则有：，则有：，则有： 下面的结论对建立迭代法的收敛条件十分重要下面的结论对建立迭代法的收敛条件十分重要下面的结论对建立迭代法的收敛条件十分重要下面的结论对建立迭代法的收敛条件十分重要 ：定理定理定理定理3 3定理3（续）证明：证明：证明：证明：5.2迭代法的收敛条件证明：证明：证明：证明：定理定理定理定理4 4由由由由5.15.1 的结果，可以得到如下收敛定理的结果，可以得到如下收敛定理的结果，可以得到如下收敛定理的结果，可以得到如下收敛定理 ：对任意初始向量对任意初始向量对任意初始向量对任意初始向量x x(0)(0)和右端项和右端项和右端项和右端

33、项g g，由迭代格式：由迭代格式：由迭代格式：由迭代格式：迭代法的收敛条件（续1）推论推论推论推论1 1迭代法的收敛条件（续2）推论推论推论推论2 2 定理定理定理定理4 4表明，迭代法收敛与否只决定于迭代矩阵表明，迭代法收敛与否只决定于迭代矩阵表明，迭代法收敛与否只决定于迭代矩阵表明，迭代法收敛与否只决定于迭代矩阵的谱半径，与初始向量及方程组的右端项无关。的谱半径，与初始向量及方程组的右端项无关。的谱半径，与初始向量及方程组的右端项无关。的谱半径，与初始向量及方程组的右端项无关。 对同一方程组，由于不同的迭代法其迭代矩阵不同，因对同一方程组，由于不同的迭代法其迭代矩阵不同，因对同一方程组，由

34、于不同的迭代法其迭代矩阵不同，因对同一方程组，由于不同的迭代法其迭代矩阵不同，因此可能出现有的方法收敛，有的方法发散的情形。此可能出现有的方法收敛，有的方法发散的情形。此可能出现有的方法收敛，有的方法发散的情形。此可能出现有的方法收敛，有的方法发散的情形。两种迭代法举例例例例例4 4 讨论讨论讨论讨论JacobiJacobi迭代法与迭代法与迭代法与迭代法与Gauss-SeidelGauss-Seidel迭代法的收敛性。迭代法的收敛性。迭代法的收敛性。迭代法的收敛性。 解：解：解：解：首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用首先要求出迭代矩阵，然后利用

35、推论推论推论推论1 1（充分条（充分条（充分条（充分条件）及件）及件）及件）及定理定理定理定理4 4（充分必要条件）进行讨论。（充分必要条件）进行讨论。（充分必要条件）进行讨论。（充分必要条件）进行讨论。 对对对对JacobiJacobi迭代法：迭代法：迭代法：迭代法：例4（Jacobi迭代法续）例4（G-S迭代法续）对对对对G-SG-S迭迭迭迭代法：代法：代法：代法： 两种迭代法说明注注1：对对对对G-SG-S法法法法，为避免，为避免，为避免，为避免求逆阵求逆阵求逆阵求逆阵可按下面两个方法：可按下面两个方法：可按下面两个方法：可按下面两个方法：两种迭代法说明（续）注注2：例例例例4 4也说明

36、也说明也说明也说明0 0 2 2确实只是松驰法的确实只是松驰法的确实只是松驰法的确实只是松驰法的必要条件必要条件必要条件必要条件，而而而而非充分条件非充分条件非充分条件非充分条件，因为，因为，因为，因为G-SG-S法法法法即为即为即为即为 = = 1 1的情形。的情形。的情形。的情形。 定理定理定理定理4 4虽然给出了判别迭代法收敛的充要条件，但实际虽然给出了判别迭代法收敛的充要条件，但实际虽然给出了判别迭代法收敛的充要条件，但实际虽然给出了判别迭代法收敛的充要条件，但实际使用时很不方便，因为求逆矩阵和特征值的难度并不亚于使用时很不方便，因为求逆矩阵和特征值的难度并不亚于使用时很不方便，因为求

37、逆矩阵和特征值的难度并不亚于使用时很不方便，因为求逆矩阵和特征值的难度并不亚于用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论用直接法求解线性方程组。而推论1 1仅为充分条件。很多仅为充分条件。很多仅为充分条件。很多仅为充分条件。很多情况下如例情况下如例情况下如例情况下如例3 3，由推论，由推论，由推论，由推论1 1无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊无法判别收敛性。下面对一些特殊的方程组，从方程组本身出发给出几个常用的判别条件，的方程组，从方程组本身出发给出几个常用的判别条件，的方程组，从方程组本

38、身出发给出几个常用的判别条件，的方程组，从方程组本身出发给出几个常用的判别条件，而不必求迭代阵的特征值或范数。而不必求迭代阵的特征值或范数。而不必求迭代阵的特征值或范数。而不必求迭代阵的特征值或范数。 直接用矩阵A判定敛散性且至少有一个且至少有一个且至少有一个且至少有一个 i i 值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则值，使上式中不等号严格成立，则称称称称A A为为为为弱对角占优阵弱对角占优阵弱对角占优阵弱对角占优阵。若对所有。若对所有。若对所有。若对所有 i i，上式中不等号均上式中不等号均上式中不等号均上式中不等号均严格成立，则称严格成立

39、，则称严格成立，则称严格成立，则称A A为为为为严格对角占优阵严格对角占优阵严格对角占优阵严格对角占优阵。 定义定义定义定义4 4直接用矩阵A判定敛散性（续）为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，JacobiJacobi迭代法与迭代法与迭代法与迭代法与G G- -S S迭代法均收敛。迭代法均收敛。迭代法均收敛。迭代法均收敛。 又如例又如例又如例又如例3 3中中中中，系数矩阵：，系数矩阵：，系数矩阵：，系数矩阵：为非严格对角占优，但为非严格对角占优，但为非严格对角占优，但为非严格对角占优，但A A为对称正定矩阵，且为对称正定矩阵，且为对称正定矩阵，且为对称正定矩

40、阵，且 = 1.4 = 1.4 松驰法收敛。松驰法收敛。松驰法收敛。松驰法收敛。 如例如例如例如例1 1中中中中，线性方程组的系数矩阵：，线性方程组的系数矩阵：，线性方程组的系数矩阵：，线性方程组的系数矩阵： 设有线性方程组设有线性方程组设有线性方程组设有线性方程组AxAx= = b b，下列结论成立：下列结论成立：下列结论成立：下列结论成立：1. 1. 若若若若A A为严格对角占优阵，则为严格对角占优阵，则为严格对角占优阵，则为严格对角占优阵，则JacobiJacobi迭代法与迭代法与迭代法与迭代法与G G- -S S法均收敛；法均收敛；法均收敛；法均收敛；2. 2. 若若若若A A为严格对

41、角占优阵，为严格对角占优阵，为严格对角占优阵，为严格对角占优阵，0 0 1 1，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；3. 3. 若若若若A A为对称正定矩阵，为对称正定矩阵，为对称正定矩阵，为对称正定矩阵， 0 0 2 2，则松驰法收敛；，则松驰法收敛；，则松驰法收敛；，则松驰法收敛； 若若若若A A为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛为对称正定阵，松驰法收敛 0 0 2 2。三种迭代法判定敛散性举例解：解：解：解：可以总结，讨论迭代法的收敛性，应首先从可以总结，讨论迭代法的收敛性，应首先从可以总结，讨论迭代法的收敛性，应首先从可以

42、总结，讨论迭代法的收敛性，应首先从A A出发讨出发讨出发讨出发讨论其是否具有主对角占优或对称正定性；其次对迭代法的论其是否具有主对角占优或对称正定性；其次对迭代法的论其是否具有主对角占优或对称正定性；其次对迭代法的论其是否具有主对角占优或对称正定性；其次对迭代法的迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于迭代阵讨论其是否有范数小于1 1；最后利用迭代阵的谱；最后利用迭代阵的谱；最后利用迭代阵的谱；最后利用迭代阵的谱半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。半径讨论（这是充分必要条件）。例例例例5 5例5(续）对

43、对对对JacobiJacobi迭代法，其迭代阵容易由迭代法，其迭代阵容易由迭代法，其迭代阵容易由迭代法，其迭代阵容易由A A直接得到：直接得到：直接得到：直接得到：例例6解解解解JacobiJacobi迭代阵为：迭代阵为：迭代阵为：迭代阵为：例例例例6 6G-S迭代迭代阵为：阵为：两点注释 注注注注1 1：值得注意的是，改变方程组中方程的值得注意的是，改变方程组中方程的值得注意的是，改变方程组中方程的值得注意的是，改变方程组中方程的次序，即将系数矩阵进行行交换，次序，即将系数矩阵进行行交换，次序，即将系数矩阵进行行交换，次序，即将系数矩阵进行行交换， 会改变迭代法的收会改变迭代法的收会改变迭代

44、法的收会改变迭代法的收敛性，例如，设有方程组敛性，例如，设有方程组敛性，例如，设有方程组敛性，例如，设有方程组Ax Ax = = b b，其中：其中：其中：其中： 两点注释两点注释两点注释（续）注注注注2 2：在利用迭代阵的范数判定收敛时（推论在利用迭代阵的范数判定收敛时（推论在利用迭代阵的范数判定收敛时（推论在利用迭代阵的范数判定收敛时（推论1 1），只要），只要），只要），只要迭代阵的范数小于迭代阵的范数小于迭代阵的范数小于迭代阵的范数小于1 1，即可判，即可判，即可判，即可判 定其收敛性，但当定其收敛性，但当定其收敛性，但当定其收敛性，但当| |1| |1时时时时，则无法判定，还需利用谱

45、半径作最后判定，并且，由，则无法判定，还需利用谱半径作最后判定，并且，由，则无法判定，还需利用谱半径作最后判定，并且，由，则无法判定，还需利用谱半径作最后判定，并且，由于不同的范数其值不同，可能会出现某一种范数小于于不同的范数其值不同，可能会出现某一种范数小于于不同的范数其值不同，可能会出现某一种范数小于于不同的范数其值不同，可能会出现某一种范数小于1 1但很接近于但很接近于但很接近于但很接近于1 1（收敛），（收敛），（收敛），（收敛）， 这时另一种范数可能会大于这时另一种范数可能会大于这时另一种范数可能会大于这时另一种范数可能会大于1 1（无法判定）的情况，如设（无法判定）的情况，如设（无

46、法判定）的情况，如设（无法判定）的情况，如设AxAx = = b b，其中（见下）其中（见下）其中（见下）其中（见下）: :5.3误差估计定理定理定理定理5 5证明证明定理5（续） 利用利用利用利用定理定理定理定理5 5 对对对对例例例例1 1，若给出，若给出，若给出，若给出 =10=10 4 4，即要求各分量，即要求各分量，即要求各分量，即要求各分量的误差绝对值不超过的误差绝对值不超过的误差绝对值不超过的误差绝对值不超过1010 4 4，则由于：，则由于：，则由于：，则由于：式式式式（4-204-20） 常用于事后估计误差，即在实际计算时，利用常用于事后估计误差，即在实际计算时，利用常用于事

47、后估计误差，即在实际计算时，利用常用于事后估计误差，即在实际计算时，利用相邻两次迭代值之差是否达到精度要求作为停机标准。相邻两次迭代值之差是否达到精度要求作为停机标准。相邻两次迭代值之差是否达到精度要求作为停机标准。相邻两次迭代值之差是否达到精度要求作为停机标准。 这表明需要迭代这表明需要迭代这表明需要迭代这表明需要迭代1313次才能保证各分量绝对误差不超过次才能保证各分量绝对误差不超过次才能保证各分量绝对误差不超过次才能保证各分量绝对误差不超过1010-4-4。迭代改善法无论是用直接法还是用迭代法求得病态方程组的计算解,当精度不理想时， 可以使用迭代改善的办法进行处理，即使用迭代改善法 此法

48、常用于解不十分严重病态的方程组。迭代改善法：迭代改善法： （2）也可与直接法结合进行直接求解。（1）可用于改善已求得的近似争的精度，1.对Ax=b用列主元消元法，分解法均可，分解法（选主分解法（选主元）最好。元）最好。 即：即： 具体步骤为：具体步骤为：迭代改善法（续1）2.求x(1)的修正量z(1)：先求然后由即可即可的解。而就是近似解x(1)的改进解改进解. 这是因为有：这是因为有： 3.可继续下去：再求迭代改善法（续2）例例1： 与准确解若用Gauss消元法求解（取五位有效数字）比较，相差太远。迭代改善法（续3）若用迭代改善法：若用迭代改善法： K 0 0 0 0 0 1 9.9773

49、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迭代改善法（续4）例例2Hilbert 阵阵较准确的解为若用列主元法求得近似解：对x(1)用迭代改善法进行改进：先求迭代改善法（续5）用Doolittle分解法求解x(3)显然已具有四位有效数字可计算可继续求：并由Dolittle分解法解可得6非线性方程组的解法非线性方程组的一般形式为：非线性方程组的一般形式为：非线性方程组的一

50、般形式为：非线性方程组的一般形式为： 这一节讨论它的求解方法，主要是迭代解法（因为这一节讨论它的求解方法，主要是迭代解法（因为这一节讨论它的求解方法，主要是迭代解法（因为这一节讨论它的求解方法，主要是迭代解法（因为除了极为特殊的非线性方程组以外，类似于线性方程组除了极为特殊的非线性方程组以外，类似于线性方程组除了极为特殊的非线性方程组以外，类似于线性方程组除了极为特殊的非线性方程组以外，类似于线性方程组的直接解法几乎是不可能的），并且这里介绍的迭代解的直接解法几乎是不可能的），并且这里介绍的迭代解的直接解法几乎是不可能的），并且这里介绍的迭代解的直接解法几乎是不可能的），并且这里介绍的迭代解法

51、都采用线性化的方法构成各种形式的迭代格式，只介法都采用线性化的方法构成各种形式的迭代格式，只介法都采用线性化的方法构成各种形式的迭代格式，只介法都采用线性化的方法构成各种形式的迭代格式，只介绍方法，不讨论收敛性。绍方法，不讨论收敛性。绍方法，不讨论收敛性。绍方法，不讨论收敛性。 其中：其中：其中：其中：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

52、)=()=(f f1 1( (x x) )，f f2 2( (x x) )，f fn n( (x x) )T T，上述方程组上述方程组上述方程组上述方程组又可记为：又可记为：又可记为：又可记为：F(x)=0非线性方程组的解法（续） 选取一组初值选取一组初值x1(0)，x2(0)，xn(0)代入迭代代入迭代格式，可得向量序列格式，可得向量序列x(k)，并且一般有，若并且一般有，若x(k)收敛，只要收敛，只要gi连续，则收敛到原方程组的连续，则收敛到原方程组的解（向量形式：解（向量形式： x = g(x)，x(k+1) = g(x(k) ）。）。 一般方法：将上述方程组改写等价形式：一般方法：将上

53、述方程组改写等价形式：一般方法：将上述方程组改写等价形式：一般方法：将上述方程组改写等价形式：下面主要介绍下面主要介绍Newton法法 ，只介绍基本方法。只介绍基本方法。只介绍基本方法。只介绍基本方法。此式可展为：此式可展为：此式可展为：此式可展为：6.1Newton法按上述过程求按上述过程求按上述过程求按上述过程求F F( (x x) = 0) = 0的近的近的近的近似解的方法称为似解的方法称为似解的方法称为似解的方法称为Newton法法 。Newton法的具体做法用用Newton法具体做时：法具体做时： 每迭代一次，即要解一个线性方程组（即每迭代一次，即要解一个线性方程组（即每迭代一次，即

54、要解一个线性方程组（即每迭代一次，即要解一个线性方程组（即NewtonNewton方程组）方程组）方程组）方程组）, ,并且每次的系数矩阵并且每次的系数矩阵并且每次的系数矩阵并且每次的系数矩阵F F ( (x x( (k k) ) )不一样。不一样。不一样。不一样。 可以证明可以证明：NewtonNewton法具有二阶收敛速度。法具有二阶收敛速度。法具有二阶收敛速度。法具有二阶收敛速度。 控制结束控制结束：对预先给定的精度对预先给定的精度对预先给定的精度对预先给定的精度 ：两个方程情况下的Newton法两个方程的情况，加深理解两个方程的情况，加深理解Newton法：法： 两个方程情况下的New

55、ton法举例NewtonNewton方程组方程组方程组方程组 F F( (x x) )在在在在x x(0)(0)处取值，处取值，处取值，处取值，F F ( (x x) )在在在在x x(0)(0)取值得：取值得：取值得：取值得： 同单个方程的同单个方程的同单个方程的同单个方程的NwetonNweton法一样：解非线性方程组的法一样：解非线性方程组的法一样：解非线性方程组的法一样：解非线性方程组的NewtonNewton法：法：法：法：收敛快，形式简单，格式固定。收敛快，形式简单，格式固定。收敛快，形式简单，格式固定。收敛快，形式简单，格式固定。 但同时也：但同时也：但同时也：但同时也：1. 1

56、. 对初值要求高；对初值要求高；对初值要求高；对初值要求高； 2. 2. 迭代一次，需计算迭代一次，需计算迭代一次，需计算迭代一次，需计算n n+ +n n2 2个函数值及导数值；个函数值及导数值；个函数值及导数值；个函数值及导数值； 3. 3. 求解一个求解一个求解一个求解一个n n阶非线性方程组，计算量较大。阶非线性方程组，计算量较大。阶非线性方程组，计算量较大。阶非线性方程组，计算量较大。 6.2最速下降法这一小节只介绍大概算法，因为要用别的知识较多。这一小节只介绍大概算法，因为要用别的知识较多。最速下降法（续） 因此因此因此因此 ，非线性方程组的求解可转化为求解最优化问题，非线性方程组

57、的求解可转化为求解最优化问题，非线性方程组的求解可转化为求解最优化问题，非线性方程组的求解可转化为求解最优化问题（求（求（求（求( (x x) )的最小值）的最小值）的最小值）的最小值）并且没有任何约束条件，称为无条件约束最优化问题。并且没有任何约束条件，称为无条件约束最优化问题。并且没有任何约束条件，称为无条件约束最优化问题。并且没有任何约束条件，称为无条件约束最优化问题。 求解此类问题的一种基本方法是最速下降法。求解此类问题的一种基本方法是最速下降法。求解此类问题的一种基本方法是最速下降法。求解此类问题的一种基本方法是最速下降法。 最速下降法的最速下降法的最速下降法的最速下降法的基本思想基

58、本思想是是： 从最优化问题的近似解从最优化问题的近似解从最优化问题的近似解从最优化问题的近似解x x( (k k) )出发，沿使函数出发，沿使函数出发，沿使函数出发，沿使函数( (x x) )下下下下降最快的方向，寻找新的近似解降最快的方向，寻找新的近似解降最快的方向，寻找新的近似解降最快的方向，寻找新的近似解x x( (k k+1)+1)，这样继续下去，这样继续下去，这样继续下去，这样继续下去，逐步逼近最优化问题解。逐步逼近最优化问题解。逐步逼近最优化问题解。逐步逼近最优化问题解。最速下降法的二维说明以二维的情形看以二维的情形看以二维的情形看以二维的情形看较容易接受：较容易接受：较容易接受：

59、较容易接受： 最速下降法的二维说明（续）最速下降法的二维说明续 而在一维搜索方法中：若而在一维搜索方法中：若而在一维搜索方法中：若而在一维搜索方法中：若( ( ) )简单，就直接用一元函简单，就直接用一元函简单，就直接用一元函简单，就直接用一元函数极值方法求解。数极值方法求解。数极值方法求解。数极值方法求解。一般可用：一般可用：一般可用：一般可用：对分搜索，对分搜索，对分搜索，对分搜索，FibonacciFibonacci搜索，搜索，搜索，搜索，黄金分割，插值法等。黄金分割，插值法等。黄金分割，插值法等。黄金分割，插值法等。 用一维搜索任一种方法求出用一维搜索任一种方法求出用一维搜索任一种方法

60、求出用一维搜索任一种方法求出 后代入公式：后代入公式：后代入公式：后代入公式：即得到第即得到第即得到第即得到第k k + 1 + 1次近似解。次近似解。次近似解。次近似解。 上述整个过程就是求解上述整个过程就是求解上述整个过程就是求解上述整个过程就是求解( (x x1 1, ,x x2 2) )的的的的最速下降法最速下降法最速下降法最速下降法，最速下最速下最速下最速下降法降法降法降法优点优点优点优点是计算简单，收敛性好，是计算简单，收敛性好，是计算简单，收敛性好，是计算简单，收敛性好，但但但但收敛速度为线性，故收敛速度为线性，故收敛速度为线性，故收敛速度为线性，故收敛速度较慢，可与收敛速度较慢，可与收敛速度较慢，可与收敛速度较慢，可与NewtonNewton法法法法合用合用合用合用：先：先：先：先用最速下降法求一用最速下降法求一用最速下降法求一用最速下降法求一较好的近似值，较好的近似值，较好的近似值，较好的近似值，再再再再用用用用NewtonNewton法法法法。 对无约束最优化问题，还可用别的方法求解。对无约束最优化问题，还可用别的方法求解。对无约束最优化问题，还可用别的方法求解。对无约束最优化问题，还可用别的方法求解。