Gauss-Seidel迭代法

Gauss-Seidel迭代法求解线性方程组数值分析课程论文姓名:学号:Gauss-Seidel迭代法求解线性方程组Gauss-Seidel迭代法求解线性方程组摘要线性方程组的求解在许多的工程技术中是一个极为常见的问题，对于线性方程组的求解无论从理论上还是实践应用上都已经成熟.对于一般线性方程组的求解有Gauss消元法为基础的直接法，也有迭代法.其中Gauss-Seidel是一个重要的组成部分.鉴于此，本论文细致地研究了用Gauss-Seidel迭代法求解线性方程组.论文的第一部分先介绍了迭代法求解线性方程组的一般模式，并给出这种迭代法的收敛性条件，Gauss-Seidel迭代法求解线性方程组的基本原理.这一部分是Gauss-Seidel迭代法的理论基础.论文的第二部分给出了Gauss-Seidel迭代法的具体操作步骤，以伪代码的形式细致的描绘如何使用Gauss-Seidel迭代法的求解方程组.同时，为了验证算法的有效性，在这一部分，还引入一个简单的算例，用于MATLAB编程发现计算结果完全正确.论文的第三部分给出了关于Gauss-Seidel迭代法的MATLAB程序，用于计算线性方程组.关键词：Gauss-Seidel迭代法，基本原理，算例，MATLAB程序Gauss-Seidel迭代法求解线性方程组目录1Gauss-Seidel迭代法的基本理论............................................11.1线性方程组的迭代法求解..............................................11.2Gauss-Seidel迭代法的原理............................................22.具体的算例和操作步骤....................................................32.1.Gauss-Seidel迭代法的伪代码.........................................32.2.具体的算例验证算法的有效性..........................................33．MATLAB程序...........................................................4参考文献.................................................................6Gauss-Seidel迭代法求解线性方程组第1页共6页Gauss-Seidel迭代法求解线性方程组一.Gauss-Seidel迭代法的基本理论1.1线性方程组的迭代法求解在考虑求解线性方程组Ax=b时，其中A为非奇异矩阵.尽管Guass消元法通过有限次运算可以求解此问题，其对应的计算复杂度为3O(n).但是对于工程技术中和某些偏微分方程过程中出现的大型稀疏型矩阵利用迭代法可以更快的收敛，找到解.另外一方面，由于迭代法占用的计算机内存少，且便于计算.这两方面的优势促成了迭代法求解线性方程组的研究.关于迭代法的收敛的几个判定条件1（迭代法基本原理）设有方程组fBxx，对于任意初始向量0x及任意f，解此方程组的迭代法（即fBxxkk1）收敛的充要条件是1B.2（迭代法收敛的充分条件）如果方程组fBxx的迭代公式为fBxxkk1（0x为任意初始向量），且迭代矩阵的某一种范数1qBv，则：1迭代法收敛；2vkkvkxxqqxx11；3vkvkxxqqxx011.定理3如果mnRA为严格对角占优阵或为不可约弱对角占优阵，则对于任意的0x，解方程组bAx的Jacobi迭代法，Gauss-Seidel迭代法均收敛.定理4如果A为对称正定矩阵，且20，则解式bAx的SOR方法收敛.Gauss-Seidel迭代法求解线性方程组第2页共6页1.2Gauss-Seidel迭代法的原理由Jacobi方法迭代公式010kkxxBxf初始向量，可知，迭代的每一步计算过程，都是用kx的全部分量来计算1kx的所有分量，显然在计算第i个分量1kix时，已经计算出的最新分量11kx，12kx，…，11kix没有被利用.从直观上看，最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第1k次近似1kx的分量1kjx加以利用，就得到所谓解方程组的Gauss-Seidel迭代法（简称G-S方法）：002010nxxxx，，，（初始向量），nikxaxabaxijnijkjijkjijiiiki,,2,1;,2,1,0111111或写为.1,,,2,1;,2,1,01111ijnijkjijkiijiiiiikikixaxabaxnikxxx上面第2个式子利用了最新计算出的分量11kx，第i个式子利用了计算出的最新分量1,,2,11ijxkj.还可写成矩阵形式kkkkkUxbxLDUxLxbDx111,，若设1LD存在，则bLDUxLDxkk111，于是Gauss-Seidel迭代公式的矩阵形式为fGxxkk1，6.2.8其中ULDG1，bLDf1.由此可以看出，应用Gauss-Seidel迭代法解式bAx，就是对方程组fGxx应用迭代法.G称为解式的Gauss-Seidel迭代法的迭代矩阵.Gauss-Seidel迭代法的一个明显优点是，在用计算机计算时，只需一组工作单元，以便Gauss-Seidel迭代法求解线性方程组第3页共6页存放近似解.由式可以看出，每迭代一步只需计算一次矩阵与向量的乘法.二．具体的算例和操作步骤2.1.Gauss-Seidel迭代法的伪代码1.输入问题的参数A,b2.分解A为D,L,U.3.计算迭代方程G，f.4.开始迭代，随机设定一个初值.5.以迭代方程更新x的值.6.如果到达迭代次数，则进入步骤7；否则，回到步骤5.7.输出x，结束.2.2.具体的算例验证算法的有效性求解如下的线性方程组1231231238-3+2=204+11-=336+3+12=36xxxxxxxxx这个方程的真实解为（3,2,1）.程序运行结果：情况1：输入GS（A,b）GS(A,b)xhis=0002.50002.09091.22732.97732.02891.00413.00981.99680.99592.99981.99971.00022.99982.00011.00013.00002.00001.0000Gauss-Seidel迭代法求解线性方程组第4页共6页3.00002.00001.00003.00002.00001.00003.00002.00001.00003.00002.00001.0000ans=3.00002.00001.000001234012300.511.5解的迭代情况图一。解的迭代过程程序说明：xhis为迭代过程，ans为最终迭代结果.本次迭代次数为10.图一中红点标记每次迭代的解的轨迹。从图中可以看出，初始值选择在（0,0,0），经过几次就应经到达很高的精度，表明Gauss—Seidel的迭代法收敛很快。三．MATLAB程序functiony=GS(A,b)if(nargin==0)disp('你没有输入任何参数');A=ceil(10*rand(3,3));b=ceil(10*rand(3,1));A,bGS(A,b)Gauss-Seidel迭代法求解线性方程组第5页共6页elseMaxInteration=10;n=length(A(:,1));D=zeros(n,n);L=zeros(n,n);U=zeros(n,n);fori=1:nforj=1:nif(i==j)D(i,j)=A(i,j);elseif(ij)L(i,j)=-A(i,j);elseU(i,j)=-A(i,j);endendendendG=inv(D-L)*U;f=inv(D-L)*b;x1=zeros(n,1);xhis=x1;fori=1:MaxInterationx2=G*x1+f;x1=x2;xhis=[xhis,x1];endxhis=xhis';y=x1;if(n==3)plot3(xhis(:,1),xhis(:,2),xhis(:,3),'or');title('解的迭代情况');endendGauss-Seidel迭代法求解线性方程组第6页共6页参考文献[1]刘卫国，matlab程序设计教程，中国水利水电出版社，2010年[2]李庆扬，王能超，易大义，数值分析，华中科技大学出版社，2010年[3]卓金武魏永生秦健李必文，matlab在数学建模中的应用北京航天航空出版社2011年