线性方程组的直接解法及matlab的实现.doc

《线性方程组的直接解法及matlab的实现.doc》由会员分享，可在线阅读，更多相关《线性方程组的直接解法及matlab的实现.doc（20页珍藏版）》请在三一办公上搜索。

1、本科毕业论文（ 2010 届）题 目线性方程组的直接解法及matlab的实现学 院 数学与信息工程学院 专 业 数学与应用数学 班 级 2006级数学1 班 学 号 0604010127 学生姓名 胡婷婷 指导教师 王洁 完成日期 2010年5月 摘 要 随着科技技术的发展及人类对自然界的不断探索模拟.在自然科学和工程问题中的很多问题的解决常常归结为线性代数问题！本文的主要内容是对线性方程组求解方法的探讨,主要介绍了四种求解线性方程组的方法,第一种是教科书上常见的消元法,我们称之为基本法.第二种方法是标准上三角形求解法,即将增广矩阵经过初等变换后化成标准上三角形,然后求解.它改进了一般教科书上

2、的常见方法,与常见方法比较有如下优点:1)规范了自由未知量的选取;2)只用矩阵运算;3)减少了计算量.第三种方法是对特定的方程组（系数矩阵A为n阶对称正定矩阵,且A的顺序主子式均不为零.）的求解方法进行描述,并且为这种线性方程的求解提供了固定的公式化的方法.第四种方法是对现在实际问题中常常会遇到的系数矩阵为三对角矩阵的方程组的求解方法.同时给出这几种方法的数值解法（matlab程序）,由于运用电脑软件求解,所以必须考虑计算方法的时间、空间上的效率以及算法的数值稳定性问题,所以针对不同类型的线性方程组有不同的解法.但是,基本的方法可以归结为两大类,即直接法和迭代法.关键词高斯消去法;三角分解法;

3、乔莱斯基分解法;追赶法AbstractSystems of linear equations are associated with many problems in engineering and scinence ,as well as with applications of mathematics to the social sciences and the quantitative study of business and economic problems.The main content of this article is the method for solving lin

4、ear equations, we introduce four methods for solving linear equations in this paper. The first is the elimination method which is commonly found in textbooks, and we call the Basic Law. The second method is Standard on the triangle Solution, that first change Augmented matrix into standards in prima

5、ry triangle, and then solving. It improves the general textbook on common methods, compared with the common method has the following advantages:1) Specification of the free choice of unknowns; 2)Only matrix operations;3) Reduce the computation. The third method describes a way to solve a Specific eq

6、uations(N coefficient matrix A is symmetric positive definite matrix, and A are not zero-order principal minor), And for this linear equation provides a fixed formulaic approach. The fourth method is to present practical problems often encountered in the coefficient matrix is tridiagonal matrix meth

7、od for solving the equations. These methods are given numerical solution of (matlab program), As the use of computer software to solve, it is necessary to consider ways of computing time and space efficiency and numerical stability of algorithms, Therefore, different types of linear equations have a

8、 different solution. However, the basic method can be classified into two categories, namely direct methods and iterative methods.Key wordsGaussian elimination; Triangular decomposition; Cholesky decomposition method; Thomas algorithm 目 录1. 引言 12相关知识 2 2.1 向量和矩阵 2 2.2 特殊矩阵 33.问题叙述 34问题分析 44.1高斯分解法44

9、.2三角分解法64.3乔莱斯基分解法64.4追赶法75. 举例说明与总结9 5.1举例说明 95.1.1高斯分解的matlab程序方法 95.1.2三角分解法的matlab程序方法 105.1.3乔莱斯基分解法的matlab程序方法115.1.4追赶法的matlab程序方法13 5.2总结 14参考文献16谢辞17线性方程组的直接解法及matlab的实现Direct solution of linear equations and matlab implementation数学与信息工程学院 数学与应用数学专业胡婷婷 指导教师:王洁1.引言随着科技技术的发展及人类对自然界的不断探索模拟.在自然

10、科学和工程问题中的很多问题的解决常常归结为线性代数问题！例如电学中的网络问题,用最小二乘法求实验数据拟合问题（如大地测量数据处理）,解非线性方程组问题,用差分法或有限元法解常微分方程、偏微分方程边值问题等最终都归结于解线性代数方程组.从实际数据来看,这些方程组的系数矩阵大致分为两种,一种是低阶稠密矩阵（阶数不超过150）.另一种是大型稀疏矩阵（矩阵阶数高且零元素较多）.所以,现在我们需要对求线性方程组的方法进行探究,以便能够找到一些简便的方法来加以应用！本文主要就线性方程组的直接解法予以讨论.线性方程组是线性代数的主要内容,包括线性方程组有解性的判定、消元法解线性方程组和线性方程组解的结构.

11、它与矩阵、向量的内容密切相关,与矩阵、向量组相关的许多重要结论都是线性方程组有关结论的应用和推广. 如:一个向量是否可以由一个向量组线性表示、表示形式是否唯一往往与非齐次线性方程组是否有解、有唯一解还是无穷多解是等价的;一个向量组是否线性相关与齐次线性方程组 是否有非零解是等价的等等.而且随着现代工业的发展,线性方程组的应用出现在各个领域,伴随着大量方程和多未知数的出现, 例如电学中的网络问题,用最小二乘法求实验数据拟合问题（如大地测量数据处理）,解非线性方程组问题,用差分法或有限元法解常微分方程、偏微分方程边值问题等最终都归结于解线性代数方程组。所以寻找简便而且准确的求解方法就显得十分重要而

12、且具有现实意义.因此对线性方程组解法的研究就显得十分必要.从实际数据来看,这些方程组的系数矩阵大致分为两种,一种是低阶稠密矩阵（阶数不超过150）.另一种是大型稀疏矩阵（矩阵阶数高且零元素较多）.本论文的主要内容是对线性方程组求解方法的探讨,主要介绍了四种求解线性方程组的方法,第一种是教科书上常见的消元法,我们称之为基本法.第二种方法是标准上三角形求解法,即将增广矩阵经过初等变换后化成标准上三角形,然后求解.它改进了一般教科书上的常见方法,与常见方法比较有如下优点:1)规范了自由未知量的选取;2)只用矩阵运算;3)减少了计算量.第三种方法是对特定的方程组（系数矩阵A为n阶对称正定矩阵,且A的顺

13、序主子式均不为零.）的求解方法进行描述,并且为这种线性方程的求解提供了固定的公式化的方法.第四种方法是对现在实际问题中常常会遇到的系数矩阵为三对角矩阵的方程组的求解方法.同时给出这几种方法的数值解法（matlab程序）,由于运用电脑软件求解,所以必须考虑方法的计算时间和空间效率以及算法的数值稳定性问题,所以针对不同类型的线性方程组有不同的解法.但是,基本的方法可以归结为两大类,即直接法和迭代法.本文主要介绍的直接法,包括Gauss消去法和它的变形直接三角形法.以及特定方程组的解法乔莱斯基分解法、追赶法.和这几种方法运用计算机求解线性方程组的数值计算方法.2相关知识2.1 向量和矩阵 用表示全部

14、实矩阵的向量空间,表示全部复矩阵的向量空间.（称为m行n列矩阵）.（称为n维列向量） ,其中 为A的第列.同理 ,其中 为A的第行. 矩阵基本运算: (1)矩阵加法 . (2)矩阵与标量的乘法 . (3)矩阵与矩阵的乘法 . （4）单位矩阵 ,其中2.2 特殊矩阵设,则有A为:(1)对角矩阵 如果当时,;(2)三对角矩阵 如果当;(3)上三角矩阵 如果当;(4)对称矩阵 如果;(5)正定矩阵 如果设A是n阶实系数对称矩阵, 如果对任何非零向量 都有,就称A正定.3问题叙述 比较下列用直接法解线性代数方程组的方法.设有线性代数方程组 或写成矩阵形式 ,简记为 .分别用高斯消元法,三角分解法,乔莱

15、斯基分解法,追赶法来对方程进行求解. 4问题分析 该方程组（例）的矩阵系数A为非奇异矩阵.因此我们可以通过,高斯消元法,三角分解法,乔来斯基分解法,追赶法来进行求解.下面我就对该问题非别使用这几种方法来解决问题.4.1.高斯消元法 对方程组 （1）首先检查的系数,如果的系数全为零,那么方程组（1）对的系数没有任何限制,就可以任意取,而方程组（1）可看作的方程组来解。如果的系数不全为零,那么利用矩阵的初等变换,分别把第一个方程的倍加到第个方程（=2,m）.于是方程(1)就变成 (2)其中 对(2)再按照上面的考虑进行变换,并且这样一步步做下去,最后就得到一个阶梯形方程组,不妨设所得的方程组为 (

16、3)其中方程组(3)中的“0=0”这样的恒等式可能不出现,也可能出现,这样去掉它们也不影响(3)的解,而且（1）与（3）是同解的.如(3)中有方程,而。这时不管取什么值都不能使它成为等式.故(3)无解,因而(1)无解.当是零或(3)中根本没有“0=0”的方程时,分两种情况:1）r=n.这时阶梯性方程组为 (4)其中.由最后一个方程开始,的值就可以逐个地唯一地决定了.在这个情形,方程组(4),也就是方程组(1)有唯一的解.2) rn .这时阶梯形方程组为 其中.把它改写成 (5) 由此可见,任给一组值,就唯一地定出的值,也就是定出方程组(5)的一个解.一般地,由(5)我们可以把通过表示出来,这样

17、一组表达式称为方程组(1)的一般解,而称为一组自由未知量. 3) 应该容易得到,情形是不可能出现的.4.2.三角分解法（分解） 回顾高斯消元法的实质,是经过一系列的初等变换,将方阵A分解为下三角矩阵L与上三角矩阵U的乘积 A=LU,这里 , , .对系数矩阵一旦实现了这种三角分解(称为LU分解),那么此方程组就可写为等价形式于是,容易先解出y,再求出x.4.3.乔莱斯基分解法 若A为n阶对称正定矩阵,切A得顺序主子式均不为零.则A可以唯一分解为 其中L为单位下三角矩阵,D为对角矩阵. ,于是 则此时系数矩阵A可写成 其中 为下三角矩阵,即: ,其中由矩阵乘法及得,于是得到解对称正定方程组的计算

18、公式:对于有求解,即求解两个三角形方程组:(1)Ly=b,求y; (2)4.4.追赶法设三对角矩阵:.考虑,其中.且有: 将三角矩阵A分解为(),其中比较式两端的元素可得:于是有求解方程组可转变为先求解,再求解,其中.比较和的元素可得 由此可得解三对角方程组的算法如下:5. 举例说明与总结5.1举例说明5.1.1高斯分解法的matlab程序方法高斯消去法求解方程组.根据高斯消去法,编制matlab程序如下首先建立一个M-file文件,保存在work中,文件名为magauss.mfunction x=magauss(A,b,flag)%用途:Gauss消去法解线性方程组Ax=b%格式:x=gua

19、ss(A,b,flag),A为系数矩阵,b为右端项,若flag=0,则不显示中间过程,%否则显示中间过程,默认为0,x为解向量if nargin A=1 1 1 1;1 2 2 2;1 2 3 3;1 2 3 4;b=4 3 2 1; x=magauss(A,b);x得计算结果x = 5 0 0 -15.1.2三角分解法的matlab程序方法三角分解法解方程组.三角分解法的Matlab程序function x,l,u=maLU(A,b)%用途:用LU分解法解方程组Ax=b%格式: x,l,u=maLU(A,b) A为系数矩阵,b为右端向量,返回解向量,l返回下三角矩阵,u返回上三角矩阵%LU分

20、解n=length(b);u=zeros(n,n)l=eye(n,n);u(1,:)=A(1,:);l(2:n,1)=A(2:n,1)/u(1,1);for k=2:n u(k,k:n)=A(k,k:n)-l(k,1:k-1)*u(1:k-1,k:n); l(k+1:n,k)=(A(k+1:n,k)-l(k+1:n,1:k-1)*u(1:k-1,k)/u(k,k);end%解下三角方程组Ly=by=zeros(n,1);y(1)=b(1);for k=2:n y(k)=b(k)-l(k,1:k-1)*y(1:k-1);end%解上三角方程组Ux=yx=zeros(n,1);x(n)=y(n)/

21、u(n,n);for k=n-1:-1:1 x(k)=(y(k)-u(k,k+1:n)*x(k+1:n)/u(k,k);end在工作窗口输入 A=2 -1 4 -3 1;-1 1 2 1 3;4 2 3 3 -1;-3 1 3 2 4;1 3 -1 4 4; b=11 14 4 16 18; x,L,U=maLU(A,b);x得计算结果x = 1.0000 2.0000 1.0000 -1.0000 4.00005.1.3乔莱斯基分解法的matlab程序方法5.1.2中的方程组的系数矩阵是对称正定的,所以可以运用乔莱斯基分解法来求解.乔莱斯基分解法Matlab程序function x,l,d=

22、machol(A,b)%用途:用cholesky分解法解方程组Ax=b%LDL分解n=length(b);d=zeros(1,n);l=eye(n,n);d(1)=A(1,1);l(2:n,1)=A(2:n,1)/d(1);d(2)=A(2,2)-l(2,1)*l(2,1)*d(1);for i=3:n for j=2:(i-1) s=0; for k=1:(j-1) s=s+d(k)*l(i,k)*l(j,k);end l(i,j)=(A(i,j)-s)/d(j); end s=0; for j=1:(i-1) s=s+d(j)*l(i,j)*l(i,j)end d(i)=A(i,i)-se

23、nd%求解下三角方程组Ly=b(向前消去法)y=zeros(n,1);y(1)=b(1);for i=2:n y(i)=b(i)-l(i,1:i-1)*y(1:i-1);end%求解上三角方程组Dz=yfor i=1:n z(i)=y(i)/d(i);end%求解上三角方程组Lx=z(回代法)ll=l;x=zeros(n,1);x(n)=z(n);for i=(n-1):-1:1 x(i)=z(i)-ll(i,i+1:n)*x(i+1:n);endx=x;在工作窗口输入 A=2 -1 4 -3 1;-1 1 2 1 3;4 2 3 3 -1;-3 1 3 2 4;1 3 -1 4 4; b=1

24、1 14 4 16 18; x,l,d=machol(A,b)得计算结果x = 1.0000 2.0000 1.0000 -1.0000 4.00005.1.4追赶法的matlab程序方法解方程组,记,.追赶法的Mtlab程序function x=machase(a,b,c,f)%用途:追赶法解三对角方程组Ax=f%格式:x=machase(a,b,c,f) a为次下对角线元素向量,b为主对角线元素向量,%c为次上对角线元素向量,f为右端向量,为返回向量%追赶法n=length(a);for k=2:n b(k)=b(k)-a(k)/b(k-1)*c(k-1); f(k)=f(k)-a(k)/

25、b(k)*f(k-1);endx(n)=f(n)/b(n);for k=n-1:-1:1 x(k)=(f(k)-c(k)*x(k+1)/b(k)end在工作窗口输入 a=-1*ones(5,1);b=2*ones(5,1);c=-1*ones(5,1);f=1 0 0 0 0; x=machase(a,b,c,f)输出结果x = 0 0 0 0.5422 0.2778x = 0 0 0.7817 0.5422 0.2778x = 0 0.9656 0.7817 0.5422 0.2778x = 0.9828 0.9656 0.7817 0.5422 0.2778x = 0.9828 0.965

26、6 0.7817 0.5422 0.27785.2.总结通过对实际方程组的求解,我们可以很容易的用Gauss消元法及LU分解法的matlab程序求解!由于该方程组的系数矩阵不是正定的,所以不能用乔莱斯基分解法求解!通过观察,很容易正定这个方程组的系数矩阵是是呈现带状分布的,而且0元素很多,这种形式的系数矩阵在科学与工程计算中会经常遇到.但在实际问题中的矩阵都非常的庞大,我们知道用gauss消去法和LU分解法求n阶的方程组都需要大约个乘除法,若我们假定n=,则需作次乘除法,用一台每秒作次乘除法的计算机求解,约费时一个小时,但是这样的时间也是不够快的.若是用乔莱斯基分解法,则计算量约为,大约为前两

27、种方法计算量的一半.但乔莱斯基分解法只能用于系数矩阵是对称正定的方程组!但对于系数矩阵为三对角的方程组来说,可以运用更简单的方法来求解,即追赶法,因为追赶法计算时忽略了除三对角线的元素外的其他零元素,从而使运算的时间大大缩短,运算效率也有显著的提高!所以在求解方程组时,我可以根据方程组系数矩阵的特点选用最有效的方法来进行求解.参考文献1 马昌凤,林伟川.现代数值计算方法MATLAB版 M北京:科学出版社,2008:79-88. 2 张凯院,徐仲.数值代数 2版M北京:科学出版社,2006.33-54.3 李庆扬,王能超,易大义.数值分析 4版M.北京:清华大学出版社,2008:161-193.

28、 4 陈传淼.科学计算概论M 北京:科学出版社,2007:1-15 .5 北京大学数学系几何与代数教研室前代数小组.高等代数-3版M北京高等教育出版社,2003.9:61-83,105-111,226-231.6 卢学飞,徐仲.求三对角方程组的新算法J.西安:数学的实践与认识,2007 ,37(3):112-118. 7 宫野,王友年等.块三对角矩阵方程的追赶法及其应用J大连理工大学学报,1997,17（4）:406-409.8 马昌凤,林伟川.现代数值计算方法:matlab版M.北京:科学出版社,2008:35-57,205-216.9 同济大学数学教研室编.线性代数M.北京:高等教育出版社

29、,2000.10 日有马哲,浅枝阳著,胡师度,周世武译.线性代数讲解M.成都:四川人民出版社,1985.11 杨士俊. 线性方程组的解法J.杭州师范学院学报(社会科学版),1994,(3):99-105.12 姜建飞,胡良剑,唐俭.数值分析及其matlab实验M.北京:科学出版社,2004.13 蔡大用,白峰杉.高等数值分析M.北京:清华大学出版社,1997.14 弓爱芳,郭明月. 线性方程组各种解法的讨论与思考J.高等函授学报(自然科学版),2005,(5):41-44.15 关治,陆金甫.数值分析基础M.北京:高等教育出版社,1998.16 徐成贤,徐宗本.矩阵分析M.西安:西北工业大学出

30、版社,199117 陈芳,陆全.求解分块三对角线性方程组的一种新算法J.工程数学学报,2004,21(8):35-40.18 David Kincaid and Ward Cheney.Numerical Mathematics and Computing.Brooks/Cole Publishing Co., Pacific Grove,CA,fourth edition,1999. ISBN.0-534-35184-0.19 James F. Epperson. An Introduction to Numerical Methods and Analysis. Wiley, 2001.

31、ISBN. 0-471-31647-4.20 Christian Rakotonirina Institut Superieur de Technologie dAntananarivo, ON THE CHOLESKY METHODIST-T, BP 8122, MadagascarJune 9, 200921 http:/scicomp.ucsd.edu/spav/pub/numas.pdf谢辞这篇论文得以完成,除了自己的一些努力外,还要谢谢我的论文指导老王洁讲师,如果不是她在关键的时候给予我帮助指导,我想这篇论文也不会这么容易的完成. 她严谨细致、一丝不苟的作风一直是我工作、学习中的榜样

32、; 她循循善诱的教导和灵动特别的思路给了我灵动的启迪. 在她的关心与督促下,我了解了论文何为论,如何论,也让我们了解了论文写作的要点在哪里!在她的指导与鼓励下,我认真的完成了论文写作的准备工作!在她的督促下,我终于完成了这篇论文.在她的信心检查与教导下,我最终完成了对论文细节的修订.所以,在这里,我要诚挚的谢谢我的指导老师!在这里,我还要感谢这四年里教导我们的老师.是你们让我学到了新的知识,是你们让我发现数学字符的美妙,是你们让我对自己及所学专业有了深刻的认识!感谢我的室友们,当我只身从千里之外来到这个陌生的城市,是你们让我感受到了这个环境中的温馨.谢谢你们和我共同维系着彼此之间真挚的友情，维系着寝室那份家的融洽.四年了,仿佛就在昨天.四年里,我们没有红过脸,没有吵过嘴,没有发生上大学前所担心的任何不开心的事情.最后,我还要感谢一下这个社会的科技.科技让我能较轻松的找到自己想要的文献资料,科技让我能够跟很多人交流心得,这都为我论文的写作奠定了基石.