學(xué)院理學(xué)學(xué)士論文摘要I摘要隨著科學(xué)和工程技術(shù)的發(fā)展，越來(lái)越多的問(wèn)題需要求解大規(guī)模的線性方程組，對(duì)這類方程的快速求解已成為數(shù)值代數(shù)研究的熱點(diǎn)之一，特別是具有稀疏結(jié)構(gòu)的大型方程組的求解?；贕alerkin原理的Arnoldi算法是求解這種線性代數(shù)方程組的近似算法，以下稱這種方法為廣義極小殘余算法(GMRES算法)。GMRES方法是目前求解大型稀疏非對(duì)稱線性方程組最為流行的一種迭代方法。GMRES算法在迭代過(guò)程中通常表現(xiàn)出一種加速收斂行為，隨著迭代次數(shù)的增加，這種加速收斂現(xiàn)象越明顯，即殘量收斂會(huì)隨著迭代步數(shù)的增加而逐漸得到改善。在CG方法中，這種加速收斂與Ritz值有密切關(guān)系。通過(guò)分析，我們發(fā)現(xiàn)GMRES的加速收斂與其斜投影過(guò)程中產(chǎn)生的Ritz值對(duì)特征值的逼近程度有關(guān)系。在實(shí)際應(yīng)用中，為了減少存儲(chǔ)量和計(jì)算量，我們通常使用GMRES算法的重新開始版本來(lái)求解大型非對(duì)稱線性方程組。本文描繪了GMRES和GMRES(m)的加速收斂現(xiàn)象，并通過(guò)實(shí)驗(yàn)給予解釋。關(guān)鍵字：廣義最小殘量；Krylov子空間；Ritz值；加速收斂；正交投影方法；非對(duì)稱線性方程組學(xué)院理學(xué)學(xué)士論文AbstractIIOnTheSuperlinearConvergenceofGMRESAbstractWiththedevelopmentofscienceandprojecttechnology,moreandmorequestionsneedthesolutionofbiglinearsystems.Thissolutionisoneofthefastestwaysforresearchingnumericalalgebra,especiallyforthebigsparsematrix.ThewayofArnoldiisbasedupontheprincipleofGalerkin,whichisclosedtothesolutionofthelinearnumericalsystem.Here,wecallthesolutionasGeneralizedMinimumResidual(GMRES).GMRESisoneofthemostpopulariterativemethodsforthesolutionofbignonsingularnonsymmetriclinearsystems.Itusuallyhasaso-calledsuperlinearconvergencebehavior.Therateofconvergenceseemstoimproveastheiterationproceeds.Foranothersay,therateofresidualvariablewillbeimprovedasweincreaseitsiteration.Fortheconjugategradientsmethod,thismethodhasbeenrelatedtoadegreeofconvergenceoftheRitzvalue.Throughsomeanalysis,wefoundthatforGMREStoo,changesinconvergencebehaviorseemtoberelatedtotheconvergenceofRitzvalue.Inourpracticalapplication,wealsousuallyuseGMRES(m)forreducingstorageandcountersolvingbiglinearsystems.ThispaperstudiesthesuperlinearconvergencebehaviorofGMRESandGMRES(m),andsuppliesexplainthroughexperiment.Keyword:GMRES；Krylovsubspace；Ritzvalue；superlinearconvergence；orthogonalizationmethod；nonsymmetriclinearsystem學(xué)院理學(xué)學(xué)士論文目錄III目錄摘要.IABSTRACT.II第一章引言.1第二章GMRES算法基礎(chǔ)知識(shí).32.1向量范數(shù).32.2線性方程組最小二乘問(wèn)題.42.2.1Gram-Schmidt正交化方法.42.2.2Givens變換.4第三章GMRES算法理論.63.1KRYLOV子空間方法的基本理論.63.2ARNOLDI算法.73.3GMRES算法結(jié)構(gòu).8第四章GMRES算法的加速收斂現(xiàn)象分析.9第五章數(shù)值示例與算法實(shí)現(xiàn).195.1數(shù)值實(shí)驗(yàn).195.2算法改進(jìn)與實(shí)現(xiàn).225.2.1預(yù)處理技術(shù).225.2.2算法實(shí)現(xiàn).245.3實(shí)驗(yàn)總結(jié).34致謝.35參考文獻(xiàn).36REPORTOFLITERATURE.37文獻(xiàn)報(bào)告.41學(xué)院理學(xué)學(xué)士論文第一章引言1第一章引言關(guān)于線性方程組的數(shù)值解法一般分為兩大類:直接法和迭代法。直接法是在沒有舍入誤差的情況下，通過(guò)有限步四則運(yùn)算可以求得方程組精確解的方法。但是，在實(shí)際計(jì)算時(shí)，由于初始數(shù)據(jù)變?yōu)闄C(jī)器數(shù)而產(chǎn)生的誤差以及計(jì)算過(guò)程所產(chǎn)生的舍入誤差等都對(duì)解的精確度產(chǎn)生影響，因此直接法實(shí)際上也只能算出方程組真解的近似值。直接法的基本思想是將結(jié)構(gòu)上比較復(fù)雜的原始方程組，通過(guò)等價(jià)變換化成結(jié)構(gòu)簡(jiǎn)單的方程組，使之變成易于求解的形式，然后再通過(guò)求解結(jié)構(gòu)簡(jiǎn)單的方程組來(lái)得到原始方程組的解。即AxbGxdG通常是對(duì)角矩陣、三角矩陣或者是一些結(jié)構(gòu)簡(jiǎn)單的矩陣。目前較實(shí)用的直接法是Gauss消去法的一些變形，例如選主元的Gauss消去法和矩陣的三角分解法，它們都是目前計(jì)算機(jī)上常用的有效方法。迭代法就是對(duì)任意給定的初始近似解向量(0)x，按照某種方法逐步生成近似解序列(0)(1)(2)(),.,.kxxxx,使極限()limkkxx為方程組的解，即()Axb。因此迭代法是用某種極限過(guò)程去逐步逼近真解的方法，從而也可以用有限步運(yùn)算出具有指定精確度的近似解。迭代法主要有Jacobi迭代法、Gauss-Seidel迭代法、逐次超松弛法以及共軛斜量法。直接法的優(yōu)點(diǎn)是計(jì)算量小，并且可以事先估計(jì)，缺點(diǎn)是所需存儲(chǔ)單元較多，編寫程序復(fù)雜；迭代法的優(yōu)點(diǎn)是原始系數(shù)矩陣始終不變，因而算法簡(jiǎn)單，編寫程序也比較方便，且所需存儲(chǔ)單元也較少，缺點(diǎn)是只有近似解序列收斂時(shí)才能被采用，而且存在收斂性和收斂速度的問(wèn)題。對(duì)于中等規(guī)模的n階(n100)線性方程組，由于直接法的準(zhǔn)確性和可靠性，所以它們是經(jīng)常被采用的方法。對(duì)于較高階的方程組，特別是對(duì)某些偏微分方程離散化后得到的大型稀疏方程組(系數(shù)矩陣中絕大多數(shù)為零元素)，由于直接解法的計(jì)算代價(jià)較高，使得迭