1006014248高洁线性方程组的极小残余算法

咸阳师范学院本科毕业论文TheGeneralizedMinimalResidualAlgorithminsystemoflinearequations分类号密级公开题目（中、英文）线性方程组的广义极小残余算法作者姓名指导教师学科门类提交论文日期专业名称成绩评定高洁数学与应用数学马欣荣2014年4月理学107221006014248学校代码学号I线性方程组的广义极小残余算法（即GMRES算法）高洁（咸阳师范学院数学与信息科学学院陕西咸阳712000）摘要伴随科学技术的进步与快速发展，大规模稀疏线性方程组的求解成为很多问题的解决方法之一，然而一种求解大型非对称线性方程组有效的迭代方法之一就是广义极小残余算法。本文章就是通过对线性方程组的学习及相应矩阵理论知识的了解，探究Krylov子空间上广义极小残余算法的基本理论。首先，介绍线性方程的一些基本概念，定理和问题；下来为研究做一些准备工作，了解投影法的基本思想和Krylov子空间；文章的最后给出了在Galerkin原理之下的广义极小残余算法和在其他方面的一些应用。关键词：线性方程组；广义极小残余算法；Krylov子空间法；投影法；正交；矩阵。IITheGeneralizedMinimalResidualAlgorithmInSystemOfLinearEquations（asGMRESalgorithm）GaoJie（SchoolofMathematicsandInformationScience,XianYangNormalUniversity,ShanXiXianYang712000）AbstractWiththerapiddevelopmentofscienceandtechnology,moreandmoreproblemstosolvinglarge-scalesparselinearequations,however,generalizedminimalresidualalgorithmisakindofnonsymmetriclinearequationiterativemethod.Inthispaper,throughstudyoflinearequationsandthecorrespondingmatrixtheoryknowledgeunderstanding,studyKrylovsubspaceonthebasictheoryofgeneralizedminimalresidualalgorithm.Firstofall,introducessomebasicconceptsoflinearequations,theoremsandproblems;Downanddosomepreparationworkforstudy,understandthebasicideasandKrylovsubspaceprojection;FinallyundertheGalerkinprincipleofgeneralizedminimalresidualalgorithmanditsapplicationinotheraspects.KeyWords:linearequations;GMRESalgorithm;Krylovsubspacemethods;projectionmethod;Orthogonality;matrix.III目录摘要…………………………………………………………………...................ⅠAbstract……………………………………………………………………………...................Ⅱ目录.....................................................................................................................Ⅲ1引言………………………………………………………………………………...................12线性方程组………………………………………………………………………...................12.1线性方程组的定义…………………………………………………………....................12.2线性方程组的三种表示形式………………………………………………....................12.3线性方程组的求解问题……………………………………………………....................23基本理论…………………………………………………………………………...................33.1投影方法的基本思想………………………………………………………....................33.2Krylov子空间的简介………………………………………………………....................54GMRES算法的理论…………………………………………………………..........................64.1Galerkin原理………………………………………………………………….................64.2Arnoldi算法…………………………………………………………………...................74.3GMRES算法…………………………………………………………………...............105GMRES(m)算法在其他方面的应用………………………………………………...............145.1在离散不适定问题中的应用…………………………………………………..............145.2求解三维第一类Fredholm积分方程……………………………………….................15总结………………………………………………………………………………….................17参考文献……………………………………………………………………………….............18谢辞…………………………………………………………………………………….............19.咸阳师范学院2011届本科毕业论文（设计）11引言数学研究的主要对象之一是线性方程的研究，它有着严谨的理论，和独特的解决问题的方法，也可以应用于各个领域的多种实际问题的处理，并且在这快速发展信息的社会中，尤其是工程计算技术和科学水平的发展，有着越来越多的复杂的大型的问题，在需要解决的这些诸多问题的同时更重要的是需要求解一些大规模离散不适定的线性方程组，并且例如有：有限差分，有限元素值的求解，数理方程的反问题等等，快速高效的求解这几类方程成为数学研究之中矩阵与数值代数研究的主要热点之一。在1986年，由M.H.Schltz和Y.Saad两位著名数学家提出的关于基于Galerkin原理的GMRES(m)算法，并且此算法是一种求解非对称线性适定方程组的Krylov子空间投影法，而且是采用正交投影或斜投影之一在子空间上产生迭代向量进行的计算。因为广义极小残余算法是关于基于Krylov向量的完全化正交化，所以在于对应的Krylov子空间有且只能求出一个近似解或着拟最小残值。在且加上以该算法计算的所需要的内存量和计算量较少等优势，所以在社会上目前广泛应用于各种工程应用领域的各种问题。本文章在矩阵论与数值代数的基础上主要研究线性方程组的一个迭代方法，即广义极小残余算法的理论与应用。2线性方程组2.1线性方程组的定义2.1.1线性方程组指各个方程关于未知量均为一次的方程组。2.1.2齐次线性方程组指对于一般线性方程组来说，常数项均为零。2.1.3非齐次线性方程组指对于一般线性方程组来说，常数项不全为零。2.2线性方程组的三种表示形式2.2.1一般形式的表示一般线性方程组是指形如线性方程组的广义极小残余算法211112211211222221122nnnnmmmnnmaxaxaxbaxaxaxbaxaxaxb（2.1）的方程组，其中12,,,nxxx是指n个未知量，m是指该方程组所包含的方程的个数，(1,2,,;1,2,,)ijaimjn是方程组的系数，(1,2,,)jbjm是常数项。并且由（2.1）式可以看出，一个线性方程组的确定是完全由方程组的系数和常数项所确定，且在一般情况下方程组的常数项写在方程等式的右边。2.2.2向量形式的表示可以表示为：1122nnxxxb（2.2）其中111121212221212,,,,nnnmmmnmbaaaaaabbaaab2.2.3矩阵形式的表示可以表示为：AXb（2.3）其中1212(,,,),(,,,)TnnAXxxx于此特别的，如果方程组中0,b则可以把AXb称作为齐次线性方程组，而如果方程组中,bo则可以把AXb称作非齐次线性方程组。2.3线性方程组的求解问题2.3.1一般方程组一般的小型的线性方程组可以利用解的性质与Cramer法则求解，解决一些相关问题。2.3.2特殊系数方程组对于方程AXb的系数矩阵具有某些特殊的性质，例如：系数矩阵A对称正定；有性质即存在交换矩阵P，使得112DHPAPRD,其中1D和2D为两个对称矩阵；H矩咸阳师范学院2011届本科毕业论文（设计）3阵…，则可以根据这些加在系数矩阵A上的条件，采用SOR和SSOR迭代，最速下降法等方法求解。2.3.3大型一般条件方程组对于求解大型线性方程组且方程的系数矩阵不在具有某些特殊性质，即力图在最一般的条件下，讨论AXb的求解问题，这就是本文章主要研究的线性方程组的求解问题，我们只假定方程中的系数矩阵是一个非奇异矩阵。3基本理论3.1投影方法的基本思想假设需要求解如（2.3）式方程组，其中的系数矩阵A是大型非对称矩阵，并且还是非奇异的矩阵。假定A和b都是实矩阵，且令12,,,mmVvvv是n维空间中一组m个线性无关的向量，12(,,,)mmKspanvvv是12,,,mvvv所张成的子空间。则其的基本思想就是找一个（2.3）式的近似解()mX且使得：()()()mmmjXKAXbv1,2,,.jm（3.1.1）令()(),mmmXVY其()mY是一个m维向量，则（3.1.1）式可以改写为()TmTmmmVAVYVb（3.1.2）假设（3.1.2）有唯一解，则可通过求解一个m个未知数的方程，得到()mY，从而得到X的一个近似解()mX。例1．2111101110,01,2231003AVb根据以上可直接计算得到对应的（3.1.2）式为线性方程组的广义极小残余算法4(2)111112Y（3.1.3）可以得到，转化为（3.1.3）式的方程组无解。所以为了避免出现这一算法上的困难，不得不假设所取mV使得（3.1.2）式有唯一解。例2.如何选mV，使得算法在计算机上可非常有效的实现？答：令m表示在子空间mK上的正交投影算子，且假设mbK，将可以在下面的推论中看出，所假设的不难实现。用正交投影算子的符号，方程（3.1.1）可改写为()()()0mmmmXKAXb（3.1.4）为方便理论分析，再引入算子mA，其代表mA并限制在定义域只在mK之上，这样找近似解()mX就变为求解0mAXb(3.1.5)的问题，其中因为假设mbK，所以可得bbb。由以上可得到的近似解与（2.3）式的精确解()X之间存在着误差值，具体有多大的误差？我们先看以下引理：引理1令()mmmrA，则方程（3.1.4）式满足()mmmmbAXrX（