(完整版)第三章线性方程组迭代法

（五）（五）迭代法的收敛条件迭代法的收敛条件（一）（一）迭代法的一般形式迭代法的一般形式主要内容：主要内容：（二）（二）雅可比（雅可比（JacobiJacobi）迭代法）迭代法（三）（三）高斯高斯-赛德尔赛德尔(GsussGsuss-Seidel)-Seidel)迭代法迭代法 （四）（四）松弛法松弛法(六六)小结小结1（一）一般迭代形式（一）一般迭代形式 x=x=Mx+gMx+g （3-2）代入迭代公式x x（k+1k+1）=MxMx(k)(k)+g+g (k=0,1,2,-)(k=0,1,2,-)（3-3）1、对线性方程组 Ax=b （3-1）构造同解方程组2产生向量序列 ，当k充分大时，以 作为方程组（3-1）的近似解-一般迭代法。主要解决的问题：(1).在多种方法中，构造那种迭代格式的好？(2).他们的收敛性如何？(3).在收敛的条件下，最佳计算运行格式？计算近似值的迭代次数.(4).多种迭代格式误差的类比。32、向量序列、矩阵序列的收敛性、向量序列、矩阵序列的收敛性,如果定义定义3、1 设 为 中向量序列，(3-4)其中 为范数，则称 收敛于x，记为 其中 为矩阵范数，则称 收敛于A，记为 (3-5)定义定义3、2 设 为n阶方阵序列，A为n阶方阵,如果()kA4定理定理3.1中的向量序列 收敛于 中的x当且仅当充要条件定理定理3.2 设下面 收敛于矩阵A的均为n阶方阵，则矩阵序列5系数矩阵A是非奇异的，不妨设将方程组（3-1）变为6取初始向量 代入（3-2）右边有新向量。7 如此下去，产生一个序列 ，满足为中向量序列 （3-33-3）上述过程给出的迭代法称雅可比迭代法（简单迭代法）。其矩阵表示为（3-4）8i从1到n循环输入：置初值：输出k,xi(i=1,-,n)结束i从1到n循环输入：置初值：yesNoJacobi迭代法的算法框图9例例1解解100.194450.250000.166670.5000000.583330.611110.500000.66667043210k567890.601850.597220.600310.599540.60050.208330.199080.201390.199850.2002311例例2 2.用雅可比迭代法求解方程组解解：1213，如此下去，易知，方程组的精确解为 迭代结果（当迭代次数增大时）越来越接近精确解。14clear;fprintf(Jacobi迭代法)x1(1)=0;x2(1)=0;x3(1)=0;for i=1:10 x1(i+1)=7.2+0.1*x2(i)+0.2*x3(i);x2(i+1)=8.3+0.1*x1(i)+0.2*x3(i);x3(i+1)=8.4+0.2*x1(i)+0.2*x2(i);endx=x1,x2,x3x=0 0 0 7.2000 8.3000 8.4000 9.7100 10.7000 11.5000 10.5700 11.5710 12.4820 10.8535 11.8534 12.8282 10.9510 11.9510 12.9414 10.9834 11.9834 12.9804 10.9944 11.9944 12.9933 10.9981 11.9981 12.9978 10.9994 11.9994 12.9992 10.9998 11.9998 12.999715例：用Jacobi迭代法求解方程组，精确解为16解：按迭代过程取初始向量，迭代10次得实际计算结果表明Jacobi迭代法收敛与精确解。17 研究研究JacobiJacobi迭代法就会发现在逐个求的分量迭代法就会发现在逐个求的分量时时,当计算时都已求出当计算时都已求出,但没有被利用但没有被利用.直观上看直观上看,新算出的分量可能比旧的分量要准确新算出的分量可能比旧的分量要准确.因此因此,设想一旦当新分量已求出设想一旦当新分量已求出,马上马上就用它来就用它来代替代替,也就是在也就是在Jacobi迭代法中求迭代法中求18公式（3-4）表示为 19从而得迭代式上式中矩阵 为Gauss-Seidel迭代矩阵。20yesNo输出k,xi(i=1,-,n)结束i从1到n循环输入：置初值：Gauss-Seidel迭代法的算法框图21例例3.解解220.199850.6003140.199750.199080.194450.1666700.600050.601850.611110.66667053210k23例例4 4 用用Gauss-SeidelGauss-Seidel迭代法求解方程组迭代法求解方程组取初值 代入迭代式有 解解：24易知，方程组的精确解为 迭代结果（当迭代次数为迭代结果（当迭代次数为6 6次时）就赶上雅可比迭次时）就赶上雅可比迭代代9 9次的结果。（其它情况以后再讨论）次的结果。（其它情况以后再讨论）如此下去，25clear;fprintf(Gauss-Seidel迭代法)x1(1)=0;x2(1)=0;x3(1)=0;for i=1:7 x1(i+1)=7.2+0.1*x2(i)+0.2*x3(i);x2(i+1)=8.3+0.1*x1(i+1)+0.2*x3(i);x3(i+1)=8.4+0.2*x1(i+1)+0.2*x2(i+1);endx=x1,x2,x3Gauss-Seidel迭代法迭代法x=0007.20009.020011.644010.430811.671912.820510.931311.957212.977710.991311.994712.997210.998911.999312.999610.999911.999913.000011.000012.000013.000026clear;fprintf(SOR(超松弛)迭代法)x1(1)=0;x2(1)=0;x3(1)=0;for i=1:7 x1(i+1)=(1-1.42)*x1(i)+1.42/10*(7.2+0.1*x2(i)+0.2*x3(i);x2(i+1)=(1-1.42)*x1(i)+1.42/10*(8.3+0.1*x1(i+1)+0.2*x3(i);x3(i+1)=(1-1.42)*x1(i)+1.42/5*(8.4+0.2*x1(i+1)+0.2*x2(i+1);endx=x1,x2,x3SOR(超松弛)迭代法x=0 0 0 1.0224 1.1931 2.5114 0.6813 0.8302 2.0420 0.8061 0.9619 2.1999 0.7600 0.9133 2.1421 0.7770 0.9313 2.1634 0.7707 0.9246 2.1556 0.7730 0.9271 2.158527例：用Gauss-Seidel迭代法求解方程组，精确解为。28解：其迭代过程取初始向量，迭代5次得与Jacobi迭代10次的精度相同。29注：1.Jacobi迭代法收敛，迭代法不一定收敛；2.编程计算时，Gauss-Seidel迭代法用一 套存储单元，而Jacobi迭代法用两套存储 单元。30四四.松弛法松弛法为加速迭代过程的收敛，引入参数 在上得到一种新算法（3-5）按（按（3-5）计算方程组（）计算方程组（3-1）的近似解序列的方法为松弛法。）的近似解序列的方法为松弛法。为低松弛，为低松弛，为为Gauss-SeidelGauss-Seidel迭代法，迭代法，为超松弛法为超松弛法(SOR)(SOR)。31例例5.用超松弛法求解方程组有迭代公式（3-5）有解：解：32继续下去，方程组有解 与精确解 比较，误差为 33clear;fprintf(SOR(超松弛)迭代法)x1(1)=1;x2(1)=1;x3(1)=1;for i=1:9 x1(i+1)=(1-1.4)*x1(i)+1.4/2*(1+x2(i);x2(i+1)=(1-1.4)*x2(i)+1.4/2*(x1(i+1)+x3(i);x3(i+1)=(1-1.4)*x3(i)+1.4/2*(1.8+x2(i+1);endx=x1,x2,x3SOR(超松弛)迭代法x=1.0000 1.0000 1.0000 1.0000 1.0000 1.5600 1.0000 1.3920 1.6104 1.2744 1.4626 1.6396 1.2140 1.4125 1.5929 1.2032 1.3922 1.5974 1.1933 1.3966 1.5987 1.2003 1.4006 1.6010 1.2003 1.4007 1.600134例：分别用Gauss-Seidel迭代法和SOR迭代法()求解方程组当取初始向量时，停止迭代35结论：v1。Gauss-Seidel迭代法要迭代72次得v2SOR迭代法()，只须迭代72次得适当选择，SOR迭代法具有明显的加速收敛效果。36小结 4.松弛迭代法松弛迭代法(SOR)37思考与练习思考与练习 1若用Jacobi迭代法求解方程组迭代收敛的充要条件是讨论实数a与收敛性的关系。2若用Jacobi迭代法求解方程组38五五.迭代法的收敛条件迭代法的收敛条件 5 51 1 矩阵的谱半径矩阵的谱半径 定义定义6（谱半径（谱半径)谱半径谱半径。39矩阵矩阵A A的谱半径与范数有如下关系：的谱半径与范数有如下关系：40定理定理1 1 ：设A为n阶方阵，则的充要条件为 由极限存在准则，有 5 5、2 2迭代法的收敛条件迭代法的收敛条件证明：证明：若若必要性必要性,41若若 矩阵A的谱半径与范数的关系有充分性充分性。42 定理定理2 2 对任意初始向量 和右边g，由迭代 格式 产生向量序列 收敛条件是设存在n维向量x*，使得则x*满足 由迭代公式 证明：证明：43因x0为任意n维向量，上式成立必须推论推论1 1、在定理、在定理2 2条件下，若条件下，若 ，则，则 收敛。收敛。推论推论2 2、松弛法收敛的必要条件为、松弛法收敛的必要条件为 。44例例5。1、解：454647解方程组讨论雅可比迭代法与Gauss-Seidel迭代法的收敛性。（1）由定理2知迭代法是收敛等价迭代矩阵 的谱半径例例5。2、解解：48特征方程为雅可比迭代法收敛。49（2）由Gauss-Seidel迭代法，50Gauss-Seidel迭代法发散。特征方程为51注注：例也说明确实 只是松弛法收敛的必要条件，而非充分的，因为Gauss-Seidel迭代法（）。52（1-1）若矩阵为严格对角占优,即对所有的方阵满足为方便给出以下判据：为方便给出以下判据：（1-2）若矩阵为弱对角占优，若至少由一个值，使下式成立。（1）：53（）：（2-1）若矩阵为可约,若矩阵能通过行、列的互换成为（-2）若矩阵为不可约,若矩阵不能通过行、列的互换成为 54矩阵为对称正定的，则松弛法收敛矩阵为对称正定的，则松弛法收敛如：例中系数矩阵如：例中系数矩阵 严格对角占优，严格对角占优，Jacobi迭代法迭代法和和Gauss-Seidel迭代法迭代法均收敛。均收敛。设有线性方程组，下例结论成立：设有线性方程组，下例结论成立：（）若矩阵为（）若矩阵为严格对角占优严格对角占优或为或为不可约弱对角占优不可约弱对角占优，则则Jacobi迭代法迭代法和和Gauss-Seidel迭代法迭代法均收敛。均收敛。（）若矩阵为对称正定的，（）若矩阵为对称正定的，则松弛法收敛则松弛法收敛（）若矩阵为严格对角占优，（）若矩阵为严格对角占优，则松弛法收敛。，则松弛法收敛。55为非严格对角占优阵，但为对称正定矩阵，例中例中系数矩阵松弛法收敛。试讨论用三种迭代法求解的收敛性。例、设有方程组，其中56因为对称正定矩阵（各阶主子式大于零），由判别条件知Gauss-Seidel迭代法收敛，松弛法收敛。但不是弱对角占优阵，则不能用判别条件断定迭代法收敛性。只能通过计算迭代矩阵为解解：57由定理知雅可比迭代法不收敛。特征方程为58、误差估计、误差估计 收敛于收敛于，则有误差估计，则有误差估计定理定理、设有迭代格式、设有迭代格式注注由误差估计式（由误差估计式（