线性方程组的迭代法及程序实现毕业论文.doc

毕业论文题 目 线性方程组的迭代法及程序实现 学生姓名 专业班级 学 号 系 （部） 数理科学系 指导教师(职称) 完成时间 2012年5月20日 毕业设计（论文）任务书题目：线性方程组的迭代法及程序实现 专业：信息与计算科学 学号 ： 姓名 一、主要内容：通过本课题的研究，学会如何运用有限元方法来解决线性代数方程组问题，特别是Gaussie-Seidel迭代法和Jacobi迭代法来求解线性方程组。进一步学会迭代方法的数学思想，并对程序代码进行解析与改进，这对于我们以后学习和研究实际问题具有重要的意义。本课题运用所学的数学专业知识来研究，有助于我们进一步掌握大学数学方面的知识，特别是迭代方法。通过这个课题的研究，我进一步掌握了迭代方法的思想，以及程序的解析与改进，对于今后类似实际问题的解决具有重要的意义。二、基本要求：1 学会编写规范论文，独立自主完成。2 运用所学知识发现问题并分析、解决。3.通过对相关资料的收集、整理，最终形成一篇具有自己观点的学术论文，以期能对线性方程组迭代法的研究发展有一定的实践指导意义。4.在毕业论文工作中强化英语、计算机应用能力。 完 成 期 限： 2012年 月 指导教师签名： 专业负责人签名： 年 月 日目 录中文摘要 英文摘要 1 综述12 经典迭代法概述3 2.1 Jacobi迭代法3 2.2 GaussSeidel迭代法4 2.3 SOR（successive over relaxation）迭代法4 2.4 SSOR迭代法5 2.5 收敛性分析5 2.6 数值试验63 matlab实现的两个例题8 3.1 例1 迭代法的收敛速度8 3.2 例2 SOR迭代法松弛因子的选取12 致谢16 参考文献17 附 录19线性方程组的迭代法及程序实现摘 要 线性代数方程组的迭代方法是一种极限方法是解大型稀疏矩阵方程组的有效方法。它的基本思想是用某种极限过程去逐步逼近线性方程组的精确解,是一种逐步逼近的方法。迭代法将n阶线性方程组变形为某种迭代公式。对于任意给定的迭代初始值，由某一迭代格式便可生成一向量序列，我们的目的是求解方程组的解，因此我们会希望向量序列的极限逼近方程组的解。本文首先介绍了求解大型线性方程组的主要迭代算法，对一些经典迭代法(Jacobi方法、GaussSeidel方法、SOR方法和SSOR方法)进行了详细的讨论，其次着重讨论了经典迭代法的收敛性，详细总结并给出了各种迭代方法的收敛性定理，并通过举例及其Matlab程序实现进一步阐述了迭代法的收敛性。关键字 线性方程组/Jacobi迭代法/Gauss-Seidel方法/SOR方法/收敛性 Iterative method and procedures for implementation of the linear equationsABSTRACT The iterative method of linear algebraic equations is an extreme method is an effective method for the solution of large sparse matrix equations. The basic idea is to a certain limit process to gradually approach the exact solution of linear equations, a step-by-step approximation method. The iterative method will be iterative formula for a deformation of n linear equations. For any given iteration of the initial value, by an iterative scheme can generate a vector sequence, our aim is the solution to solving the equations, so we will want to limit approximation the solution of equations of vector sequences. This paper first introduces the main iterative algorithm for solving large linear equations, a detailed discussion of some classical iterative method (Jacobi method, Gauss-Seidel method, SOR and SSOR methods), followed focused on the classical iterative convergence of the method, summarized in detail and gives a variety of iterative methods convergence theorem, and further elaborated by example and Matlab program iterative methods.KEYWORDS linear equations ， Jacobi iterative method ， Gauss-Seidel method ，the SOR method，convergence1 综述在科学研究和大型工程设计中出现了越来越多的数学问题，而这些问题往往需要求数值解。在进行数值求解时，经离散后，常常归结为求解行如Ax=b的大型线性方程组。20世纪50年代至70年代，由于电子计算机的发展，人们开始考虑和研究在计算机上用迭代法求线性方程组Ax=b的近似解，用某种极限过程去逐渐逼近精确解，并发现了许多非常有效的迭代方法。迭代法是按照某种规则构造一个向量序列x，使其极限向量x是Ax=b的精确解。因此，对迭代法来说一般有下面几个问题：（1）如何构造迭代序列？（2）构造的迭代序列是否收敛？在什么情况下收敛？（3）如果收敛，收敛的速度如何？我们应该给予量的刻划，用以比较各种迭代法收敛的快慢。（4）因为计算总是有限次的，所以总要讨论近似解的误差估计和迭代过程的中端处理问题，这又和舍入误差的分析有关。迭代法具有需要计算机存储单元少、程序设计简单、原始系数矩阵在计算过程中始终不变等优点。例如Jacobi方法、Gauss-Seidel方法、SOR方法、SSOR方法，这几张迭代方法是最常用的一阶线性定常迭代法。大量偏微分方程的离散形式是大规模线性代数方程组，其数值计算是科学工程计算的核心，占有绝大部分的总体运算时间，解大规模稀疏线性方程组的Krylov子空间方法显示出与众不同的有效性。当矩阵是对称正定时，常用的方法是具有短递推的共轭度方法(CG)。系数矩阵不对称时，常用的方法中有完全正交化方法（FOM）和广义最小参量方法（GMRES）。还有很多迭代方法正在被人们发现和研究，新的有效的方法层出不穷，其中基于大型稀疏非Bermitian的正定阵的系数矩阵的Bermitian和Skew-Bermitian分裂的BSS方法，IBSS方法等具有非常好的实用性。但没有一种算法是通用的，对于具体问题必须根据所得到的线性方程组和算法的特点进行选择。 MATLAB是Mathworks公司的产品，MATLAB的产生是与数学计算紧密联系在一起的，其基本数据结构是矩阵，它的表达式与数学工程计算中使用的形式十分相似，便于用户学习和使用系统包括5个部分：MATLAB语言、MATLAB工作环境、MATLAB图形处理系统、MATLAB数学函数库和MATLAB应用程序接口其主要功能包括：数值计算；符号计算；数据分析和可视化；文字处理；Simulink动态仿真在数值计算中，线性方程组的求解是一个很重要的问题用MATLAB来求解线性方程组，有几种方法，非常简单，通过对一些矩阵和函数的操作可以轻松地得到线性方程组的解，不需要使用者掌握任何程序设计语言，对迭代法只需编写简单的程序2 经典迭代法概述20世纪50年代至70年代，人们开始考虑和研究用迭代法求解线性方程组 （2-1）的近似解，发展了许多有效的方法，其中有Jacobi方法、Gauss-Seidel方法、SOR方法、SSOR方法，这几种迭代方法均属一阶线性定常迭代法，即若系数矩阵A的一个分裂：；M为可逆矩阵，线性方程组（2-1）化为：；得到迭代方法的一般公式： （2-2）其中：,。2.1 Jacobi迭代法若D为A的对角素构成的对角矩阵，且对角线元素全不为零。系数矩阵A的一个分解：A=D(E+F);这里D为A的对角矩阵，E为严格下三角阵，F为严格上三角阵。其中： Jacobi迭代的矩阵形式为： （2-3）(2-3)式中：；，称为Jacobi迭代矩阵。其计算公式为： （2-4）2.2 GaussSeidel迭代法对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解： (2-5)GaussSeidel迭代矩阵形式为 (2-6)其计算公式为： （2-7）2.3 SOR（successive over relaxation）迭代法对于非奇异方程组，若D为A的对角素构成的对角矩阵，且对角线元素全不为零；系数矩阵A的一个分解： （2-8）这里D为A的对角素构成的对角矩阵，E为严格下三角形，F为严格上三角形。SOR迭代法的矩阵形式为: （2-9）计算公式为： （2-10）（8） 式中：为实数，称为松弛因子，0<<2。2.4 SSOR迭代法SSOR（symmetric successive over relaxation）迭代法的矩阵形式为： (2-11)SSOR迭代矩阵为： （2-12）计算公式分为以下两步：先按自然次序（i=1,2，n）用向前的SOR法逐点计算。 (2-13)然后按相反的次序（i=n，n-1，1）用向后的SOR方法逐点计算。 (2-14)2.5 收敛性分析综合上面前三种迭代格式，它们可以统一表示为下面形式： （2-15）对Jacobi方法来说，,；对Gauss-Seidel方法来说，,；对SOR方法来说，,。定理1：简单迭代法（2-15）收敛的充分必要条件是迭代矩阵B的谱半径.定理2：若迭代矩阵B的范数，则迭代公式（2-15）收敛，且有误差估计式 （2-16） （2-17）定理3：设对于方程组，若系数矩阵A是严格对角占优矩阵，则Jacobi迭代法和Gauss-Seidel迭代法都收敛。定理4：设A为n阶非奇异方阵，则的解总能通过Gauss-Seidel方法得到。定理5：设是二阶矩阵，且，则有： （1）方程组若用J方法与G-S方法解之，敛散性相同； （2）方程组若发散，总可以通过交换两行的方法得到解（当 时）。定理6：若系数矩阵A对称正定，则G-S迭代公式收敛。定理7：若系数矩阵A对称正定，且也为对称正定阵，则Jacobi迭代收敛。定理8：若系数矩阵A为对称正定阵，则当时，SOR迭代法收敛。定理9：若系数矩阵A为严格对角占优阵，则当时，SOR迭代法收敛。定理10：若系数矩阵A为是正定的，则当时，SSOR迭代法收敛。简单迭代法的比较：（1） 一般情况下，J方法与G-S方法比较并无优劣。收敛情况与速度均不一定。（2） 但是，具有相容次序的矩阵，在相同精确要求下，G-S法比J方法快一倍，而SOR法的收敛速度可提高一个数量级。2.6 数值试验下面通过一个数值实例来比较Jacobi方法、Gauss-Seidel方法、SOR方法的收敛速度。数值实验：我们取一个系数为64阶的线性方程组：AX=b。其中： 精确解：X=（1 1 1 1 1）;取X=（0 0 0 0 0）；精度为：0.0001。执行c语言程序interator method.c(见附录)得到result.txt文件。从中可以得到三种方法的迭代性能对比如表2-1MethodIT CPU Time/msInfoJacobi183.000008.19628Gauss-Seidel102.000001.68024几乎比Jacobi速度快一倍SORwith =1.0102.000001.68024退化成G-S迭代SORwith =61.000005.47552是SOR迭代达到最快SORwith =1.5173.000002.09836的取值对于SOR迭代的收敛速度影响很大3 matlab实现的两个例题3.1 例1 迭代法的收敛速度用迭代法分别对n=20，n=200解方程组Ax=b,其中（1）选取不同的初值和不同的右端向量b，给定迭代误差，用两种迭代法计算，观测得到的迭代向量并分析计算结果给出结论；（2）取定初值和右端向量b，给定迭代误差，将A的主对角元成倍放大，其余元素不变，用Jacobi迭代法计算多次，比较收敛速度，分析计算结果并给出结论。原理解析：运用了Jacobi迭代，Gauss-Seidel迭代1）Jacobi迭代算法：1. 取初始点,精度要求，最大迭代次数N，置；2. 由 （3-1）计算出；3. 若,则停算，输出作为方程组的近似解；4. 若k=N，则停算，输出迭代失败信息；否则置，转步2。2）Gauss-Seidel迭代算法： （3-2）3.若，则停算，输出x作为方程组的近似解；4. 若k=N，则停算，输出迭代失败信息；否则置=x，k=k+1，转步骤2。解：（1）打开matlab软件，新建一个M文件，编写程序（见附录二），运行程序，记录结果；（2）把程序中=ones(n,1)改为=eye(n,1)，运行程序，记录结果；（3）把程序中A(i,i)=m改为A(i,i)=2*m，注释掉=majacobi(A,b);后面的部分，运行程序，记录结果；（4）仿照（3）再把主对角元成倍放大，运行程序，记录结果。运行结果为：（1）对于n=20时：n = 20Columns 1 through 12 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 0 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 0 0 0 0 0 0 0 0 0 -0.2000 -0.3333 4.0000 0 0 0 0 0 0 0 0 0 0 -0.2000 -0.3333 0 0 0 0 0 0 0 0 0 0 0 -0.2000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0Columns 13 through 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.2000 0 0 0 0 0 0 0 -0.3333 -0.2000 0 0 0 0 0 0 4.0000 -0.3333 -0.2000 0 0 0 0 0 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 -0.2000 0 0 0 0 -0.2000 -0.3333 4.0000 -0.3333 0 0 0 0 0 -0.2000 -0.3333 4.0000k= 11x1 =1.0000 1.0000/有20个1.0000k= 8x2 =1.0000 1.0000/有20个1.0000ans = 3.3039e-007（2）当n=200时：A由于阶数太大省略；k= 11x1=1.0000 1.0000 /有200个1.0000k= 8x2=1.0000 1.0000 /有200个1.0000ans = 1.1368e-006（2）k= 4x1 = 1.0000 1.0000（20阶）k= 4x2 = 1.0000 1.0000（20阶）ans =4.8999e-008结果分析：比较结果可知，选取不同的初值和不同的右端向量b，所求得的结果也会不同，Jacobi迭代和Seidel迭代的误差也会随之改变，说明初值对结果有影响，由迭代误差可知Seidel迭代优于Jacobi迭代。再比较结果，由k=6与k=5可知，主对角元越大，Jacobi迭代收敛越快。3.2 例2 SOR迭代法松弛因子的选取（1）给定迭代误差，选取不同的超松弛因子，从1.00到2.00，观察不同的松弛因子对解得影响。然后利用雅可比迭代求的的解与它们比较； （2）给定迭代误差，选取不同的低松弛因子，从1.00到2.00，观察不同的松弛因子对解得影响。然后利用雅可比迭代求的的解与它们比较。原理解析：（1）逐次超松弛迭代法是Gauss-Seidel迭代法的加速。Gauss-Seidel迭代格式为： （3-3）（2）SOR迭代格式为 （3-4）其中，叫做松弛因子，当>1时叫超松弛，当1>>0时叫低松弛。=1是Gauss-Seidel迭代法；（3）SOR迭代法的算法：输入矩阵A，向量b，初始点,精确度，最大迭代次数N，松弛因子的选取；进行迭代；判断迭代的情况。解：（1） 数据准备：A=12*eye(200,200);for i=1:199 A(i,i+1)=-2; A(i+1,i)=-2;endfor j=1:198 A(j,j+2)=1; A(j+2,j)=1;endb=5*ones(200,1);（2）给定迭代误差1e-6，取=1.00,1.10,1.20,1.30,1.40,1.50,1.60,1.70,1.80,1.90,1.91,1.92,1.95,1.97,1.98,1.99,2.00，代入x=masor(A,b，)，x20=majacobi(A,b)并利用norm(x-x20)分别分析与雅可比迭代求的解的误差； (3) 给定迭代误差1e-6，取=0.02,0.03,0.040.10,0.20,0.30,0.40,0.50,0.60,0.70,0.80,0.90,0.97.0.98,0.99，代入x=masor(A,b，)，=majacobi(A,b)并利用分别分析与雅可比迭代求的解的误差。运行结果为：表3-1 >1的情况k1.0089.7346e-0071.10109.6821e-0071.20121.0307e-0061.30161.0200e-0061.40201.1434e-0061.50261.2691e-0061.60361.2272e-0061.70511.4364e-0061.80831.4657e-0061.901771.7205e-0061.911981.7542e-0061.922242.2548e-0061.953211.5060e-0061.974711.8146e-0061.98>5001.99>500表3-2 <1的情况k0.000.02>5000.033863.8618e-0040.042972.8217e-0040.101261.0286e-0040.20644.0889e-0050.30422.1010e-0050,40301.4555e-0050.50238.1655e-0060.60185.0040e-0060.70143.7920e-0060.80112.3675e-0060.9091.0772e-0060.9789.7786e-0070.9889.7481e-0070.9989.7361e-007结果分析：（1）由表1-1可以看出，在其它条件不变的情况下，改变的值，会改变解得值，且越接近于1，误差越小，越接近于2，误差越大，而且当的值越大，它的迭代次数越大，就本例而言，当为1.98时，就因迭代次数过大，跳出程序；（2）由表1-2可以看出，在其它条件不变的情况下，改变的值，会改变解得值，且越接近于1，误差越小，越接近于0，误差越大，且迭代次数也越大，就本例而言，当为0.02时，就因迭代次数过大，跳出程序，且不能取值为0；（3）综上（1）（2）所述，的取值范围为0<<2,且越接近1，误差值越小，迭代次数也越小。 参考文献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.