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

　　对于改进后的消下三角矩阵法, 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