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

山东财经大学学士学位论文 山东财经大学本科毕业论文题目：原始高斯消元法的改进以及在污水处理上的简单应用学 院 数学与数量经济学院 专 业 数学与应用数学 班 级 2008级 1班 姓 名 王 帅 学 号 20080544120 指导老师 郭洪峰 日 期 2012 年4月 山东财经大学教务处制二 年 月山东财经大学学士学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体，均已在论文中作了明确的说明并表示了谢意。本声明的法律结果由本人承担。学位论文作者签名： 年 月 日山东财经大学关于论文使用授权的说明本人完全了解山东财经大学有关保留、使用学士学位论文的规定，即：学校有权保留、送交论文的复印件，允许论文被查阅，学校可以公布论文的全部或部分内容，可以采用影印或其他复制手段保存论文。指导教师签名： 论文作者签名： 年 月 日 年 月 日摘 要传统的高斯消元法只能处理多元一次方程组满秩的情况,从而限制了它的应用范围。而近年来人工智能的发展,为改进高斯消元法提供了新的思路,改进后的算法编程简单,能处理所有的多元一次方程组。本文分析了线性方程组解的误差起源,在gauss消元过程中避开除法,消除了由于消元过程中系数相除所产生的舍入误差,用改进的gauss消去法求解线性方程组,大大提高了线性方程组解的精确值。高斯消去法对数据没有任何要求，弥补了迭代法的一些不足。而且在消元过程中避免了误差的产生,只要在回代中的除法能除尽,就能得到精确解。本算法在工业污水处理预测中能起到非常好的作用，文章用该方法研究某地区工业污水各成份对环境的影响程度。 关键词： 应用数学；高斯消去法；多元线性回归；改进算法；污水处理,APPLICATION OF THE IMPROVED GAUSSELIMINATION METHOD TO SEWAGE TREATMENTMODELABSTRACTthis paper researched the error origin of solving the system of linear equations,avoiding the error during the division of coefficients between each other without using the division, improving gauss elimination method, raising greatly the accurate value of solutions of a system of linear equations. there is no any requirement for gauss elimination operation that not only remedies the iteration but also prevents the error from the elimination. so long as it can be divided exactly for back substitution the accurate solution can be obtained. the method is effective for sewage treatment prediction. this paper uses the method to deal with influence of sewage treatment in some area. Keywords：gauss elimination method; multiple regression; the improved algorithm;sewage treatment一、 引言在科学和工程计算中,线性方程组数值解的非常重要。所有的算法都有误差问题。在求解线性方程组的过程中,系数相除所产生的舍入误差累积带入了未知量的直接求解式,导致了线性方程组解的误差。如果在求解过程中不使用或尽可能少使用除法,或对于除法采取分数代入(因为计算机的字长总是有限的),误差就可以完全消除或达到误差最小。本文引进了一种改进后的高斯消元法，此方法在不考虑计算量的情况下,将求最大公因式中的辗转相除法融入到Gauss 消去法中,在归一消元化为等价同解的上三角形方程组的过程中,将系数相除取整,避开了除法运算所产生的舍入误差,消除了消元过程中除法造成的误差累积,大大提高了线性方程组解的精确值。在应用多元线性回归模型进行预测时,回归系数的确定对结果来说是最为重要的。本文将基于线性回归模型,采用改进的Gauss 消去法来帮助研究河流受工业污水污染情况。二、 高斯消元法的改进 1. 1 传统的高斯消元法首先介绍一下高斯消元法。 则给定线性方程组的矩阵形式为Ax=bA 称为方程组的系数矩阵，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) =rm或jn时中止。 经过初等变换得(2)用改进后的消上三角矩阵法进行处理。对消上三角矩阵法的改进在于设置i=m, j=n,在第j列从aij往上找,直至找到一个非零值或者找遍该列aij以上部分(含aij)都为零值。若找到的非零值为aij,则将非零值放到aij,消去该列其它值(向上),然后i减1, j减1,对下一列进行处理;若该列aij以上部分(含aij)都为零值时, j减1,而i不变,对下一列进行处理。当i=0或j=0时中止。 同上可得(3)分析新方程。可以看出经过消元后的系数矩阵在左下方和右上方有一片零值区。消元后的新的方程组中的方程分为4种情况:系数矩阵对应的一行中只有一项非零,则该项对应的变量有唯一解;系数矩阵对应的一行中不只一项非零,则非零项对应的变量有无穷解,该变量具有非单调性;系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行不为零,则方程组中存在超协调的情况,即某个变量同时取两个值;系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行也为零,说明方程组中有冗余情况。对第一种情况,求解与传统的高斯消元法相同,然后删去该行。 对第四种情况,删去该行即可。重要的是对第二种、第三种情况的处理。不同的处理体现了不同的非单调、超协调策略。首先对第三种情况进行处理。对超协调性的解决方法是维护协调性。最简单的处理方法是删去该行,则方程组中消除了超协调的情况。则相当于当变量同时取两个值时,任意删除其中的一个赋值。(4)处理无穷解的情况。处理完第一、第三、第四种情况后,则新的方程组中就只剩下第二种情况。对非单调的解决方法是扩充不完全的知识。给出一批缺省规则(一般是对每个变量给一个缺省值)和相应的优先级,对于有无穷解的变量组,选择与该变量组中变量相关的优先级最高的缺省规则(优先级相同时可按变量顺序选择或随机选择),加入方程组中。若无穷解的变量组为空,则所有变量都已有唯一解,算法结束。否则转到步骤1继续处理。由上述算法可知,当所有变量都有唯一解时,运算与高斯消元法一样。只是在非单调、超协调的情况下,采取了相应的处理策略。具体来说,在新方程中对第二种情形的处理即是对非单调知识的处理,借用了非单调逻辑中缺省理论的方法。而对第三种情形的处理即是对超协调知识的处理,则是超协调逻辑中分域逻辑的一种简化。从理论上讲,改进的高斯消元法实质是建立在一种新的公理体系的基础上,因为它限制了方程的和差乘除仍为方程的公理的运用范围,从而达到能处理非单调、超协调的情形。传统的高斯消元法实质就是不断应用不同行相消产生新方程,最终产生只含一个变量的方程,而在非单调和超协调的情况下(即满秩情形),或者会出现无论如何变换最终仍含多个变量的方程,这时必须停止不同行相消,利用缺省规则加入新的方程后再继续;或者会出现矛盾方程(即方程左端无变量而右端不为零的方程),这时必须禁止矛盾方程与其它行相消。以上所述即是要限制公理的使用范围,这种思想是从非单调、超协调逻辑中借用来的。而在单调、协调的情况下,它与传统的高斯消元法完全一致。定理1:该算法在满秩时等价于传统的高斯消元法。证明:在满秩时, m=n。对于改进后的消下三角矩阵法, i、j均从0出发,由于矩阵中不会出现一列中无非零值的情形(否则矩阵不满秩),则每列操作i、j均加1,当处理完n列时, i=m=n, j=n,消下三角矩阵法中止。故与改进前的消下三角矩阵法完全相同。对于改进后的消上三角矩阵法,由于m=n , i、j均视为从m出发,由于矩阵中不会出现一列中无非零值的情形(否则矩阵不满秩),则每列操作i、j均减1,当处理完n列时, i=0, j=0,消上三角矩阵法中止。故与改进前的消上三角矩阵法完全相同。分析新方程时,只存在第一种情形,处理也同传统的高斯消元法相同。不存在处理无穷解的情况。即： 综上所述,该算法在满秩时等价于传统的高斯消元法。定理2:该算法在非满秩时能保证对单调、协调的变量的求解的正确性。证明:改进后的消下三角矩阵法和消上三角矩阵法中采用的不同列相消不会影响变量的值(否则变量就不是单调、协调的)。消元后的变量处于新方程组的第一种情况中,采用的求解方法与传统的高斯消元法一致,故能保证它的正确性。综上所述,该算法在非满秩时能保证对单调、协调的变量的求解的正确性。三、改进的高斯消元法在污水处理模型中的简单应用下面是对改进的高斯消元法应用于工业污水处理分析上的阐述：下表为某地水质抽样经过分析后测得的质量分数；表1 测定结果水体项目名称高锰酸钾指数(COD)BOD5氨氮眼硝酸盐氮挥发酚氰化物总砷六价铬西支河27.3364.865.480.0720.0300.0230.0280.002干渠19.5332.697.280.0740.0060.0060.0150.002洸河10.499.160.680.0320.0010.0020.0120.002白水渠11.5420.014.120.0820.0020.0200.0180.002小青河2.490.660.240.0240.0010.0020.0050.002白杨河2.650.550.23.0.0240.0010.0020.0070.002赣江2.660.560.230.0250.0020.0030.0090.002黄子河27.346.895.490.0740.0330.0250.0290.002西行河28.346.995.590.0840.0430.0350.0390.012以上数据单位：毫克/升（mg/L）表2 GHZB.1-1999值项目|等级一级二级三级四级五级Pi3.43表3 计算可得上述水样Pi值及水质等级如下水体项目西支河干渠洸河白水渠小清河白杨河赣江黄子河西行河Pi4.853.502.132.070.520.540.564.874.88水质等级五级五级四级四级二级二级二级五级五级根据表1、表2、表3的数据可见立多元线性方程组：改进的高斯消元法步骤如下：第1步。先判别式(2)中0 的系数是否有负数,若有,则将该方程两边同乘以-1;求出式(2)中0 的非零最小系数(若全为0,则方程组无唯一解),并将此方程与第一个方程交换位置(由于0 的系数均为1,故不用交换);式(2)中第i 个方程减去第一个方程的11lixx(对11lixx取整)倍。其中i=2,3,8;对方程组经过步骤之后第一个方程以后的a 系数进行判定:若不全为0,则重复步骤和,直至全为0。(2)第k 步。先判别式(2)中k 1 的系数是否有负,若有,则将该方程两边同乘以-1;求出式(2)中1 的非零最小系数(若全为0,则方程组无唯一解),并将此方程与第一个方程交换位置;式(2)中第i 个方程减去第一个方程的kkikxx(对kkikxx取整)倍。其中i =k+1,8;对方程组经过第k 步的步骤之后第一个方程以后的0 系数进行判定:若不全为0,则重复第k 步的步骤和步骤,直至全为0。经过上述步骤解得的结果为：0 =2.062, 1=0.315, 2 =-0.006, 3 = 0.057, 4 = -39.396, 5 = -150.696, 6 =100.535, 7 = -25.226。8=82.795。得出的结论有两点：首先，如果回收处是水质的断面水质综合指数，可以知道各种污染因素对于水质污染的影响程度分别是多少。可见，氰化物对于水质污染的影响成度较大，而挥发酚对于水质的污染程度相应较小。这对于工业水质污染的处理方向尤为重要。可以针对对于水质污染影响较大的因子通过多种途径来进行重点治理，以较少的经济，人力，物力投入来获取较大的成效，对于节省财政支出具有一定的意义。如果抽样量很大，范围很广，就更能突显此方法的优越性及重要性。4 结论本文所采用的改进的Gauss 消去法对数据没有任何的要求