线性方程组的多种求解问题2

1、青海师范大学数学系2013届信息与计算科学专业毕业论文多种求解线性方程组的方法比较知识就是力量 姓 名：李积鑫 班 级：2009级C班 指导教师：陈桂秀（职称） 完成时间：2013年4月28日目 录摘要 1Abstract 11 线性方程组的求解历史起源12 线性方程组的多种求解方法22.1 高斯消去法 22.1.1 高斯顺序消去法 22.1.2 高斯选主元素消去 32.1.1 列主元素消去法 3 2.2 克莱姆规则4 2.3 迭代法 62.3.1 雅可比迭代法 62.3.2 高斯-赛德尔迭代法7 2.4 MATLAB在求解线性方程组中的应用 73 总结 104 参考文献10多种求解线性方程组

2、的方法比较李积鑫青海师范大学 810008摘要：线性代数是数学的一个古老分支，广泛应用于现代科学的许多分支,其核心问题之一就是线性方程组的求解问题。而历史上线性代数的第一个问题是关于解线性方程组的问题，且线性方程组是线性代数中一个最基础的内容，它在科学和工程计算等领域都发挥着重要的作用。本文首先介绍线性方程组的求解历史，重点介绍了解线性方程组的几种方法:消元法、克莱姆解线性方程组以及迭代法。最后介绍了如何利用Matlab等常用电脑软件解线性方程。关键词：线性方程组 Matlab 迭代法 高斯消元法 Abstract:Linear Algebra is an ancient branch f m

3、athematics, widely used in many branches f mdern science, ne f the cre issues is the prblem f slving linear equatins. The histry f linear algebra first questin is abut the prblem f slving linear equatins, linear equatins and linear algebra in the mst basic cntent, it plays an imprtant rle in the fie

4、ld f scientific and engineering cmputing. This paper first intrduces the histry f linear equatins, the highlights are several ways t understand linear equatins: eliminatin methd, Clem slving linear equatins and iterative methd. Finally, hw t use Matlab and ther cmmnly used cmputer sftware fr slving

5、linear equatins.Keywrd: Linear Algebra;Matlab;Iterative methd;Gaussian eliminatin 一、线性方程组的求解历史起源我们把形如的这种方程叫做线性方程组的一般形式。同时线性方程组中的系数也可以写成矩阵形式，即则方程组为的矩阵形式。九章算术是中国古代一部重要的数学经典之作。其“方程术”解线性方程组的方法是世界上最早、最完整的线性方程组的解法，其中所述方法实质上相当于现代的对方程组的增广矩阵施行初等行变换从而消去未知量的方法，即高斯消元法。刘徽提出了比较系统的方程理论。在西方，线性方程组的研究是在 17 世纪后期由莱布尼茨开

6、创的。他曾研究含两个未知量的三个线性方程组组成的方程组。线性方程组解结构的早期研究，是由麦克劳林和克莱姆从线性方程组的求解入手，用线性方程组的系数给出解的表达式，虽然麦克劳林的发现要早两年，但是相比之下，克莱姆的规律更简明清晰，更加完美.18世纪下半叶，法国数学家贝祖对线性方程组理论进行了一系列研究，证明了元齐次线性方程组有非零解的条件是系数行列式等于零。19世纪，英国数学家史密斯 (H.Smith) 和道奇森 (C-L.Ddgsn) 继续研究线性方程组理论，前者引进了方程组的增广矩阵和非增广矩阵的概念，后者证明了个未知数个方程的方程组相容的充要条件是系数矩阵和增广矩阵的秩相同。这正是现代方程

7、组理论中的重要结果之一。大量的科学技术问题，最终往往归结为解线性方程组。因此在线性方程组的数值解法得到发展的同时，线性方程组解的结构等理论性工作也取得了令人满意的进展。现在，线性方程组的数值解法在计算数学中占有重要地位。2、 线性方程组的多种求解方法1、 高斯消去法高斯消去法（又叫顺序消去法或逐次消去法）是一个古老的求解线性方程组的直接方法（早在公元前250年我国就掌握了解三元线性方程组的方法），其基本思想是用逐次消去未知量的方法，把原来方程组化为其同解的三角形方程组，求解三角方程组就比较容易。高斯消去法主要包括高斯顺序消去法、高斯完全主元素消去法、列主元素消去法等。下面举例分析这三种方法的具

8、体做法及特点。1.1高斯顺序消去法求解方程组其基本思想利用矩阵的初等变换（互换变换、倍数变换、消去变换）将方程组中的系数矩阵约化为具有简单形式的矩阵（如上三角矩阵，单位矩阵等）。例1、用高斯顺序消去法解线性方程组解： 解之得1.2高斯选主元素消去法其基本思想是对方程组中的系数矩阵进行行和列的交换，首先从的个元素中选取绝对值最大的元素作为主元素，然后进行消元和回代计算。例2用完全主元素消去法解线性方程组 解：于是对应的上三角线方程组为解之得 1.3列主元素消去法其基本思想是每次选取主元素时，仅依次按列选取绝对值最大的元素作为主元素，并且进行交换两行，然后进行消元和回代计算。例3用列主元素消去法解

9、线性方程组 解：解之得 经过上述三种做法，我们直观上首先可以看出高斯顺序消元法相对比较简便些，但是顺序法也有它的局限性，在解线性方程组的消元过程中，可能会出现如下两种情况：第一是的情形，致使消元过程无法继续下去；第二即使，但其绝对值很小的时作除数可能会导致其他元素数量级的严重增长和舍入误差的传播，使计算结果不可靠。所以在采取高斯消元法解方程组时，小主元素可能会产生计算结果失真，故应避免采用绝对值小的主元素。对一般矩阵来说，比较好每一步选取系数矩阵（或消元后的低阶矩阵）中绝对值最大的元素作为主元素，以使高斯消去法具有良好数值稳定性。所以我们可以采取选主元素的方法来克服高斯顺序消去法的这一缺点。完

10、全主元素消去法是解低阶稠密矩阵方程组的有效方法，但是这种方法在选主元素时会花费一些时间，而且由于变量之间的位置在消元过程中（列变换）发生了改变，这使得对最后解上三角形方程组时，变量的值容易发生错误，所以在计算过程中应记住各变量的具体位置，最后按变量的原始顺序输出方程组的解。由于完全主元素这一局限性，在实际计算中也常用部分选主元素（即列主元素）消去法。2、 克莱姆法则定理1、（克莱姆规则）一个含有n个未知量n个方程的线性方程组当它的行列式D0时，有且只有一个解此处是把行列式的第j列元素换以方程组的常数项而得到的n阶行列式。其中D是系数行列式，D是在系数行列式基础之上结合方程组右边常数形成的新行列

11、式，利用行列式的性质计算行列式最为有效，对于二、三阶行列式可以利用对角线法则计算。克莱姆法则克服了消元法计算效率低甚至无法计算多元一次方程组的缺点，但是对于系数行列式等于零以及欠定或者超定方程组的情况，它是无能为力的)事实上，当未知元数过多时，克莱姆法则的计算效率就很低。例2.1解线性方程组解：这个方程组的行列式。因为,我们可以应用克莱姆规则再计算以下的行列式由克莱姆规则，得方程组的解是：克莱姆法则建立了线性方程组的解和已知的系数与常数项之间的关系，它主要适用于理论推导。克莱姆法则克服了消元法计算效率低甚至无法计算多元一次方程组的缺点，但是克莱姆也有它的不足：（1）克莱姆法则只能用于求解方程个

12、数与未知数个数相等的线性方程组；（2）克莱姆法则只能求得系数行列式不为零时的线性方程组的唯一解；即如果方程个数与未知数个数不相等，或系数行列式等于零，则克莱姆法则失效。（3）计算量大，要计算 n+1 个 n 阶行列式的值。所以使用克莱姆法则求解线性方程组时应该遵循两个条件，首先方程个数和未知量个数必须相等；其次，系数行列式不为零。3、 迭代法线性方程组为A=b（A为非奇异矩阵），当系数矩阵A为低阶稠密矩阵时，利用高斯消去法求解这类方程组是合适的，但如果矩阵A的阶数n很大（n）且零元素很多的情况下，利用迭代法解这类方程组是比较合理的。所以以下介绍几种迭代法及其基本思想。3.1雅可比迭代法(Jac

13、bi)对于n元线性方程组A=b中的系数矩阵A可分解为几个特殊矩阵的和A=U+D+L，其中U为严格上三角矩阵，D为A的对角素构成的对角矩阵，L为严格下三角阵，则A=b写作（U+D+L）=b，（U+L)+D=b,D=-(U+L)+b,由此可得雅可比迭代公式的矩阵形式：=-D-1(U+L)(k)+D-1b，记B=-D-1(U+L)，f=D-1b,从而有(k+1)=B(k)+f，其中矩阵B称作雅可比迭代法的迭代矩阵。例3.1用雅可比迭代法解线性方程组解：首先从上面的三个方程中分别分离出变量，由此将这个方程组改写成便于迭代且等价的方程形式，据此建立迭代公式，取迭代初始解向量，代入上式并反复迭代，当迭代次

14、数增加时迭代结果就越来越逼近准确解，这种迭代过程是收敛的吧，迭代得到的解向量序列是以为极限，这种方式则称为雅可比迭代法。3.2高斯赛德尔迭代法（G-S）对于n元线性方程组A=b中的系数矩阵A作分解A=U+D+L，其中U为严格上三角矩阵，D为A的对角素构成的对角矩阵，L为严格下三角阵，则A=b写作（U+D+L)=b，D=-L=U+b,根据分量形式就有D(k+1)=-L(k+1)-U(k)+b，从而（D+L）(k+1)=-U(k)+b,如果（D+L）-1存在，则高斯-赛德尔迭代公式的矩阵形式为(k+1)=-（D+L）-1U(k)+（D+L）-1b,即B=-(D+L)-1U,f=(D+L)-1b,于

15、是有(k+1)=B(k)+f，其中矩阵B称作高斯-赛德尔迭代法的迭代矩阵。例3.2用高斯-赛德尔迭代法解线性方程组解：从上面的三个方程中分别分离出变量，由此将这个方程组改写成便于迭代且等价的方程组形式，据此建立迭代公式，取迭代初始解向量，代入上式并反复迭代，从而得到迭代公式。两种迭代法的比较：一般情况下，J法与GS法比较并无优劣，收敛情况与速度均不一定。但是，具有相容次序的矩阵，在相同精度要求下，GS法比J法快一倍。若线性方程组系数A是严格对角占优或不可约对角占优矩阵，则J法和GS法都收敛。4、 MATLAB在求解线性方程组中的应用MATLAB是功能强大的科学及工程计算软件，它不但具有以矩阵计

16、算为基础的强大计算和分析功能，而且还具有丰富的可视化图形表现功能和方便的程序设计能力。对于线性方程组其中为此线性方程组的系数矩阵为列向量,矩阵为由构成的此方程组的增广矩阵。则线性方程组的解可分为以下三种个情况：（1） 当m=n且rank(A) = rank(B) = n时线性方程组有唯一解，可通过求出解。例4.1求解方程组解：>> A=1 2 3 4;4 3 2 1;1 3 2 3;4 1 3 2;b=5;4;3;2;>> b=5;4;3;2;>> B=A,b;>> n=4;>> RA=rank(A)>> RB=rank(

17、B)>> =Ab = -8.2000 4.0000 18.8000 -12.8000（2） 若 rank(A)rank(B)则方程组 无解.例4.2求解方程组解：>> A=1 -5 2 -3;-3 1 -4 2;-1 -9 0 -4;5 3 6 -4;>> b=11;-5;-1;1;>> B=A,b;>> n=4;>> RA=rank(A)RA = 3>> RB=rank(B)RB = 4RA<RB 无解（3）当rank(A) = rank(B) = r < n 时线性方程组 A = b 有无穷多解

18、.例4.3求齐次方程组的解解：>> clear>> A=1 2 4 -3;3 5 6 -4;4 5 -2 3;3 8 24 -19;>> frmat rat>> n=4;>> RA=rank(A)RA = 2 >> if(RA=n)elseA=null(A,'r')endA= 8 -7 -6 5 1 0 0 1 >> syms k>> =kA = 8k, -7k -6k, 5k k, 0 0, k可见，MATLAB语言实现线性方程组的求解具有程序简单、直观的特点，同时还具有计算效率高的优点，在实际计算巾摆脱了系数矩阵阶数未知元数等的限制。3、 总结本文首先介绍了线性方程组求解的起源问题，然后主要介绍了线性方程组的几种解法。消元法，克莱姆法则和迭代法求解线性方程组。高斯消去法的计算量非常大，我认为我们不仅要学会做题目时会用方法解题，也需要具备在电脑