超松弛迭代法及其松弛因子的选取

取0901数学系法》是我个人在导师崔艳星指导下进行的研究工作及取得的研究成果. 料.所有合作者对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意. 论文. 容的一致性和准确性. 要本文首先给出了超松弛迭代法解线性方程组的基本概念，引进了关于超松弛迭代法收敛性判别的一些定理.再基于超松弛迭代法收敛性快慢与松弛因子的选择密切相关，本文给出了能准确快速地确定最优松弛因子的方法逐步搜索法和黄金分割法，并且写出了其Matlab程序(附录)，最后通过实例验证了方法的准确性，快速性.方程组；超松弛迭代；Matlab程序；松弛因子AbstractThispaperfirstlyintroducesthebasicconceptofthesuperrelaxationiterationmethodforsolvinglinearequations,introducedonsomecriteriontheoremOverrelaxationiterativeconvergence,givesasimpleMatlabprogramsuperrelaxationiteration(Appendix1).ThenOverrelaxationiterativeconvergenceconvergencespeedandrelaxationfactorisselectedbasedonthecloserelationisproposedinthispaperpaper,therapidandaccuratemethodofdeterminingtheoptimalrelaxationfactorofthedirectsearchmethodmethodandthegoldensectionmethod,andwritetheMatlabprogram(Appendix2),finallythemethodisaccurate,rapid.松弛因子的选取09404307程启远信息与计算科学指导教师崔艳星在科学计算和工程设计中，经常会遇到求解线性代数方程组的问题，而怎样快速的求解一直是我们共同关心的课题.随着计算机技术及数学编程软件的发展，我们有了在计算机上解线性方程组的条件.最初遇到的方程数和未知数比较少的方程组我们就是利用线性代数知识直接解出来.直接解法只能适用于经过有限步运算能求得解的方程组.后来遇到的方花费时间太多，因此迭代法发展了起来.从最初的Jacobi迭代法到Gauss-Seidel迭代法，很多学在Gauss-Seidel迭代法基础上，人们发现通过迭代-松弛—再迭代的方法，能更加减少计算步骤，极大的缩短计算时间，在此基础上，超松弛迭代法被学者们研究出来.通过比较三种迭代方法，我们得到超松弛迭代的收敛速度是最快的，而且超松弛迭代法具有计算公式简单，编制程序容易等突出优点.在求解大型稀疏线性方程组中超松弛迭代法得到广泛应用.而SOR迭代方法中松弛因子的取值直接影响到算法的收敛性及收敛速度，是应用超松弛迭代法的关键.选择得当,可以加快收敛速度,甚至可以使发散的迭代变成收敛.因此,超松弛因子的选取是学者们又一个研究目标.通过一些被验证的定理，我们知道为了保证迭代过程的收敛,必须要求1<<2，而且松弛因子和迭代矩阵谱半径之间有着密切的联系，现今学者们已经研究出部分特殊矩阵的最优松弛因子的计算公式.对于一般的矩阵，我们也可以从松弛因子和谱半径的关系着手研究最优松弛因子的选取，这就为本篇论文的形成提供了行文思路.本文给出了求超松弛迭代最优松弛因子的两种方法.1.1超松弛迭代法定义[1]超松弛(SuccessiveOverRelaxation)迭代法，简称SOR迭代法，它是在Gauss-Seidel法基础上为提高收敛速度，采用加权平均而得到的新算法.设解方程组的Gauss-Seidel法记为iij=1j=i+1(1)iiij=1j=i+1(1)再由x(k)与x(k+1)加权平均得iiiiiii这里ω＞0称为松弛参数，将(1)代入则得iij=1j=i+1(2)iiij=1j=i+1(2)称为SOR迭代法，ω＞0称为松弛因子，当ω=1时(2)即为Gauss-Seidel法，将(2)写成矩阵形 式，则得于是得SOR迭代的矩阵表示[3]iOi其中OO1.2收敛性判别条件根据迭代法收敛性定理[2]，SOR法收敛的充分必要条件为p(G)想1，但要计算p(G)比OO较复杂，通常都不用此结论，而直接根据方程组的系数矩阵A判断SOR迭代收敛性，下面先给出收敛必要条件.ijii，必要条件是0＜ω＜2.定理2[5]若A=Rn人n对称正定，且0＜ω＜2，则解Ax=b的SOR迭代法(3)对Vx=Rn迭代收敛.杂，且已有不少理论结果.下面只给出一种简单且便于使用的结论.1.3收敛速度的估计SOR迭代法的迭代矩阵G与o有关，当选取不同的o时，其迭代速度也有所不同.因此，obb需要找到最优的松弛因子o，使对应o的SORbbD1M2MD21212的特征值都和a无关，则称A是相容次序矩阵.ARnnA角元，且是2-循环和相容次序的矩阵.又设B=D_1(L+U)是方程组Ax=b的Jacobi法迭代的迭代矩阵,且B2的所有特征值均在J (0,1)上，若p(B)<1记山=p(B)则SOR法的最优松弛因子o为J,J,bo=2且ll4b4bbp(G)=minp(G)obob12松弛因子选取方法(1)给出的范围，当取不同的值时，进行迭代，在符合同一个精度要求下依次求出谱半径的值，比较出最小的谱半径，那么这个最小的谱半径所对应的的,即为所求最佳松弛因子.(2)给出的范围，当取不同的值时，进行迭代，看它们在相同精度范围内的迭代次数，找到迭代次数最少的那一个，其所对应的即为最佳松弛因子.”2.1逐步搜索法xk1)=Gx(k)+fi找出符合精度要求e的迭代次数及谱半径;Step循环迭代，最后找到最优松弛因子Step4:改变的取值范围，重新设定变化步长，重复Step2.2.2黄金分割法函数的极小和极大值是非常方便和有效的[9]，因此，我们可以把黄金分割法应用在求最优松弛因子上，其算法与主要思想是：Step1:利用优选法思想，在(1,2)之间选取四个点，1244131414Step2:分别取p与p作为松弛因子代入迭代程序，比较出最少的迭代次数，如果对p应232的迭代次数少，则选取(p,p)作为收敛区间，如果是对应的p迭代次数少，则选取133(p,p)作为收敛区间.24Step3:在所选取的收敛区间里循环进行上述的两个步骤，直到选取出满足精度要求且p，2p所对应的迭代次数差不超过某个数A时选p为最优松弛因子.33例1:矩阵AA||||||101-30000-310101|||解法1:黄金分割法由上可以看出我们只需作几次0.618法就可以找到最优松弛因子，本例中最优松弛因子图3中，其横坐标表示松弛因子，纵坐标表示谱半径.步长为0.01来继续求更精确的松弛因子.程序结果如下：图4中，其横坐标表示松弛因子，纵坐标表示谱半径.这样继续缩小松弛因子范围，以更小的步长求得的最优松弛因子为1.0900，更加精确.，「40000-1-100]x=(0,0,0,0,0,0,0,0,0)T.求最优松弛因子.0解法1黄金分割法，求得最优松弛因子为1.1772.解法2逐步搜索法求得的最优松弛因子为1.2000,然后重新设定范围，以步长为0.01运行程序在改变范围，以步长为0.001运行，程序结果如下：求得的最优松弛因子为1.1780.由这两个例子可以看出利用黄金分割法求最优松弛因子比用逐步搜索法更加简便快速，但是用逐步搜索法步长取的很小时求得的松弛因子比黄金分割法更加精确.中都会应用.而且超松弛迭代法公式简单，编制程序容易.而使用超松弛迭代法的关键在于选取合适的松弛因子，如果松弛因子选取合适，则会大大缩短计算时间.本文依据松弛因子和矩阵谱半径的关系给出了两种选取松弛因子的方法逐步搜索法和黄金分割法及其Matlab程序.但这两种方法仍不是足够简便，有所不足，有待进一步研究.M.[2]施吉林.计算机数值方法[M].北京:高等教育出版社,2000.M[4]李建宇，黎燕.牛顿一SOR迭代方法中最佳松弛因子的算法[J]，四川大学学报，4,381-382,1995.[5]王诗然.稀疏线性方程组求解的逐次超松弛迭代法[J]，沈阳师范大学学报,4,407-409,2006.MATLABM.[7]张知难.关于相容次序矩阵的性质的图论证明[J].新疆大学学报,1983,12(3):23-26.[8]李春光，徐成贤.确定SOR最优松弛因子的一个实用算法[J].计算[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=[];%创建两个空矩阵分别存放相对应的谱半径和记录迭代次数%forw=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');grid;holdon%计算迭代矩阵的特征值%%找出绝对值最大的谱半径%%画出w和R的关系图%f=inv(D-w*L)*b*w;x0=[0;0;0;0];%取迭代初值%y=Gw*x0+f;n=1;whilenorm(y-x0)>=1.0e-6f=inv(D-w*L)*b*w;%迭代条件%x0=y;y=Gw*x0+f;n=n+1;dt=[t,n];d%求解过程g=1.0+(k-1)*0.01;f=inv(D-g*L)*b*g;y=Gw*x0+f;n=1;whilenorm(y-x0)>=1.0e-6;f=inv(D-g*L)*b*g;x0=y;y=Gw*x0+f;n=n+1;dk,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));