逐次超松弛迭代法

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 足够大时，此序列就可以作为线性方程组的近似解。

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 足够大时，此序列就可以作为线性方程组的近似解。

超松弛迭代法例题超松弛迭代法（Successive Over-Relaxation，简称SOR）是一种解线性方程组的迭代方法，它在雅可比迭代法的基础上，对于每次迭代的结果进行超松弛处理。

超松弛迭代法通过引入一个松弛因子来加快收敛速度，尤其对于收敛慢的问题具有较好的效果。

超松弛迭代法的基本思想是，在每次迭代时，在当前解的基础上引入一个松弛因子ω，将当前解对应的分量更新为上一次迭代得到的解和当前迭代中该分量的修正量的线性组合。

换句话说，超松弛迭代法通过适当地加权迭代，既保留了松弛迭代法的简洁性，又在一定程度上加快了收敛速度。

超松弛迭代法可以用以下公式表示：x_i^{(k+1)} = (1 - ω)x_i^{(k)} + ω/α_ii(b_i - \sum_{j=1}^{n}α_ijx_j^{(k+1)}) (i = 1, 2, ..., n)其中，x_i^{(k+1)} 表示第k+1次迭代时第i个未知量的近似解，x_i^{(k)} 表示第k次迭代时第i个未知量的近似解，α_ij 是系数矩阵的元素，b_i 是方程组的常数向量的第i个分量，α_ii是系数矩阵的第i行的对角元素，n 表示未知量的个数，k 表示当前的迭代次数，ω 是松弛因子。

超松弛迭代法的收敛性与松弛因子ω有关，当ω=1时，迭代法变成了雅可比迭代法；当0 < ω < 1时，称为欠松弛迭代；当ω > 1时，称为超松弛迭代。

一般来说，超松弛迭代法只在0 < ω < 2的范围内收敛。

对于特定的线性方程组，选择一个合适的松弛因子可以有效地加快迭代的收敛速度。

在实际求解问题时，选择合适的松弛因子是非常重要的。

如果选取的松弛因子过大，可能导致迭代法不收敛或者收敛非常慢；如果选取的松弛因子过小，则可能无法发挥超松弛迭代法的优势。

一种常用的方法是通过试验和经验来确定最佳的松弛因子，或者通过一些启发式的方法进行优化。

总结起来，超松弛迭代法是一种通过引入松弛因子来加快雅可比迭代法收敛速度的方法。

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致谢本文在指导老师崔老师的精心指导下完成的，无论是在选题、确定研究内容和研究过程中都凝聚着由老师的辛勤与汗水.由老师的严谨治学态度、无私奉献的精神、丰富的教学经验令我受益匪浅.在他那里不仅让我学到了许多宝贵的知识财富，更让我懂得了许多做人的道理.在这里我衷心地向我的指导教师崔艳星老师表示最诚挚的谢意和尊敬.最后向所有关心我和帮助我的老师和同学们表示我衷心的感谢和最诚挚的谢意！。

超松弛迭代法课程设计一、课程目标知识目标：1. 学生能理解超松弛迭代法的概念，掌握其基本原理和应用场景。

2. 学生能够运用超松弛迭代法解决线性方程组问题，并理解其收敛性。

3. 学生能了解超松弛迭代法在工程和科学计算中的重要性。

技能目标：1. 学生能够独立进行超松弛迭代法的计算步骤，包括设定松弛因子、构造迭代矩阵等。

2. 学生能够运用数学软件（如MATLAB）实现超松弛迭代法的算法，并进行简单的程序调试。

3. 学生通过实际案例分析，培养运用超松弛迭代法解决实际问题的能力。

情感态度价值观目标：1. 学生通过学习超松弛迭代法，培养对科学计算和数学建模的兴趣，增强对数学学科的学习信心。

2. 学生在小组讨论和合作中，学会尊重他人意见，培养团队协作精神。

3. 学生能够认识到超松弛迭代法在科技发展中的重要作用，增强科技创新意识和社会责任感。

课程性质：本课程为高中数学选修课，以培养学生解决实际问题能力和数学思维能力为目标。

学生特点：学生具备一定的线性代数基础，具有较强的逻辑思维能力和动手操作能力。

教学要求：教师应注重理论与实践相结合，引导学生通过实际案例掌握超松弛迭代法的应用。

同时，注重培养学生的团队协作能力和创新意识。

在教学过程中，关注学生的学习进度，及时调整教学策略，确保课程目标的实现。

通过课堂讲解、上机实践和小组讨论等多种教学方式，提高学生的学习效果。

二、教学内容1. 引言：介绍超松弛迭代法的背景和在实际问题中的应用，激发学生学习兴趣。

相关教材章节：第二章第四节“迭代法及其应用”。

2. 基本概念：讲解超松弛迭代法的基本原理，包括迭代格式、松弛因子选取等。

相关教材章节：第二章第四节“超松弛迭代法”。

3. 算法实现：详细讲解超松弛迭代法的计算步骤，并通过实例进行演示。

相关教材章节：第二章第四节“超松弛迭代法的计算步骤”。

4. 实践应用：分析实际案例，让学生动手实践，运用超松弛迭代法解决线性方程组问题。

相关教材章节：第二章第五节“迭代法解决实际问题”。

设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等。

松弛迭代法
拉格朗日松弛迭代法(Rayleigh-Ritz Relaxation Method，简称 RRR 法)也称为牛顿松弛迭代法，它结合了牛顿法和松弛迭代法的理论思想，是一种求解常微分方程组的迭代法。

该法引入拉格朗日函数作为迭代的手段，是一种改进的迭代法。

拉格朗日松弛迭代法的基本思想是：针对解决系统方程中的迭代过程，可以将周期性求解出的解表达成一个拉格朗日函数，然后计算最优解以期达到更快的收敛。

具体工作步骤如下：
第一步：初始化变量和精度参数；
第二步：将各变量表示成Fourier级数；
第三步：任意给定初始值，用此为步进量，将目标函数拆分为拉格朗日函数，使得精度参数达到最优值；
第四步：将此值作为步长，依次求解各个变量；
第五步：在迭代过程中，改变步长，即可更新函数值，达到最优解。

拉格朗日松弛迭代法基于牛顿法可以求解出一个准确的解，并以此作为步长，松弛系数以较小的步长，任意的改变步长，不断的拉格朗日函数更新，然后求解最优解，使得整个迭代过程逐渐收敛，同时也充分考虑了步长的变化，可以研究出解析解。

本方法既可以用于求解定常面上的静解又可以用于求解一定频率的动解，甚至于一般情况下的复杂系统，该法有着广泛的应用。

超松弛迭代法历史演变超松弛迭代法（SOR）是一种用于线性方程组求解的数值方法。

它结合了松弛迭代法和高斯-赛德尔迭代法的优点，具有快速收敛和稳定性的特点。

本文将从超松弛迭代法的起源开始，详细阐述它的历史演变。

超松弛迭代法最早由美国数学家David M.Young于1950年提出。

当时，他受到高斯-赛德尔迭代法的启发，希望通过引入松弛参数来提高迭代的收敛速度。

这个想法是在每次迭代时，对于每个未知数，根据已知的值和方程组来更新它的值，而不是等到所有未知数都计算完毕再更新。

这样可以更快地逼近方程组的解。

然而，Young的初始提案并不是很成功。

他发现在一些情况下，超松弛迭代法的收敛速度并没有比传统的迭代法更快。

于是，他开始研究如何选择合适的松弛参数。

在他的研究中，他发现如果松弛参数大于1，超松弛迭代法的收敛速度会加快，而如果松弛参数小于1，收敛速度反而会变慢。

这一发现打开了超松弛迭代法的新局面。

在1960年代，科学家们开始对超松弛迭代法进行更深入的研究和改进。

他们发现，超松弛迭代法在对称正定矩阵的线性方程组求解中表现得尤为出色。

这是由于对称正定矩阵具有特殊的性质，可以使得超松弛迭代法更快地收敛。

为了进一步提高超松弛迭代法的收敛速度，研究人员开始探索如何自适应地选择松弛参数。

他们发现，选择合适的松弛参数可以使得超松弛迭代法在不同情况下都表现得更好。

于是，一些自适应超松弛迭代法被提出。

在20世纪80年代和90年代，随着计算机技术的快速发展，科学家们开始使用超松弛迭代法来解决更大规模的线性方程组。

他们发现，超松弛迭代法可以通过并行计算的方式，进一步提高求解效率。

这为超松弛迭代法的应用提供了更广阔的空间。

随着时间的推移，超松弛迭代法在求解线性方程组中的应用越来越广泛。

它被广泛应用于科学计算、工程建模、优化问题等领域。

许多数值计算软件和库都提供了超松弛迭代法的实现，使得使用者可以方便地应用该方法。

尽管超松弛迭代法在求解线性方程组中表现出色，但它也有一些局限性。

超松弛迭代法公式与jacobi的关系超松弛迭代法（SOR）和Jacobi迭代法是常用的求解线性方程组的迭代方法。

它们都是通过迭代逼近线性方程组的解，但是在具体的迭代过程和收敛性上有所不同。

首先来看一下Jacobi迭代法。

给定线性方程组Ax=b，其中A是一个n×n的方阵，b是一个n维向量，x是我们要求解的未知向量。

Jacobi迭代法的思想是将线性方程组的每个方程分别写成一个未知量的函数，并通过迭代的方式逐步求解。

具体来说，Jacobi迭代法的迭代公式如下：$$x^{(k+1)}=D^{-1}(b-Rx^{(k)})$$其中，$x^{(k+1)}$表示第k+1次迭代得到的近似解，$x^{(k)}$表示第k次迭代得到的近似解，D是A的对角线元素组成的对角矩阵，R是A的非对角线元素组成的矩阵。

这个公式的意义是，我们通过用上一次迭代得到的近似解$x^{(k)}$来逼近线性方程组的解，每次迭代都只使用上一次迭代得到的近似解。

接下来我们来看看超松弛迭代法。

超松弛迭代法是对Jacobi迭代法的改进，通过引入一个松弛因子ω来加速迭代过程。

其迭代公式如下：$$x^{(k+1)}=(D-ωL)^{-1}[(1-ω)D+ωU]x^{(k)}+(D-ωL)^{-1}b$$其中，L是A的下三角部分，U是A的上三角部分。

超松弛迭代法在每次迭代中使用了上一次迭代和当前迭代的信息，通过调节松弛因子ω的取值，可以加速收敛过程。

从迭代公式可以看出，Jacobi迭代法和超松弛迭代法的主要区别在于超松弛迭代法引入了松弛因子ω，并且在每次迭代中使用了上一次迭代的信息。

这使得超松弛迭代法在一定条件下可以比Jacobi迭代法更快地收敛到线性方程组的解。

在实际应用中，选择合适的松弛因子ω对超松弛迭代法的收敛性和稳定性至关重要。

通常情况下，选择ω的取值范围为(0,2)，对于某些特定的线性方程组，可以通过一些经验规则或者数值试验来确定最佳的ω值。

基于自适应遗传算法的SOR迭代（华南理工大学理学院数学系计算数学牛海静）摘要：对于确定逐次超松驰迭代法中的最佳松驰因子问题, 迄今, 人们还没有给出一可行实用的方法. 利用自适应遗传算法全局搜索性能、并行性及其遗传操作, 构造出近似确定最佳松驰因子的一种自适应进化方法, 并由此得到一近似确定功能的自适应逐次超松驰迭代算法. 数值算例表明, 该算法在求解线性方程组中是可行的, 实用和快捷的.关键词：逐次超松驰迭代法; 遗传算法; 最佳松驰因子; 线性方程组1引言在科学计算和工程设计中, 人们经常会遇到求解线性代数方程组问题, 而且在计算方法的其它分支的研究也往往归结为此类问题. 目前, 大型的线性方程组都是利用计算机进行数值求解, 归结起来, 主要有两类: 一类是直接解法, 就是指经过有限步运算求得方程组的解的一类方法, 此类方法比较适用于系数矩阵稠密的中、小型线性方程组; 另一类是迭代解法,适用于解大型、稀疏矩阵的线性方程组. 逐次超松驰迭代法(Successive Over-Relaxation) 是解线性方程组的一种迭代加速法, 是求解大型线性方程组的有效方法之一. 通过选择恰当的松驰因子, 它能使收敛速度变得较快, 也使发散的可能变成收敛, 因此, 超松驰迭代法算法有着极高的应用价值. 本文利用自适应遗传算法全局搜索性能和并行性、及其遗传操作, 构造出一种近似确定最佳松驰因子的自适应进化算法, 并由此得到一个近似确定功能的自适应遗传逐次超松驰迭代法(Adaptive Genetic Algorithm Successive Over-Relaxation) 算法, 简称为A GA SOR.2 逐次超松驰迭代法超松驰迭代法简称为SOR 法, 是求解线性代数方程组的一种迭代加速法, 它是在Gauss Seidel 迭代法的基础上进行加速的, 将前一步的结果ki x与Gauss Seidel 迭代方法的迭代值(1)k ix 适当的加权平均, 期望获得更好的近似值(1)k ix .其迭代公式如下:1(1)()(1)()1(1)[],i n k k k k iiiijjijjj j iiixx b a xa xa1,2,,;0,1,2,i n k其中：为松弛因子. SOR 法中取值对迭代公式的收敛速度影响很大, 它的好坏直接影响到收敛速度的快慢. 为了保证迭代过程的收敛, 必须要求02，但是在0 和2 之间有很多的取值, 究竟如何取值至今没有较好的解决方法. 基于此目的, 文中提出一个可一般确定近似值的自适应数值进化方法, 该方法利用的是自适应遗传算法中全局性、并行性及其遗传操作, 使其快捷方便. 该算法适用于满足SOR 迭代方法的大型稀疏矩阵的线性方程组.3 遗传算法原理与A GA SOR 算法3.1 适应度函数与编码实现若一个代数方程组, 它由n 个方程组组成, 涉及m 个变量:11()()()()iinnX X X X f A fA fA(1)其中：1()f 可为除分段函数外的任意形式的函数表达式,,{|(,)}.j i j Xx x x X x a b 12m ，，...,求解方程组(1)等价于求极值问题: 求一X ,以使式(2)取值最小.当最小值为0时,所对应的X ,即为方程之解; 当其最小值不为0 时, 则此方程组无解. 设适应度函数: 1()(),niii F X X XfA(2)本文是用遗传算法寻找SOR 法中的最佳松驰因子, 确定在(0, 2) 区间的最优值. 对于,选定迭代初始值后, 它与方程组的解X 联系是比较紧密, 较好的可以在较少的迭代次数内得到较精确的解. 因而, 为了更好的平衡这种关系,可以用式(2) 与迭代次数K 的平均值的负值做为适应度函数, 即:1()()(),22niii X K F X KFit XfA(3)（或者可以选择适应度函数为 111()()()n iii Fit F X KX KfA也可以吧，不知道效果怎么样）求适应度函数时, 也要把迭代次数考虑进来. 如果比较差, 有可能达不到所要求的精度, 就会无限迭代下去. 因此,给出一个限定条件, 如果迭代次数达到最大限定, 则k 取最大限, 适应度还按式(3) 进行处理. 同时为使算法能适用于任意的线性方程组, 必须根据用户输入的系数矩阵A 和常数项向量B , 还有选代初始值0X 和要求精度, 用上述方法生成适应度函数.对于染色体编码, 本文采用实数编码. 与二进制编码相比, 采用实数编码方式, 使算法具有较高的通用性. 同时, 为了更好地与实际问题相结合, 将方程组的解X 和迭代次数K 放在的后面, 一起组成一个染色体Pop , 即:[].i i i Pop X K 其中的X 和K 都是采用实数表示, 即用原值表示. 这样更利于最佳松驰因子寻优和方程求解.3.2 遗传算子 3.2.1 选择算子选择算子采用轮盘法、锦标赛选择法和几何规划排序选择法的结合. 轮盘法的基本精神是个体被选中的概率取决于个体的相对适应度:i iif p f (4)其中: i p 个体i 被选中的概率; if 个体i 的适应度;if 群体的累加适应度.显然, 个体适应度越高被选中的概率愈大. 但是, 适应度小的个体也有可能被选中, 以便增加下代群体的多样性. 而锦标赛选择法是随机地从种群中选一定数目的()Tour 个体, 然后将最好的个体选做父个体. 这个过程重复进行完成个体的选择. 锦标赛选择法的参数为竞赛规模Tour , 其取值范围为 [ 2,N ind ] (其中N ind 是竞赛规模, 允许比2大的数) , 这里取Tour 为3, 使多样化得到一定的损失. 几何规划排序选择法是基于几何规划排序进行选择,主要是对适应度进行排序, 较好的做为父个体, 这有利于防止较好个体的破坏. 综合各自的特点, 本算法选择是先利用几何规划排序选择法对初始群体进行选择, 然后用锦标赛选择法对几何规划排序选择法得到的父群体进行选择, 最后用轮盘法选择. 这样可以提高收敛速度和搜索范围, 更有利于交叉与变异的进行. 3.2.2交叉算子算术交叉算子是实数编码遗传算法中应用最广泛的一种算子, 其采用的交叉方法是线性插值. 比如在两个体1,2之间进行算术交叉, 则交叉运算所产生出的两个新个体为*112*212(1)(1)(5)其中是在[0,1] 区间内的参数, 它可以是一个常数, 也可以是由进化所决定的变量, 本文选择为[ 0, 1 ]区间上的随机数. 3.2.3变异算子本文采用均匀变异和边界变异两种变异算子. 对其说明如下:均匀变异是指分别用符合某一范围内均匀分布的随机数, 以某一较小的概率替换个体编码串中各个基因座上的原有基因值. 其具体过程是: 假设有一个个体为12k l XX X X X .若k X 为变异点, 其取值范围为min max [,]k k U U (其中minkU 表示的是基因k X 可取值范围的最小值, 而max kU 表示最大值) , 在该点以个体X进行均匀变异后, 可得到一个新的个体''12,k l X X X X X 其中变异点的新基因值是: minm min 'ax ().k k k kU r U U X 式中r 为范围内符合均匀分布的一个随机数.边界变异是均匀变异操作的一个变形遗传算子. 在进行边界变异操作时, 随机地取基因座的二个对应边界基因之一取代原有基因值. 在进行由12k l XX X X X 向''12k l X X X X X 的边界变异时, 若变异点k X 处的基因值取范围为min max [,]k kU U ,则新的基因'k X 由下式确定:min max,, 1.kk U U如果random(0,1)=0;如果random(0,1)= (6)式中if random(0,1)表示以均匀等概率从0，1中任取其一.( 补充：由于本文中的染色体只有三个基因组成，且后面的两个基因X 和K 的值是随着基因的选取而相应变化的，所以我们本文的交叉和变异操作只针对于基因进行，这样X 和K 的值会根据适应度函数等相应产生新的值.) 3.2.4终止条件以设定的最大的遗传代数为终止条件 3.3 交叉概率c P 和变异概率m P遗传算法的参数中交叉概率c P 和变异概率m P 的选择是影响遗传算法行为和性能的关键所在, 直接影响算法的收敛性. c P 越大, 新个体产生的速度就越快, 但过大时遗传模式被破坏的可能性也越大; 但是如果 c P 过小, 会使搜索过程缓慢, 以至停滞不前. 对于变异概率m P , 如果 m P 过小, 就不易产生新的个体结构; 如果m P 取值过大, 那么遗传算法就变成了纯粹的随机搜索算法. 针对此问题, Srinvivas 等提出一种自适应遗传算法(Adaptive GA ,A GA ) , c P 和m P 能够随适应度自动改变. 本算法中,c P 和m P 根据式(7)式(8)来动态确定, 从而增加算法的进化能力和收敛速度.'12'1max '1,()(),c c avg c avgavgcc avgP P f f P f f f f P P f f (7)12max1max1,()(),m m m avgavg mm avgP P f f P ff f f P P ff (8)其中: 1212max 0.9,0.6,0.1,0.001,c c m m P P P P f 为群体中最大的适应度值;avg f 为每代群体的平均适应度值; 'f 为要交叉的两个个体中较大的适应度值; f 为要变异个体的适应度值.3.4 次超松驰迭代(A GA SOR)描述 具体算法过程描述如下:Step 1 参数接收: 接收用户输入线性方程组的系数矩阵A 、常数项b 、迭代初始值0X 和要求的精度; 确定种群规模N ;定出K 的最大限max K 的值和最大遗传代数T .Step 2 群体初始化: 随机生成N 个代入SOR 的迭代公式, 根据系数矩阵 A 、常数项b 、迭代初始值 0X 和要求的精度生成适应度函数;Step 3 计算适应度, 并保存迭代终止时的迭代次数k : 如果k 达到最大限, 则k 就等于最大限定次数; 否则按达到精度时的K 值保存;并产生N 个个体的初始种群S ;置代数计数器t 1.Step 4 寻找并保存当前代最优个体(也就是适应度值最大的个体); Step 5 进行以下遗传操作:(最初针对初始种群全体)(a) 选择算子: 按几何规划排序选择法、锦标赛选择法、轮盘法(按选择概率i P 所决定的选中机会,每次从群体中随机选定一个染色体并将其复制,共做N 次,然后将复制所得的N 个染色体组成群体1S )进行选择;(b) 交叉算子: 按式(7)计算c P 并决定出参加交叉的染色体数c ,从1S 中随机确定c 个染色体,随机配对并用算术交叉算子进行交叉,并用产生的新染色体代替原染色体,得群体2S ;(c) 变异算子: 按式(8)计算m P 并决定变异次数m ，从2S 中随机确定m 个染色体，分别进行均匀变异和边界变异两种算子，并用产生的新染色体代替原染色体,得群体3S;(d) 计算适应度: 并保存迭代次数k, 如果k达到最大限, 则k就为最大限定次数; 否则按原值保存;(e) 寻找并保存最优个体, 并用前代最优个体代替当前代的最差个体，置t t1;Step 6如果达到最大遗传代数, 则结束并输出所找到的最优松驰因子,然后转Step7; 否则转Step 5，;Step 7把代入SOR公式 , 另取精度1（使1，原可以取略大一点，加快收敛速度），得出方程的解X和迭代次数k,并结束.4 数值算例与分析为了验证本文算法的有效性,在计算机上进行了数值模拟计算.选择参数为:5 结论本文的近似确定X进化算法, 是基于遗传算法对X 的寻找而得到的, 因而, 不难把它平行地推广到对称超松驰迭代法(SSOR ) , 加速超松驰迭代法(AOR).参考文献:[ 1 ] 王世瑞, 王金金, 冯有前, 等. 计算方法[M ]. 西安: 电子科技大学出版社, 1997, 1: 33241.3 期谢竹诚, 等: 基于自适应遗传算法的逐次超松驰迭代法159[ 2 ] 马东升. 数值计算方法[M ]. 北京: 机械工业出版社, 2002, 1: 922102.[ 3 ] 李春光, 徐成贤. 确定SOR 最佳松驰因子的一个实用算法[J ]. 计算力学学报, 2002, 8, 19 (3) : 2992302.[4 ] 胡小兵, 吴树范等. 一种基于遗传算法的求代数方程组数值解的新方法[ J ]. 控制理论与应用, 2002, 19 (4) : 5672570.[ 5 ] HE Jun, XU ji2you, YAO Xin. So lving equations by hybrid evo lutionary computation techniques[J ]. IEEE T ranson Evo lutionary Computation, 2000,4 (3) : 2952304.[ 6 ] 罗亚中, 袁端才等. 求解非线性方程组的混合遗传算法[J ]. 计算力学学报, 2005,22 (1) : 1092114.[ 7 ] 周明, 孙树冻. 遗传算法原理及应用[M ]. 北京: 国防工业出版社, 1999.[ 8 ] 王小平, 曹立明. 遗传算法——理论、应用与软件实现[M ]. 西安: 西安交通大学出版社, 2002, 1.[ 9 ] 刘新胜, 张知难. 查找最佳松驰因子的一种实用方法[J ]. 新疆大学学报(自然科学版) , 2005, 5, 22 (2) : 1612164.[文档可能无法思考全面，请浏览后下载，另外祝您生活愉快，工作顺利，万事如意!]。