线性方程组的数值解法与比较论文.doc

《线性方程组的数值解法与比较论文.doc》由会员分享，可在线阅读，更多相关《线性方程组的数值解法与比较论文.doc（20页珍藏版）》请在三一办公上搜索。

1、目 录1 引言12 线性方程组的相关概念13 讨论线性方程组的数值解法23.1 高斯消元法解线性方程组23.1.1 高斯顺序消元法23.1.2 高斯列主元素消元法63.2 矩阵三角分解法解线性方程组93.2.1 直接三角分解法93.2.2 追赶法124 总结16参考文献17致谢18线性方程组的数值解法与比较摘要:本文给出了线性方程组数值解法的几种直接求解方法,探讨这些方法的主要思想,具体解法以及它们各自的特点,针对几种解法对于不同条件下的线性方程组的求解,进行了一定的分析,并对其加以比较,以此来促进对线性方程组数值解法的理解.关键词:线性方程组;高斯消元法;直接三角分法;追赶法 The num

2、erical solution and compared of linear equationsAbstract: This paper gives several direct solving methods of linear equations nume- rically, probing into the main ideas, the specific method and their respective conclu- sions.According to several solutions to different conditions of linear equations

3、of the solution, this paper analyzes and compares in order to promote the understanding of linear equations numerically.Key word: linear equations; Gaussian elimination; direct triangle points method; Chase-after method 1 引言线性方程组是最简单也是最重要的一类代数方程组.在实际生活中,存在大量的解线性方程组的问题,很多数值方法到最后都会涉及到线性方程组的求解问题.它的数值解法

4、不仅在实际问题中起到重要的作用,而且在计算数学中更是占有重要的地位.针对我们所学习的现有的中小型线性方程组,直接法就可以直接简明的对其进行求解.我们所运用的求解线性方程组的直接法,通常包括高斯消元法中的高斯顺序消元法与高斯列主消元法,以及矩阵三角分解法中的直接三角分解法与追赶法.本文通过探讨这几种求解方法的思想,解法与结论,对其加以分析并进行了相应的比较. 2 线性方程组的相关概念一 线性方程组的一般形式含个方程,个未知量的线性方程组的一般形式为: 其中为未知量, 和为常数; 称为型线性方程组如果,则称方程组为齐次线性方程组如果存在,则称方程组为非齐次线性方程组例:型线性方程组的一般形式为:

5、其中每一个方程都表示平面上一条直线,一个型线性方程组中两直线在平面上的位置有下列三种情况:(1)两直线相交于一点,则交点就是方程组的唯一解； (2)平行,则该方程组无解；(3)重合,则直线上任何一个点都是方程组的解. 例:型齐次线性方程组的一般形式为: 其中每一个方程都表示一个以向量为法向量,过点的平面,其解是一个与平行.,均正交的向量.(1)若,不共面,则方程组只有零解；(2)若,共面但不共线,则垂直于 ,的向量均是解,这些解彼此平行；(3)若,共线,则以为法向量的平面是所有向量,都是解.即解向量组成一个平面. 定义1.1: 设有型线性方程组(I)和型线性方程组(II),如果(I)和(II)

6、的解向量集合相等,则称(I)和(II)为等价的线性方程组. 齐次线性方程组可以看成是非齐次线性方程组常数列均0的情形,因而对于非齐次线性方程适用的结论对齐次方程也是适用的. 3 讨论线性方程组的数值解法设有n元线性方程组 或 其中 设系行列式,则方程组有唯一解. 直接法解线性方程组:如果不计运算过程的舍入误差,经过有限次运算后可得到方程组的精确解的方法. 3.1 高斯消元法解线性方程组 3.1.1 高斯顺序消元法写出方程组的增广矩阵,并记, 若,则施行第一次消元:对计算 原增广矩阵被变换成: 将这一过程继续下去.第步的计算过程为若,则施行第一次消元: 对 计算 原增广矩阵被变换成 若所有的,则

7、经过n-1次消元得到: 以为增广矩阵的上三角线性方程组 与原方程组是同解方程组.回代过程就是由方程组的最后一个方程解出,然后通过逐步回代,依次求 . 具体算法为 例1 用顺序Gauss消去法解以下线性方程组 解:用增广矩阵表示法求解: 消元过程 回代过程 同解方程组为 程序为:#include #include #define N 4 /* N 为方程组系数矩阵的阶数 */int Gauss(float aNN,float bN) int i,j,k,flag=1; float t; for(i=0;iN-1;i+) if(aii=0) flag=0; break; else for(j=i+

8、1;jN;j+) /*消元过程开始*/ t=-aji/aii; bj=bj+t*bi; for(k=i;kN;k+) ajk=ajk+t*aik; return(flag); void zg_matric(float aNN,float bN) /* 输出增广矩阵 */ int i,j; for(i=0;iN;i+) for(j=0;j=0;i-) xi=bi; for(j=i+1;jN;j+) xi=xi-aij*xj; xi=xi/aii; for(i=0;iN;i+) /* 输出方程组的解 */ printf( x%d=%11.7fn,i+1,xi); ;运行结果截图为: 3.1.2 高

9、斯列主元素消元法引例 考虑用顺序Gauss消去法求解以下方程组,在运算中每次运算保留到小数点后四位. 消元后的同解方程组为 回代求解得 与准确解 相差很大.对此做改进所得结果为:对调过程 消元后的同解方程组为 回代求解得 与准确解 相差很大.由此,我们会发现对于这种用绝对值很小的数作除数,舍入的误差会增大,同时会严重影响计算结果的精度.因此,我们要选择绝对值最大的元素做主元素,可以避免消元时消元系数绝对值大于1(即避免放大舍入误差).也就是说,我们可以来用高斯列主消元法更精确的解此类线性方程组.高斯列主元消元法的主要过程如下: 1 消元过程 对 选主元 找, 使 若 , 则计算停止,若,则换行

10、 , 消元 对 计算 2 回代过程若, 则计算停止, ; 否则 对 例2 解方程组 四位有效数字精确解为 解:(1)顺序高斯消元法 四位有效数字精确解为 由上,高斯顺序消元法求解表明:所得结果会与我们的精确解相差较大,为避免这一误差,我们引进了高斯列主元消元法.(2)列主元素法 四位有效数字精确解为 由上,当增加选主元后,所得结果会与精确解相差较小,即运用高斯列主元消元法可以减小计算误差. 3.2 矩阵三角分解法解线性方程组高斯消元法实质上是对方程组进行等价变形,即是对系数矩阵施行初等变换,这些初等变换又可以用矩阵表示.矩阵的三角分解是高斯消元法的另一种表示方法,或者说是高斯消元法的变形.它在

11、解线性方程组的直接法中起着重要的作用. 3.2.1 直接三角分解法 如果方程组的系数矩阵能分解成 其中是下三角矩阵,是上三角矩阵,这时方程组就可化为两个容易求解的三角形方程组 先由解出向量,再由解出向量,这就是原方程组的解. 若是单位下三角阵,则称相应的分解为 Doolittle分解(也称为分解).定理 1 矩阵有唯一的Doolittle分解的充分必要条件是的前个顺序主子式.设矩阵非奇异,且的前个顺序主子式都不为零.则有Dool-ittle分解 由矩阵的乘法可知 当时有 对于Doolittle分解算法,我们知道:(1)对 (2)对 其中可以利用分解求解线性方程组的算法,则可以先求解,即 所以

12、再求解,即 回代求解 例3 利用Doolittle分解求解以下方程组 解: 所以 回代求解 由此可知,矩阵分解中的直接三角分解法是以分解为基础进行矩阵分解,以上则是运用Doolittle分解求解线性方程组的解题过程.3.2.2 追赶法 设元线性方程组的系数矩阵为非奇异矩阵的三对角矩阵 这种方程组称为三对角线性方程组.这类方程组具有许多明显的应用背景,在求微分方程数值解、三次样条函数等问题中, 都会遇到这样的线性方程组.设的前个顺序主子式都不为零,则有唯一的分解,并且的分解有如下形式 其中 三对角方程组的追赶法 1 向前追的过程 (1)(2) 对计算 2 往回赶的过程(2) 对,计算 例4 设4

13、阶方程组为 这就是一个三对角方程组,既系数矩阵除了对角线的三斜线以外的元素均为0.用追赶法求解三对角方程组的一种做法是把系数矩阵写成下列形式的分解(这里采用Doolittle分解): 即为单位上三角阵,两斜行,主对角线元素为1,其下方的斜行元素待定；为上三角阵,也是两斜行,主对角线元素待定,其上方斜行的元素与对应的斜行元素相同(直接验算可知道). 利用矩阵乘法规则按顺序依次考虑的,并对比两端可得 即得分解 于是用前推过程求解下三角方程组 得 再用回代过程求解上三角方程组 得 即的方程组的解 从实例看到,三对角方程组的追赶法是三角分解发的一种特殊应用,因此,一般地,如果对三角矩阵非奇异,其顺序主

14、子式,则解三对角方程组: 的追赶法可描述如下:令,则 利用矩阵乘法规则,可求和的计算公式: 于是,求解得 再求解,得三对方程组的解 上述3个公式便组成解三角方程组的追赶法.当然,这是在假定三角矩阵 非奇异,其顺序主子式的条件下才能实现的.从公式和看出,关键在于有. 4 总结线性方程组的各个数值解法之间有着一定的联系,同时也存在不同之处.矩阵直接三角分解法是高斯消元法的变形方法.高斯消元法有多种变形,有的是高斯消元法的改进,有的是用于某种特殊系数矩阵的化简.高斯消元法解线性方程组先消元,然后再带回.当用矩阵描述时,是对系数矩阵分解为一个上三角矩阵和一个下三角矩阵的乘积,即分解.因此,高斯消元法与

15、矩阵三角分解法中的分解是一致的.当然,针对线性方程组不同的形式与所具备的条件所选择的方法也是有区别的. 高斯消元法的基本思想是通过行变换,逐步消元,把方程组化为系数矩阵为三角形矩阵的等价的方程组,然后用回代法解此三角形方程组得原方程组的解.对于高斯顺序消元法,标记元素的绝对值很小时,若用它作除数,则根据数值运算中用绝对值很小的数作除数,舍入误差会增大,而且严重影响计算结果的精度的原则,表明这种方法在一定程度上是具有局限性的.因此,在高斯顺序消元法的基础上,我们引进了高斯列主元消元法.它是在高斯消元法的消去过程中第k步增加选主元操作,成为首先在第列中,从中选出绝对值最大的元素.经过行交换(把绝对

16、值最大者所在的行与第行交换)把绝对值最大的元素换到akk的单位中；然后做高斯顺序消去法的消去过程中第k步,初等变换产生第列的个零元素.对于非奇异矩阵的方阵,我们则利用直接三角分解法推导得到的公式(Doolittle分解公式或者Crout分解公式)进行求解.追赶法是针对带状矩阵(尤其是三对角矩阵)这一大稀疏矩阵的特殊结构,得出的一种保带性分解的公式推导,进行求解线性方程组.因此,针对不同类型的方程组应该选择合适的数值解法.参考文献:李书刚.线性代数.M.北京:科学出版社,2010,第91-109页.卢刚.线性代数.M.北京:高等教育出版社,2002,第80-86页.李庆扬.王能超.易大义.数值分析.M.4版.武汉:华中科技大学出版社,2006,第29-36页.居余马.线性代数.M.北京:清华大学出版社,2002,第43-51页.首都师范大学数学系组编.数值分析.M.北京:科学出版社,2005,第12-21页.朱金寿.线性代数.M.2版.北京:科学出版社,1998,第107-119页.谢寿才,陈渊.大学数学.M.北京:科学出版社,2010,第48-51页.谭浩强.C程序设计(第三版).M.北京:清华大学出版社,2005,第69-86页.刘萍.计算方法.M.北京:人民邮电出版社,2002,第71页.王能超.计算方法.M.北京:高等教育出版社,2006,第156-197页.致谢