开题报告 线性代数方程组的基本迭代方法研究.doc

毕业设计(论文)开题报告题 目： 线性代数方程组的基本迭代方法研究 学院： 理学院 专 业： 信息与计算科学 学生姓名： 左双 学 号： 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迭代法、GaussSeidel迭代法等，而在引入了松弛因子和加速因子之后，又出现了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。迭代法的收敛速度一般与系数矩阵的谱分布有关，上述几种迭代法收敛的充分必要条件是迭代矩阵的谱半径小于126。在迭代格式收敛的情况下，又如何控制迭代过程的结束呢？在实际问题中，通常总是预先给定了一个精度要求，如果在迭代过程中，某此迭代值满足了预先给定的精度要求，则就取此次迭代值作为方程组的近似解，迭代过程结束。但由于方程组的准确解一般是未知的，因此，判断某此迭代值是否满足精度要求很困难的。一般总是认为，当相邻两次的迭代值非常接近时，其方程组的准确值也与迭代值很接近18,19。此时的迭代次数就是该迭代方法的复杂性。 通常用迭代偏差刻划迭代值的精度。为防止迭代过程不收敛，或者收敛速度过于缓慢，可以设置最大迭代次数，如果迭代次数超过最大迭代次数尚不能达到精度要求，则宣告迭代失败。解线性方程组的迭代法的计算步骤是：（1）选择合适的迭代方法。（2）适当提供迭代的初始值。（3）按照所选取的迭代公式将老值不断地迭代出新值，并且用新值来代替老值。（4）若迭代偏差小于指定精度，则该新值就是所求解的线性方程组的解，迭代过程结束，否则执行下一步。（5）若迭代次数尚未达到最大迭代次数，则按照第3步继续迭代，否则迭代失败，迭代过程结束5,20。 参考文献1陈桂秀,方程求解中迭代法的使用N,青海师范大学学报(自然科学版),2009 年 第 1 期 .2曹志浩.数值线性代数M.复旦大学出版社，19963G.E.福赛斯，C.B.莫勒.线性代数方程组的计算机解法M，徐树荣译.科学出版社， 1976. 4蒋尔雄等.数值逼近M.复旦大学出版社，1996.5王能超.计算方法简明教程,高等教育出版社M, 2004,(01).6石东洋.计算方法.郑州大学出版社M,2007，（05）.7李庆杨，王能超，易大义.数值分析.华中工学院出版社M，19828袁慰平，张令敏，黄新芹.计算方法与实习.东南大学出版设M，19929姚敬之.计算方法.河南大学出版设M，1993.10陈兰平,王凤等.数值分析.科学出版设M,2000,(08).11田学全，朱世建.有无穷解的线性方程组的迭代法N,塔里木农垦大学学报,第16卷第2 期,2004,(6).12花威,线性方程组的迭代解法及其 Matlab实现程序N,长江工程职业技术学院学 报,第2 6卷 第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北京，科学出版社，199920白红梅 .Jacobi迭代法与Gauss-Seidel迭代法的收敛性比较分析J.呼伦贝尔 学院学报,第 17 卷第 6 期 2009,(12). 21J.A.Mantuefel,An iterative for solving nonsymmetric linear systems with dynamic estimation of parameterj.Report UIUCDCS-R-75-758.Dept.of Computer Science,Univ of ILLinois at Urbana-Champaign,Ph.D Thesis,1975. 22D.Peaceman&H.Rachford,Thenumerical solution of elliptic and parabolic equationsJ.3(1955),28-41. 23M.Engeli，T.Ginsburg,H.Rutishauser,and E.Stefel,Refined Iterative Methodsfor Computation of the solution and the Eigenvalues of Self-ADJOINT Boundary Value ProblemsJ.Birkhauser,Basel/Stullgart.1964.24 Burden Richard L, Faires J Douglas. Numerical analysisM. 7th ed. Beijing: Higher Education Press, 2001. 25 Saad Y. Numerical methods for large eigenvalue problemsM. New York: Halstead Press NY,1992. 26 DMYoungIterative solution oflarge linear systemMAcademic Press， NewYork and London，1971毕 业 设 计（论 文）开 题 报 告开题报告：一、课题的目的与意义；二、课题发展现状和前景展望；三、课题主要内容和要求；四、研究方法、步骤和措施开 题 报 告一、课题的目的与意义通过本课题的研究，学会如何运用有限元方法来解决线性代数方程组问题，特别是Gaussie-Seidel迭代法和Jacobi迭代法来求解线性方程组。进一步学会迭代方法的数学思想，并对程序代码进行解析与改进，这对于我们以后学习和研究实际问题具有重要的意义。本课题运用所学的数学专业知识来研究，有助于我们进一步掌握大学数学方面的知识，特别是迭代方法。通过这个课题的研究，我进一步掌握了迭代方法的思想，以及程序的解析与改进，对于今后类似实际问题的解决具有重要的意义。二、课题发展现状和前景展望随着科学技术的快速发展，数学在科学研究中的比重越来越大特别是随着计算机技术的飞跃，计算数学显得格外突出当今在计算数学中十分重要的研究课题之一就是大规模稀疏线性代数系统的高效求解方法因为在科学与工程的许多重要领域，如计算流体力学、材料模拟与设计、电磁场计算、电力系统的优化设计、石油勘探数据处理、地震数据处理、数值天气预报及核爆数值模拟等都离不开微分方程的数值求解，而解决这些问题方法通常是通过有限体积、有限元、有限差分法或无网格方法等进行离散，最终转化为大规模稀疏线性代数系统。因此研究大规模线性代数系统的高效求解方法显得十分重要解线性代数系统的方法可分为两类：直接法和迭代法直接法有在不计舍入误差的情况下能得到准确解的优点，但当系数矩阵的条件数很大时，舍入误差的影响常引起所求出的解与准确解相差甚远。在方程规模很大的情况下，直接法一般需要内存和花费的时间都很大，这是不能接受的因此，迭代法已经取代直接法成为了求解大型稀疏线性代数系统的一类最重要的方法。对 迭代法的研究也一直是国内外研究的热点问题迭代法一般分为两类：一类定常迭代法，如Jacobi，GaussSeidel，SOR和AOR等由于定常迭代法形式简单，易于计算机实现，因此在Jacobi方法诞生以来，新的定常迭代法层出不穷，也受到了工程人员的青睐然而，随着科学技术迅速发展需要，所求解问题的规模越来越大，定常迭代法往往非常低效，已经很少单独被使用另一类是非定常的迭代法，其中应用最广泛的有CG，MINRES，GMRES，BiCGStab等Krylov对线性代数系统采用预处理技术使系数矩阵谱聚集是解决该收敛性问题的有效途径，成为迭代法研究中热点问题之一三、课题主要内容和要求 线性代数方程组的迭代方法是一种极限方法是解大型稀