迭代法解线性方程组-数值分析实验报告

数学与计算科学学院《数值分析》课程设计题目：迭代法解线性方程组专业：信息与计算科学学号：1309302-24姓名：谭孜指导教师：郭兵成绩：二零一六年六月二十日一、前言：（目的和意义）1.实验目的①掌握用迭代法求解线性方程组的基本思想和步骤。②了解雅可比迭代法，高斯-赛德尔法和松弛法在求解方程组过程中的优缺点。2.实验意义迭代法是用某种极限过程去逐步逼近线性方程组精确解的方法，它是解高阶稀疏方程组的重要方法。迭代法的基本思想是用逐次逼近的方法求解线性方程组。比较雅可比迭代法，高斯-赛德尔迭代方法和松弛法，举例子说明每种方法的试用范围和优缺点并进行比较。二、数学原理：设有方程组bAx…①将其转化为等价的，便于迭代的形式fBxx…②(这种转化总能实现，如令bfAIB,),并由此构造迭代公式fBxxkk)()1(…③式中B称为迭代矩阵，f称为迭代向量。对任意的初始向量)0(x，由式③可求得向量序列0)(}{kx，若*)(limxxkk，则*x就是方程①或方程②的解。此时迭代公式②是收敛的，否则称为发散的。构造的迭代公式③是否收敛，取决于迭代矩阵B的性1.雅可比迭代法基本原理设有方程组),,3,2,1(1nibxajjnjij…①矩阵形式为bAx,设系数矩阵A为非奇异矩阵，且),,3,2,1(,0niaii从式①中第i个方程中解出x，得其等价形式)(111jnjjijiiixabax…②取初始向量),,,()0()0(2)0(1)0(nxxxx，对式②应用迭代法，可建立相应的迭代公式：)(111)()1(njjikjijiikibxaax…③也可记为矩阵形式：JxJkFBxk)()1(…④若将系数矩阵A分解为A=D-L-U，00000000000000111211212211212222111211nnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaULDA式中nnaaaD2211，0000121323121nnnnaaaaaaL，0000122311312nnnnaaaaaaU。则方程Ax=b变为bxULD)(得bxULDx)(于是bDxULDx11)(bDxADIbDxADD1111)()(于是式中④中的bDfADIBJJ11,。式③和式④分别称为雅克比迭代法的分量形式和矩阵形式，分量形式用于编程计算，矩阵型式用于讨论迭代法的收敛性。2.高斯—赛德尔迭代法高斯—赛德尔（Gauss-Seidel）迭代法，其迭代公式为)(1)(111)1()1(ikjijnijijkjijiikibxaxaax（i=1,2,…,n）也可以写成矩阵形式SGkSGkfxBx)()1(仍将系数矩阵A分解为ULDA则方程组变为bxULD)(得bUxLxDx将最新分量代替为旧分量，得bUxLxDxkkk)()1()1(即bUxxLDkk)()1()(于是有bLDUxLDxkk1)(1)1()()(所以ULDBSG1)(bLDfSG1)(3.超松弛迭代法设已知第k次迭代向量)(kx，及第k+1次迭代向量的前i-1个分量)1(kjx，（j=1,2,…i-1）,现在研究如何求向量)1(kx的第i个分量)1(kix。首先，有高斯—赛德尔迭代法求出一个值，记为)(1~1)()1(11)1(nijkjijkjijijiiikixaxabax（i=1,2,…n）再将第k次迭代向量的第i个分量)(kjx与)1(~kix进行加权平均，得)1(kix，即：)1(kix)1()(~)1(kikixx)~()()1()(kikikixxx于是的SOR迭代公式)()(1)1(11)()1(kjnjijkjijijiiikikixaxabaxx(i=1,2,…n)…①或)()1()(1)1(11)()1(kjnijijkjijijiiikikixaxabaxx（i=1,2,…n）…②当=1时，式①即为高斯—赛德尔迭代法；当01时，式①称为低松弛方法，当某些方程组用高斯—赛德尔迭代法不收敛时，可以用低松弛方法获得收敛；当1时，式①称为超松弛方法，可以用来提高收敛速度。将式②写成矩阵的形式，得：)()1()()1()()1(kkkkUXLXbDXDX即bxUDxLDkk)()1(])1[()(于是得SOR迭代的矩阵表示fXBxkk)()1(式中])1[()(1UDLDBbLDf1)(三、举例说明及代码例1：解下面方程组.（雅克比迭代方法、高斯-赛德尔和松弛法的比较）111x1221112-21321xx解：先计算迭代矩阵：02-2-1-01-22-0U)LDB1-J（2003-2022-0UL)-DB1-G（BJ与BG的特征值跟收敛半径为10B321i0BJJi）（），，，，（）（12B2B0BGG32G1）（，）（，）（，所以，用雅可比迭代法求解，迭代过程收敛，而用高斯-塞德尔迭代法求解，迭代过程发散。取x0=(0;0;0),为达到精度10-5，取w=0.1。雅可比迭代法松弛法3184代码：1.雅可比迭代法function[x,k]=jacobi(A,b,x0,esp)%k为迭A=input('InputA=');b=input('Inputb=');x0=input('Inputx0=');esp=1.0e-5;k=0;n=length(b);x=x0;whilemax(abs(b-A*x0))esp&k=500;fori=1:nsum=0;forj=1:nifj~=isum=sum+A(i,j)*x0(j);endendx(i)=(b(i)-sum)/A(i,i);endx0=x;k=k+1;ifk500fprintf('迭代达到上限')returnendendkInputA=[12-2;111;221];Inputb=[111]';Inputx0=[000]'运行结果：k=3ans=-3312.高斯-赛德尔迭代法clear;clc;A=[12-2;111;221];b=[111]';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=-triu(A,1);%上三角B=inv(D-E)*F;g=inv(D-E)*b;eps=0.0001;%相邻解的距离小于该数时，结束迭代%--------开始迭代-------fork=1:1000%最大迭代次数为100fprintf('第%d次迭代：',k);y=B*x+g;fprintf('\n与上次计算结果的距离(2范数):%f?\n',norm(x-y)^2);ifnorm(x-y)epsbreak;endx=yendx运行结果：（因为发散结果不能确定）3.松弛迭代法w=0.1;dalt=1.0e-5;A=[12-2;111;221];b=[111]';r=size(b);a=b;x0=zeros(3,1);x=x0;r=r(1);m=0;e=1;fort=1:ra(t)=A(t,t);A(t,t)=0;A(t,:)=A(t,:)/a(t);endb=b./a;root=[0x']whileedaltroot=m;e=0;fori=1:rt=x(i);x(i)=(1-w)*x(i)+w*(b(i)-A(i,:)*x);root=[rootx(i)];t=abs(x(i)-t);iftee=t;endendrootm=m+1;end运行结果：root=184.0000-3.00013.00001.0000例2：（超松弛法）达到同样的精度10-5，松弛因子的不同，会使得收敛速度大大不同（w取1.0—1.9）11114-11114-11114-111144321xxxx代码：w=1;dalt=1.0e-5;A=[4111;1-411;11-41;111-4];b=[1;1;1;1];r=size(b);a=b;x0=zeros(4,1);x=x0;r=r(1);m=0;e=1;fort=1:ra(t)=A(t,t);A(t,t)=0;A(t,:)=A(t,:)/a(t);endb=b./a;root=[0x']whileedaltroot=m;e=0;fori=1:rt=x(i);x(i)=(1-w)*x(i)+w*(b(i)-A(i,:)*x);root=[rootx(i)];t=abs(x(i)-t);iftee=t;endendrootm=m+1;end运行结果整理：松弛因子迭代次数松弛因子迭代次数1.071.6321.181.73368（不收敛）1.2101.81946（不收敛）1.3131.91372（不收敛）1.4171.523例3：用三种方法分别计算下列方程组并进行比较：2.43.82.751121012110321xxx解：雅克比迭代法1）改写成等价形式)..24(51),28.3(101),22.7(101213312321xxxxxxxxx2）构造迭代公式，即为雅可比迭代公式.,2,1,0),.24(51),28.3(101),27.2(101)(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk3）取初始向量Tx)0,0,0()0(，即,0)0(3)0(2)0(1xxx代入上式，求出0.84,0.83,0.72)1(3)1(2)1(1xxx依次迭代，计算结果如下表：要求精度迭代次数方程组的近似解0.017（1.0994,1.1994,1.2993）0.0019（1.0999，1.1999,1.2999）0.000113（1.1000,1.2000,1.3000）高斯-赛德尔迭代法1）原方程组改为等价方程组)..24(51),28.3(101),22.7(101213312321xxxxxxxxx2）构造迭代公式，即为高斯-赛德尔迭代公式.,2,1,0),34.2(51),28.3(101),27.2(101)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(1kxxxxxxxxxkkkkkkkkk3）取初始向量Tx)0,0,0()0(，即,0)0(3)0(2)0(1xxx代入上式，求出0.72)1(1x0.902)1(2x1.1644)1(3x迭代计算下去，得下表.要求精度迭代次数方程组的近似解0.014（1.0931，1.1957,1.2978）0.0015（1.0991,1.1995,1.2997）0.00017（1.10