线性方程组迭代法省公共课一等奖全国赛课获奖课件.pptx

（五）（五）迭代法收敛条件迭代法收敛条件（一）（一）迭代法普通形式迭代法普通形式主要内容：主要内容：（二）（二）雅可比（雅可比（JacobiJacobi）迭代法）迭代法（三）（三）高斯高斯-赛德尔赛德尔(Gsuss-Seidel)(Gsuss-Seidel)迭代法迭代法 （四）（四）松弛法松弛法(六六)小结小结1第1页（一）普通迭代形式（一）普通迭代形式 x=Mx+g x=Mx+g （3-2）代入迭代公式x x（k+1k+1）=Mx=Mx(k)(k)+g+g (k=0,1,2,-)(k=0,1,2,-)（3-3）1、对线性方程组 Ax=b （3-1）结构同解方程组2第2页产生向量序列 ，当k充分大时，以 作为方程组（3-1）近似解-普通迭代法。主要处理问题：(1).在各种方法中，结构那种迭代格式好？(2).他们收敛性怎样？(3).在收敛条件下，最正确计算运行格式？计算近似值迭代次数.(4).各种迭代格式误差类比。3第3页2、向量序列、矩阵序列收敛性、向量序列、矩阵序列收敛性,假如定义定义3、1 设 为 中向量序列，(3-4)其中 为范数，则称 收敛于x，记为 其中 为矩阵范数，则称 收敛于A，记为 (3-5)定义定义3、2 设 为n阶方阵序列，A为n阶方阵,假如()kA4第4页定理定理3.1中向量序列 收敛于 中x当且仅当充要条件定理定理3.2 设下面 收敛于矩阵A均为n阶方阵，则矩阵序列5第5页系数矩阵A是非奇异，不妨设将方程组（3-1）变为6第6页取初始向量 代入（3-2）右边有新向量。7第7页 如此下去，产生一个序列 ，满足为中向量序列 （3-33-3）上述过程给出迭代法称雅可比迭代法（简单迭代法）。其矩阵表示为（3-4）8第8页i从1到n循环输入：置初值：输出k,xi(i=1,-,n)结束i从1到n循环输入：置初值：yesNoJacobi迭代法算法框图9第9页例例1解解10第10页0.194450.250000.166670.5000000.583330.611110.500000.66667043210k567890.601850.597220.600310.599540.60050.208330.199080.90.199850.311第11页例例2 2.用雅可比迭代法求解方程组解解：12第12页13第13页，如此下去，易知，方程组准确解为 迭代结果（当迭代次数增大时）越来越靠近准确解。14第14页clear;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.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第15页例：用Jacobi迭代法求解方程组，准确解为16第16页解：按迭代过程取初始向量，迭代10次得实际计算结果表明Jacobi迭代法收敛与准确解。17第17页 研究研究JacobiJacobi迭代法就会发觉在逐一求分量时迭代法就会发觉在逐一求分量时,当计算时都已求出当计算时都已求出,但没有被利用但没有被利用.直观上看直观上看,新算新算出分量可能比旧分量要准确出分量可能比旧分量要准确.所以所以,构想一旦当新分量已求出构想一旦当新分量已求出,马上马上就用它来就用它来代替代替,也就是在也就是在Jacobi迭代法中求迭代法中求18第18页公式（3-4）表示为 19第19页从而得迭代式上式中矩阵 为Gauss-Seidel迭代矩阵。20第20页yesNo输出k,xi(i=1,-,n)结束i从1到n循环输入：置初值：Gauss-Seidel迭代法算法框图21第21页例例3.解解22第22页0.199850.6003140.199750.199080.194450.1666700.600050.601850.611110.66667053210k23第23页例例4 4 用用Gauss-SeidelGauss-Seidel迭代法求解方程组迭代法求解方程组取初值 代入迭代式有 解解：24第24页易知，方程组准确解为 迭代结果（当迭代次数为迭代结果（当迭代次数为6 6次时）就赶上雅可比迭次时）就赶上雅可比迭代代9 9次结果。（其它情况以后再讨论）次结果。（其它情况以后再讨论）如此下去，25第25页clear;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.9.020011.644010.430811.671912.820510.931311.957212.977710.991311.994712.997210.998911.999312.999610.999911.999913.000011.000012.000013.000026第26页clear;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第27页例：用Gauss-Seidel迭代法求解方程组，准确解为。28第28页解：其迭代过程取初始向量，迭代5次得与Jacobi迭代10次精度相同。29第29页注：1.Jacobi迭代法收敛，迭代法不一定收敛；2.编程计算时，Gauss-Seidel迭代法用一 套存放单元，而Jacobi迭代法用两套存放 单元。30第30页四四.松弛法松弛法为加速迭代过程收敛，引入参数 在上得到一个新算法（3-5）按（按（3-5）计算方程组（）计算方程组（3-1）近似解序列方法为松弛法。）近似解序列方法为松弛法。为低松弛，为低松弛，为为Gauss-SeidelGauss-Seidel迭代法，迭代法，为超松弛法为超松弛法(SOR)(SOR)。31第31页例例5.用超松弛法求解方程组有迭代公式（3-5）有解：解：32第32页继续下去，方程组有解 与准确解 比较，误差为 33第33页clear;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.1.4006 1.6010 1.1.4007 1.600134第34页例：分别用Gauss-Seidel迭代法和SOR迭代法()求解方程组当取初始向量时，停顿迭代35第35页结论：v1。Gauss-Seidel迭代法要迭代72次得v2SOR迭代法()，只须迭代72次得适当选择，SOR迭代法含有显著加速收敛效果。36第36页小结 4.松弛迭代法松弛迭代法(SOR)37第37页思索与练习思索与练习 1若用Jacobi迭代法求解方程组迭代收敛充要条件是讨论实数a与收敛性关系。2若用Jacobi迭代法求解方程组38第38页五五.迭代法收敛条件迭代法收敛条件 5 51 1 矩阵谱半径矩阵谱半径 定义定义6（谱半径（谱半径)谱半径谱半径。39第39页矩阵矩阵A A谱半径与范数有以下关系：谱半径与范数有以下关系：40第40页定理定理1 1 ：设A为n阶方阵，则充要条件为 由极限存在准则，有 5 5、2 2迭代法收敛条件迭代法收敛条件证实：证实：若若必要性必要性,41第41页若若 矩阵A谱半径与范数关系有充分性充分性。42第42页 定理定理2 2 对任意初始向量 和右边g，由迭代 格式 产生向量序列 收敛条件是设存在n维向量x*，使得则x*满足 由迭代公式 证实：证实：43第43页因x0为任意n维向量，上式成立必须推论推论1 1、在定理、在定理2 2条件下，若条件下，若 ，则，则 收敛。收敛。推论推论2 2、松弛法收敛必要条件为、松弛法收敛必要条件为 。44第44页例例5。1、解：45第45页46第46页47第47页 解方程组讨论雅可比迭代法与Gauss-Seidel迭代法收敛性。（1）由定理2知迭代法是收敛等价迭代矩阵 谱半径例例5。2、解解：48第48页特征方程为雅可比迭代法收敛。49第49页（2）由Gauss-Seidel迭代法，50第50页Gauss-Seidel迭代法发散。特征方程为51第51页注注：例也说明确实 只是松弛法收敛必要条件，而非充分，因为Gauss-Seidel迭代法（）。52第52页（1-1）若矩阵为严格对角占优,即对全部方阵满足为方便给出以下判据：为方便给出以下判据：（1-2）若矩阵为弱对角占优，若最少由一个值，使下式成立。（1）：53第53页（）：（2-1）若矩阵为可约,若矩阵能经过行、列交换成为（-2）若矩阵为不可约,若矩阵不能经过行、列交换成为 54第54页矩阵为对称正定，则松弛法收敛矩阵为对称正定，则松弛法收敛如：例中系数矩阵如：例中系数矩阵 严格对角占优，严格对角占优，Jacobi迭代法迭代法和和Gauss-Seidel迭代法迭代法均收敛。均收敛。设有线性方程组，下例结论成立：设有线性方程组，下例结论成立：（）若矩阵为（）若矩阵为严格对角占优严格对角占优或为或为不可约弱对角占优不可约弱对角占优，则则Jacobi迭代法迭代法和和Gauss-Seidel迭代法迭代法均收敛。均收敛。（）若矩阵为对称正定，（）若矩阵为对称正定，则松弛法收敛则松弛法收敛（）若矩阵为严格对角占优，（）若矩阵为严格对角占优，则松弛法收敛。，则松弛法收敛。55第55页为非严格对角占优阵，但为对称正定矩阵，例中例中系数矩阵松弛法收敛。试讨论用三种迭代法求解收敛性。例、设有方程组，其中56第56页因为对称正定矩阵（各阶主子式大于零），由判别条件知Gauss-Seidel迭代法收敛，松弛法收敛。但不是弱对角占优阵，则不能用判别条件断定迭代法收敛性。只能经过计算迭代矩阵为解解：57第57页由定理知雅可比迭代法不收敛。特征方程为58第58页、误差预计、误差预计 收敛于收敛于，则有误差预计，则有误差预计定理定理、设有迭代格式、设有迭代格式注注由误差预计式（由误差预计式（3 36 6），据给定），据给定精度精度，可预计出迭代次数可预计出迭代次数：59第59页实际上实际上，60第60页定理、公式应用定理、公式应用61第61页如在例中，若要求各分量误差绝对值不超出，则由 代入（3-7）得所需迭代1次才能确保各分量误差绝对值不超出。62第62页采取采取事后误差预计事后误差预计方法方法-用用相邻两次迭代值之差相邻两次迭代值之差作为到达精度标准。作为到达精度标准。收敛于，则有误差预计更加好结论更加好结论：设有迭代格式63第63页等价极值问题等价极值问题-求解方程组两种方法求解方程组两种方法1、最速下降法；、最速下降法；2、共轭梯度法、共轭梯度法设设x*方程组方程组Ax=b准确解，准确解，Ax*=b，若，若A是正定矩阵是正定矩阵仅当仅当x=x*，二次函数，二次函数F0(x)=(x-x*)A(x-x*)=xAx-2bx+(x*)Ax*到达极小值到达极小值F0(x*)=0。这里这里F0(x)与二次函数与二次函数F(x)=xAx-2bx仅差一个常数仅差一个常数(x*)Ax*，它们极小值点是相同，它们极小值点是相同，所以解所以解Ax*=b等价于求解二次函数等价于求解二次函数F(x)极小值点极小值点x*。64第64页例、用共轭梯度法求解对称正定方程组例、用共轭梯度法求解对称正定方程组A=3-1;-1,1;b=2 0;x,k=getd(A,b)d=0.2222 0.6667d=1.0e-015*0.0000 -0.1110d=1.0e-015*-0.1110 -0.1110 x=1.0000 1.0000k=365第65页%A=2-1-1;-120;-101;b=010;x,k=getd(A,b)%d=0.50000.25000d=0.22220.11110.3333d=1.0e-016*0.00000.0000-0.5551d=1.0e-016*-0.55510.0000-0.5551x=111k=4例、用共轭梯度法求解对称正定方程组例、用共轭梯度法求解对称正定方程组66第66页function x,k=getd(A,b,x0,ep,Nmax)%用共轭梯度法求解正定系数矩阵线性方程组AX=b%A为线性方程组系数矩阵，正定对称，b为方程组右端向量%x为解向量，k为迭代次数，x0为迭代初值%ep为精度，Nmax为迭代次数上限以防发散（默认值为500）n=length(A);k=0;if nargin5 Nmax=500;endif nargin4 ep=1e-10;endif narginep&kNmax k=k+1;x0=x;alpha=(r*r)/(d*A*d);r1=r;s=alpha*d;x=x+s;r=r-A*s;beta=(r*r)/(r1*r1);d=r+beta*dendif k=Nmax warning(已迭代上限次数);end 67第67页68第68页思索与练习思索与练习 1若用Jacobi迭代法求解方程组迭代收敛充要条件是讨论实数a与收敛性关系。2若用Jacobi迭代法求解方程组69第69页3设有方程组(1)分别写出Jacobi迭代法，Gauss-Seidel迭代法和SOR法(2)对任意初值，各迭代是否收敛？说明理由。计算公式及迭代矩阵。70第70页4设有方程组试写出收敛迭代式，并说明理由。71第71页5设有方程组 (2)用迭代收敛充要条件给出使这两种 迭代法都收敛 a取值范围。(1)分别写出Jacobi迭代法和Gauss-Seidel迭代法计算公式。72第72页6分别用Jacobi迭代法和Gauss-Seidel迭代法求解方程组取初值，问迭代是否收敛？若收敛，需要迭代多少次，才能确保各分量绝对误差小于73第73页7.证实对称矩阵当为正定矩阵，且只有当时，用Jacobi迭代法求解方程组Ax=b才收敛。74第74页 若迭代法收敛速度慢时，可经过校正、利用特征若迭代法收敛速度慢时，可经过校正、利用特征值外推和最小零偏差等方法加速收敛速度。值外推和最小零偏差等方法加速收敛速度。评注评注 迭代法是求解大型线性系统（尤其是稀疏矩阵迭代法是求解大型线性系统（尤其是稀疏矩阵情形）有效方法，含有存放空间小、程序简单等特情形）有效方法，含有存放空间小、程序简单等特点。点。JacobiJacobi法法Gauss-SeidelGauss-Seidel法法SORSOR法是基本迭代方法，法是基本迭代方法，其理论形成于其理论形成于2020世纪世纪5050年代。迭代法收敛性与稀年代。迭代法收敛性与稀疏矩阵特征仅仅相关，在计算中应选取收敛速度疏矩阵特征仅仅相关，在计算中应选取收敛速度快迭代法。快迭代法。75第75页计算方法选择计算方法选择与详细问题相关。与详细问题相关。共轭梯度法与预处理技术相结合，会大大改进收共轭梯度法与预处理技术相结合，会大大改进收敛速度，得到好结果。对于非对称矩阵，将作一些敛速度，得到好结果。对于非对称矩阵，将作一些推广，如：方程残量法、共轭残量法、不完全分解推广，如：方程残量法、共轭残量法、不完全分解预优共轭梯度法和预优共轭梯度法和SSOR-CGSSOR-CG法等。法等。对于大型稀疏矩阵，一些迭代法是很有效，但对于大型稀疏矩阵，一些迭代法是很有效，但仍在发展中，因为他们收敛性问题还没有完全处理。仍在发展中，因为他们收敛性问题还没有完全处理。76第76页