《数值分析03-线性方程组迭代解法》由会员分享，可在线阅读，更多相关《数值分析03-线性方程组迭代解法（66页珍藏版）》请在金锄头文库上搜索。
1、第三章 线性方程组 迭代解法3-1阜师院数科院第三章 线性方程组迭代解法第三章目录1 1 向量序列与矩阵序列的极限向量序列与矩阵序列的极限 2 2 JacobiJacobi迭代法迭代法 3 3 GaussSeidelGaussSeidel迭代法迭代法 4 4 松驰法松驰法 5 5 迭代法的收敛条件及误差估计迭代法的收敛条件及误差估计5.1 5.1 矩阵的谱半径矩阵的谱半径5.2 5.2 迭代法的收敛条件迭代法的收敛条件5.3 5.3 误差估计误差估计 6 6 非线性方程组迭代法非线性方程组迭代法6.1 6.1 NewtonNewton法法6.2 6.2 最速下降法最速下降法 2阜师院数科院第三
2、章 线性方程组迭代解法第三章 方程组的迭代解法概述这一章讨论线性方程组的另一类解法这一章讨论线性方程组的另一类解法迭代法迭代法，由于，由于 迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别迭代法能充分避免系数矩阵中零元的存贮与计算，因此特别 适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏）适用于求解系数矩阵阶数很高而零元素又很多（即大型稀疏） 的线性方程组。的线性方程组。解线性方程组的迭代法的解线性方程组的迭代法的基本思想基本思想与解方程的迭代法相与解方程的迭代法相 似，首先将方程组似，首先将方程组AxAx = = b b化为等价方程组化为等价方程组x x = = MxMx + +
3、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， 代入迭代公式：代入迭代公式：产生向量序列产生向量序列 x x( (k k) ) ，若此序列收敛于若此序列收敛于x x* *，则有则有x x* = * = MxMx* *+g+g，即即 x x* *为原方程组的解。因此，可根据精度要求选择一个合适的为原方程组的解。因此，可根据精度要求选择一个合适的x x( (k k) )（k k充分大时）作为近似解，这就是解线性方程组的迭代法，充分大时）作
4、为近似解，这就是解线性方程组的迭代法， 上式称为迭代格式，上式称为迭代格式，MM称为迭代矩阵，若序列称为迭代矩阵，若序列 x x( (k k) ) 极限存极限存 在，称此迭代过程收敛，否则称为发散。在，称此迭代过程收敛，否则称为发散。3阜师院数科院第三章 线性方程组迭代解法1 向量序列与矩阵序列的极限与求解方程类似，需要讨论的问题是：如何建与求解方程类似，需要讨论的问题是：如何建 立迭代公式，向量序列的收敛条件是什么，若向量立迭代公式，向量序列的收敛条件是什么，若向量 序列序列 x x( (k k) ) 收敛，如何进行误差估计？收敛，如何进行误差估计？ 1 1 向量序列与矩阵序列的极限向量序列
5、与矩阵序列的极限由于由于R Rn n中的向量可与中的向量可与R Rn n的点建立一一对应关系，的点建立一一对应关系， 因此由点列的收敛概念及向量范数的等价性，可得因此由点列的收敛概念及向量范数的等价性，可得 到向量序列的收敛概念。到向量序列的收敛概念。 定义定义1 14阜师院数科院第三章 线性方程组迭代解法向量序列与矩阵序列的极限（续） n n维点列收敛的一种等价描述是其对应坐标序列均维点列收敛的一种等价描述是其对应坐标序列均 收敛，向量序列也有类似的结论。收敛，向量序列也有类似的结论。 定理定理1 15阜师院数科院第三章 线性方程组迭代解法矩阵序列的收敛概念及定理定义定义2 2完全类似地，可
6、以定义矩阵序列的收敛：完全类似地，可以定义矩阵序列的收敛：与向量序列类似，也有：与向量序列类似，也有：定理定理2 2 6阜师院数科院第三章 线性方程组迭代解法2 雅可比（Jacobi）迭代法 设有设有n n阶线性方程组：阶线性方程组：简记为：简记为：其系数矩阵其系数矩阵A A非奇异，不妨设非奇异，不妨设a aii ii 0 (1,2, 0 (1,2,n n) )可将上式可将上式 改写为等价方程组：改写为等价方程组：7阜师院数科院第三章 线性方程组迭代解法雅可比（Jacobi）迭代法（续）也可也可写作为：写作为：可简记为：可简记为：由此可建立迭代格式：由此可建立迭代格式：8阜师院数科院第三章 线
7、性方程组迭代解法Jacobi迭代法定义选取初始向量选取初始向量x x(0)(0)代入（代入（4-44-4）右端，可得）右端，可得x x(1) (1) = = BxBx(0) (0) + + g g，再将再将x x (1)(1)代入（代入（3-43-4）右端，可得）右端，可得x x(2) (2) = = BxBx(1) (1) + + g g，如此继续下去，如此继续下去，就产生一个向量序列就产生一个向量序列 x x( (k k) ) ，按（按（3-23-2）或（）或（3-33-3）格式迭代求解）格式迭代求解 的方法称为的方法称为雅可比（雅可比（JacobiJacobi）迭代法迭代法，又叫，又叫简
8、单迭代法简单迭代法。迭代式（迭代式（3-43-4）中的）中的B B 称为迭代矩阵，它可直接由（称为迭代矩阵，它可直接由（3-23-2） 或（或（3-33-3）得到，也可用系数矩阵）得到，也可用系数矩阵A A来表示：来表示：若将系数矩阵若将系数矩阵A A分解为分解为A A = = D D L L U U，其中：其中： 9阜师院数科院第三章 线性方程组迭代解法Jacobi迭代法定义（续）式（式（3-53-5）为简单迭代法的矩阵形式）为简单迭代法的矩阵形式。10阜师院数科院第三章 线性方程组迭代解法Jacobi迭代法举例用用JacobiJacobi迭代法求解线性方程组：迭代法求解线性方程组：例例1
9、1 解解：由第一个方程解：由第一个方程解x x1 1，第二个方程解第二个方程解x x2 2，第三第三 个方程解个方程解x x3 3得得JoacbiJoacbi迭代格式为：迭代格式为： 继续迭代下去，迭代结果见表继续迭代下去，迭代结果见表3-13-1：取取x x(0)(0) = (0,0,0)= (0,0,0)T T代入迭代式代入迭代式 （3-63-6）或（）或（3-73-7）得：）得：11阜师院数科院第三章 线性方程组迭代解法Jacobi迭代法举例 0 00.00000.00000.00000.00000.00000.00001 17.20007.20008.30008.30008.40008
10、.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.
11、994112.997812.99789 910.999410.999411.999411.999412.999212.9992表表3-13-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，从从表表3-13-1可以看出，随着迭可以看出，随着迭 代次数的增加，迭代结果越来越接近
12、精确解。代次数的增加，迭代结果越来越接近精确解。 12阜师院数科院第三章 线性方程组迭代解法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
13、k+1)+1)。 13阜师院数科院第三章 线性方程组迭代解法高斯塞德尔(Gauss-Seidel)迭代法续114阜师院数科院第三章 线性方程组迭代解法Gauss-Seidel迭代法求解 例例2 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.02
14、0011.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) ) xx3 3( (k k) )表表3-23-2显然，
15、用显然，用Gauss-SeidelGauss-Seidel迭代法比迭代法比JacobiJacobi迭代法收敛快，这个结论迭代法收敛快，这个结论 在多数情况下是成立的，但也有在多数情况下是成立的，但也有Gauss-SeidelGauss-Seidel迭代比迭代比JacuobiJacuobi迭代收迭代收 敛慢，甚至还有敛慢，甚至还有JacobiJacobi迭代收敛，迭代收敛，Gauss-SeidelGauss-Seidel迭代发散的情形。迭代发散的情形。 15阜师院数科院第三章 线性方程组迭代解法求例2中的Gauss-Seidel法的迭代阵M的两种方法16阜师院数科院第三章 线性方程组迭代解法求例2中的Gauss-Seidel法的迭代阵M的两种方法续1方法方法2 2：可按代入法求可按代入法求MM，以避免计算逆矩阵，在以避免计算逆矩阵，在Gauss-Gauss- SeidelSeidel迭代式（迭代式（3-103-10）中，第）中，第 二个式子中的以第一个式子二个式子中的以第一个式子 代替。可将第二式右端上标都化为代替。可将第二式右端上标都化为k k（可以不管常数）：可以不管常数）：17阜师院数科院第三章 线性方程组迭代解法求例2中的Gauss-Seidel法的迭代阵M的两种方法续2由于（由于（3-103-10）第一式及（）第一式及（3-113
