《迭代法适用于求解大型稀疏的线性方程组其基本思想是通过》由会员分享，可在线阅读，更多相关《迭代法适用于求解大型稀疏的线性方程组其基本思想是通过（83页珍藏版）》请在金锄头文库上搜索。
1、数值分析数值分析数值分析数值分析 迭代法适用于求解大型稀疏的线性方程组，其迭代法适用于求解大型稀疏的线性方程组，其基本思想是通过构造迭代格式产生迭代序列，由迭代基本思想是通过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组的解，因此，要解决的基本问题序列来逼近原方程组的解，因此，要解决的基本问题是：是：1. 如何构造迭代格式如何构造迭代格式 2.迭代序列是否收敛迭代序列是否收敛第五节第五节 线性代数方程组的迭代解法线性代数方程组的迭代解法一一一一 . . 基本迭代法的格式及收敛性基本迭代法的格式及收敛性基本迭代法的格式及收敛性基本迭代法的格式及收敛性二二二二 . . 几种实用的基本迭代法几种
2、实用的基本迭代法几种实用的基本迭代法几种实用的基本迭代法三三三三 . . 应用实例应用实例应用实例应用实例数值分析数值分析数值分析数值分析一一 . . 基本迭代法的格式及收敛性基本迭代法的格式及收敛性 设有线性代数方程组设有线性代数方程组 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 . . . . . . . . . . . . . . . . . . . . . an1x1+an2x2+annxn=bnA=M+N M的逆的逆好求。好求。Ax =b (M+N)x=b Mx=-Nx+b x=-M-1Nx+M-1b 用矩阵表示：用矩阵表示： Ax =b A
3、为系数矩阵，非奇异且设为系数矩阵，非奇异且设aii0；b为右端，为右端，x为解向量为解向量数值分析数值分析数值分析数值分析 注：分解注：分解A是一个重要问题是一个重要问题数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析在在R Rn n中，点列的收敛等价于每个分量的收敛。即中，点列的收敛等价于每个分量的收敛。即 数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析
4、数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析二.几种实用的基本迭代法n1、Jacobi迭代法迭代法n2、Gauss-Seidel迭代法迭代法n3、超松弛迭代法（、超松弛迭代法（SOR)n4、对称超松弛迭代法（、对称超松弛迭代法（SSOR)n5、块超松弛迭代法（、块超松弛迭代法（BSOR法）法）数值分析数值分析数值分析数值分析 1 1、Ja
5、cobiJacobi 迭代迭代数值分析数值分析数值分析数值分析Jacobi迭代矩阵迭代矩阵数值分析数值分析数值分析数值分析推导其分量形式推导其分量形式第第i个方程除以个方程除以aii( (i = =1,2,n),1,2,n),得得数值分析数值分析数值分析数值分析JacobiJacobi迭代的分量形式迭代的分量形式数值分析数值分析数值分析数值分析则则 x x( (k k+1)+1)= =B BJ Jx x( (k k) )+g+g ，这里这里 B BJ J=D=D-1-1(L+U) , g=D(L+U) , g=D-1-1b b 数值分析数值分析数值分析数值分析Jacobi迭代公式（分量形式）迭
6、代公式（分量形式） 给出初始向量给出初始向量 x(0), 即可得到向量序列：即可得到向量序列： 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)ex(14)=-3.99972.99981.9998数值分析数值分析数值分析数值分析例例
7、2：设方程组为设方程组为 解：解： Gauss-Seidel迭代格式为迭代格式为试写出试写出Gauss-Seidel迭代格式迭代格式.2、Gauss-Seidel迭代法迭代法数值分析数值分析数值分析数值分析Gauss-Seidel迭代的迭代的分量形式分量形式数值分析数值分析数值分析数值分析推导推导Gauss-Seidel迭代法的迭代法的矩阵形式矩阵形式数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析Gauss-Seidel迭代矩阵迭代矩阵数值分析数值分析数值分析数值分析Gauss-Seidel迭代公式迭代公式 给出初始向量给出初始向量 x(0), 即可得到向量序列：即可得到向量
8、序列： x(1),x(2),x(k),若若 x(k) x*, 则则x*是是解。解。数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析Ab.ma(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
9、);x=zeros(1,n);for k=1:1000 error=0; for i=1:n s=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); endif error/n0.0001,break;endendfprintf(k.no.=%3.0f,error=%7.2en,k,error)数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值
10、分析|A|=12+4-15=1, |2D-A|=12-4-15=-7数值分析数值分析数值分析数值分析例例: :讨论用讨论用Gauss-SeidelGauss-Seidel迭代法求解方程组迭代法求解方程组Ax=bAx=b时的收时的收敛性，已知敛性，已知解解:(1)对对A：不是严格对角占优的矩阵，无法用充不是严格对角占优的矩阵，无法用充分准则分准则I，(2)考虑充分准则考虑充分准则II，计算计算Jacobi迭代矩阵迭代矩阵BJ=D-1（L+U）=I-D-1A数值分析数值分析数值分析数值分析不满足充分准则不满足充分准则II，故无法判断。故无法判断。先求出先求出Gauss-Seidel迭代矩阵迭代矩阵
11、 BG=(D-L)-1U(3)考虑用定理考虑用定理2的充分条件的充分条件 不满足定理不满足定理2的充分的充分条件条件，故无法判断。故无法判断。数值分析数值分析数值分析数值分析(4)再用定理再用定理1的充要条件的充要条件数值分析数值分析数值分析数值分析例例: :讨论用讨论用JacobiJacobi迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法求解迭代法求解方程组方程组Ax=b时的收敛性，如果收敛，并比较哪种方法时的收敛性，如果收敛，并比较哪种方法收敛较快，其中收敛较快，其中解解: (1)对对Jacobi方法，迭代矩阵方法，迭代矩阵数值分析数值分析数值分析数值分析 (2)对
12、对Gauss-SeidelGauss-Seidel方法，迭代矩阵方法，迭代矩阵Gauss-SeidelGauss-Seidel方法比方法比Jacobi方法收敛快。方法收敛快。数值分析数值分析数值分析数值分析3、超松弛迭代法（、超松弛迭代法（SOR法）法）数值分析数值分析数值分析数值分析以三阶方程为例，推导超松弛迭代法（以三阶方程为例，推导超松弛迭代法（SORSOR法）的分量形式法）的分量形式数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析SOR迭代公式（分量形式）迭代公式（分量形式）数值分析数值分析数值分析数值分析 推导推导SOR迭代格式的矩阵形
13、式（以三阶方程为例）迭代格式的矩阵形式（以三阶方程为例）数值分析数值分析数值分析数值分析 推导推导SOR迭代格式的矩阵形式迭代格式的矩阵形式数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析SORSOR法收敛性的结论：法收敛性的结论：（1 1）SORSOR方法收敛的必要条件为方法收敛的必要条件为0 0 22（2 2）若系数阵）若系数阵A A对称正定，则当对称正定，则当0 0 22时，时， SORSOR方法收敛方法收敛（3 3）若系数阵）若系数阵A A严格对角占优，则当严格对角占优，则当0 0 1 1时，时， SORSOR方法收敛。方法收敛。数值分析
14、数值分析数值分析数值分析 在计算机上采用动态计算形式在计算机上采用动态计算形式数值分析数值分析数值分析数值分析(1) x(i)=0 (i=1,2,n) (2)对对k =1,Kmax,循环计算到第循环计算到第(7)步步(3)置置ER=0数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析4、对称超松弛迭代法（、对称超松弛迭代法（SSOR法）法）数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析SSORSSOR迭代法的矩阵形式：迭代法的矩阵形式：注：注：（1）关于）关于 的收敛条件和准则与的收敛条件和准则与SOR方法相同；方法相同；（2）收敛快慢对）收敛快慢对 的选取不敏
15、感。的选取不敏感。数值分析数值分析数值分析数值分析5 5、块超松弛迭代法（、块超松弛迭代法（BSORBSOR法）法）数值分析数值分析数值分析数值分析案案 例例 1 (1 (热传导问题热传导问题) )设有一维热传导方程的初边值问题设有一维热传导方程的初边值问题试用数值方法求出试用数值方法求出t=0.2时刻金属杆的温度分布时刻金属杆的温度分布.三应用实例三应用实例数值分析数值分析数值分析数值分析解解:(1)对空间进行离散对空间进行离散.(2)对微分算子进行离散对微分算子进行离散.t0.020.0100 0.1 0.2 . 0.9 1 x数值分析数值分析数值分析数值分析采用无条件稳定的采用无条件稳定
16、的Crank-Nicholson格式格式,则有则有数值分析数值分析数值分析数值分析或或加上边界条件后有加上边界条件后有数值分析数值分析数值分析数值分析加上边界条件后有加上边界条件后有其矩阵形式为其矩阵形式为 ATn+1=dn数值分析数值分析数值分析数值分析案案 例例 2 2 数值求解正方形域上的数值求解正方形域上的Poisson方程边值问题方程边值问题数值分析数值分析数值分析数值分析解解:(1)剖分求解域剖分求解域.(2)对微分算子进行离散对微分算子进行离散.0 1 2 . N N+1 XYN+1N：210数值分析数值分析数值分析数值分析在每个点在每个点(xi,yj)上的有限差分方程为上的有限
17、差分方程为在边界上在边界上又又称为五点差分格式称为五点差分格式(i,j)(i,j+1)(i,j-1)(i-1,j)(i+1,j)数值分析数值分析数值分析数值分析对非边界点进行编号对非边界点进行编号: 顺序为顺序为-从下往上从下往上,从左往右从左往右相应的解向量和右端向量分别为相应的解向量和右端向量分别为 数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析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 %迭代
18、求解迭代求解 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
