《第四章线性方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx》由会员分享，可在线阅读，更多相关《第四章线性方程组的迭代解法省公共课一等奖全国赛课获奖课件.pptx（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 线性方程组迭代解法线性方程组迭代解法电子科技大学应用生命学院 陈华富9月第1页电子科技大学生命学院 陈n n迭代法基本思想迭代法基本思想n nJacobi迭代和迭代和GaussSeidel迭代迭代n n迭代法收敛性迭代法收敛性n n超松弛迭代超松弛迭代第四章第四章 线性方程组迭代解法线性方程组迭代解法第2页电子科技大学生命学院 陈4.1 迭代法基本思想：迭代法基本思想：例：求解方程组例：求解方程组其准确解是其准确解是x*=(3,2,1)T。现将原方程组改写为现将原方程组改写为简写为简写为x=B0 x+f，其中，其中第3页电子科技大学生命学院 陈任取初始值，如取任取初始值，如取x(
2、0)=(0,0,0)T，代入，代入x=B0 x+f右边，右边，若等式成立则求得方程组解，不然，得新值若等式成立则求得方程组解，不然，得新值x(1)=(x1(1),x2(1),x3(1)T=(2.5,3,3)T，再将，再将x(1)代入，重复计代入，重复计算，得一向量序列算，得一向量序列x(k)和普通计算公式（迭代公和普通计算公式（迭代公式）：式）：简写为简写为x(k+1)=B0 x(k)+f k=0,1,2,x(10)=(3.000032,1.999838,0.999813)T迭代到第迭代到第10次时有次时有|(10)|=|x(10)x*|=0.000187第4页电子科技大学生命学院 陈定义：定
3、义：（1）对于给定方程组）对于给定方程组x=Bx+f，用迭代公式，用迭代公式x(k+1)=Bx(k)+f(k=0,1,2,)逐步代入求近似解逐步代入求近似解方法称迭代法；方法称迭代法；（2）若）若k时时lim x(k)存在（记为存在（记为x*），称此），称此迭代法收敛，显然迭代法收敛，显然x*就是方程组解，不然称迭就是方程组解，不然称迭代法发散；代法发散；（3）B称为迭代矩阵。称为迭代矩阵。问题：问题：怎样建立迭代格式？怎样建立迭代格式？收敛速度？收敛速度？向量序列收敛条件？向量序列收敛条件？误差预计？误差预计？第5页电子科技大学生命学院 陈设设Ax=b，A非奇异，且对角元不为零，将原方非奇异
4、，且对角元不为零，将原方程组改写为程组改写为4.2 Jacobi迭代与迭代与GaussSeidel迭代迭代4.2.1 Jacobi迭代法迭代法第6页电子科技大学生命学院 陈又代入，重复继续，得迭代格式：又代入，重复继续，得迭代格式：称称Jacobi迭代法。迭代法。选取初始向量选取初始向量代入上面方程组右端得代入上面方程组右端得第7页电子科技大学生命学院 陈Jacobi迭代法矩阵表示：迭代法矩阵表示：第8页电子科技大学生命学院 陈故计算公式为：故计算公式为：(i=1,2,n)，(k=0,1,2,表迭代次数表迭代次数)矩阵表示：矩阵表示：第9页电子科技大学生命学院 陈则则BJ=I-D-1 A=D-
5、1(L+U)，fJ=D-1b，称称BJ为为Jacobi迭代矩阵。迭代矩阵。（aii0）将方程组将方程组Axb系数矩阵系数矩阵A分解为：分解为：A=D-L-U第10页电子科技大学生命学院 陈例例1:用用Jacobi迭代法求解方程组迭代法求解方程组,误差不超出误差不超出10-4。解解:第11页电子科技大学生命学院 陈第12页电子科技大学生命学院 陈第13页电子科技大学生命学院 陈依这类推依这类推,得方程组满足精度解为得方程组满足精度解为x12迭代次数：迭代次数：12次次 x4=3.0241 1.9478 0.9205 d=0.1573 x5=3.0003 1.9840 1.0010 d=0.091
6、4 x6=2.9938 2.0000 1.0038 d=0.0175 x7=2.9990 2.0026 1.0031 d=0.0059 x8=3.0002 2.0006 0.9998 d=0.0040 x9=3.0003 1.9999 0.9997 d=7.3612e-004x10=3.0000 1.9999 0.9999 d=2.8918e-004x11=3.0000 2.0000 1.0000 d=1.7669e-004x12=3.0000 2.0000 1.0000 d=3.0647e-005第14页电子科技大学生命学院 陈n n若在迭代时尽可能利用最新信息，则可将迭若在迭代时尽可能利用
7、最新信息，则可将迭代格式变为代格式变为4.2.2 GaussSeidel迭代法迭代法称称GaussSeidel迭代法迭代法。第15页电子科技大学生命学院 陈计算公式：（i=2,3,n-1）(i=1,2,n)即第16页电子科技大学生命学院 陈其中其中 BG-S=(D-L)-1 U 称称GaussSeidel迭代矩阵迭代矩阵。(D L)x(k+1)=b Ux(k)故故GaussSeidel迭代格式：迭代格式：第17页电子科技大学生命学院 陈例例2.用用Gauss-Seidel迭代法求解例迭代法求解例1.解解:第18页电子科技大学生命学院 陈x1=2.5000 2.0909 1.2273 d=3.4
8、825x2=2.9773 2.0289 1.0041 d=0.5305x3=3.0098 1.9968 0.9959 d=0.0465x4=2.9998 1.9997 1.0002 d=0.0112x5=2.9998 2.0001 1.0001 d=3.9735e-004x6=3.0000 2.0000 1.0000 d=1.9555e-004x7=3.0000 2.0000 1.0000 d=1.1576e-005经过迭代经过迭代,至第至第7步得到满足精度解步得到满足精度解x7：从例从例1和例和例2能够看出能够看出,Gauss-Seidel迭代法收敛速迭代法收敛速度比度比Jacobi迭代法要
9、快。迭代法要快。Jacobi迭代法和迭代法和Gauss-Seidel迭代法统称为迭代法统称为简单简单迭代法迭代法。第19页电子科技大学生命学院 陈Jacobi迭代算法迭代算法A=9-1-1;-1 10-1;-1-1 15;b=7;8;13;x=0;0;0;y=x;for k=1:6 for i=1:3 s=0;t=x(i);x(i)=0;for j=1:3 s=s+A(i,j)*x(j);end x(i)=t;y(i)=(b(i)-s)/A(i,i);end x=yend0.7778 0.8000 0.86670.9630 0.9644 0.97190.9929 0.9935 0.99520.
10、9987 0.9988 0.99910.9998 0.9998 0.99981.0000 1.0000 1.0000第20页电子科技大学生命学院 陈Gauss-Seidel迭代算法迭代算法A=9-1-1;-1 10-1;-1-1 15;b=7;8;13;n=length(b);x=b;er=1;k=0;while er0.00005 er=0;k=k+1;for i=1:3 s=0;t=x(i);x(i)=0;for j=1:3 s=s+A(i,j)*x(j);end x(i)=(b(i)-s)/A(i,i);er=max(abs(x(i)-t),er);end xend3.1111 2.41
11、11 1.23481.1829 1.0418 1.01501.0063 1.0021 1.00061.0003 1.0001 1.00001.0000 1.0000 1.00001.0000 1.0000 1.0000第21页电子科技大学生命学院 陈4.3 迭代法收敛性迭代法收敛性设解线性方程组迭代格式设解线性方程组迭代格式将上面两式相减将上面两式相减,得得而方程组准确解为而方程组准确解为X*，则，则第22页电子科技大学生命学院 陈则则所以迭代法收敛充要条件所以迭代法收敛充要条件可转变为可转变为引理：引理：迭代格式迭代格式收敛充要条件为收敛充要条件为第23页电子科技大学生命学院 陈定理：定理：
12、迭代格式迭代格式收敛充要条件为收敛充要条件为迭代矩阵谱半径迭代矩阵谱半径(B)1。证证:对任何对任何 n 阶矩阵阶矩阵B，都存在非奇矩阵，都存在非奇矩阵P，使，使 B=P 1 J P其中，其中，J 为为B Jordan 标准型。标准型。其中其中,Ji 为为Jordan块块第24页电子科技大学生命学院 陈其中其中,i 是矩阵是矩阵B特征值特征值,由由 B=P 1 J PB k=(P 1 J P)(P 1 J P)(P 1 J P)=P 1 J k P迭代法迭代法 x(k+1)=B x(k)+f 收敛收敛 (i=1,2,r)(i=1,2,r)谱半径谱半径 (B)1第25页电子科技大学生命学院 陈定
13、理：定理：设设x*为方程组为方程组 Ax=b 解，若解，若|B|1,则则 对迭代格式对迭代格式 x(k+1)=B x(k)+f，有有（1）（2）推论推论 若若|B|1，则迭代法则迭代法x(k+1)=B x(k)+f 收敛。收敛。（因为（因为(B)|B|）第26页电子科技大学生命学院 陈证证 由由|B|1，故用其特征，故用其特征值判断。值判断。第31页电子科技大学生命学院 陈所以所以Gauss-Seidel迭代法发散。迭代法发散。注：注：在例在例1和例和例2中中,Gauss-Seidel迭代法收敛速度迭代法收敛速度比比Jacobi迭代法要高，但例迭代法要高，但例3却说明却说明Gauss-Seid
14、el迭代法发散时而迭代法发散时而Jacobi迭代法却收敛，所以迭代法却收敛，所以,不不能说能说Gauss-Seidel迭代法比迭代法比Jacobi迭代法更加好。迭代法更加好。可得可得故故第32页电子科技大学生命学院 陈n n定义定义 设设A=(aij)nn Rnn，若，若(i=1,2,n)则称则称A为为对角占优矩阵对角占优矩阵，若不等式严格成立，则，若不等式严格成立，则称称A为为严格对角占优矩阵严格对角占优矩阵。迭代法收敛其它结论：迭代法收敛其它结论：定理定理 若若Ax=b中中A为严格对角占优矩阵，则为严格对角占优矩阵，则Jacobi迭代和迭代和GaussSeidel迭代均收敛。迭代均收敛。证
15、实：证实：因为系数矩阵因为系数矩阵A严格对角占优，所以严格对角占优，所以第33页电子科技大学生命学院 陈故故Jacobi迭代法收敛迭代法收敛(1)对于对于Jacobi迭代法迭代法,其迭代矩阵为其迭代矩阵为第34页电子科技大学生命学院 陈即即从而从而所以所以因为因为可得可得(2)对于对于GS迭代法迭代法,其迭代矩阵为其迭代矩阵为第35页电子科技大学生命学院 陈矛盾矛盾由前述定理知，由前述定理知，GS迭代法收敛迭代法收敛定理定理 若若A为对称正定阵，则为对称正定阵，则GaussSeidel迭迭代收敛。代收敛。第36页电子科技大学生命学院 陈考虑解线性方程组考虑解线性方程组Gauss-Seidel迭
16、代法迭代法4.4 超松弛迭代法（超松弛迭代法（SOR）迭代法加速迭代法加速第37页电子科技大学生命学院 陈令令所以所以第38页电子科技大学生命学院 陈上式称为逐次超松弛法(SOR迭代法),由由G-S迭代法矩阵形式迭代法矩阵形式第39页电子科技大学生命学院 陈第40页电子科技大学生命学院 陈上式为逐次超松弛法(SOR迭代法)矩阵形式令令第41页电子科技大学生命学院 陈SOR法化为法化为G-S迭代法G-S法为SOR法特例,SOR法为G-S法加速例例1.用用G-S法和法和SOR法求以下方程组解法求以下方程组解,要求精度要求精度1e-6第42页电子科技大学生命学院 陈解解:(1)G-S迭代法迭代法第4
17、3页电子科技大学生命学院 陈 1 1 1 1 1 1 0.7500000 0.3750000 1.5000000 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431 0.7018229 0.6582031 1.6727431.0.9999933 0.9999923 1.9999926 0.9
18、999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 0.9999952 0.9999944 1.9999946 k=71 k=71x=x=0.9999950.9999950.9999940.9999941.9999951.999995满足精度解满足精度解迭代次数为迭代次数为71次次第44页电子科技大学生命学院 陈(2)SOR迭代法迭代法 1 1 11 1 1 0.6375000 0.0121875 1.319906
19、3 0.6375000 0.0121875 1.3199063 0.270 0.3717572 1.3122805 0.270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932 0.7058468 0.7733401 1.7771932.0.9999990 0.9999976 1.9999991 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999
20、984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 0.9999996 0.9999998 1.9999997 k=24 k=24x=x=1.0000001.0000001.0000001.0000002.0000002.000000满足精度解满足精度解迭代次数为迭代次数为24次次SOR法收敛速度比法收敛速度比G-S法要快得多法要快得多第45页电子科技大学生命学院 陈n nSOR迭代收敛条件：迭代收敛条件：uu SOR迭代收敛迭代收敛(B)1；uu SOR迭代收敛必要条件是迭代收敛必要条件是0 2；uu 若若A对称正定，则当对称正定，则当0 2时，时，SOR收敛。收敛。uu 若若A为严格对角占优矩阵，则当为严格对角占优矩阵，则当0 1时，时，SOR收敛。收敛。另外另外,松弛因子选取是很困难松弛因子选取是很困难,普通采取试算进行。普通采取试算进行。第46页电子科技大学生命学院 陈P101-102习题四：习题四：1 ，2，3本章作业第47页