迭代法及其在数值求解线性方程组中的应用.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流迭代法及其在数值求解线性方程组中的应用.精品文档.郑州师范学院毕业论文 题 目 迭代法及其在数值求解 线性方程组中的应用 姓 名 陈丹丹 学 号 124103052041 院 系 数学与统计学院 专 业 数学与应用数学 年级班级 B12数应2班 指导教师 王明建 2016年 5 月 20 日毕业论文作者声明本人郑重声明：所呈交的毕业论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。本人完全了解有关保障、使用毕业论文的规定，同意学校保留并向有关毕业论文管理机构送交论文的复印件和电子版。同意省级优秀毕业论文评选机构将本毕业论文通过影印、缩印、扫描等方式进行保存、摘编或汇编；同意本论文被编入有关数据库进行检索和查阅。本毕业论文内容不涉及国家机密。论文题目：迭代法及其在数值求解线性方程组中的应用作者单位：郑州师范学院作者签名：目 录摘要1引言31.预备知识3 1.1迭代法的基本形式3 1.2 Jocabi迭代法4 1.2.1分量形式的Jacobi迭代法4 1.2.2矩阵形式的Jacobi迭代法5 1.2.3 Jacobi迭代法的算法实现步骤6 1.3 Gauss-Seidel迭代法6 1.3.1分量形式的Gauss-seidel迭代法6 1.3.2矩阵形式的Gauss-seidel迭代法6 1.3.3 Gauss-Seidel迭代法的算法实现步骤7 1.4超松弛迭代法（SOR迭代法）7 1.4.1分量形式的SOR方法7 1.4.2矩阵形式的SOR方法8 1.4.3 SOR迭代法的算法实现步骤9 1.5迭代法的收敛性92. 数值求解线性方程组10 2.1用Jacobi迭代法求解10 2.2用Gauss-Seidel迭代法求解11 2.3用超松弛迭代法求解12小 结13参考文献15致谢16迭代法及其在数值求解线性方程组中的应用摘要：迭代解法就是通过逐次迭代逼近来得到的近似解的方法。而线性方程组的求解问题是科学研究及工程计算中最常出现的问题，如结构分析、网络分析、数据分析、大地测量等，都需求解线性方程组。由于从不同的问题而导出的线性方程组的系数矩阵不同，因此对于大型稀疏矩阵(零元素很多的多阶矩阵，一般)所对应的线性代数方程组，用迭代法求解，在某些精度要求比较高的问题中，经常用迭代法求解。其基本思想为：从某一初始向量出发，按照某种迭代规则，不停地对上一次的近似值进行修正，得到近似解的向量。当近似解收敛于方程组的精确解向量时，满足给定精度要求的近似解向量就可看作是的数值解。关键词：线性方程组；迭代法；Jacobi法；Gauss-Seidel法；逐次超松弛法Iterative Method and Its Application to Numerical Solution of Linear EquationsAbstract：Iterative method is the approximate solution obtained by successive iteration. The problem of solving linear equations is the most common problems in scientific research and engineering calculation, such as structural analysis, network analysis, data analysis, geodetic survey, etc., all need solution of linear equations. Due to the different problems of different and the coefficient matrix of the linear equations derived from, so for large sparse matrix corresponding to the system of linear algebraic equations, is solved by iterative method. In certain accuracy requirement is relatively high, often solved by iterative method. The basic idea is as follows: starting from a certain initial vector, according to some kind of iterative rule, the last time approximation is corrected, and the approximate solution is obtained. When the approximate solution converges to the exact solution of the equation, the approximate solution vector which satisfies the given accuracy requirement can be regarded as the numerical solution.Keywords：linear equations; iterative method; Jacobi method; Gauss-Seidel method; successive over relaxation method引言一般情况下，对于中小型方程组，直接法是非常有效并且迅速的，而对于高阶并且系数矩阵稀疏的线性方程组，尤其是大型线性方程组，却遇到了难题。因为直接法的计算量大，存储量大，连非零元素也要存储。因而对于大型的线性方程组，常常用迭代法来求解。迭代法与直接法是有差异的，它不能直接通过有限次的算术运算求出方程的精确解，而是间接的通过迭代来逐步逼近此方程组的精确解。因此，考虑其收敛性是使用迭代法的关键问题。迭代法较直接法有明显的优势：程序设计简洁，存储量和计算量少等。尤为重要的是，迭代法是解决具有大型稀疏矩阵的线性方程组的重要方法之一。1.预备知识为了更深入的学习迭代法在数值求解线性方程组中的应用，我们有必要回顾一下迭代法的基本知识。1.1迭代法的基本形式设有线性方程组， （1.1.1）其中为非奇异矩阵，向量，因此有唯一的解。下面介绍迭代法的基本格式。将方程组（1.1.1）变形可得到等价的线性方程组， （1.1.2） 任取初值向量为（1.1.1）的近似解，由公式 （1.1.3）可构造出向量序列，若满足下面的式子， （1.1.4） 则迭代法收敛，就是方程组（1.1.1）的解，反之，迭代法就发散。而式子（1.1.3）为迭代格式，为迭代矩阵，为第次迭代的近似的解，而为第次的近似误差。1.2 Jocabi迭代法1.2.1分量形式的Jacobi迭代法对线性方程组，有分量形式： （1.2.1）（1）设，用其它的个变元来表示线性方程组的第个方程中的第个变元，就可得到： (1.2.2)也既是： (1.2.3)（2）用迭代格式写出来就是： (1.2.4)也就是： (1.2.5)(3)任意给定的初值向量代入式(1.2.4)就可逐步算出向量序列，且。当向量序列收敛时，对于事先给定的精度要求(为一个很小的正数)，就有也即是方程组的近似解。1.2.2矩阵形式的Jacobi迭代法假设线性方程组（1.2.1）的系数矩阵A为非奇异，并且对于对角线上的元素，那么就可将矩阵分解成 (1.2.6)若令则有 ,即 可替换为 ，变形为：，因为 ，那么 ，得到迭代公式如下：， (1.2.7)若令 ；，就有 ，那么就称公式(1.2.7)矩阵形式的Jacobi迭代格式，称为Jacobi迭代矩阵。以上为Jacobi迭代格式的两种不同形式，在讨论收敛性的时候，主要用Jacobi迭代格式的矩阵形式，而在实际的应用计算中，则需要用到Jacobi迭代格式的分量形式。1.2.3 Jacobi迭代法的算法实现步骤步1.输入必要的初始数据，及(迭代的最大次数)步2.对做到步5其过程为：步3.对做 步4.若，则输出停机。否则 步5.对做 步6.输出“超出最大迭代次数”，停机。1.3 Gauss-Seidel迭代法1.3.1分量形式的Gauss-seidel迭代法对于公式（1.2.5），可将公式右端前个分量的上标由换成，可得到分量形式的Gauss-seidel迭代法。 （1.3.1）1.3.2矩阵形式的Gauss-seidel迭代法对方程组 ，由前文知 。由于 ,因此 等价于 ，解得 ，所以 （1.3.2）可得到迭代格式 （1.3.3）若令 ,，那么 （1.3.4）公式（1.3.4）就是矩阵形式的Gauss-Seidel迭代格式，是Gauss-Seidel迭代矩阵。1.3.3 Gauss-Seidel迭代法的算法实现步骤步1.输入必要的初始数据，及（迭代的最大次数）步2.对,做到步4其过程为：步3.对做 步4.若，则输出，停机。步5.输出“超出最大迭代次数”，停机。1.4超松弛迭代法（SOR迭代法）对于解线性方程组，一般来说，Jacobi迭代法的收敛速度缓慢，在实际的生活中很少运用。Gauss-Seidel迭代法虽说比Jacobi迭代法收敛的速度稍快，但收敛的速度也不是说特别明显，因此就需要对其修改，提高收敛的速度。而逐次超松弛迭代法（又称SOR方法）就是对修改后的迭代法的一种加速。它的计算公式简洁，但为了使其在迭代的过程中保持较快的迭代速度，选择合适的松弛因子是关键。1.4.1分量形式的SOR方法设线性方程组，其中系数矩阵为非奇异的，,，第步迭代近似值记为，那么 （1.4.1）表示近似解的残余误差，则有加速迭代格式 （1.4.2）就称作松弛因子。若用分量形式的Jacobi迭代格式就是： (1.4.3)当选择恰当的松弛因子，就可获得期望的较快的收敛速度。而在计算时，若用前面的Gauss-Seidel迭代思想，利用已经计算出来的分量，那么就得到一个全新的迭代格式： （1.4.4）当然，当 时，将迭代格式（1.4.4）应用到方程组，可得到 由此可推出下列松弛迭代格式： （1.4.5）容易发现，当的取值为1时，式（1.4.5）是Gauss-Seidel迭代格式。为保证迭代过程的收敛，就必须使，当时称低松弛法，当时称超松弛法。1.4.2矩阵形式的SOR方法对方程组 ，仍由前文知 对任意实数 ，线性方程组就等价于 （1.4.6）同样，线性方程组也等价于 （1.4.7）假设 ，可得出 也即是 是非奇异的。令 得到矩阵形式的SOR迭代格式： （1.4.8）同样，矩阵就是矩阵形式的SOR迭代法的迭代矩阵，称为松弛因子。1.4.3 SOR迭代法的算法实现步骤步1.输入必要的初始数据，及(迭代的最大次数)步2.对做到步4其过程为：步3.对做 步4.若，则输出,停机。步5.输出“超出最大迭代次数”，停机。1.5迭代法的收敛性定理1.对任意的初始向量和任意的，设矩阵为迭代矩阵，则是迭代法收敛的充分必要条件。定义1.对于矩阵，若即主对角线上元素的绝对值大于同行其他元素的绝对值之和，则称矩阵是对角占优矩阵。定理2.如果线性方程组的系数矩阵A是对角占优矩阵，则线性方程组的Jacobi迭代格式和Gauss-Seidel迭代格式都是收敛的。 定理3.若是对称正定矩阵，则解方程组的Gauss-Seidel迭代法收敛。定理4.若解方程组的SOR法收敛，则。定理5.若是对称正定矩阵，且有，则解方程组的SOR法收敛。2.数值求解线性方程组在此给出几个例子从而更清晰的理解用迭代法来求解线性方程组。2.1用Jacobi迭代法求解例1.解线性方程组解：对方程进行变形，分离出变量，：对应的迭代格式为：取迭代初值为,迭代的结果如下表1所示。可得到方程组的精确解为，。表1 Jacobi迭代格式的数值结果00.20001.30002.000010.73001.72002.380020.84801.84902.782030.94131.94122.878640.96981.96982.953050.98761.98762.975860.99391.99392.990170.99741.99742.995180.99881.99882.999090.99971.99972.9998100.99991.99992.9990迭代解为，2.2用Gauss-Seidel迭代法求解例2.用Gauss-Seidel迭代格式求解例1，即求解下列方程组。解：对方程组进行变形，分离出变量由迭代格式（1.3.1），可得到方程组的精确解,迭代的初始向量选为。迭代的结果如下表2所示。表2 Gauss-Seidel迭代格式的数值结果000010.20001.32002.38420.80881.85772.900030.96581.97662.974840.99261.99422.994450.99831.99872.998760.99961.99972.9997由本例可比较出，Gauss-Seidel迭代法比Jacobi迭代法收敛速度快。当初始向量相同，近似解达到同样精度的时候（取），Gauss-Seidel迭代法仅需要6次迭代就满足要求，而Jacobi迭代法则要迭代9次才能够满足此要求。2.3用超松弛迭代法求解例31.用SOR法求解方程组松弛因子取值为，要求。解：由题意知，方程组的系数矩阵为正定矩阵，所以用SOR法求解此方程组一定是收敛的。可求出迭代公式为：迭代的初始向量选为，迭代的结果如下表3所示。表3 SOR迭代格式的数值结果000014.961.5872-3.228022.29352.6854-2.112831.91213.1223-2.245041.59733.2692-2.167751.53633.3146-2.172261.50873.3280-2.166971.50283.3319-2.167081.50063.3330-2.166791.50013.3333-2.1666小 结迭代法是一种通过逐次逼近来求解方程组精确解的方法，它的优点是：程序算法简单、占用的内存小，有利于在计算机上实现，因此它适用于求解大型稀疏线性方程组。常用的迭代法有：Jacobi迭代法、Gauss-Seidel迭代法及超松弛迭代法（SOR迭代法）。Jacobi迭代法简单，有很好的并行性，适用于并行计算，但收敛的速度较慢；Gauss-Seidel迭代法是典型的串行算法，当Jacobi迭代法与Gauss-Seidel迭代法同时收敛的时候，后者比前者收敛速度要快，但这两种迭代法互不包含，不能够互相代替。而在实际应用中较多的是超松弛迭代法，且Gauss-Seidel迭代法是超松弛迭代法的特例，超松弛迭代法实际上就是Gauss-Seidel迭代法的一种加速，然而选取最佳松弛因子是不太容易的，在本论文中没有详细的展开。对于迭代法来说，迭代法的收敛性和收敛速是使用的关键，并且判别收敛的充分条件应该掌握好，同时不收敛的迭代公式在迭代法中是毫无意义的。有些时候对线性方程组做一些简单的同解的变形8后，再次构造迭代公式就可以起到意想不到的结果。本论文中针对典型的系数矩阵是对角占优矩阵和对称正定矩阵线性方程组展开讨论，非线性方程组的迭代法不在本文的讨论范围内。此外，对于解线性方程组的迭代法，还有SSOR迭代法、USSOR迭代法、TOR迭代法11、子空间迭代法、递归迭代法、滤频迭代法、主元加权迭代法10和分裂迭代法9等。迭代法中还有有不少的问题都有待人们深入的研究。参考文献1贺俐，陈桂兴.计算方法M.武汉.武汉大学出版社，1998；2陈晓江，黄樟灿.数值分析M.北京.科学出版社，2010；3吕同福，康兆敏，方秀男.数值计算方法M.北京.清华大学出版社，2008；4孙文瑜，杜其奎，陈金如.计算方法M.北京.科学出版社，2007；5吴勃英，高广宏.数值分析学习指导M.北京.高等教育出版社，2007；6王志军，王海红，孟红玲.数值计算M.郑州.河南大学出版社，2012；7杨泮池.计算方法重点内容重点题M.西安.西安交通大学出版社，2005；8程晓亮，刘影.初等数学研究M.北京.北京大学出版社，2011；9温瑞萍，李苏丹，任孚鲛.求解复对称线性方程组的新分裂迭代方法及预处理子（英文）J.应用数学，2016（1）：173-182.10唐丽，李鹏飞.主元加权迭代法求解病态线性方程组J.科学技术与工程，2012，12（2）：381-383.11张喆.用六种迭代法求超定线性方程组的最小二乘解J.科学与财富，2011（5）：322-323.致谢从确定论文选题至今，我的本科毕业论文已经顺利的完成了。在此，我要特别感谢我的论文指导老师郑州师范学院数学与统计学院王明健老师。从开始的选定论文题目到搜集资料，从确定论文大体的框架到进行开题报告，从修改初稿二稿直到最终的定稿，老师给了我特别悉心的指导。老师是一位十分认真严谨的老师，对我的论文要求十分严格，不论是内容格式，还是标点符号都进行了严格的把关。可以说，老师对我的论文指导尽职尽责、呕心沥血。这才使得我的论文能够如期、保质保量地完成。在写毕业论文的这段日子里，老师严谨的治学态度、渊博的知识结构、精益求精的工作作风以及诲人不倦的高尚师德给我留下了深刻的印象，并将使我受益终身。在此，还要感谢我身边的朋友和同学，感谢他们在论文写作过程中对我的指导、帮助和支持，感谢他们的宝贵建议，感谢所有关心、支持、帮助过我的良师益友。最后，向在百忙中抽出时间对本文进行评审并且提出宝贵意见的各位老师表示衷心的感谢！