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