浅谈高斯消元法的改进以及在工程上的应用
论文关键词：高斯消元法 非单调逻辑 超协调逻辑 约束
论文摘要：传统的高斯消元法只能处理多元一次方程组满秩的情况,本文应用人工智能中非单调逻辑和超协调逻辑的思想,通过对高斯消元法的改进,使其对所有的多元一次方程组都能进行有效的处理,从而扩展了在工程上的应用范围。
0 引言
传统的高斯消元法只能处理多元一次方程组满秩的情况,从而限制了它的应用范围。而近年来人工智能的发展,为改进高斯消元法提供了新的思路,改进后的算法编程简单,能处理所有的多元一次方程组,并在一个建筑CAD软件中进行了应用,取得了很好的效果。
1 对高斯消元法的改进
首先介绍一下高斯消元法。
则给定线性方程组的矩阵形式为Ax=b
A 称为方程组的系数矩阵, 称为方程组的增广矩阵。
以r (A)和r (C)分别表示系数矩阵A与增广矩阵C的秩,则有
(1)当m=n且r (A) =r (C) =n时(即方程组满秩时),方程组有唯一解。
(2)当r (A)<r (C)时,方程组无解,这时的方程组称为矛盾方程组。
(3)当r (A) =r (C) =r<n时,方程组有无穷多组解。
1. 1传统的高斯消元法[1]
高斯消元法只能用于处理第一种情况,它的核心是消下三角矩阵法和消上三角矩阵法。经过消元后,增广矩阵变为对于第二、第三种情况,高斯消元法则无法处理。在第二种情况下,方程组存在矛盾,但并不是每个方程之间都存在矛盾,某些变量还可能只存在唯一解;同样,在第三种情况下,方程组有无穷多组解,并不等于每个变量都有无穷多组解,某些变量可能只存在唯一解。而要找出在第二、第三种情况下的变量的唯一解,则必须对高斯消元法进行改进。而第二种情况下,方程组中必然存在一个变量同时取两个以上的值,即必须在超协调的情况下进行处理;在第三种情况下,方程组中必然存在一个变量无唯一解(即有无穷解),即必须在非单调的情况下进行处理。
以下我简单介绍一下超协调和非单调的概念。这两个概念最初是在人工智能中针对经典逻辑的单调性和协调性的概念提出的,在经典逻辑中知识是完备和不矛盾的,这时对知识的处理具有单调性和协调性,而现实生活中的知识是不完备的,并且可能存在矛盾。于是人们把知识不完备时对知识的处理称为非单调性,而把知识存在矛盾时对知识的处理称为超协调性。
随着人工智能对非单调知识和超协调知识处理的发展,逐步形成了不同于经典逻辑的新的逻辑体系——非单调逻辑和超协调逻辑。
非单调逻辑是经典逻辑的强化,因为在非单调逻辑中,一些原来在经典逻辑中推不出来的结论,现在可以在非单调逻辑中推出。而在经典逻辑中能推出的结论,在非单调逻辑中照样可以推出。
超协调逻辑是经典逻辑的弱化,因为在超协调逻辑中,一些原来在经典逻辑中能推出的结论,现在在超协调逻辑中不能推出。而在经典逻辑中不能推出的结论,在非单调逻辑中照样不能推出。
非单调性的解决方法是:对不完全知识的扩充。常用的非单调方法有限制、缺省理论、自知逻辑等。超协调性的解决方法是:维护协调性。常用的超协调方法有分域逻辑DL、超协调 系统Cn和悖论逻辑LP等。
当应用这些概念到多元一次方程组的求解中时,我们同样发现当满秩时方程组是完备和不矛盾的,即在第一种情况下,方程组同样具有单调性和协调性;而在第二种情况下,方程组存在矛盾,这时如果对方程组进行处理,我们同样定义为超协调性;在第三种情况下,方程组有无穷多组解,这时的方程组是不完备的,这时如果对方程组进行处理,我们同样定义为非单调性。对于单个变量,我们定义有且只有唯一解的变量是单调和协调的;若它同时取两个以上的解,则我们称该变量是超协调的,若它无唯一解(既有无穷解),则称该变量是非单调的。
这样我们发现对高斯消元法的改进,也就是使只能处理单调、协调的方程组的高斯消元法能够同样处理超协调和非单调的情形。方程组的非单调性说明方程不足,方程组的超协调性说明方程之间冲突。这与逻辑推理中知识不完全和知识矛盾是类似的,应用非单调逻辑和超协调逻辑的思想,我们可得到如下改进的高斯消元法。
改进后的高斯消元法的算法分为如下四个步骤:
(1)用改进后的消下三角矩阵法进行处理。
对消下三角矩阵法的改进在于设置i=1, j=1,若第j列中aij以下部分(含aij)有非零值时,将非零值放到aij,消去该列其它值(向下),然后i加1, j加1,对下一列进行处理;当一列中aij以下部分(含aij)无非零值时, j加1,而i不变,对下一列进行处理。当i>m或j>n时中止。
(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:该算法在非满秩时能保证对单调、协调的变量的求解的正确性。
证明:改进后的消下三角矩阵法和消上三角矩阵法中采用的不同列相消不会影响变量的值(否则变量就不是单调、协调的)。
消元后的变量处于新方程组的第一种情况中,采用的求解方法与传统的高斯消元法一致,故能保证它的正确性。
综上所述,该算法在非满秩时能保证对单调、协调的变量的求解的正确性。
2 应 用
在工程设计的参数化造型中,图纸的绘制是由基本拓扑结构的绘制和长度、角度等约束关系的加入两个构成的,然后计算机自动根据长度、角度等约束关系(即数据)修正原草图,形成精确的工程图纸。在基本拓扑结构的绘制过程中,长度、角度等具体尺寸不必精确,这样大大节省了绘制时间,并便于修改。
以下我介绍改进的高斯消元法在参数化造型中的应用。
在工程上,一些尺寸是要求精确的,而有些尺寸却不要求精确,这时往往希望不输入这些尺寸值而利用原始草图中的粗略值,这在工程上就是处理约束不足的情形。另一方面,由于图纸的复杂,输入的各种尺寸或约束关系很可能出错,这在工程上是约束冲突,这时希望能发现错误。
在工程上,约束大多以方程的方式表示,约束的处理从另一个方面看就是对求解方程组,而方程大多可通过求导、求积等形式化为多元一次方程。方程组的非单调性说明约束不足,方程组的超协调性说明约束冲突。约束不足就应该加入新的约束,约束冲突就应该删去某些约束,维护其协调性,都是对约束的增减。
传统的高斯消元法无法解决约束不足和约束冲突的问题。而改进后的高斯消元法却能很容易解决这类问题。只要将原始草图中的粗略值定为这些尺寸变量的缺省值并指定优先级,在输入精确值时尺寸变量会按照精确值进行处理,而未输入精确值时尺寸变量会按照缺省值(原始草图中的粗略值)进行处理。
而约束冲突时,会出现方程组中的第三种情况。这时根据工程上的不同需要,有两种处理办法:
(1)按改进的高斯消元法中的方法删去第三种情况的方程,以消除约束冲突情况;
(2)中止处理,提示是由哪个尺寸变量或哪几个约束方程引起的约束冲突,由用户修改。
3 结 论
用非单调逻辑和超协调逻辑的思想改进高斯消元法,是逻辑思想在代数领域的应用。改进后的高斯消元法时间复杂度与传统的高斯消元法相同,在单调、协调的情形下等价于传统的高斯消元法,具有很好的应用价值。另外,算法中对非单调、超协调情况的处理并不是唯一的,如应用其它非单调逻辑和超协调逻辑的思想,可扩大算法的应用范围。同时,该方法将非单调思想和超协调思想有机地结合在一起,对于研究如何结合当前的非单调逻辑和超协调逻辑构造出新的非单调超协调逻辑有一定的启发意义。
参考文献
1 武汉大学、山东大学计算数学教研室。计算方法。人民教育出版社, 1979
2 D. W. Etherington. Reasoning with Incomplete Information。Morgan Kaufman, 1988
3 林作铨,石纯一。非单调推理十年进展。计算机科学, 17 (6), 1990
4 Roos N. A Logic to Reasoning with Inconsistent Knowledge。Artificial Intelligence, 57, 1992
【浅谈高斯消元法的改进以及在工程上的应用】相关文章：