第四章 线性方程组的迭代解法精选PPT.ppt

《第四章 线性方程组的迭代解法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第四章 线性方程组的迭代解法精选PPT.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 线性方程组的迭代解法第1页，此课件共47页哦n n迭代法的基本思想迭代法的基本思想n nJacobi迭代和迭代和GaussSeidel迭代迭代n n迭代法的收敛性迭代法的收敛性n n超松弛迭代超松弛迭代第四章第四章 线性方程组的迭代解法线性方程组的迭代解法第2页，此课件共47页哦4.1 迭代法的基本思想：迭代法的基本思想：例：求解方程组例：求解方程组其精确解是其精确解是x*=(3,2,1)T。现将原方程组改写为现将原方程组改写为简写为简写为x=B0 x+f，其中，其中第3页，此课件共47页哦任取初始值，如取任取初始值，如取x(0)=(0,0,0)T，代入，代入x=B0 x+f右边，右边

2、，若等式成立则求得方程组的解，否则，得新值若等式成立则求得方程组的解，否则，得新值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页，此课件共47页哦定义：定义：（1）对于给定方程组）对于给定方程组x=Bx+f，用迭代

3、公式，用迭代公式x(k+1)=Bx(k)+f(k=0,1,2,)逐步代入求近似解的方法逐步代入求近似解的方法称迭代法；称迭代法；（2）若）若k时时lim x(k)存在（记为存在（记为x*），称此迭代），称此迭代法收敛，显然法收敛，显然x*就是方程组的解，否则称迭代法就是方程组的解，否则称迭代法发散；发散；（3）B称为迭代矩阵。称为迭代矩阵。问题：问题：如何建立迭代格式？如何建立迭代格式？收敛速度？收敛速度？向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？第5页，此课件共47页哦设设Ax=b，A非奇异，且对角元不为零，将原方非奇异，且对角元不为零，将原方程组改写为程组改写为4.2 J

4、acobi迭代与迭代与GaussSeidel迭代迭代4.2.1 Jacobi迭代法迭代法第6页，此课件共47页哦又代入，反复继续，得迭代格式：又代入，反复继续，得迭代格式：称称Jacobi迭代法。迭代法。选取初始向量选取初始向量代入上面方程组右端得代入上面方程组右端得第7页，此课件共47页哦Jacobi迭代法的矩阵表示：迭代法的矩阵表示：第8页，此课件共47页哦故计算公式为：故计算公式为：(i=1,2,n)，(k=0,1,2,表迭代次数表迭代次数)矩阵表示：矩阵表示：第9页，此课件共47页哦则则BJ=I-D-1 A=D-1(L+U)，fJ=D-1b，称称BJ为为Jacobi迭代矩阵。迭代矩阵。

5、（aii0）将方程组将方程组Axb的系数矩阵的系数矩阵A分解为：分解为：A=D-L-U第10页，此课件共47页哦例例1:用用Jacobi迭代法求解方程组迭代法求解方程组,误差不超过误差不超过10-4。解解:第11页，此课件共47页哦第12页，此课件共47页哦第13页，此课件共47页哦依此类推依此类推,得方程组满足精度的解为得方程组满足精度的解为x12迭代次数：迭代次数：12次次 x4=3.0241 1.9478 0.9205 d=0.1573 x5=3.0003 1.9840 1.0010 d=0.0914 x6=2.9938 2.0000 1.0038 d=0.0175 x7=2.9990

6、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页，此课件共47页哦n n若在迭代时尽量利用最新信息，则可将迭代若在迭代时尽量利用最新信息，则可将迭代格式变为格式变为4.2.2 GaussSeidel迭代法迭代法称称GaussS

7、eidel迭代法迭代法。第15页，此课件共47页哦计算公式：（i=2,3,n-1）(i=1,2,n)即第16页，此课件共47页哦其中其中 BG-S=(D-L)-1 U 称称GaussSeidel迭代矩阵迭代矩阵。(D L)x(k+1)=b Ux(k)故故GaussSeidel迭代格式：迭代格式：第17页，此课件共47页哦例例2.用用Gauss-Seidel迭代法求解例迭代法求解例1.解解:第18页，此课件共47页哦x1=2.5000 2.0909 1.2273 d=3.4825x2=2.9773 2.0289 1.0041 d=0.5305x3=3.0098 1.9968 0.9959 d=0

8、.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迭代法要快。迭代法要快。Jacobi迭代法和迭代法和Gauss-Seidel迭代法统称为迭代法统称为简单迭简单迭代法代法。第

9、19页，此课件共47页哦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.9987 0.9988 0.99910.9998 0.9998 0.99981.0000 1.0000 1.0000第20

10、页，此课件共47页哦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.4111 1.23481.1829 1.0418 1.01501.0063 1.0021 1.00061.0003 1.0001 1

11、.00001.0000 1.0000 1.00001.0000 1.0000 1.0000第21页，此课件共47页哦4.3 迭代法的收敛性迭代法的收敛性设解线性方程组的迭代格式设解线性方程组的迭代格式将上面两式相减将上面两式相减,得得而方程组的精确解为而方程组的精确解为X*，则，则第22页，此课件共47页哦则则因此迭代法收敛的充要条件因此迭代法收敛的充要条件可转变为可转变为引理：引理：迭代格式迭代格式收敛的充要条件为收敛的充要条件为第23页，此课件共47页哦定理：定理：迭代格式迭代格式收敛的充要条件为收敛的充要条件为迭代矩阵的谱半径迭代矩阵的谱半径(B)1。证证:对任何对任何 n 阶矩阵阶矩阵

12、B，都存在非奇矩阵，都存在非奇矩阵P，使，使 B=P 1 J P其中，其中，J 为为B的的 Jordan 标准型。标准型。其中其中,Ji 为为Jordan块块第24页，此课件共47页哦其中其中,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页，此课件共47页哦定理：定理：设设x*为方程组为方程组 Ax=b 的解，若的解，若|B|1,则则 对迭代格式对迭代格式 x(k+1)=B x(

13、k)+f，有有（1）（2）推论推论 若若|B|1，则迭代法则迭代法x(k+1)=B x(k)+f 收敛。收敛。（因为（因为(B)|B|）第26页，此课件共47页哦证证 由由|B|1，故用其特征值，故用其特征值判断。判断。第31页，此课件共47页哦所以所以Gauss-Seidel迭代法发散。迭代法发散。注：注：在例在例1和例和例2中中,Gauss-Seidel迭代法收敛速度比迭代法收敛速度比Jacobi迭代法要高，但例迭代法要高，但例3却说明却说明Gauss-Seidel迭代法迭代法发散时而发散时而Jacobi迭代法却收敛，因此迭代法却收敛，因此,不能说不能说Gauss-Seidel迭代法比迭代

14、法比Jacobi迭代法更好。迭代法更好。可得可得故故第32页，此课件共47页哦n n定义定义 设设A=(aij)nn Rnn，若，若(i=1,2,n)则称则称A为为对角占优矩阵对角占优矩阵，若不等式严格成立，则，若不等式严格成立，则称称A为为严格对角占优矩阵严格对角占优矩阵。迭代法收敛的其他结论：迭代法收敛的其他结论：定理定理 若若Ax=b中中A为严格对角占优矩阵，则为严格对角占优矩阵，则Jacobi迭迭代和代和GaussSeidel迭代均收敛。迭代均收敛。证明：证明：因为系数矩阵因为系数矩阵A严格对角占优，所以严格对角占优，所以第33页，此课件共47页哦故故Jacobi迭代法收敛迭代法收敛(

15、1)对于对于Jacobi迭代法迭代法,其迭代矩阵为其迭代矩阵为第34页，此课件共47页哦即即从而从而因此因此由于由于可得可得(2)对于对于GS迭代法迭代法,其迭代矩阵为其迭代矩阵为第35页，此课件共47页哦矛盾矛盾由前述定理知，由前述定理知，GS迭代法收敛迭代法收敛定理定理 若若A为对称正定阵，则为对称正定阵，则GaussSeidel迭代收迭代收敛。敛。第36页，此课件共47页哦考虑解线性方程组的考虑解线性方程组的Gauss-Seidel迭代法迭代法4.4 超松弛迭代法（超松弛迭代法（SOR）迭代法的加速迭代法的加速第37页，此课件共47页哦令令因此因此第38页，此课件共47页哦上式称为逐次超

16、松弛法(SOR迭代法),由由G-S迭代法的矩阵形式迭代法的矩阵形式第39页，此课件共47页哦第40页，此课件共47页哦上式为逐次超松弛法(SOR迭代法)的矩阵形式令令第41页，此课件共47页哦SOR法化为法化为G-S迭代法G-S法为SOR法的特例,SOR法为G-S法的加速例例1.用用G-S法和法和SOR法求下列方程组的解法求下列方程组的解,要求精度要求精度1e-6第42页，此课件共47页哦解解:(1)G-S迭代法迭代法第43页，此课件共47页哦 1 1 1 1 1 1 0.7500000 0.3750000 1.5000000 0.7500000 0.3750000 1.5000000 0.5

17、625000 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.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999943 0.9999935 1.9999937 0.9

18、999952 0.9999944 1.9999946 0.9999952 0.9999944 1.9999946 k=71 k=71x=x=0.9999950.9999950.9999940.9999941.9999951.999995满足精度的解满足精度的解迭代次数为迭代次数为71次次第44页，此课件共47页哦(2)SOR迭代法迭代法 1 1 11 1 1 0.6375000 0.0121875 1.3199063 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.2004270 0.3717572 1.3122805

19、 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.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999998 0.9999994 1.9999998

20、 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页，此课件共47页哦n nSOR迭代收敛条件：迭代收敛条件：uu SOR迭代收敛迭代收敛(B)1；uu SOR迭代收敛的必要条件是迭代收敛的必要条件是0 2；uu 若若A对称正定，则当对称正定，则当0 2时，时，SOR收敛。收敛。uu 若若A为严格对角占优矩阵，则当为严格对角占优矩阵，则当0 1时，时，SOR收敛。收敛。另外另外,松弛因子的选取是很困难的松弛因子的选取是很困难的,一般采用试算进行。一般采用试算进行。第46页，此课件共47页哦P101-102习题四：习题四：1 ，2，3本章作业第47页，此课件共47页哦