写作网域名：
频道：传统的高斯消元法只能处理多元一次方程组满秩的情况,从而限制了它的应用范围。而近年来人工智能的发展,为改进高斯消元法提供了新的思路,改进后的算法编程简单,能处理所有的多元一次方程组,并在一个建筑CAD软件中进行了应用,取得了很好的效果。
1 对高斯消元法的改进
首先介绍一下高斯消元法。
以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.2改进后的高斯消元法
改进后的高斯消元法的算法分为如下四个步骤:
(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种情况:
●系数矩阵对应的一行中只有一项非零,则该项对应的变量有唯一解;
●系数矩阵对应的一行中不只一项非零,则非零项对应的变量有无穷解,该变量具有非单调性;
●系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行不为零,则方程组中存在超协调的情况,即某个变量同时取两个值;
●系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行也为零,说明方程组中有冗余情况。
