搜索
毕业设计(论文)开题报告题目：线性代数方程组的基本迭代方法研究学院：理学院专业：信息与计算科学学生姓名：左双学号：200710010237指导老师：杨继明2011年3月25日毕业设计（论文）开题报告1．文献综述：结合毕业设计（论文）课题情况，根据所查阅的文献资料，每人撰写2500字以上的文献综述，文后应列出所查阅的文献资料。文献综述0引言线性代数方程组的迭代方法是一种极限方法是解大型稀疏矩阵方程组的有效方法。它的基本思想是用某种极限过程去逐步逼近线性方程组的精确解,是一种逐步逼近的方法,首先选定方程f(x)=0的一个近似根后，然后使用某个固定公式反复校正这个根的近似值,使之逐步精确化,一直到满足给定的精度要求为止.迭代法将n阶线性方程组变形为某种迭代公[1]。对于任意给定的迭代初始值，由某一迭代格式便可生成一向量序列，我们的目的是求解方程组的解，因此我们会希望向量序列的极限逼近方程组的解。若迭代格式是收敛的，即迭代无穷多次后的值会收敛到某一特定的值，则这一特定的值就是方程组的解。由此看来，用迭代法解线性方程组，需要解决如下三个问题:（1）迭代格式的构造；(2)判断迭代格式是否收敛；(3)迭代格式的收敛速度估计[2,3,4]。对于迭代格式的构造，我们要研究其迭代格式的建立；迭代法的设计技术；迭代过程的收敛性；误差估计；接近准确解时的迭代次数等问题[5]。迭代法是利用计算机求解方程组时常用的方法。特别是对大型稀疏矩阵方程组，即系数矩阵中零元素占大部分的那种方程组。对于迭代方法，主要雅克比迭代法，高斯-塞德尔迭代法，还有松弛迭代法，松弛迭代法是一个应用极为广泛的方法，目前比较常用的迭代方法是雅克比迭代法和高斯-塞德尔迭代法。高斯-塞德尔迭代法是对雅克比迭代法的一种改进，但由于两种方法的迭代矩阵是不同的，所以存在有些方程组用雅克比迭代法收敛，而用高斯-塞德尔迭代法发散的情况。每一种迭代法都有一定的应用范围，对于同一方程组，有些收敛，有些不收敛，在应用迭代法时应该对收敛性条件给予充分的重视，不收敛的迭代公式是毫无意义的。而且在收敛的迭代中，有些收敛的快，有些收敛的慢，所以研究某一些或某一类特殊系数矩阵的大型稀疏线性方程组的高效的迭代方法，使之达到比较理想的收敛效果，已经成为当前数值计算研究的主要对象。[6,7,8,9]在科技，工程，医学，经济等各个领域中，很多问题常常归结为解线性方程组，有些问题的数学模型虽不直接表现为求解线性方程组，但其数值解法中却需将该问题“离散化”或“线性化”为线性方程组，例如电学中的网络问题，经济学中的投入产出问题，用最小二乘法求实验数据的曲线拟合问题，工程中的三次样条函数的差值问题，用迭代法解非线性方程组的问题，用差分法或者有限元法解微分方程问题等都导致求解线性代数方程组[10]。求解线性方程组的方法主要有直接法和迭代法，直接法(如GAUSS消去法,平方根法等)在计算机上可以求解的线性方程组的规模也越来越大,但直接法大多数均需要对系数矩阵A进行分解,因而一般不能保持A的稀疏性,而实际应用中,特别是偏微分方程的数值求解时,常常遇到大型稀疏线性方程组的求解问题,迭代法是能保持线性方程组稀疏性的有效算法,它也是数值代数中的一种常用的非常重要的方法。本文运用雅可比(Jacobi)迭代法,高斯-塞得尔(Gauss-Seidel)迭代法探讨有无穷解的线性方程组的迭代法。凡是迭代解法都有一个收敛性问题。但是，迭代解法具有程序设计简单，适于自动计算，还可以充分利用系数矩阵的稀疏矩阵的稀疏性减少存贮。加之一个好的迭代法常可用较直接法更少的计算量而获得满意的解。因此，迭代法亦是解线性方程组，尤其是求解具有大型稀疏系数矩阵的线性方程组的重要方法之一[11,10]。对迭代法来说一般有下面几个问题:(1)如何构造迭代序列?(2)构造的迭代法序列是否收敛?在什么情况下收敛?(3)如果收敛,收敛的速度如何?我们应该给予量刻划,用以比较各种迭代法收敛的快慢。(4)因为计算总是有限次的,所以总要讨论近似解的误差估计和迭代过程的中断处理问题,这又和舍入误差的分析有关[12]。此外，利用迭代法求解线性方程组还涉及到一些问题。例如，任意选取初始向量，利用迭代公式得到的向量序列是否一定收敛；如果收敛需要满足什么条件；对于同一线性方程组，用那种迭代公式收敛速度更快[6]。1迭代方法的研究情况数学、物理、流体力学、工程技术和经济学等学科中的许多问题最终都归结为求解大型稀疏矩阵的线性代数方程组。解线性方程组主要有直接法和迭代法。对于大规模线性方程组的求解问题，特别是大规模稀疏线性方程组，迭代法是求解线性方程组的一种有效方法,它有存储空间小，程序简单等特点。使用迭代法求解方程组充分利用了矩阵的稀疏性，从而节省大量计算存储空间，故其在求解大规模计算问题中发挥着重要的作用，成为求解大型稀疏代数方程组的实用方法。为了更快更好地求解大型稀疏线性方程组，先后有Jacobi迭代法、Gauss．Seidel迭代法等，而在引入了松弛因子和加速因子之后，又出现了SOR迭代法、AOR迭代法等基本迭代法【13,14,16】。虽然发现用迭代方法求解线性方程组的起源在是在19世纪初(高斯),但是在工程和科学方面由于需求受到特殊技术的限制，关于迭代方法的研究在这些方面经历了一个爆炸性的历程。在过去的五十年里，有着非常卓越的新发展，在科学与工业的计算模型，对于解决大型问题，迭代法是一个非常实在的工具[15]。标准迭代法在六七十年代得到很大发展，Varga,Young&Householderder等人都曾在自己的著作中对迭代法有历史性的综述。雅克比是数学史上最勤奋的学者之一。雅克比迭代法虽然是最简单的迭代法，但是该方法对系数矩阵有对角占优性质的线性系统效果明显。Gaussie-Seidel迭代和Jacobi迭代同属于一个大的迭代族，都是对系数矩阵进行分裂而得到的迭代形式[17]。为了改进Gaussie-Seidel迭代法收敛速度有可能很慢的缺点，SOR超松弛迭代对Gaussie-Seidel迭代法进行了修正，因而Gaussie-Seidel迭代法又名为松弛迭代法。超松弛迭代法实际上可以看做Gaussie-Seidel迭代法的加速，另一个加速收敛的方法是Chebyshev方法。该方法是Manteufel在1957年提出的，其简单明了的三项迭代公式被称为Chebyshev半迭代方法，具有较好的数值稳定性[21]。1955年，Peaceman&Rachford提出了求解大规模线性系统的交替方向迭代方法（ADI），该算法主要应用于求解离散椭圆型微分方程边值问题，充分利用了原问题的特殊结构[22]。以上提及的迭代法在一定程度上都依赖于参数，而适当选取这些参数需要很大的计算代价。正对系数矩阵为对称正定的线性系统，瑞士数学家苏黎世应用数学学院的E.Stiefel和美国国家标准局数值分析研究学会的Magnus.R.Hestenes进行了研究，并各自发表了论文。1952年，二者联合发表了题为《线性系统的共轭梯度法》的论文，此后也开始了Krylov子空间迭代方法的时代。直到1959年，M.Engeli等人第一次把共轭梯度法列入迭代法的类型。认为该方法的计算公式是一个迭代过程，而且由于舍入误差的影响，共轭梯度法并不能有限终止[17,23,24,25]。随着计算机贮存量的日益增大和计算速度的迅速提高，使得求解线性代数方程组的直接法如高斯消去法等在计算机上可以用来解决大规模线性代数方程组，并且由于处理稀疏矩阵存贮和计算技术的飞速发展，加之直接方法理论的日臻完善，都进一步断定了直接方法的巨大实用价值和可靠性。因而在近几十年来直接法被广泛地采用[3,10]。解线性方程组的迭代法基本问题为：（1）迭代格式的构造，（2）迭代的收敛性分析，（3）收敛速度的分析，（4）复杂性分析（计算的工作量大小），（5）初始值的选取。主要的迭代格式是根据选择的迭代方法而定，主要是Jacobi迭代法Gaussie-Seidel迭代法和SOR迭代法。对于一个线性代数方程组，用任意建立简单迭代格式所计算得到的迭代值序列不会一定收敛于方程组的准确接。通常，只有当建立的迭代格式满足一定条件时，其迭代值序列才会收敛于方程组的准确解，并且与选取的初始迭代值无关[18]。迭代法的收敛速度一般与系数矩阵的谱分布有关，上述几种迭代法收敛的充分必要条件是迭代矩阵的谱半径小于1[26]。在迭代格式收敛的情况下，又如何控制迭代过程的结束呢？在实际问题中，通常总是预先给定了一个精度要求，如果在迭代过程中，某此迭代值满足了预先给定的精度要求，则就取此次迭代值作为方程组的近似解，迭代过程结束。但由于方程组的准确解一般是未知的，因此，判断某此迭代值是否满足精度要求很困难的。一般总是认为，当相邻两次的迭代值非常接近时，其方程组的准确值也与迭代值很接近[18,19]。此时的迭代次数就是该迭代方法的复杂性。通常用迭代偏差刻划迭代值的精度。为防止迭代过程不收敛，或者收敛速度过于缓慢，可以设置最大迭代次数，如果迭代次数超过最大迭代次数尚不能达到精度要求，则宣告迭代失败。解线性方程组的迭代法的计算步骤是：（1）选择合适的迭代方法。（2）适当提供迭代的初始值。（3）按照所选取的迭代公式将老值不断地迭代出新值，并且用新值来代替老值。（4）若迭代偏差小于指定精度，则该新值就是所求解的线性方程组的解，迭代过程结束，否则执行下一步。（5）若迭代次数尚未达到最大迭代次数，则按照第3步继续迭代，否则迭代失败，迭代过程结束[5,20]。参考文献[1]陈桂秀,方程求解中迭代法的使用[N],青海师范大学学报(自然科学版),2009年第1期.[2]曹志浩.数值线性代数[M].复旦大学出版社，1996[3]G.E.福赛斯，C.B.莫勒.线性代数方程组的计算机解法[M]，徐树荣译.科学出版社，1976.[4]蒋尔雄等.数值逼近[M].复旦大学出版社，1996.[5]王能超.计算方法简明教程,高等教育出版社[M],2004,(01).[6]石东洋.计算方法.郑州大学出版社[M],2007，（05）.[7]李庆杨，王能超，易大义.数值分析.华中工学院出版社[M]，1982[8]袁慰平，张令敏，黄新芹.计算方法与实习.东南大学出版设[M]，1992[9]姚敬之.计算方法.河南大学出版设[M]，1993.[10]陈兰平,王凤等.数值分析.科学出版设[M],2000,(08).[11]田学全，朱世建.有无穷解的线性方程组的迭代法[N],塔里木农垦大学学报,第16卷第2期,2004,(6).[12]花威,线性方程组的迭代解法及其Matlab实现程序[N],长江工程职业技术学院学报,第26卷第4期,2009,(12).[13]张传文.新预条件下矩阵的收敛性分析及其比较[D].扬州大学,2010,(4).[14]陈丽红,周志刚,万立.求解线性方程组的一种迭代法的改进.武汉科技学院学报,第23卷第2期,2010,(4).[15]朱莉,预处理HSS方法和模糊线性方程组的迭代解法,南京:南京师范大学,2007,(4).[16]常双领,张传林.求解线性方程组的一种迭代解法[J].暨南大学学报,2004(3):06.[17]葛学滨.线性方程组节结构的历史研究.山东：山东大学，2009.[18]韩丹夫，吴庆标.数值计算方法.浙江大学出版社，2006，（06）.[19]胡家赣，线性方程组的迭代解法[M]．北京，科学出版社，1999．[20]白红梅.Jacobi迭代法与Gauss-Seidel迭代法的收敛性比较分析[J].呼伦贝尔学院学报,第17卷第6期2009,(12).[21]J.A.Mantuefel,Aniterativeforsolvingnonsymmetriclinearsystemswithdynamicestimationofparameter[j].ReportUIUCDCS-R-75-758.Dept.ofComputerScience,UnivofILLinoisatUrbana-Champaign,P