《超松弛迭代法及其松弛因子的选取》由会员分享，可在线阅读，更多相关《超松弛迭代法及其松弛因子的选取（25页珍藏版）》请在金锄头文库上搜索。
1、2013届学士学位毕业论文超松弛迭代法及其松弛因子的选取学号:姓名:班级:指导教师:专业:系别:09404307程启远信息0901崔艳星信息与计算科学数学系完成时间：2013年5月学生诚信承诺书本人郑重声明：所呈交的论文超松弛迭代中松弛因子的选取方 法是我个人在导师崔艳星指导下进行的研究工作及取得的研究成果. 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写的研究成果，也不包含为获得长治学院或其他教 育机构的学位或证书所使用过的材料.所有合作者对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意.签名： 日期：论文使用授权说明本人完全了解长治学院有关保
2、留、使用学位论文的规定，即：学 校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存 论文.签名： 日期：指导教师声明书本人声明：该学位论文是本人指导学生完成的研究成果，已经审 阅过论文的全部内容，并能够保证题目、关键词、摘要部分中英文内 容的一致性和准确性.指导教师签名： 时间本文首先给出了超松弛迭代法解线性方程组的基本概念，引进了关于超松弛迭代法收敛 性判别的一些定理再基于超松弛迭代法收敛性快慢与松弛因子的选择密切相关，本文给出 了能准确快速地确定最优松弛因子的方法逐步搜索法和黄金分割法，并且写出了其Matlab 程序（
3、附录），最后通过实例验证了方法的准确性，快速性.关键词 线性方程组；超松弛迭代；Mat lab程序；松弛因子AbstractThis paper firstly introduces the basic concept of the super relaxation iteration method for solving linear equations, introduced on some criterion theorem Overrelaxation iterative con verge nee, gives a simple Matlab program super relaxa
4、ti on iterati on (Appe ndix 1). Then Overrelaxati on iterative con verge nce speed and relaxati on factor is selected based on the close relati on is proposed in this paper, the rapid and accurate method of determining the optimal relaxation factor of the direct search method and the golden secti on
5、 method, and write the Matlab program (Appe ndix 2), fin ally the method is accurate, rapid.Key word: Linear equations; Successive Over Relaxation; Matlab program; relaxation factor超松弛迭代法及其松弛因子的选取09404307 程启远信息与计算科学指导教师 崔艳星引言在科学计算和工程设计中，经常会遇到求解线性代数方程组的问题，而怎样快速的求解一直是我们共同关心的课题.随着计算机技术及数学编程软件的发展，我们有了在计
6、 算机上解线性方程组的条件最初遇到的方程数和未知数比较少的方程组我们就是利用线性 代数知识直接解出来直接解法只能适用于经过有限步运算能求得解的方程组后来遇到的方 程数和未知数都比较多的方程组,特别是经常会遇到的大型的方程组，直接解法工作量太大， 花费时间太多，因此迭代法发展了起来从最初的Jacobi迭代法到Gauss-Seide 1迭代法，很多 学者一直在研究找到一种迭代法能更加快速，简单的解决线性方程组通过不断的实验和计 算，在Gauss-Seide 1迭代法基础上，人们发现通过迭代-松弛一再迭代的方法，能更加减少计 算步骤，极大的缩短计算时间，在此基础上，超松弛迭代法被学者们研究出来通过比
7、较三 种迭代方法，我们得到超松弛迭代的收敛速度是最快的，而且超松弛迭代法具有计算公式简 单，编制程序容易等突出优点在求解大型稀疏线性方程组中超松弛迭代法得到广泛应用而 SOR迭代方法中松弛因子的取值直接影响到算法的收敛性及收敛速度，是应用超松弛迭 代法的关键选择得当，可以加快收敛速度，甚至可以使发散的迭代变成收敛.因此，超松弛因 子的选取是学者们又一个研究目标通过一些被验证的定理，我们知道为了保证迭代过程的 收敛，必须要求lv 0称为松弛参数，将(1)代入则得X (k+1) = (1 -3 ) X (k) + (b -2 a X (k+1) 一区 a X (k) ),i = 1,2, n(2)
8、iI a I ij jij jiij=1j=i+1称为SOR迭代法，3 0称为松弛因子，当3 =1时(2)即为Gauss-Seidel法，将(2)写成矩阵形式，则得Dx (k+1) = (1-3 ) Dx (k) +3 (b + Lx (k+1) + Ux (k)于是得SOR迭代的矩阵表示X (k+1) = G X(k) +其中G = (D-3 L)-1(1-3) D + 3U 3f =3( D-3 L)-1 b31.2收敛性判别条件根据迭代法收敛性定理2，SOR法收敛的充分必要条件为P (G3) 1，但要计算P (G3)比较复杂，通常都不用此结论，而直接根据方程组的系数矩阵A判断SOR迭代收
9、敛性，下面先给出收敛必要条件.定理14设 A = (a ) g Rnxn, a 丰 0(i = 1,2,., n)ijii则解方程Ax = b的SOR迭代法收敛的必要条件是0V3 V2.定理2 若A e Rnxn对称正定，且0VeV2,则解Ax=b的SOR迭代法(3)对Vx e Rn迭代 收敛.对于SOR迭代法，松弛因子的选择对收敛速度影响较大，关于最优松弛因子田研究较为复 杂，且已有不少理论结果下面只给出一种简单且便于使用的结论.1.3收敛速度的估计SOR迭代法的迭代矩阵G与有关，当选取不同的时，其迭代速度也有所不同因此，(D需要找到最优的松弛因子，使对应的SOR方法收敛最快.bb定理3设A
10、 e Rn，如果存在排列矩阵P,使D MPAPt = i 1M D2 2其中，D, D2为对角矩阵，则称A是2-循环的此外，若当丰0时，矩阵a D-i L + 1D-1U的特征值都和a无关，则称A是相容次序矩阵.定理4 设A e Rnxn，A有非零的对角元，且是2-循环和相容次序的矩阵又设B = D-i(L + U)是方程组Ax = b的Jacobi法迭代的迭代矩阵，且B2的所有特征值均在 J(0,1)上，若P (B ) 1记P = P(B )则SOR法的最优松弛因子为J,J ,bCDbH +2 U2 4( 1)2,0 (4b一 1, 2lbP (G )二 min p (G )b0 2b图12
11、松弛因子选取方法方法思想:(1) 给出的范围，当取不同的值时，进行迭代，在符合同一个精度要求下依次求出谱半 径的值，比较出最小的谱半径，那么这个最小的谱半径所对应的的，即为所求最佳松弛因 子.(2) 给出的范围，当取不同的值时，进行迭代，看它们在相同精度范围内的迭代次数, 找到迭代次数最少的那一个，其所对应的即为最佳松弛因子”21逐步搜索法算法：Step 1：读入线性方程组的系数矩阵，常数向量，初值，精度，给的取值范围，以及其变化步长；Step 2：按照如下公式迭代x (k+1) = G x( k) +找出符合精度要求的迭代次数及谱半径;Step 3：循环迭代，最后找到最优松弛因子Step 4
12、:改变o的取值范围，重新设定变化步长，重复Step2.2.2黄金分割法从定理4我们可以看到，最优松弛因子对应的谱半径最小，而黄金分割法对于数值求解单调 函数的极小和极大值是非常方便和有效的，因此，我们可以把黄金分割法应用在求最优松弛因子上，其算法与主要思想是:Step 1:利用优选法思想，在（1,2）之间选取四个点p = 1,p = p 一 0.618（p 一 p ）, p = p + 0.618（p 一 p ）, p = 21244131414Step 2:分别取p与p作为松弛因子代入迭代程序，比较出最少的迭代次数，如果对p应 232的迭代次数少，则选取（p , p ）作为收敛区间，如果是对
13、应的p迭代次数少，则选取 133（p，p ）作为收敛区间.24Step 3:在所选取的收敛区间里循环进行上述的两个步骤，直到选取出满足精度要求且p，2p所对应的迭代次数差不超过某个数A时选p为最优松弛因子. 333数值算例例1：矩阵_-3101_1-300A =00-31_ 101-3_b （-1,-2,-2,-1）T，精度为|xk -xk-1| 1.0*10-6解法1:黄金分割法令A 0.05，程序结果如下：w2 =1. 0901r 二1. 38201. 23611. 14591. 09021912108S =由上可以看出我们只需作几次0.618法就可以找到最优松弛因子，本例中最优松弛因子3= 1.0901，迭代次数为8次.解法2：逐步搜索法，步长为0.1，1 2程序结果如下:图3图3中，其横坐标表示松弛因子，纵坐标表示谱半径.h 二8t 二1381 113182230-4267142HL =CrilujTLt-LS 1 through 90. 29
