终稿线性方程组直接法和迭代法

1、毕 业 论 文2012届线性方程组的直接法和迭代法 学生姓名 刘玲 学 号 08102117 院 系 数理信息学院 专 业 信息与计算科学 指导教师 祝汉灿 完成日期 2012年5月25日 线性方程组的直接法和迭代法摘 要在现实生活当中，经常会遇到自然以及社会科学领域中的诸多问题。这些问题中所包含的数学模型都可以与一定的线性方程组所对应起来。因此，在科学技术、工程和经济领域中都会遇到解线性方程组的问题。求解线性方程组AX=b是科学计算的中心问题。解线性方程组主要有直接法和迭代法。对于系数矩阵为低阶稠密矩阵的线性方程组可以用直接法进行消元。对于大规模线性方程组的求解问题，特别是大规模稀疏线性方程

2、组，直接法会显得比较繁琐。迭代法是求解线性方程组的一种有效方法，它有存储空间小，程序简单等特点。比较常用的迭代方法有Jacobi迭代和Gauss-Seidel迭代。（1） 这两种迭代法的收敛性态并不相同，很多情况下Gauss-Seidel迭代法比Jacobi迭代法收敛快. 关键词 线性方程组； 直接法； 迭代法；发散； 收敛 THE DIRECT AND ITERATION METHOD OF LINEAR EQUATIONSABSTRACT In science, technology, engineering and economic fields, we will meet the pr

3、oblem of solving linear equations. Generally speaking, there are direct methods and iterative methods for solving linear equations. For coefficient matrix and low order dense matrix of linear equations, we can use direct method for the elimination. For large-scale linear equations, especially large

4、sparse linear equations, a direct method is much complicated. In this situation, the iterative method is the more effective method to solve the linear equations. The most common used methods are the Jacobi iteration and Gauss-Seidel iteration. In this paper, we mainly study the convergence of the tw

5、o methods. (13) KEY WORDS: solving linear equations; low order dense matrix; large-scale linear; direct method; iterative method 目 录 摘 要IABSTRACTII目 录III引 言11.线性方程组的直接法21.1Cramer法则21.2Gauss消元法3用Gauss消元法为线性方程组求解32.线性方程组迭代法42.1Jacobi迭代法42.2Gauss-Seide迭代62.3SOR迭代82.4迭代法收敛92.5迭代法收敛的应用123.结论：14参考文献15附录16

6、致 谢20引 言 在现实生活当中，经常会遇到自然以及社会科学领域中的诸多问题，这些问题中所包含的数学模型都可以与一定的线性方程组所对应起来，换句话说，求解线性方程组的过程就是就是解决实际遇到的自然及社会科学问题的过程，在线性方程组的求解的重要性可见一斑。求解线性方程组AX=b是科学计算的中心问题。解线性方程组主要有直接法和迭代法。直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法但实际计算中由于误差的存在和影响，这种方法也只能得到线性方程组的近似解，而且该方法也只是是求解低阶稠密矩阵方程组的有效方法。迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法该方法具有对计算机的存

7、贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解。 在求解线性方程组直接法中主要有Cramer法则，Gauss消元法。Cramer法则是线性代数中一个关于求解线性方程组的定理。（2）它适用于变量和方程数目相等的线性方程组，是瑞士数学家克莱姆（1704-1752）于1750年，在他的线性代数分析导言中发表的。Gauss消元法是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个“行梯阵式”。 该方法是以数学家卡

8、尔高斯的名字命名的，但最早出现于中国古籍九章算术，成书于约公元前150年。在求解线性方程组的迭代法的180多年的发展历史过程，产生了众多不同的迭代方法。经典的迭代法，(5)例如Jacobi迭代法、Gauss-Seidel迭代法、超松弛(SOR)迭代法，都是Hadjidimos在1978年所提出的加速超松弛(AOR)迭代法的特例。本课题运用所学的数学专业知识研究，有助于我们进一步掌握大学数学方面的知识，特别是Jacobi迭代和Gauss-Seide迭代。1. 线性方程组的直接法 直接法就是经过有限步算术运算，无需迭代可直接求得方程组精确解的方法。 1.1 Cramer法则 Cramer法则用于判

9、断具有n个未知数的n个线性方程的方程组解的情况。当方程组的系数行列式不等于零时，方程组有解且解唯一。如果方程组无解或者有两个不同的解时，则系数行列式必为零。如果齐次线性方程组的系数行列式不等于零，则没有非零解。如果齐次线性方程组有非零解，则系数行列式必为零。 定理1如果方程组中，则有解，且解事唯一的，解为是D中第i列换成向量b所得的行列式。Cramer法则解n元方程组有两个前提条件：1、未知数的个数等于方程的个数。2、系数行列式不等于零 例1 a取何值时，线性方程组有唯一解。解：所以当时，方程组有唯一解。定理2当齐次线性方程组，时该方程组有唯一的零解。定理3 齐次线性方程组有非零解。1.2 G

10、auss消元法 Gauss消元法是线性代数中的一个算法，可用来为线性方程组求解，求出矩阵的秩，以及求出可逆方阵的逆矩阵。当用于一个矩阵时，高斯消元法会产生出一个“行梯阵式”。 1.2.1 用Gauss消元法为线性方程组求解eg：Gauss消元法可用来找出下列方程组的解或其解的限制：这个算法的原理是：首先，要将以下的等式中的消除，然后再将以下的等式中的消除。这样可使整个方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。在刚才的例子中，我们将和相加，就可以将中的消除了。然后再将和相加，就可以将中的消除。方程组则变为：现在将和相加，就可将

11、中的消除，方程组变为：这样就完成了整个算法的初步，一个三角形的格式(指:变量的格式而言,上例中的变量各为3,2,1个)出现了。第二步，就是由尾至头地将已知的答案代入其他等式中的未知数。第一个答案就是。然后直接带入，立即就可得出第二个答案：和最后一个答案。这样，我们利用高斯消元法解决了这个方程组。2. 线性方程组迭代法 迭代法就是用某种极限过程去逐步逼近线性方程组精确解的方法该方法具有对计算机的存贮单元需求少，程序设计简单、原始系数矩阵在计算过程中不变等优点，是求解大型稀疏矩阵方程组的重要方法迭代法不是用有限步运算求精确解，而是通过迭代产生近似解逼近精确解如Jacobi迭代、Gauss Seid

12、el迭代、SOR迭代法等。2.1 Jacobi迭代法 对于线性方程组则，即将A分解为一个严格下三角矩阵、一个对角阵和一个严格上三角矩阵之和，从而可写出Jacobi迭代格式的矩阵表示形式为：，其迭代矩阵)称为雅可比迭代矩阵. 将线性方程组变为一个通解方程组，对其进行迭代式改写，矩阵B为迭代矩阵 由方程组（I）的第i个方程解出，得到一个同解方程组：构造相应的迭代公式取初始向量，利用（III）反复迭代可以得到一个向量序列，利用此迭代格式求解方程组的解法称为Jacobi迭代法。用Jacobi迭代求解下列方程组输入A=4 3 0;3 3 -1;0 -1 4；b=24;30;-24；x, k, index

13、=Jacobi(A, b, 1e-5, 100)输出：x = -2.9998 11.9987 -3.0001k = 100index = 0所以解为：=-2.9998, =11.9987, =-3.00012.2 Gauss-Seide迭代 若L、 U、 D为上述的L、 U、 D。则GaussSeidel迭代法的矩阵表示为：，现将显示化由得：，令，则得：，此即为GaussSeidel迭代法的矩阵表示形式，G称为迭代阵。 由Jacobi迭代法中，每一次的迭代只用到前一次的迭代值，若每一次迭代充分利用当前最新的迭代值，即在计算第个分量时，用最新分量，代替旧分量，就得到所谓解方程组的Gauss-Se

14、idel迭代法。其迭代格式为 (初始向量)， 或者写为用Gauss-Seide迭代求解下列方程组 输入A=4 3 0;3 3 -1;0 -1 4；b=24;30;-24；x0=0;0;0；v,sN,vChain=gaussSeidel(A,b,x0,0.00001,11)输出：v = 0.6169 11.1962 -4.2056sN = 11vChain = 6.0000 10.0000 -6.0000 -1.5000 2.0000 -3.5000 4.5000 10.3333 -5.5000 -1.7500 3.6667 -3.4167 3.2500 10.6111 -5.0833 -1.9

15、583 5.0556 -3.3472 2.2083 10.8426 -4.7361 -2.1319 6.2130 -3.2894 1.3403 11.0355 -4.4468 -2.2766 7.1775 -3.2411 0.6169 11.1962 -4.2056 0 0 0 0 0 0 0 0 0 0 0 0所以结果为：= 0.6169, =11.1962, =-4.2056 。2.3 SOR迭代在很多情况下，Jacobi和GaussSeidel法收敛速度较慢，SOR法是GaussSeidel法的一种加速方法，需要施加合适的松弛因子。若L、 U、 D为上述的L、 U、 D 。SOR迭代公式

16、为，其中，。用SOR迭代求解下列方程组。取初始点松弛因子，精度要求。输入A=0.76 -0.01 -0.14 -0.16；-0.01 0.88 -0.03 0.06； -0.14 -0.03 1.01 -0.12；-0.16 0.06 -0.12 0.72;B=0.68 1.18 0.12 0.72;X0=0;0;0;0;W=1.05x,n=SOR(A,b,x0,w)输出x=1.27151.28440.48581.2843n=7 有上述结果得出：经过7次迭代后，该方程组的解为x1=1.2715, x2=1.2844, x3=0.4858, x4=1.28432.4 迭代法收敛引理：设A为n阶方

17、阵，则的充要条件为（为普半径）。证明：必要性若由矩阵收敛的定义知有因为所以由夹逼定理可得出，又因为所以由可得出充分性：若，取，存在矩阵范数，使得则有：，由算子范数相容性可得：由夹逼定理可得出。定理1： 迭代公式收敛的充分必要条件是迭代矩阵的谱半径 证明：必要性设存在n维向量，使得，则满足由迭代公式得出所以因为为任意n维向量，因此上式成立必须由引理可得出。充分性：若，则不是B的特征值，因而有,于是对任意的n维向量f，方程组有唯一解，记为。即：且，又因为所以，对任意初始向量都有即迭代公式收敛。注解： 代矩阵的谱半径这里的是矩阵的特征值。定理2： 若迭代矩阵的一种范数，则对任意的初始向量和任意。迭代

18、格式均收敛。 迭代法收敛与否只决定于迭代矩阵的普半径，于初始向量及右端项无关。对于同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的发散的情形。注解：三种常用矩阵范数为：，（是的最大特征值）。 由上述两个定理可得：Jacobi迭代收敛的充分必要条件是，收敛的充分条件是任一种范数，GaussSeidel迭代收敛的充分必要条件是，收敛的充分条件是任一种范数。 定理3： 对角占优线性方程组的Jacobi迭代格式和GaussSeidel迭代格式均收敛。注解：n阶方阵A，如果其主对角线元素的绝对值大于同行其他元素绝对值之和，则称A是对角占优的虽然定理1是充分必要条件，可是需要计算迭代矩

19、阵的特征值，我们在线性代数上看到一个大型矩阵的特征值是非常难求的，计算量是很大的。定理2和定理3的计算量相对定理1来说是相当小的，因为它们只是简单的加减乘除；但是他们是充分条件，不满足时需要再改用定理1来判断。所以收敛的判断可先采用定理2和定理3，不行再选择定理1。 预处理是用来加速迭代法收敛的一个重要手段。值得注意的是，经典的求解线性方程组的迭代法也都能够看作是求解采用不同的因子预处理之后得到的线性方程组的迭代法。换句话来说，原线性方程组的松弛迭代法等价于预处理之后的方程组的定点迭代法。谱条件数是反映预处理因子性态是否良好的一个有效指标。在估计特征值和条件数的界的研究领域，虽然已经有了很多的

20、研究成果，但是支持理论还是一个全新的概念。支撑理论是一个用于分析预处理方程组的最大(或最小)特征值和条件数的代数架构，它最初产生于对称正定的线性方程组(7)2.5 迭代法收敛的应用用Jacobi迭代，GaussSeidel迭代 两种方法求解下列方程组是否收敛。解：因为迭代法收敛与否只决定于迭代矩阵的普半径。所以求普半径是否小于1. ，Jacobi迭代矩阵其特征方程所以，所以 所以Jacobi迭代法收敛。GaussSeidel迭代矩阵其特征方程所以特征值为所以所以GaussSeidel迭代法发散。上述例子说明对于同一方程组，由于不同的迭代法迭代矩阵不同，可能出现有的方法收敛，有的发散的情形。 3

21、. 结论： 毕业论文是本科学习的一个重要阶段。在这次的毕业论文中，我对线性方程组的解法更加熟悉了。通过这次论文的练习，我运用所学基础知识，解决实际问题的能力得到一定的提高。同时也提高了我查阅文献资料，设计规范以及电脑等方面的基础知识。 虽然毕业论文的课题很广，但我选取了最经典的方面去完成。这次的论文提高了我对整体的掌控，对局部的取舍，以及对细节的斟酌处理能力，并且经验得到了丰富，意志品质力，抗压能力及耐力也都得到了不同程度的提升。这是我们都希望看到的也正是我们进行毕业设计的目的所在。这次论文简单介绍了解线性方程组的直接法和迭代法，以及各自的区别。 本次实验是在指导老师指导下完成的。在实验研究的

22、过程中，老指导师给予了指导，并提供了很多与该研究相关的重要信息，培养了我们对科学研究的严谨态度和创新精神。这将非常有利于我们今后的学习和工作。在此表示衷心的感谢！参考文献【1】 赵秉新，郑来运. MATLAB在求解线性方程组中的多种应用J. 通化师范学院学报, 2007,28（12）：13-24. 【2】 周均，韩乐文应用matlab求线性方程组的Cramer法则方法探讨J重庆职业技术学院学报, 2004，13(3)：129-130.【3】 李庆扬，王能超，易大义数值分析M武汉：华中科技大学出版社, 2002.【4】 袁媛，杨建伟求解非线性方程重根的二阶迭代法J. 南京信息工程大学学报(自然科

23、学版)， 2010, 2(1): 71-73.【5】 韩艳丽求解线性方程组的Jacobi和GaussSeidel迭代法的收敛定理J中国西部科技，2009， 20：31. 【6】 徐树方，高立，张平文数值线性代数M，北京：北京大学出版社，2005. 【7】 倪健，马昌凤解非线性方程牛顿迭代法的一种新的加速技巧J广西科学院学报，2010, 26(1): 1-3.【8】 戈卢布G H，范洛恩C F矩阵计算M袁亚湘，译，北京：科学出版社，2001：370-37.【9】 张艺线性方程组求解的一个迭代算法J宁波大学学报：理工版，2001，14(1)：51-55【10】李庆扬，关治，白峰杉数值计算原理M北京

24、：清华大学出版社2000【11】A拉尔斯登，等数字计算机上用的数学方法(第二卷), 中国科学院计算技术研究所三室译, 上海：人民出版社，1976【12】常双领，张传林求解线性方程组的一种迭代解法J暨南大学学报，2004(3)：06【13】Abbasbandy S, Asady B. Newtons method for solving fuzzy nonlinear equations JApplied Mathematics and ComputationJ2004(2)：349-356【14】张传林数值方法M北京：中国科学文化出版社，2001: 80-150【15】栾世超，王云诚 求解非线

25、性方程的一个全局收敛算法J. 鲁东大学学报(自然科学版), 2010, 26(1): 20-22.【16】张荣锋. 数值分析中的迭代法解线性方程组J，中国科教创新导刊，2011, 20: 112.【17】陈丽红，周志刚，万立. 求解线性方程组的一种迭代法的改进J. 武汉科技学院报，2010, 4: 33-35.附录由MATLAB提供的求行列式值的函数det(A)实现，分别求得凡+1个行列式的值，用Cramer法则求得Ax=b的解可编写下列函数文件cramerm：function X=cramer(A，b)for k=1：length(b)D =A： D(：，k)=b；x(k)=det(D)de

26、t(A)；endX用matlAB编写Jacobi迭代函数function Y=jacobi(A，b，xO，jingdu)if nargin = =3jingdu=1.Oe一6；elesif nargin =jingduxO=Y：Y=B xO+f；n=n+1；endYN用matlAB编写GaussSeidel迭代函数 function Y=gauss seidel(A，b，xO，jingdu)if nargin = =3jingdu = 1.Oe一6；elesif nargin = jingduxO = Y：Y = G * xO + f：n=n+1： endYN用matlAB编写SOR迭代函数 function Y SOR(A，b，W，xO，jingdu) if nargin = =4jingdu = 1.Oe一6；elesif nargin = jingdux0=Y； Y=Lw * x0 + f；n=n+1：endyn 输入矩阵并根据要求调用函数，运行结果如下图表示 用Gauss消元法找出逆矩阵 高斯消元法可以用来找出一个可逆矩阵的逆矩阵。设A 为一个N * N的矩阵，其逆矩阵可被两个分块矩阵表示出来。将一个N *