算法的加速收敛现象分析—计算机毕业设计(论文)

《算法的加速收敛现象分析—计算机毕业设计(论文)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学院理学学士论文摘要算法的加速收敛现象分析摘要随着科学和工程技术的发展，越来越多的问题需要求解大规模的线性方程组，对这类方程的快速求解已成为数值代数研究的热点之一，特别是具有稀疏结构的大型方程组的求解。基于Galerkin原理的Arnoldi算法是求解这种线性代数方程组的近似算法，以下称这种方法为广义极小残余算法(GMRES算法)。GMRES方法是目前求解大型稀疏非对称线性方程组最为流行的一种迭代方法。GMRES算法在迭代过程中通常表现出一种加速收敛行为，随着迭代次数的增加，这种加速收敛现象越明显，即残量收敛会随着迭代步数的增加而逐渐得到改善。在CG方法中，这

2、种加速收敛与Ritz值有密切关系。通过分析，我们发现GMRES的加速收敛与其斜投影过程中产生的Ritz值对特征值的逼近程度有关系。在实际应用中，为了减少存储量和计算量，我们通常使用GMRES算法的重新开始版本来求解大型非对称线性方程组。本文描绘了GMRES和GMRES(m)的加速收敛现象，并通过实验给予解释。关键字：广义最小残量；Krylov子空间；Ritz值；加速收敛；正交投影方法；非对称线性方程组I学院理学学士论文AbstractOnTheSuperlinearConvergenceofGMRESAbstractWiththedevelopmentofsc

3、ienceandprojecttechnology,moreandmorequestionsneedthesolutionofbiglinearsystems.Thissolutionisoneofthefastestwaysforresearchingnumericalalgebra,especiallyforthebigsparsematrix.ThewayofArnoldiisbasedupontheprincipleofGalerkin,whichisclosedtothesolutionofthelinearnumericalsystem.Here,

4、wecallthesolutionasGeneralizedMinimumResidual(GMRES).GMRESisoneofthemostpopulariterativemethodsforthesolutionofbignonsingularnonsymmetriclinearsystems.Itusuallyhasaso-calledsuperlinearconvergencebehavior.Therateofconvergenceseemstoimproveastheiterationproceeds.Foranothersay,therateo

5、fresidualvariablewillbeimprovedasweincreaseitsiteration.Fortheconjugategradientsmethod,thismethodhasbeenrelatedtoadegreeofconvergenceoftheRitzvalue.Throughsomeanalysis,wefoundthatforGMREStoo,changesinconvergencebehaviorseemtoberelatedtotheconvergenceofRitzvalue.Inourpracticalapplica

6、tion,wealsousuallyuseGMRES(m)forreducingstorageandcountersolvingbiglinearsystems.ThispaperstudiesthesuperlinearconvergencebehaviorofGMRESandGMRES(m),andsuppliesexplainthroughexperiment.Keyword:GMRES;Krylovsubspace;Ritzvalue;superlinearconvergence;orthogonalizationmethod;nonsymmetric

7、linearsystemIII学院理学学士论文目录目录摘要IABSTRACTII第一章引言1第二章GMRES算法基础知识3§2.1向量范数3§2.2线性方程组最小二乘问题4§2.2.1Gram-Schmidt正交化方法4§2.2.2Givens变换4第三章GMRES算法理论6§3.1Krylov子空间方法的基本理论6§3.2Arnoldi算法7§3.3GMRES算法结构8第四章GMRES算法的加速收敛现象分析9第五章数值示例与算法实现19§5.1数值实验19§5.2算法改进与实现22§5.2.1预处理技术22§5.2.2算法实现24§5.3实验总结34致谢35

8、参考文献36REPORTOFLITER