《迭代法适用于求解大型稀疏的线性方程组其基本思想是通过.ppt》由会员分享，可在线阅读，更多相关《迭代法适用于求解大型稀疏的线性方程组其基本思想是通过.ppt（83页珍藏版）》请在三一文库上搜索。
1、迭代法适用于求解大型稀疏的线性方程组，其 基本思想是通过构造迭代格式产生迭代序列，由迭代 序列来逼近原方程组的解，因此，要解决的基本问题 是：1. 如何构造迭代格式 2.迭代序列是否收敛,第五节 线性代数方程组的迭代解法,一 . 基本迭代法的格式及收敛性 二 . 几种实用的基本迭代法 三 . 应用实例,一 . 基本迭代法的格式及收敛性,设有线性代数方程组 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 . . . . . . . . . . . . . . . . . . . . . an1x1+an2x2+annxn=bn,用矩阵表示： Ax =b A 为
2、系数矩阵，非奇异且设aii0；b为右端，x为解向量,注：分解A是一个重要问题,在Rn中，点列的收敛等价于每个分量的收敛。即,二.几种实用的基本迭代法,1、Jacobi迭代法 2、Gauss-Seidel迭代法 3、超松弛迭代法（SOR) 4、对称超松弛迭代法（SSOR) 5、块超松弛迭代法（BSOR法）,1、Jacobi 迭代,Jacobi迭代矩阵,推导其分量形式,第i个方程除以aii(i =1,2,n),得,Jacobi迭代的分量形式,则 x(k+1)=BJx(k)+g ， 这里 BJ=D-1(L+U) , g=D-1b,Jacobi迭代公式（分量形式）,给出初始向量 x(0), 即可得到向
3、量序列： x(1),x(2),x(k),若 x(k) x*, 则x*是解。,例1：设方程组为,解：Jacobi迭代格式为,试写出其Jacobi分量迭代格式以及相应的迭代矩阵，并求解。,故Jacobi迭代矩阵为,取 x(0)=(0,0,0)t, e=10-3,终止准则：x(k)-x(k-1)e,例2：设方程组为,解： Gauss-Seidel迭代格式为,试写出Gauss-Seidel迭代格式.,2、Gauss-Seidel迭代法,Gauss-Seidel迭代的分量形式,推导Gauss-Seidel迭代法的矩阵形式,Gauss-Seidel迭代矩阵,Gauss-Seidel迭代公式,给出初始向量
4、x(0), 即可得到向量序列： x(1),x(2),x(k),若 x(k) x*, 则x*是解。,Ab.m a(1,1)=1/2+1/4+1/3;a(1,2)=-1/4;a(1,3)=-1/3; a(2,1)=a(1,2);a(2,2)=1/4+1/3+1/5;a(2,3)=-1/5; a(3,1)=a(1,3);a(3,2)=a(2,3);a(3,3)=1/3+1/5+1/3; b(1)=20/2;b(2)=0;b(3)=5/3;,function x,k=gs(A,b) n n=size(A); x=zeros(1,n); for k=1:1000 error=0; for i=1:n s
5、=0;xb=x(i); for j=1:n if i=j,s=s+A(i,j)*x(j);end end x(i)=(b(i)-s)/A(i,i); error=error+abs(x(i)-xb); end if error/n0.0001,break;end end fprintf(k.no.=%3.0f,error=%7.2en,k,error),|A|=12+4-15=1, |2D-A|=12-4-15=-7,例:讨论用Gauss-Seidel迭代法求解方程组Ax=b时的收敛性，已知,解:(1)对A：不是严格对角占优的矩阵，无法用充分准则I， (2)考虑充分准则II，计算Jacobi迭
6、代矩阵BJ=D-1（L+U）=I-D-1A,不满足充分准则II，故无法判断。,先求出Gauss-Seidel迭代矩阵 BG=(D-L)-1U,(3)考虑用定理2的充分条件,不满足定理2的充分 条件，故无法判断。,(4)再用定理1的充要条件,例:讨论用Jacobi迭代法和Gauss-Seidel迭代法求解方程组Ax=b时的收敛性，如果收敛，并比较哪种方法收敛较快，其中,解: (1)对Jacobi方法，迭代矩阵,(2)对Gauss-Seidel方法，迭代矩阵,Gauss-Seidel方法比Jacobi方法收敛快。,3、超松弛迭代法（SOR法）,以三阶方程为例，推导超松弛迭代法（SOR法）的分量形式
7、,SOR迭代公式（分量形式）,推导SOR迭代格式的矩阵形式（以三阶方程为例）,推导SOR迭代格式的矩阵形式,SOR法收敛性的结论：,（1）SOR方法收敛的必要条件为0 2,（2）若系数阵A对称正定，则当0 2时， SOR方法收敛,（3）若系数阵A严格对角占优，则当0 1时， SOR方法收敛。,在计算机上采用动态计算形式,(1) x(i)=0 (i=1,2,n) (2)对k =1,Kmax,循环计算到第(7)步 (3)置ER=0,4、对称超松弛迭代法（SSOR法）,SSOR迭代法的矩阵形式：,注： （1）关于 的收敛条件和准则与SOR方法相同； （2）收敛快慢对 的选取不敏感。,5、块超松弛迭代
8、法（BSOR法）,案 例 1 (热传导问题),设有一维热传导方程的初边值问题,试用数值方法求出t=0.2时刻金属杆的温度分布.,三应用实例,解:(1)对空间进行离散.,(2)对微分算子进行离散.,t 0.02 0.01 0,0 0.1 0.2 . 0.9 1 x,采用无条件稳定的Crank-Nicholson格式,则有,或,加上边界条件后有,加上边界条件后有,其矩阵形式为 ATn+1=dn,案 例 2,数值求解正方形域上的Poisson方程边值问题,解:(1)剖分求解域.,(2)对微分算子进行离散.,0 1 2 . N N+1 X,Y N+1 N ： 2 1 0,在每个点(xi,yj)上的有限
9、差分方程为,在边界上,又称为五点差分格式,对非边界点进行编号: 顺序为-从下往上,从左往右,相应的解向量和右端向量分别为,Gauss-Seidel迭代法参考程序: n=9; b(2:n+1,2:n+1)=0.02; U=zeros(n+2,n+2); e=0.000000001; for k=1:1000 %迭代求解 er=0; for j=2:n+1 for i=2:n+1 Ub=U(i,j); U(i,j)=(U(i-1,j)+U(i+1,j)+U(i,j-1)+U(i,j+1)+b(i,j)/4; er=er+abs(Ub-U(i,j); %估计当前误差 end end if er/n2e,break;end %判断是否达到计算精度，如果达到则退出循环 end,f(x,y)=2, h=0.1,差分方程组的矩阵形式为 Au=f,如果把每一条线上的网点看作一个组,如,其中,可用块迭代法 (即线迭代法) 求解Au=f,三版习题 P139-20，23，24，25，22,二版习题 P149-2, 5, 6, 7,4,