原始高斯消元法的改进以及在工程上的应用

山东财经大学学士学位论文山东财经大学本科毕业论文题目：原始高斯消元法的改进以及在污水处理上的简单应用学院数学与数量经济学院专业数学与应用数学班级2008级1班姓名王帅学号20080544120指导老师郭洪峰日期2012年4月山东财经大学教务处制二Ｏ年月山东财经大学学士学位论文山东财经大学学士学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明确的说明并表示了谢意。本声明的法律结果由本人承担。学位论文作者签名：年月日山东财经大学关于论文使用授权的说明本人完全了解山东财经大学有关保留、使用学士学位论文的规定，即：学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布论文的全部或部分内容，可以采用影印或其他复制手段保存论文。指导教师签名：论文作者签名：年月日年月日山东财经大学学士学位论文摘要传统的高斯消元法只能处理多元一次方程组满秩的情况,从而限制了它的应用范围。而近年来人工智能的发展,为改进高斯消元法提供了新的思路,改进后的算法编程简单,能处理所有的多元一次方程组。本文分析了线性方程组解的误差起源,在gauss消元过程中避开除法,消除了由于消元过程中系数相除所产生的舍入误差,用改进的gauss消去法求解线性方程组,大大提高了线性方程组解的精确值。高斯消去法对数据没有任何要求，弥补了迭代法的一些不足。而且在消元过程中避免了误差的产生,只要在回代中的除法能除尽,就能得到精确解。本算法在工业污水处理预测中能起到非常好的作用，文章用该方法研究某地区工业污水各成份对环境的影响程度。关键词：应用数学；高斯消去法；多元线性回归；改进算法；污水处理,山东财经大学学士学位论文APPLICATIONOFTHEIMPROVEDGAUSSELIMINATIONMETHODTOSEWAGETREATMENTMODELABSTRACTthispaperresearchedtheerrororiginofsolvingthesystemoflinearequations,avoidingtheerrorduringthedivisionofcoefficientsbetweeneachotherwithoutusingthedivision,improvinggausseliminationmethod,raisinggreatlytheaccuratevalueofsolutionsofasystemoflinearequations.thereisnoanyrequirementforgausseliminationoperationthatnotonlyremediestheiterationbutalsopreventstheerrorfromtheelimination.solongasitcanbedividedexactlyforbacksubstitutiontheaccuratesolutioncanbeobtained.themethodiseffectiveforsewagetreatmentprediction.thispaperusesthemethodtodealwithinfluenceofsewagetreatmentinsomearea.Keywords：gausseliminationmethod;multipleregression;theimprovedalgorithm;sewagetreatment山东财经大学学士学位论文一、引言在科学和工程计算中,线性方程组数值解的非常重要。所有的算法都有误差问题。在求解线性方程组的过程中,系数相除所产生的舍入误差累积带入了未知量的直接求解式,导致了线性方程组解的误差。如果在求解过程中不使用或尽可能少使用除法,或对于除法采取分数代入(因为计算机的字长总是有限的),误差就可以完全消除或达到误差最小。本文引进了一种改进后的高斯消元法，此方法在不考虑计算量的情况下,将求最大公因式中的辗转相除法融入到Gauss消去法中,在归一消元化为等价同解的上三角形方程组的过程中,将系数相除取整,避开了除法运算所产生的舍入误差,消除了消元过程中除法造成的误差累积,大大提高了线性方程组解的精确值。在应用多元线性回归模型进行预测时,回归系数的确定对结果来说是最为重要的。本文将基于线性回归模型,采用改进的Gauss消去法来帮助研究河流受工业污水污染情况。二、高斯消元法的改进1.1传统的高斯消元法首先介绍一下高斯消元法。1111221121122222nnnnaxaxaxbaxaxaxbmn对于的多元一次方程组1122mmmnnmaxaxaxbmnmnmmnnnbxaxaxabxaxaxabxaxaxa2211222221211112212111mnmmnnaaaaaaaaaA211222111211Tnxxxx),,,(21Tmbbbb),,,(21则给定线性方程组的矩阵形式为Ax=b山东财经大学学士学位论文nmnmmnnbaaabaaabaaaC.21222221111211A称为方程组的系数矩阵，C称为方程组的增广矩阵。以r(A)和r(C)分别表示系数矩阵A与增广矩阵C的秩,则有(1)当m=n且r(A)=r(C)=n时(即方程组满秩时),方程组有唯一解。(2)当r(A)r(C)时,方程组无解,这时的方程组称为矛盾方程组。(3)当r(A)=r(C)=rn时,方程组有无穷多组解。传统的高斯消元法只能用于处理第一种情况,它的核心是消下三角矩阵法和消上三角矩阵法。经过消元后,增广矩阵变为''222'111000000nnnbababa''2222'1111nnnnbxabxabxannnnabxabxabx///'22'2211'11对于第二、第三种情况,高斯消元法则无法处理。在第二种情况下,方程组存在矛盾,但并不是每个方程之间都存在矛盾,某些变量还可能只存在唯一解;同样,在第三种情况下,方程组有无穷多组解,并不等于每个变量都有无穷多组解,某些变量可能只存在唯一解。而要找出在第二、第三种情况下的变量的唯一解,则必须对高斯消元法进行改进。而第二种情况下,方程组中必然存在一个变量同时取两个以上的值,即必须在超协调的情况下进行处理;在第三种情况下,方程组中必然存在一个变量无唯一解(即有无穷解),即必须在非单调的情况下进行处理。以下我简单介绍一下超协调和非单调的概念。这两个概念最初是在人工智能中针对经典逻辑的单调性和协调性的概念提出的,在经典逻辑中知识是完备和不矛盾的,这时对知识的处理具有单调性和协调性,而现实生活中的知识是不完备的,并且可能存在矛盾。于是人们把知识不完备时对知识的处理称为非单调性,而把知识存在矛盾时对知识的处理称为超协调性。随着人工智能对非单调知识和超协调知识处理的发展,逐步形成了不同于经典逻辑的新的逻辑体系——非单调逻辑和超协调逻辑。非单调逻辑是经典逻辑的强化,因为在非单调逻辑中,一些原来在经典逻辑中推不出来的结论,现在可以在非单调逻辑中推出。而在经典逻辑中能推出的结论,在非单调逻辑中照样可以推出。超协调逻辑是经典逻辑的弱化,因为在超协调逻辑中,一些原来在经典逻辑中能推出的结论,现在在超协调逻辑中不能推出。而在经典逻辑中不能推出的结论,在非单调逻辑中照样不能推出。非单调性的解决方法是:对不完全知识的扩充。常用的非单调方法有限制、缺省理论、自知逻辑等。超协调性的解决方法是:维护协调性。常用的超协调方法有分域逻辑DL、超协调系统Cn和悖论逻辑LP等。当应用这些概念到多元一次方程组的求解中时,我们同样发现当满秩时方程组是完备和不矛盾的,即在第一种情况下,方程组同样具有单调性和协调性;而在第二种情况下,方程组存在矛盾,这时如果对方程组进行处理,我们同样定义为超协调性;在第三种情况下,方程组有无穷多组解,这时的方程组是不完备的,这时如果对方程组进行处理,我们同样定义为非单调性。对于单个变量,我们定义有且只有唯一解的变量山东财经大学学士学位论文是单调和协调的;若它同时取两个以上的解,则我们称该变量是超协调的,若它无唯一解(既有无穷解),则称该变量是非单调的。这样我们发现对高斯消元法的改进,也就是使只能处理单调、协调的方程组的高斯消元法能够同样处理超协调和非单调的情形。方程组的非单调性说明方程不足,方程组的超协调性说明方程之间冲突。这与逻辑推理中知识不完全和知识矛盾是类似的,应用非单调逻辑和超协调逻辑的思想,我们可得到如下改进的高斯消元法。1.2改进后的高斯消元法改进后的高斯消元法的算法分为如下四个步骤:(1)用改进后的消下三角矩阵法进行处理。对消下三角矩阵法的改进在于设置i=1,j=1,若第j列中aij以下部分(含aij)有非零值时,将非零值放到aij,消去该列其它值(向下),然后i加1,j加1,对下一列进行处理;当一列中aij以下部分(含aij)无非零值时,j加1,而i不变,对下一列进行处理。当im或jn时中止。nnnnnbaaabaabaA002122221111经过初等变换得'''2'22'1'11'00000nnnbababaA(2)用改进后的消上三角矩阵法进行处理。对消上三角矩阵法的改进在于设置i=m,j=n,在第j列从aij往上找,直至找到一个非零值或者找遍该列aij以上部分(含aij)都为零值。若找到的非零值为aij,则将非零值放到aij,消去该列其它值(向上),然后i减1,j减1,对下一列进行处理;若该列aij以上部分(含aij)都为零值时,j减1,而i不变,对下一列进行处理。当i=0或j=0时中止。nnnnnbabaabaaaB0002222111211同上可得'''2'22'1'11'000000nnnbababaB(3)分析新方程。可以看出经过消元后的系数矩阵在左下方和右上方有一片零值区。消元后的新的方程组中的方程分山东财经大学学士学位论文为4种情况:●系数矩阵对应的一行中只有一项非零,则该项对应的变量有唯一解;●系数矩阵对应的一行中不只一项非零,则非零项对应的变量有无穷解,该变量具有非单调性;●系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行不为零,则方程组中存在超协调的情况,即某个变量同时取两个值;●系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行也为零,说明方程组中有冗余情况。对第一种情况,求解与传统的高斯消元法相同,然后删去该行。对第四种情况,删去该行即可。重要的是对第二种、第三种情况的处理。不同的处理体现了不同的非单调、超协调策略。首先对第三种情况进行处理。对超协调性的解决方法是维护协调性。最简单的处理方法是删去该行,则方程组中消除了超协调的情况。则相当于当变量同时取两个值时,任意删除其中的一个赋值。(4)处理无穷解的情况。处理完第一、第三、第四种情况后,则新的方程组中就只剩下第二种情况。对非单调的解决方法是扩充不完全的知识。给出一批缺省规则(一般是对每个变量给一个缺省值)和相应的优先级,对于有无穷解的变量组,选择与该变量组中变量相关的优先级最高的缺省规则(优先级相同时可按变量顺序选择或随机选择),加入方程组中。若无穷解的变量组为空,则所有变量都已有唯一解,算法结束。否则转到步骤1继续处理。由上述算法可知,当所有变量都有唯一解时,运算与高斯消元法一样。只是在非单调、超协调的情况下,采取了相应的处理策略。具体来说,在新方程中对第二种情形的处理即是对