解线性方程组的几种迭代算法

解线性方程组的几种迭代算法内容摘要:本文首先总结了分裂法解线性方程组的一些迭代算法,在此基础上分别通过改变系数矩阵A的分裂形式和对SSOR算法的改进提出了两种新的算法,并证明了这两种算法的收敛性.与其它方法相比,通过改变系数矩阵A的分裂形式得到的新算法具有更好的收敛性,改进的SSOR算法有了更快的收敛速度.最后通过数值实例验证了这两种算法在有些情况下确实可以更有效的解决问题.关键词:线性方程组迭代法算法收敛速度SeveralkindsofsolvinglinearequationsiterativealgorithmAbstract:Inthispaper,wefirstlysummarizesomeIterativealgorithmsofAnti-secessionlawsolutionoflinearequations.Basedonthese,twonewalgorithmsareputforwardbychangingthefissionformofcoefficientmatrixAandimprovingthealgorithmofSSOR,andtheconvergenceofthetwoalgorithmsisdemonstrated.Comparedwithothermethods,thenewalgorithmacquiredbychangingthefissionformofcoefficientmatrixAispossessedofabetterconvergence.AndtheimprovedSSORalgorithmhasafasterconvergencespeed.Finally,somenumericalexamplesverifythatthetwoalgorithmscansolveproblemsmoreeffectivelyinsomecases.Keywords:LinearequationsIterationmethodalgorithmConvergencespeed目录1.引言.............................................................12.迭代法原理.......................................................13.基本迭代法.......................................................23.1Jacobi迭代..................................................23.2Gauss-Seidel迭代法..........................................33.3SOR算法.....................................................33.4SSOR算法....................................................43.5收敛性分析..................................................44.几种新的迭代算法.................................................54.1基于矩阵分裂形式的新迭代算法................................54.2加权－对称超松弛迭代法......................................75.算法的不足与改进方法.............................................96.数值实例.........................................................96.1渐进收敛速度.................................................96.2几种迭代方法的比较..........................................10附录...............................................错误!未定义书签。参考文献..........................................................111解线性方程组的几种迭代算法1.引言在工程技术、自然科学和社会科学中的许多问题最终都可归结为解线性方程组,因此线性方程组的求解对于解决实际问题是极其重要的.线性方程组的解法有很多种,主要的方法有直接法和迭代法.迭代法就是用某种极限过程去逼近线性方程组精确解的方法,该方法具有对计算机的存贮单元需求少,程序计算简单,原始系数矩阵在计算过程中不变等优点,是求解大型稀疏矩阵方程组的重要方法.目前,人们已经得到了一些较为成熟的线性方程组的迭代解法,从某种意义上讲它们都可归结为分裂法.但在解决具体问题时我们仍面临着许多问题,如:怎样设计出满足要求的求解算法；如何分析、区别算法的好坏；可否改进现有的算法使其更有效；求解所给问题最好可能的算法会是什么,等等.针对这些问题,很多人都做过了大量的研究.文献[2]对迭代法的原理及一些常用的迭代算法进行了研究.文献[1],[3],[4],[5]给出了一些基本的迭代算法并证明了其收敛性.文献[6],[9],[10],[13],[16]研究了一些特殊方程组的迭代解法.文献[7],[8],[12],[14],[15]都是针对不同的问题对超松弛迭代算法进行了改进.文献[11]主要讨论了迭代法解线性方程组的MATLAB实现.本人在求解线性方程组的问题时,通过对现有迭代算法的改进得到了两种新的算法.本文对这两种算法的收敛性进行了证明,并通过数值实例验证了其在解决某些问题时具有的优势.2.迭代法原理设线性代数方程组为AXb(1)常常将系数矩阵A分裂成两个矩阵M和N之差,即AMN(2)且用迭代(1)1()1kkXMNXMb(3)来解线性方程组(1).将(3)式表示为(1)(),0,1,kkXBXfk(4)其中,11,BMNfMb,称此迭代方法为分裂法,而将B称为迭代格式(4)的迭代矩阵.然而迭代法需要解决的首要任务是迭代格式是否收敛的问题,任取初始向量(0)(0)(0)(0)12,,,TnXxxx代入(4)中,计算可得迭代序列(1)(2)(1),,.kXXX若迭代序列(1)kX收敛,设()KX的极限为*X,对迭代式(4)两边取极限可得:2(1)()limlimkkkkXBXf即**XBXf,*X是方程组(1)的解,此时称迭代法收敛,否则称迭代法发散.我们有如下的结果:定理2.1[1]迭代格式(4)收敛的充分必要条件是迭代矩阵B的谱半径()1B,而且B越小,收敛越快.定理2.2[1]若pB为矩阵B的某范数,则总有pBB.对于矩阵A的分裂应该说是有很多形式,但并不是所有分裂形式产生的迭代格式都有意义.于是我们有正规分裂的概念:定义2.1[2]对于实方阵A,若矩阵M和N满足AMN,且10,0MNN则称AMN是A的一个正规分裂.那么正规分裂与其他分裂形式相比到底有什么优势呢?我们有如下定理:定理2.3[2]若AMN为A的正规分裂,且10A,则1111ANMNAN从而11MN,此时相应的迭代格式(3)必收敛.如果针对矩阵A给出两种正规分裂,如何来衡量它的好坏呢?定理2.4[2]若矩阵有两个正规分裂,设1122,AMNAMN且10A,211120,0,NNNNN,则有11112101MNMN.3.基本迭代法下面给出常见的几种基本迭代格式.将ijAa分裂为ADLU(5)其中,11121212221,10000,,00nnnnnnnaaaaaaDLUaaa3.1Jacobi迭代取,.MDNLU(6)3则(4)式中迭代矩阵B和右端向量f分别为11,.BDLUfDb迭代格式(4)的分量形式为(1)()1,1,2,.0,1,.kkiiijjjiiixbaxinka称它为Jacobi迭代法,该迭代法具有和(1)kx中分量的计算次序无关,容易并行计算等优点.3.2Gauss-Seidel迭代法取,,MDLNU(7)此时(4)式中迭代矩阵B和右端向量f分别为11,.BDLUfDLb迭代格式(4)的分量形式为(1)(1)()111,1,2,.0,1,.kkkiiijjijjjijiiixbaxaxinka称它为Gauss-Seidel迭代法.和Jacobi迭代法相比Gauss-Seidel迭代法使用了最新已经计算的分量.3.3SOR算法取11,,MDLNMADU(8)此时(4)式中迭代矩阵B和右端向量f分别为111,.BDLDUfDLb迭代格式(4)的分量形式为1(1)()(1)()111,1,2,.0,1,inkkkkiiiijjijjjjiiixxbaxaxinka其中,称为松弛因子(总假定是实数).迭代格式的矩阵形式为:11(1)()1kkXDLDUXDLb称它为对应于松弛因子的逐次超松弛迭代法(SuccessiveOverRelaxation,简称SOR).它可以看成Gauss-Seidel迭代法与原向量的组合,但使用了最新已经4计算的分量.也就是把(1)kix取为Gauss-Seidel迭代法中()kix与(1)kix的某个平均值,即:(1)()(1)()(1)()1kkkiiikkkiiixxxxxx当1时,它就是Gauss-Seidel迭代法.因此希望选取合适的使得它比Gauss-Seidel迭代法具有更快的收敛速度.3.4SSOR算法SOR迭代格式还可以写为(1)()1,0,1,kkDLXDUXbk将上式L和U的位置互换就得到一个新的迭代格式,具体表示为:1()()21()(1)211,0,1,kkkkDLXDUXbDLXDUXbk若消去1()2kX,就得到迭代格式(4),其中1111111,2BDUDDLDLDDUfDUDDL称为对称逐次超松弛迭代法(SymmetricSuccessiveOverRelaxation,简称SSOR).对一类椭圆微分方程离散后得到的线性方程组,Young[3]给出了最佳松弛因子,即为2211B其中B是Jacobi迭代法中的迭代矩阵.在实际问题中最佳松弛因子是很难计算的,但一般都在(0,2)之间.3.5收敛性分析定义3.1[3]若实矩阵ijnnAa,满足1,,1,2,nijiijjiaain或1,,nijjjiijaa1,2,jn则称A为严格对角占优矩阵；若满足51,,1,2,nijiijjiaain或1,,(1,2,)nijjjiijaajn且上述不等式至少有一个严格成立,则称A为弱严格对角占优矩阵.定义3.2[3]设A为n阶矩阵,2n.若存在n阶排列矩阵P,使得1112