《超松弛迭代法及其松弛因子的选取》由会员分享，可在线阅读，更多相关《超松弛迭代法及其松弛因子的选取（17页珍藏版）》请在金锄头文库上搜索。
1、电孑科技大学数值分析实验报告题目：超松弛迭代法及其松弛孑的选取学生姓名：学 号：日 期：年 月 日超松弛迭代法及其松弛因子的选取问题提出：在Gauss-Seidel迭代法基础上，人们发现通过迭代-松弛一再迭代的方法，能 更加减少计算步骤，极大的缩短计算时间，在此基础上，超松弛迭代法被学者们研究出来。 在求解大型稀疏线性方程组中超松弛迭代法得到广泛应用.而SOR迭代方法中松弛因子3的 取值直接影响到算法的收敛性及收敛速度，是应用超松弛迭代法的关键选择得当，可以加快 收敛速度，甚至可以使发散的迭代变成收敛。因此，超松弛因子的选取是学者们又一个研究目 标.通过一些被验证的定理，我们知道为了保证迭代过
2、程的收敛必须要求13 2,而且松弛 因子和迭代矩阵谱半径之间有着密切的联系，现今学者们已经研究出部分特殊矩阵的最优松 弛因子的计算公式.对于一般的矩阵，我们也可以从松弛因子和谱半径的关系着手研究最优 松弛因子的选取。问题分析：1.超松弛迭代基本知识11超松弛迭代法定义超松弛(Successive Over Relaxation)迭代法，简称SOR迭代法，它是在Gauss-Seidel法基础上为提高收敛速度，采用加权平均而得到的新算法.设解方程组的Gauss-Seidel法记为x (k+1)ia iii工 a x (k+1)-ij jj=1艺 a x (k),i =j jj=i+112(1)再由
3、x.(k)与x (k+1)加权平均得i iX (k+1) = (1 -3 ) X (k) +3 X(k+1) = X (k) +3 (X (k+1) - X (k) ), i = 1,2, niiiii这里30称为松弛参数，将(1)代入则得X (k+1) = (1 3)X (k) +(b ii a iiij=1a x (k+1)艺 a x (k),i = 1,2,nij j ij jj=i+1(2)称为SOR迭代法，30称为松弛因子，当3 =1时(2)即为Gauss-Seidel法，将(2)写成矩阵形式，则得Dx（ k+i）= （1）Dx（ k）+（b + Lx（ k+i）+ Ux（ k）于是
4、得SOR迭代的矩阵表示x (k+1) = G X( k) + f1 o (3)其中G = (D-oL)-i(1-o) D + oU f =o( D o L)-i bo1.2收敛性判别条件根据迭代法收敛性定理，SOR法收敛的充分必要条件为P (G ) 1，但要计算P (G )比 oo较复杂，通常都不用此结论，而直接根据方程组的系数矩阵A判断SOR迭代收敛性，下面先给出收敛必要条件.定理1 设A = (a ) g Rnxn,a丰0(i = 1,2,., n)则解方程Ax = b的SOR迭代法收敛的 ijii，必要条件是0V3 2.定理2 若A G Rnxn对称正定，且0V3 V2,则解Ax=b的S
5、OR迭代法(3)对Vx g Rn迭代收敛.对于SOR迭代法，松弛因子的选择对收敛速度影响较大，关于最优松弛因子少研究较为复杂，且已有不少理论结果下面只给出一种简单且便于使用的结论.1.3收敛速度的估计SOR迭代法的迭代矩阵G与o有关，当选取不同的o时，其迭代速度也有所不同因此， o需要找到最优的松弛因子o，使对应o的SOR方法收敛最快.bb定理3设A e Rnxn，如果存在排列矩阵p,使D MPAPt =11M D2 2其中，D1, D2为对角矩阵，则称A是2-循环的此外，若当丰0时，矩阵a D-1L + a-1D-1U的特征值都和a无关，则称A是相容次序矩阵.定理4 设A e Rnx” ,
6、a有非零的对角元，且是2-循环和相容次序的矩阵.又设B二Di(L + U)是方程组Ax二b的Jacobi法迭代的迭代矩阵，且B2的所有特征值均在J(0,1)上，若P (B ) 1记P = P(B )则SOR法的最优松弛因子为J ,J ,b2二一b 1 + J1 -卩 2H+ 购2 H2 - 4( - 1)2P %)=一 1, 2bp (G )二 min p (G )图12松弛因子选取方法方法思想8：(1) 给出的范围，当取不同的值时，进行迭代，在符合同一个精度要求下依次求出谱半 径的值，比较出最小的谱半径，那么这个最小的谱半径所对应的的，即为所求最佳松弛因 子.(2) 给出的范围，当取不同的值
7、时，进行迭代，看它们在相同精度范围内的迭代次数, 找到迭代次数最少的那一个，其所对应的即为最佳松弛因子”21逐步搜索法算法：Step 1读入线性方程组的系数矩阵，常数向量，初值，精度，给的取值范围，以及其变化步长；Step 2：按照如下公式迭代x (k+1) = G X( k) +找出符合精度要求的迭代次数及谱半径;Step 3：循环迭代，最后找到最优松弛因子Step 4:改变o的取值范围，重新设定变化步长，重复Step2.2.2黄金分割法从定理4我们可以看到，最优松弛因子对应的谱半径最小，而黄金分割法对于数值求解单调 函数的极小和极大值是非常方便和有效的，因此，我们可以把黄金分割法应用在求最
8、优松弛因子上，其算法与主要思想是：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 )作为收敛区间，如果是对应的p迭代次数少，则选取133(p，p )作为收敛区间.24Step 3:在所选取的收敛区间里循环进行上述的两个步骤，直到选取出满足精度要求且p2，p所对应的迭代次数差不超过某个数A时选p为最优松弛因子.3 33数值算例例1:矩阵-310
9、11300A =00311013b = (1,2, 2,1)T，精度为卜k xk 一口 1.0*10 -6解法1:黄金分割法令 = 0.05，程序结果如下:w2 =1. 0901r =1. 38201. 23611. 14591. 0902由上可以看出我们只需作几次0.618法就可以找到最优松弛因子，本例中最优松弛因子二1.0901，迭代次数为8次.解法2：j逐步搜索法，步长为0.1，1 2程序结果如下:图3图3中，其横坐标表示松弛因子，纵坐标表示谱半径.h 二8t 二1381 113182230-4267142HL =CrilujTLt-LS 1 through 90. 29090. 100
10、00. 2I：II：IO 0. 30000. 40000. 5Lii：iO 0. 60000. 70000. 8000ColuJTLfL 100. 9000g 二1. 1000也可以求出最优松弛因子为1.1,迭代次数为8然后我们改变松弛因子区间，令1 1.1以步长为0.01来继续求更精确的松弛因子程序结果如下：图4图4中，其横坐标表示松弛因子，纵坐标表示谱半径.1313121212111110988JTL 二CoIujiltls 1 through 90.29090.27640.26110.24490.22760.20870.18770.16300.1301CoIujiltls 10 thro
11、ugh 110.09000.1000g 二这样继续縮小松弛因子范围，以更小的步长求得的最优松弛因子为1.0900，更加精确.例2方程组Ax二b-40 000-1-10004 000-10-1000 400-1-1-1000 0400-10-1A =00 00400-1-1-1-1 -1004000-10 -1-1004000-1 -10-1004000 -1-1-10004b = (2,2,0,2,2,1 ,1,1,1)T .精度为 |xk -xk_i| 1.0*10-6 .初始迭 代值为 x = (0,0,0,0,0,0,0,0,0) t.求最优松弛因子.0解法1黄金分割法令A = 0.00
12、1,程序结果如下:3418121411w2 =1. 1772r =CoIujiltls 1through 91. 38201.23611. 1459CoIujiltls ILthrough121. 18031.17841. 1772y 二2014115711s 二CoIijjtltls 1througl_L 91. 61801.38191. 2360C 0 IiJJTlTlS 1 0 t 1_lL 0Uh12求得最优松弛因子为1.1772.1.18341.18031.1784解法2逐步搜索法10910981.23611. 20161. 180310 1261051. 29181. 23601. 20161. 16721.18031.17531.18031.18851.1803首先以1 2，步长为0.1搜索k =3h =H|t =221711141723304367143jtl =Co1ujtli-ls 1 thirrmgh 90. 80000.5000 LL 3786 U. 2000 U. 30000. 40000.50000. 60000. 7000ColujTLt-L 10LL 9000求得的最优松弛因子为1.2000,然后重新设定范围，以步长为0.01运行程序g =1. 2000h 二10 t 二1716161514141312101111ITl =ColujTLrLS
