Jacobi 迭代法与Gauss-Seidel迭代法算法比较目录1 引言 (1)1.1Jacobi迭代法 (2)1.2Gauss-Seidel迭代法 (2)1.3逐次超松弛（SOR）迭代法 (3)2算法分析 (3)3 结论 (5)4 附录程序 (5)参考文献 (8)Jacobi 迭代法与Gauss-Seidel 迭代法比较1 引言解线性方程组的方法分为直接法和迭代法，直接法是在没有舍入误差的假设下，能在预定的运算次数内求得精确解，而迭代法是构造一定的递推格式，产生逼近精确值的序列。
这两种方法各有优缺点，直接法普遍适用，但要求计算机有较大的存储量，迭代法要求的存储量较小，但必须在收敛性得以保证的情况下才能使用。
对于高阶方程组，如一些偏微分方程数值求解中出现的方程组，采用直接法计算代价比较高，迭代法则简单又实用，所以比较受工程人员青睐。
迭代法求解方程组就是构造一个无限的向量序列，使它的极限是方程组的解向量。
即使计算机过程是精确的，迭代法也不能通过有限次算术运算求得方程组的精确解，而只能逐步逼近它。
因此迭代法存在收敛性与精度控制的问题。
迭代法是常用于求解大型稀疏线性方程组（系数矩阵阶数较高且0元素较多），特别是某些偏微分方程离散化后得到的大型稀疏方程组的重要方法。
设n 元线性微分方程组b Ax = (1)的系数矩阵A 非奇异，右端向量0≠b ,因而方程组有唯一的非零解向量。
而对于这种线性方程组的近似解，前辈们发展研究了许多种有效的方法，有Jacobi 迭代法、Gauss —Seidel 迭代法，逐次超松弛迭代法（SOR 法），这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A 分解成两个矩阵N 和P 的差，即P N A -=；其中N 为可逆矩阵，线性方程组(1)化为：b x P N =-)（b Px Nx +=b N Px N x 11--+=可得到迭代方法的一般公式：d Gx xk k +=+))1(（ （2）其中：P N G 1-=，b N d 1-=，对任取一向量)0(x 作为方程组的初始近似解，按递推公式产生一个向量序列)1(x ，)2(x ，...，）k x(，...，当k 足够大时，此序列就可以作为线性方程组的近似解。
2013届学士学位毕业论文超松弛迭代法及其松弛因子的选取学号：09404307姓名：程启远班级：信息0901指导教师：崔艳星专业：信息与计算科学系别：数学系完成时间：2013年5月学生诚信承诺书本人郑重声明：所呈交的论文《超松弛迭代中松弛因子的选取方法》是我个人在导师崔艳星指导下进行的研究工作及取得的研究成果.尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得长治学院或其他教育机构的学位或证书所使用过的材料.所有合作者对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意.签名：日期：论文使用授权说明本人完全了解长治学院有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文.签名：日期：指导教师声明书本人声明：该学位论文是本人指导学生完成的研究成果，已经审阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内容的一致性和准确性.指导教师签名：时间摘要本文首先给出了超松弛迭代法解线性方程组的基本概念，引进了关于超松弛迭代法收敛性判别的一些定理.再基于超松弛迭代法收敛性快慢与松弛因子的选择密切相关，本文给出了能准确快速地确定最优松弛因子的方法逐步搜索法和黄金分割法，并且写出了其Matlab 程序（附录），最后通过实例验证了方法的准确性，快速性.关键词线性方程组；超松弛迭代；Matlab程序；松弛因子AbstractThis paper firstly introduces the basic concept of the super relaxation iteration method for solving linear equations, introduced on some criterion theorem Overrelaxation iterative convergence, gives a simple Matlab program super relaxation iteration (Appendix 1). Then Overrelaxation iterative convergence speed and relaxation factor is selected based on the close relation is proposed in this paper, the rapid and accurate method of determining the optimal relaxation factor of the direct search method and the golden section method, and write the Matlab program (Appendix 2), finally the method is accurate, rapid.Key word：Linear equations; Successive Over Relaxation; Matlab program; relaxation factor超松弛迭代法及其松弛因子的选取09404307 程启远信息与计算科学指导教师崔艳星引言在科学计算和工程设计中，经常会遇到求解线性代数方程组的问题，而怎样快速的求解一直是我们共同关心的课题.随着计算机技术及数学编程软件的发展，我们有了在计算机上解线性方程组的条件.最初遇到的方程数和未知数比较少的方程组我们就是利用线性代数知识直接解出来.直接解法只能适用于经过有限步运算能求得解的方程组.后来遇到的方程数和未知数都比较多的方程组，特别是经常会遇到的大型的方程组，直接解法工作量太大，花费时间太多，因此迭代法发展了起来.从最初的Jacobi迭代法到Gauss-Seidel迭代法，很多学者一直在研究找到一种迭代法能更加快速，简单的解决线性方程组.通过不断的实验和计算，在Gauss-Seidel迭代法基础上，人们发现通过迭代-松弛—再迭代的方法，能更加减少计算步骤，极大的缩短计算时间，在此基础上，超松弛迭代法被学者们研究出来.通过比较三种迭代方法，我们得到超松弛迭代的收敛速度是最快的，而且超松弛迭代法具有计算公式简单，编制程序容易等突出优点.在求解大型稀疏线性方程组中超松弛迭代法得到广泛应用.而SOR 迭代方法中松弛因子ω的取值直接影响到算法的收敛性及收敛速度，是应用超松弛迭代法的关键.选择得当,可以加快收敛速度,甚至可以使发散的迭代变成收敛.因此, 超松弛因子的选取是学者们又一个研究目标.通过一些被验证的定理，我们知道为了保证迭代过程的收敛,必须要求1<ω<2，而且松弛因子和迭代矩阵谱半径之间有着密切的联系，现今学者们已经研究出部分特殊矩阵的最优松弛因子的计算公式.对于一般的矩阵，我们也可以从松弛因子和谱半径的关系着手研究最优松弛因子的选取，这就为本篇论文的形成提供了行文思路.本文给出了求超松弛迭代最优松弛因子的两种方法.1.超松弛迭代基本知识1.1 超松弛迭代法定义[1]超松弛(Successive Over Relaxation)迭代法，简称SOR 迭代法，它是在Gauss-Seidel 法基础上为提高收敛速度，采用加权平均而得到的新算法.设解方程组的Gauss-Seidel 法记为1(1)(1)()111(),1,2,,i nk k k ii ij j ij j j j i ii x b a x a x i na -++==+=--=∑∑ （1）再由()k ix 与(1)k ix +加权平均得(1)(1)(1)()()()(1)(),1,2,,k k k k k k i i i ii x x xx x x i n ωωω+++=-+=+-=这里ω＞0称为松弛参数，将(1)代入则得1(1)()(1)()11(1)(),1,2,,i nk k k k iii ij jijjj j i iix x b a x a xi na ωω-++==+=-+--=∑∑ （2）称为SOR 迭代法，ω＞0称为松弛因子，当ω=1时(2)即为Gauss-Seidel 法，将(2)写成矩阵形式，则得(1)()(1)()(1)()k k k k Dx Dx b Lx Ux ωω++=-+++于是得SOR 迭代的矩阵表示[3](1)()k k i x G x f ωω+=+ (3)其中1()[(1)]G D L D U ωωωω-=--+1()f D L b ωωω-=-1.2 收敛性判别条件 根据迭代法收敛性定理[2]，SOR 法收敛的充分必要条件为()1G ωρ<，但要计算()G ωρ比较复杂，通常都不用此结论，而直接根据方程组的系数矩阵A 判断SOR 迭代收敛性，下面先给出收敛必要条件. 定理1]4[ 设(),0(1,2,...,)n nij ii A a Ra i n ⨯=∈≠=，则解方程Ax b =的SOR 迭代法收敛的必要条件是0＜ω＜2. 定理2]5[ 若n nA R ⨯∈对称正定，且0＜ω＜2，则解Ax=b 的SOR 迭代法(3)对nx R ∀∈迭代收敛.对于SOR 迭代法，松弛因子的选择对收敛速度影响较大，关于最优松弛因子研究较为复杂，且已有不少理论结果.下面只给出一种简单且便于使用的结论. 1.3 收敛速度的估计SOR 迭代法的迭代矩阵G ω与ω有关，当选取不同的ω时，其迭代速度也有所不同.因此，需要找到最优的松弛因子b ω，使对应b ω的SOR 方法收敛最快. 定理3]7[ 设n A Rn ⨯∈,如果存在排列矩阵P ，使1122T D M PAP M D =其中，1D ,2D 为对角矩阵，则称A 是2-循环的.此外，若当0α≠时，矩阵11-1D U D L αα--+的特征值都和α无关，则称A 是相容次序矩阵.定理4]7[ 设n A Rn⨯∈，A 有非零的对角元，且是2-循环和相容次序的矩阵.又设1(U)J B D L -=+是方程组A x b =的Jacobi 法迭代的迭代矩阵,且2B 的所有特征值均在（0,1）上，若()1J B ρ<,记()J B μρ=,则SOR 法的最优松弛因子b ω为211b ωμ=+-且222[4(1)]()1,2bb G ωωμωμωωωρωωω⎧+--⎪<<=⎪-<<⎩02()min ()bb G G ωωωρρ≤≤=图12 松弛因子选取方法方法思想]8[：(1)给出ω的范围，当取不同的ω值时，进行迭代，在符合同一个精度要求下依次求出谱半径的值，比较出最小的谱半径，那么这个最小的谱半径所对应的的ω,即为所求最佳松弛因子.(2)给出ω的范围，当取不同的ω值时，进行迭代，看它们在相同精度范围内的迭代次数，找到迭代次数最少的那一个，其所对应的ω即为最佳松弛因子.” 2.1 逐步搜索法 算法：Step 1：读入线性方程组的系数矩阵，常数向量，初值，精度，给出ω的取值范围,以及其变化步长；Step 2：按照如下公式迭代(1)()k k i x G x f ωω+=+找出符合精度要求ε的迭代次数及谱半径;Step 3：循环迭代，最后找到最优松弛因子Step 4: 改变ω的取值范围，重新设定变化步长，重复Step2. 2.2 黄金分割法从定理4我们可以看到，最优松弛因子对应的谱半径最小，而黄金分割法对于数值求解单调函数的极小和极大值是非常方便和有效的]9[，因此，我们可以把黄金分割法应用在求最优松弛因子上，其算法与主要思想是： Step1:利用优选法思想，在)2,1(之间选取四个点，12441314141,0.618(),0.618(),2p p p p p p p p p p ==--=+-=Step 2: 分别取2p 与3p 作为松弛因子代入迭代程序，比较出最少的迭代次数，如果对2p 应的迭代次数少，则选取),(31p p 作为收敛区间，如果是对应的3p 迭代次数少，则选取),(42p p 作为收敛区间.Step 3: 在所选取的收敛区间里循环进行上述的两个步骤，直到选取出满足精度要求且2p ，3p 所对应的迭代次数差不超过某个数∆时选3p 为最优松弛因子.3 数值算例例1: 矩阵3101130000311013A -⎡⎤⎢⎥-⎢⎥=⎢⎥-⎢⎥-⎣⎦(1,2,2,1)T b =----，精度为161.0*10k k x x ---≤解法1:黄金分割法令05.0=∆，程序结果如下：由上可以看出我们只需作几次0.618法就可以找到最优松弛因子，本例中最优松弛因子0901.1=ω，迭代次数为8次.解法2：逐步搜索法，步长为0.1，21<≤ω程序结果如下：图3图3中，其横坐标表示松弛因子，纵坐标表示谱半径.也可以求出最优松弛因子为1.1，迭代次数为8.然后我们改变松弛因子区间，令1.11≤≤ω以步长为0.01来继续求更精确的松弛因子.程序结果如下：图4图4中，其横坐标表示松弛因子，纵坐标表示谱半径.这样继续缩小松弛因子范围，以更小的步长求得的最优松弛因子为1.0900，更加精确. 例2 方程组A x b =，⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=40001-1-1-0004001-01-1-0004001-1-01-0004001-1-1-1-1-00400001-01-00400001-1-1-0040001-01-00040001-1-00004A T (2,2,0,2,2,1,1,1,1)b =.精度为161.0*10k k x x ---≤.初始迭代值为0(0,0,0,0,0,0,0,0,0)T x =.求最优松弛因子.解法1 黄金分割法令001.0=∆，程序结果如下：求得最优松弛因子为1.1772.解法2 逐步搜索法首先以21<≤ω，步长为0.1搜索求得的最优松弛因子为1.2000,然后重新设定范围，以步长为0.01运行程序在改变范围，以步长为0.001运行，程序结果如下：求得的最优松弛因子为1.1780.由这两个例子可以看出利用黄金分割法求最优松弛因子比用逐步搜索法更加简便快速，但是用逐步搜索法步长取的很小时求得的松弛因子比黄金分割法更加精确.4 结束语超松弛迭代方法是解决线性方程组的一个十分有效快捷的方法，很多工程学，计算数学中都会应用.而且超松弛迭代法公式简单，编制程序容易.而使用超松弛迭代法的关键在于选取合适的松弛因子，如果松弛因子选取合适，则会大大缩短计算时间. 本文依据松弛因子和矩阵谱半径的关系给出了两种选取松弛因子的方法逐步搜索法和黄金分割法及其Matlab程序. 但这两种方法仍不是足够简便，有所不足，有待进一步研究.5 参考文献:[1] 李庆扬，王能超，易大义.数值分析[M], 清华大学出版社，2008.[2] 施吉林. 计算机数值方法[M] . 北京: 高等教育出版社, 2000.[3] 蔡大用.数值分析与实验学习指导[M]，清华大学出版社，2001.[4] 李建宇，黎燕. 牛顿一SOR迭代方法中最佳松弛因子的算法[J]，四川大学学报，4,381-382,1995.[5] 王诗然. 稀疏线性方程组求解的逐次超松弛迭代法[J]，沈阳师范大学学报,4,407-409,2006.[6] 刘卫国. MATLAB程序设计与应用[M]，高等教育出版社，2008.[7] 张知难.关于相容次序矩阵的性质的图论证明[J].新疆大学学报, 1983, 12(3):23-26.[8] 李春光，徐成贤.确定SOR最优松弛因子的一个实用算法[J].计算力学学报，2002,19(3)：299-302.[9] 蒋家羚，王勇.最有超松弛因子的一种确定方法及其在裂纹计算中的应用[J].研究简报，2002,24(1)：133-135.[10] 王晓东. 计算机算法设计与分析[M] . 北京: 电子工业出版社, 2000.附录逐步搜索法A=[-3,1,0,1;1,-3,0,0;0,0,-3,1;1,0,1,-3]; %系数矩阵%b=[-1;-2;-2;-1];D=diag(diag(A)); %A的对角矩阵%U=-triu(A,1) ; %A上三角矩阵%L=-tril(A,-1); %A的下三角矩阵%m=[];t=[]; %创建两个空矩阵分别存放相对应的谱半径和记录迭代次数% for w=1:0.01:1.1; %取w的值%q=(D-w*L);p=inv(q); %求q的逆%Gw=p*((1-w)*D+w*U); %求得迭代矩阵%V=eig(Gw); %计算迭代矩阵的特征值%R=max(abs(V)); %找出绝对值最大的谱半径%m=[m,R];plot(w,R,'o'); %画出w和R的关系图%grid;hold onf=inv(D-w*L)*b*w;x0=[0;0;0;0]; %取迭代初值%y=Gw*x0+f;n=1;while norm(y-x0)>=1.0e-6 %迭代条件%f=inv(D-w*L)*b*w;x0=y;y=Gw*x0+f;n=n+1;endt=[t,n];end[h,k]=min(t); %h记录最小的迭代次数，k记录第几个数最小%求解过程g=1.0+(k-1)*0.01;f=inv(D-g*L)*b*g;y=Gw*x0+f;n=1;while norm(y-x0)>=1.0e-6;f=inv(D-g*L)*b*g;x0=y;y=Gw*x0+f;n=n+1;endk,h,t,m,g %g是最佳松弛因子%黄金分割法A=[-3,1,0,1;1,-3,0,0;0,0,-3,1;1,0,1,-3]; %系数矩阵%b=[-1;-2;-2;-1];D=diag(diag(A)); %A的对角矩阵%U=-triu(A,1) ; %A上三角矩阵%L=-tril(A,-1); %A的下三角矩阵%c=1;d=2;m=0.618;x0=[0;0;0;0];w1=d-m*(d-c);w2=c+m*(d-c);y=[];r=[];s=[];z=[];while abs(w2-w1)>=0.05n=1; w=w1;G=inv(D-w*L)*((1-w)*D+w*U);f=w*((D-w*L)*b);x=G*x0+f;while norm(x-x0)>=1.0e-6x0=x;G=inv(D-w*L)*((1-w)*D+w*U);f=w*((D-w*L)*b);x=G*x0+f;n=n+1;endr=[r,w];y=[y,n];k=1; w=w2;G=inv(D-w*L)*((1-w)*D+w*U);f=w*((D-w*L)*b);x=G*x0+f;while norm(x-x0)>=1.0e-6x0=x;G=inv(D-w*L)*((1-w)*D+w*U);f=w*((D-w*L)*b);x=G*x0+f;k=k+1;ends=[s,w];z=[z,k];if n>kc=w1;w1=d-m*(d-c);w2=c+m*(d-c);elsed=w2;w1=d-m*(d-c);w2=c+m*(d-c);endendr,y,s,z,w2致谢本文在指导老师崔老师的精心指导下完成的，无论是在选题、确定研究内容和研究过程中都凝聚着由老师的辛勤与汗水.由老师的严谨治学态度、无私奉献的精神、丰富的教学经验令我受益匪浅.在他那里不仅让我学到了许多宝贵的知识财富，更让我懂得了许多做人的道理.在这里我衷心地向我的指导教师崔艳星老师表示最诚挚的谢意和尊敬.最后向所有关心我和帮助我的老师和同学们表示我衷心的感谢和最诚挚的谢意！。
设it题目:摘要本文是在matlabll境下熟悉的运用计算机编程培言并结合超松弛变量起松弛迭代法的理论基础对方程组求解。
首先，本文以愉分方程边值问题为例，导出了离散化后线11方程组即稀疏线性方程组，转化对柿蔭线性方程组求解冋題。
其次，用起松弛（SOR）选代法编写matlab 程序，湘产生的柿疏线性方程组进行迭代法求解。
然后，分别改变松弛因子3和分段数n的值，分桥其收敛性和收敛速H, 18出各个方面的分林和比较需到相关结论。
最后，将起松弛迭代算法在it算机上运用matlab 言实现，借岀了一组与猜确解较接近的数值解,并画图比较，騎iil逐次超松弛（SOR）选代法的績确性。
关键词:柿匾线性方程组逐次超松弛迭代法松弛因子matlab编程-、间题提岀考虑两点逆值冋题为了把做分方程离IL 把[oj]E 间“等分，令/亠丄，脸=〃?，山12…山一1,得到 n 差分方程° 治 一 2)1 + X+—畑 一 X _ “or十—C< -h 2h简化为(£ + 必+i - © + 心+ % =肿,从而离散后得到的线性方程组的系数矩阵为一（2g + /?） £ + h£-（2£ + h ）A =££ + /?一（2w + h ）_对£ = 19 a = 0.4 , n = 200 ,分别用e = 1、6? = 0.5和e = 1.5的超松弛迭代法 求解线性方程组，要求有4也有效数字，然后比较与精确解的淚差，探讨使超松 弛选代法收敛较快的0取值，对结果进行分轿。
改变»论同wrOo二、超松弛迭代法产生的背景容易知道它的精确解为 + ax.£ + h—（2w +y =对从实际间题中借到维数相当夫的线11代数方程组的求解仍然十分困难，以至使人们不能在允许的时间内用貞接方法得到解，Slit,客观上要求用新的方法来解决大维数方程组的求解I'nJSo现有大名数迭代法不是对各类线11方程组都有收敛性，在解题时，要对原方程组葩晖作一根本的变换，从而可能使条件数变坏，也可能破坏了变换前后方程组的等价性，以员丧失使原方程组的对称II等。
