对高斯消元法的改进以及在工程上的应用(2)

　　当应用这些概念到多元一次方程组的求解中时,我们同样发现当满秩时方程组是完备和不矛盾的,即在第一种情况下,方程组同样具有单调性和协调性;而在第二种情况下,方程组存在矛盾,这时如果对方程组进行处理,我们同样定义为超协调性;在第三种情况下,方程组有无穷多组解,这时的方程组是不完备的,这时如果对方程组进行处理,我们同样定义为非单调性。对于单个变量,我们定义有且只有唯一解的变量是单调和协调的;若它同时取两个以上的解,则我们称该变量是超协调的,若它无唯一解(既有无穷解),则称该变量是非单调的。
这样我们发现对高斯消元法的改进,也就是使只能处理单调、协调的方程组的高斯消元法能够同样处理超协调和非单调的情形。方程组的非单调性说明方程不足,方程组的超协调性说明方程之间冲突。这与逻辑推理中知识不完全和知识矛盾是类似的,应用非单调逻辑和超协调逻辑的思想,我们可得到如下改进的高斯消元法。

　　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种情况:

　　●系数矩阵对应的一行中只有一项非零,则该项对应的变量有唯一解;

　　●系数矩阵对应的一行中不只一项非零,则非零项对应的变量有无穷解,该变量具有非单调性;

　　●系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行不为零,则方程组中存在超协调的情况,即某个变量同时取两个值;

　　●系数矩阵对应的一行中均为零,而常数项矩阵对应的那一行也为零,说明方程组中有冗余情况。

　　对第一种情况,求解与传统的高斯消元法相同,然后删去该行。 （科教作文网http://zw.NSEaC.com编辑发布）
　　对第四种情况,删去该行即可。

　　重要的是对第二种、第三种情况的处理。不同的处理体现了不同的非单调、超协调策略。首先对第三种情况进行处理。对超协调性的解决方法是维护协调性。最简单的处理方法是删去该行,则方程组中消除了超协调的情况。则相当于当变量同时取两个值时,任意删除其中的一个赋值。

　　(4)处理无穷解的情况。

　　处理完第一、第三、第四种情况后,则新的方程组中就只剩下第二种情况。对非单调的解决方法是扩充不完全的知识。给出一批缺省规则(一般是对每个变量给一个缺省值)和相应的优先级,对于有无穷解的变量组,选择与该变量组中变量相关的优先级最高的缺省规则(优先级相同时可按变量顺序选择或随机选择),加入方程组中。若无穷解的变量组为空,则所有变量都已有唯一解,算法结束。否则转到步骤1继续处理。

　　由上述算法可知,当所有变量都有唯一解时,运算与高斯消元法一样。只是在非单调、超协调的情况下,采取了相应的处理策略。具体来说,在新方程中对第二种情形的处理即是对非单调知识的处理,借用了非单调逻辑中缺省理论的方法。而对第三种情形的处理即是对超协调知识的处理,则是超协调逻辑中分域逻辑的一种简化。

　　从理论上讲,改进的高斯消元法实质是建立在一种新的公理体系的基础上,因为它限制了方程的和差乘除仍为方程的公理的运用范围,从而达到能处理非单调、超协调的情形。传统的高斯消元法实质就是不断应用不同行相消产生新方程,最终产生只含一个变量的方程,而在非单调和超协调的情况下(即满秩情形),或者会出现无论如何变换最终仍含多个变量的方程,这时必须停止不同行相消,利用缺省规则加入新的方程后再继续计算;或者会出现矛盾方程(即方程左端无变量而右端不为零的方程),这时必须禁止矛盾方程与其它行相消。以上所述即是要限制公理的使用范围,这种思想是从非单调、超协调逻辑中借用来的。而在单调、协调的情况下,它与传统的高斯消元法完全一致。

定理1:该算法在满秩时等价于传统的高斯消元法。

　　证明:在满秩时, m=n。