(完整word版)迭代法解线性方程组-数值分析实验报告

1、物力减节彳区数学与计算科学学院数值分析课程设计题 目：迭代法解线性方程组专业：信息与计算科学学号： 1309302-24姓名：谭孜指导教师：郭兵成 绩：二零一六年六月二十日、前言：(目的和意义)1 .实验目的掌握用迭代法求解线性方程组的基本思想和步骤。了解雅可比迭代法，高斯 -赛德尔法和松弛法在求解方程组过程中的优缺点。2 .实验意义迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法，它是解高阶稀疏方程组的重要方法。迭代法的基本思想是用逐次逼近的方法求解线性方程组。比较雅可比迭代法，高斯-赛德尔迭代方法和松弛法，举例子说明每种方法的试用范围和优缺点并进行比较。二、数学原理：设有方程组Ax

2、= b将其转化为等价的，便于迭代的形式x = Bx f(这种转化总能实现，如令B=I A, f =b),并由此构造迭代公式x(k1) = Bx(k)式中B称为迭代矩阵，f称为迭代向量。对任意的初始向量 x(0),由式可求得向量序列x(k)若lim x(k) =x* ,则x*就是方程或方程的解。此时迭代公 k-.式是收敛的，否则称为发散的。构造的迭代公式是否收敛，取决于迭代矩阵B的性1 .雅可比迭代法基本原理设有方程组二 aijxj -bj(i =1,2,3,n)j i矩阵形式为 Ax = b,设系数矩阵A为非奇异矩阵，且 4 #0,(i =1,2,3,，n)从式中第i个方程中解出x,得其等价形

3、式x = (b - aijxj)aiij =1j 1取初始向量x（0）=（x，x20）,，xn0）,对式应用迭代法，可建立相应的迭代公式:n(k i) iXi = (-a。Xjbi)aiij4j 1也可记为矩阵形式：(k 4)x(k)x 一 二 BjFj-L -Uaiia21ania12a22an2a2nann式中aiia220 - 一 00一 -0 -ai2a2i 00mB s0：,.： I：ann _aniann二0 一 一。- ain |mann0aiia22ann Ja2ia3ia32an 2ann 40ai2ai30a23U =0aina2nan In0则方程Ax=b变为(D - L

4、 -U )x =b若将系数矩阵A分解为A=D-L-U,Dx =(L U )x bx 二D(L U )x Db二D(D - A)x Db 二(I DA)x D1b于是式中中的BJ = I D,A, 口 = D,b。式和式分别称为雅克比迭代法的分量形式和矩阵形式，分量形式用于编程计算，矩阵型式用于讨论迭代法的收敛性。2 .高斯一赛德尔迭代法高斯一赛德尔(Gauss-Seidel )迭代法，其迭代公式为 in(i=1,2,，n)(k -1)1(k 1)、(k)xi二一ajxjajxjbi)aii j 1j 4 1也可以写成矩阵形式x(k.JBGsx(k)”仍将系数矩阵A分解为A-D -L -U则方程

5、组变为(D - L -U )x =b得Dx = Lx Ux b将最新分量代替为旧分量，得Dx(k 1) = Lx(k Ux(k) b即(D _ L)x(k 1) =Ux(k) . b于是有x(k 1) =(D - L)Ux(k) (D - L)b所以Bg =(D -L)4UfG4 =(D -L)b3 .超松弛迭代法设已知第k次迭代向量x(k),及第k+1次迭代向量的前i-1个分量x(k*) ,(j=1,2,口),现在研究如何求向量 x(k41)的第i个分量xi(k41)。首先，有高斯一赛德尔迭代法求出一个值，记为Ai 4n(k 1)1(k 1) t (k) ,、xi=(biajxj一乙 ajx

6、j )(i=1,2,n)aiij 1j 二 1再将第k次迭代向量的第i个分量x(k)与:由进行加权平均,曰(k 1)彳寸X ,即：x(ki)=(i_)Xi(k) y1)= x(k) -.(i(k1) -x(k)于是的SO砒代公式i 1n(k 1)(k)(k 1)、:(k)、Xi=x + (bi -Z ajXj -Z ajXj ) (i=l,2, n)aiij 1jJ或i Jnx(k+) _(1s)x(k)+巴(b ya x(k+) Ta x(k)ri=12 2xi (j w)xi丁 (bi乙aj xj 乙aj xj )( i=i,2, n；®aiij 1j ± 1当0 =1

7、时，式即为高斯一赛德尔迭代法；当0, .<1时，式称为低松弛方法，当某些方程组用高斯一赛德尔迭代法不收敛时， 可以用低松弛方法获得收敛；当。>1时，式称为超松弛方法，可以用来提高收敛速度。将式写成矩阵的形式，得：DX (k =(1 - )DX (k) .(b LX (k1) UX (k)即(D _ .L)x(k 1) =(1 - .)D，Ux(k)，b于是得SOR1代的矩阵表示x(k 1) = B，X(k) - f .式中B =(D - L) J(1 - )D U 1 f：,-.:伏(D 底L) b三、举例说明及代码例1:解下面方程组.(雅克比迭代方法、高斯-赛德尔和松弛法的比较)

8、12- 2 x 11111x2=1, 221_ x3_1解：先计算迭代矩阵：0- 22B J = D -1( L + U) =-10-1' - 2- 20 j0-22Bg =( D-L)-1U = 02- 3002 jBj与Bg的特征值跟收敛半径为“Bj) =0, ( i =1,2,3) , P (Bj) = 0<1 ki(B。= 0, %,3(Bg)= 2, p (Bg) = 2>1所以，用雅可比迭代法求解，迭代过程收敛，而用高斯-塞德尔迭代法求解, 迭代过程发散取x°=(0;0;0),为达到精度10-5,取w=0.1雅可比迭代法松弛法3184代码：1 .雅可比

9、迭代法function x,k=jacobi(A,b,x0,esp)%k 为迭A=input('Input A=');b=input('Input b=');x0=input( 'Input x0=');esp=1.0e-5; k=0; n=length(b);x=x0;while max(abs(b-A*x0)>esp&k<=500;for i=1:nsum=0; for j=1:n if j=i sum=sum+A(i,j)*x0(j);endend x(i)=(b(i)-sum)/A(i,i);endx0=x; k=k+

10、1; if k>500 fprintf( '迭代达到上限) returnend endkInput A=1 2 -2;1 1 1;2 2 1;Input b=1 1 1'Input x0=0 0 0'运行结果：k =3ans =-3312 .高斯-赛德尔迭代法clear;clc;A=1 2 -2;1 1 1;2 2 1; b=1 1 1'N=length(b);%解向量的维数fprintf( '库函数计算结果：)； x=inv(A)*b %库函数计算结果 x=zeros(N,1); %迭代初始值 %(A=D-E-F) D=diag(diag(A);

11、 E=-tril(A,-1);%F 三角F=-triu(A,1);%± 三角B=inv(D-E)*F;g=inv(D-E)*b;eps=0.0001;咐目邻解的距离小于该数时，结束迭代% 开始迭代for k=1:1000%<大迭代次数为 100fprintf( '第d 次迭代：',k); y=B*x+g;fprintf( 'n 与上次计算结果的距离(2 范数):f?n' ,norm(x-y)A2); if norm(x-y)<eps break ; end x=y end x运行结果：(因为发散结果不能确定)3 .松弛迭代法w=0.1;da

12、lt=1.0e-5;A=1 2 -2;1 1 1;2 2 1;b=1 1 1'r=size(b);a=b;x0=zeros(3,1);x=x0;4 =r;m=0;e=1;for t=1:ra(t尸A(t,t)；A(t,t)=0； A(t,:)=A(t,:)/a(t);endb=b./a;root=0 x'while e>daltroot=m;e=0;for i=1:rt=x(i);x(i)=(1-w)*x(i)+w*(b(i)-A(i,:)*x);root=root x(i);t=abs(x(i)-t);if t>ee=t;endendrootm=m+1;end运行

13、结果:root =184.0000 -3.0001 3.0000 1.0000例2:（超松弛法）达到同样的精度10-5,松弛因子的不同，会使得收敛速度大大不同（w取 1.0 1.9 ）4111- 41I 11- 4_1111X111x211 I X31-44 一 工代码：w=1;dalt=1.0e-5;A=4 1 1 1;1 -4 1 1;1 1 -4 1;1 1 1-4;b=1；1；1；1；r=size(b);a=b;x0=zeros(4,1);x=x0;r=r(1);m=0;e=1;for t=1:ra(t尸A(t,t)；A(t,t)=0；A(t,:)=A(t,:)/a(t);endb=b

14、./a;root=0 x'while e>daltroot=m;e=0;for i=1:rt=x(i);x(i)=(1-w)*x(i)+w*(b(i)-A(i,:)*x);root=root x(i);t=abs(x(i)-t);if t>ee=t;endendroot m=m+1;end运行结果整理:松弛因子迭代次数松弛因子迭代次数1.071.6321.181.73368 (不收敛)1.2101.81946 (不收敛)1.3131.91372 (不收敛)1.4171.523例3:用三种方法分别计算下列方程组并进行比较:10 -1-2 Xi 7.2-1 10 - 2 X2

15、= 8.311-1 -15X3_4.2解：雅克比迭代法1)改写成等价形式X210 (7.2 X2 2X3),1八、一 (8.3 X1 2X3), 102)X3=一(4.2X1X2).构造迭代公式，即为雅可比迭代公式x(k1)力7.2 x2k, 2x3k),= ±(8.3 斓 2x3k),x3k 1)1(4.2 x(k)x2k),k = 0,1,2,53)取初始向量x(0) =(0,0,0)T ,即x(0) =x20) =x3°) =0，代入上式，求出x(1) =0.72x21)=0.83x31)=0.84依次迭代，计算结果如下表：要求精度迭代次数方程组的近似解0.017(1

16、.0994,1.1994,1.2993 )0.0019(1.0999, 1.1999,1.2999 )0.000113(1.1000,1.2000,1.3000 )高斯-赛德尔迭代法)原方程组改为等价方程组xiX2110110(7.2 X2 2x3),(8.3 Xi2x3),x3一 (4.2 x1 x2).)构造迭代公式，即为高斯-赛德尔迭代公式xlkw =，(7.2 + x2k) +2x3k),x2k 1) = (8.3 x1(k 9 2x3k),10x3k1) =1(4.2x1(k 1)3x2k 1), k = 0,1,2,.5)取初始向量x(0) =(0,0,0)T ,即xj0) =x2

17、0) =x30) = 0，代入上式，求出x：) =0.72 x/： 0.902 x31)=1.1644迭代计算下去，得下表要求精度迭代次数方程组的近似解0.014(1.0931 , 1.1957,1.2978 )0.0015(1.0991,1.1995,1.2997 )0.00017(1.1000,1.2000,1.3000 )超松驰迭代法(取松驰因子金=1.3).利用SORT法，构造迭代公式Xif=xi(k)+?(7.2.i0xi(k)+x2k)+2x3k),-x产=x2k) +.(8.3 + xf-10x2k)+2x3k),x")=x3k)+£(4.2+Xi(k'

18、;)+x2k).5x3k).与高斯-赛德尔方法相同，初值为x(0)=(0,0,0)T .迭代计算结果列于下表要求精度迭代次数方程组的近似解0.015(1.0986,1.1998,1.0331 )0.0017(1.0999,1.2000,1.2999 )0.00018(1.1000,1.2000,1.3000 )代码：i.雅可比迭代法functionx,k=jacobi(A,b,x0,esp)%k为迭A=input('Input A=');b=input('Input b=');x0=input('Input x0=');esp=i.0e-5; k

19、=0; n=length(b); x=x0;while max(abs(b-A*x0)>esp&k<=500;for i=i:nsum=0; for j=1:n if j=i sum=sum+A(i,j)*x0(j);endend x(i)=(b(i)-sum)/A(i,i);endx0=x; k=k+1;if k>500 fprintf( '迭代达到上限) return end end kInput A=10 -1 -2;-1 10 -2;-1 -1 5;Input b=7.2 8.3 4.2'Input x0=0 0 0'运行结果：k =1

20、3ans =1.10001.20001.30002 .高斯-赛德尔迭代法clear;clc;A=10 3 1;2 -10 3;1 3 10; b=14 -5 14'N=length(b);%解向量的维数fprintf( '库函数计算结果：)； x=inv(A)*b %库函数计算结果 x=zeros(N,1); %迭代初始值 %(A=D-E-F) D=diag(diag(A); E=-tril(A,-1);%F 三角F=-triu(A,1);%± 三角B=inv(D-E)*F;g=inv(D-E)*b; eps=0.0001;咐目邻解的距离小于该数时，结束迭代% 开始迭

21、代for k=1:100%!大迭代次数为 100fprintf( '第d 次迭代：',k); y=B*x+g;fprintf( 'n 与上次计算结果的距离(2 范数):f?n',norm(x-y)A2); ifnorm(x-y)<eps breakend x=yendx运行结果：k=7x =1.00001.00001.00003 .松弛迭代法w=1.3;dalt=1.0e-2;A=10,-1,-2;-1,10,-2;-1,-1,5;b=7.2,8.3,4.2'r=size(b);a=b;x0=zeros(3,1);x=x0;r=r(1);m=0;e

22、=1;for t=1:ra(t尸A(t,t)；A(t,t)=0；A(t,:)=A(t,:)/a(t);endb=b./a;root=0 x'while e>daltroot=m;e=0;for i=1:rt=x(i);x(i)=(1-w)*x(i)+w*(b(i)-A(i,:)*x);root=root x(i);t=abs(x(i)-t);if t>ee=t;endendrootm=m+1;end运行结果:root =root =0 0.9360 1.2007 1.6475root =1.00001.23961.30831.2602root =2.00001.06181.

23、15221.2896root =3.00001.10251.21201.3069root =4.00001.10261.19851.2982root =5.00001.09861.19981.3001例4：用三种方法分别计算下列方程组并进行比较:一2-1一11X2-1X3-1解：雅克比迭代法2）改写成等价形式1 .、=一(XiX3),21 -、=2(1X2 X4)，X42)构造迭代公式，即为雅可比迭代公式x1 4(1x2)，1a"."(乃，2x2k1)=(x(k)x3k),x3k1)(1x2k)x4k),k 11 k X45 x3 k = 0,1,2,.代入上式，求出3)取

24、初始向量 x(0) =(1,1,1,1)T ,即 x* = x20) = x30)x（） u1,x2） u1,x3） =1.5 x4：0.5依次迭代，计算结果如下表：要求精度迭代次数方程组的近似解0.0121(1.1986,1.3939,1.5977,0.7962)0.00132(1.1996,1.3998,1.5994,0.7999)0.000153(1.2000,1.4000,1.6000,0.8000)高斯-赛德尔迭代法1 ）原方程组改为等价方程组x12(1 x2),1 ,.、x2 - 一( x1x3 ),J + 、x3 = 2(1 + 乂2 + 乂4),12 ）构造迭代公式，即为高斯2

25、-赛德尔迭代公式(k 1)x1(k 1) x2(k1) x3= 2(1 x2k),(xT)x3k),2= 2(1 x2k1)W)x4-x3 .k = 0,1,2,.X7X1nBA3 )取初始向量 x(0) =(1,1,1,1)T ,X=1,x21)=1,x"l.5, x41)=0.75迭代计算下去，得下表要求精度迭代次数方程组的近似解0.018(1.1880,1.3843,1.5873,0.7936)0.00114(1.1991,1.3988,1.5990,0.7995)0.000119(1.1999,1.3999,1.5999,0.7999)超松驰迭代法（取松驰因子。=1.4）.利

26、用SORT法，构造迭代公式(k 1)(k)(k)(k)、Xi= X (1 - 2x1x2 ),2(k 1)(k)(k 1)(k)(k)、X2=X2(X1-2X2X3 ),2X3k1) =X3k) (1X2k1).2X3k)X4k),2(k 1)(k)'( (k 1) c (k)、X4=X4 (X3-2X4 ).2与高斯-赛德尔方法相同，初值为x(0) =(1,1,1,1)T.迭代计算结果列于下表要求精度迭代次数方程组的近似解0.016(1.1961,1.3984,1.5987,0.7994)0.0018(1.1998,1.4000,1.6002,0.8000)0.000112(1.20

27、00,1.4000,1.6000,0.8000)代码：1 .雅可比迭代法functionx,k=jacobi(A,b,x0,esp)%k为迭A=input('Input A=');b=input('Input b=');x0=input('Input x0=');esp=1.0e-2; k=0; n=length(b); x=x0;while max(abs(b-A*x0)>esp&k<=500;for i=1:nsum=0; for j=1:n if j=i sum=sum+A(i,j)*x0(j);endend x(i)=

28、(b(i)-sum)/A(i,i);endx0=x; k=k+1; if k>500 fprintf( '迭代达到上限) returnend endkInput A=2 -1 0 0;-1 2 -1 0;0 -1 2 -1;0 0 -1 2;Input b=1 0 1 0'Input x0=1 1 1 1'运行结果：k =21ans =1.19861.39391.59770.79622 .高斯-赛德尔迭代法clear;clc;A=2 -1 0 0;-1 2 -1 0;0 -1 2 -1;0 0 -1 2;b=1 0 1 0'N=length(b);%解向量

29、的维数fprintf( '库函数计算结果：)；x=inv(A)*b%库函数计算结果x=ones(N,1); %迭代初始值%(A=D-E-F)D=diag(diag(A);E=-tril(A,-1);%F 三角F=-triu(A,1);%± 三角B=inv(D-E)*F;g=inv(D-E)*b;eps=0.01;咐目邻解的距离小于该数时，结束迭代% 开始迭代for k=1:100%!大迭代次数为100fprintf( '第d 次迭代：',k);y=B*x+g;fprintf( 'n与上次计算结果的距离(2 范数):f?n',norm(x-y)A2);ifnorm(x-y)<eps break ; end x=yend x运行结果： k=8x =1.18801.38431.58730.79363.松弛迭代法w=1.4;dalt=1.0e-2;A=2 -1 0 0;-1 2