- 相關(guān)推薦
對高斯消元法的改進以及在工程上的應(yīng)用
論文關(guān)鍵詞：高斯消元法 非單調(diào)邏輯 超協(xié)調(diào)邏輯 約束
論文摘要：傳統(tǒng)的高斯消元法只能處理多元一次方程組滿秩的情況,本文應(yīng)用人工智能中非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想,通過對高斯消元法的改進,使其對所有的多元一次方程組都能進行有效的處理,從而擴展了在工程上的應(yīng)用范圍。
0 引言
傳統(tǒng)的高斯消元法只能處理多元一次方程組滿秩的情況,從而限制了它的應(yīng)用范圍。而近年來人工智能的發(fā)展,為改進高斯消元法提供了新的思路,改進后的算法編程簡單,能處理所有的多元一次方程組,并在一個建筑CAD軟件中進行了應(yīng)用,取得了很好的效果。
1 對高斯消元法的改進
首先介紹一下高斯消元法。
則給定線性方程組的矩陣形式為Ax=b
A 稱為方程組的系數(shù)矩陣, 稱為方程組的增廣矩陣。
以r (A)和r (C)分別表示系數(shù)矩陣A與增廣矩陣C的秩,則有
(1)當m=n且r (A) =r (C) =n時(即方程組滿秩時),方程組有唯一解。
(2)當r (A) <r (C)時,方程組無解,這時的方程組稱為矛盾方程組。
(3)當r (A) =r (C) =r<n時,方程組有無窮多組解。
1. 1傳統(tǒng)的高斯消元法[1]
高斯消元法只能用于處理第一種情況,它的核心是消下三角矩陣法和消上三角矩陣法。經(jīng)過消元后,增廣矩陣變?yōu)?/p>
對于第二、第三種情況,高斯消元法則無法處理。在第二種情況下,方程組存在矛盾,但并不是每個方程之間都存在矛盾,某些變量還可能只存在唯一解;同樣,在第三種情況下,方程組有無窮多組解,并不等于每個變量都有無窮多組解,某些變量可能只存在唯一解。而要找出在第二、第三種情況下的變量的唯一解,則必須對高斯消元法進行改進。而第二種情況下,方程組中必然存在一個變量同時取兩個以上的值,即必須在超協(xié)調(diào)的情況下進行處理;在第三種情況下,方程組中必然存在一個變量無唯一解(即有無窮解),即必須在非單調(diào)的情況下進行處理。
以下我簡單介紹一下超協(xié)調(diào)和非單調(diào)的概念。這兩個概念最初是在人工智能中針對經(jīng)典邏輯的單調(diào)性和協(xié)調(diào)性的概念提出的,在經(jīng)典邏輯中知識是完備和不矛盾的,這時對知識的處理具有單調(diào)性和協(xié)調(diào)性,而現(xiàn)實生活中的知識是不完備的,并且可能存在矛盾。于是人們把知識不完備時對知識的處理稱為非單調(diào)性,而把知識存在矛盾時對知識的處理稱為超協(xié)調(diào)性。
隨著人工智能對非單調(diào)知識和超協(xié)調(diào)知識處理的發(fā)展,逐步形成了不同于經(jīng)典邏輯的新的邏輯體系——非單調(diào)邏輯和超協(xié)調(diào)邏輯。
非單調(diào)邏輯是經(jīng)典邏輯的強化,因為在非單調(diào)邏輯中,一些原來在經(jīng)典邏輯中推不出來的結(jié)論,現(xiàn)在可以在非單調(diào)邏輯中推出。而在經(jīng)典邏輯中能推出的結(jié)論,在非單調(diào)邏輯中照樣可以推出。
超協(xié)調(diào)邏輯是經(jīng)典邏輯的弱化,因為在超協(xié)調(diào)邏輯中,一些原來在經(jīng)典邏輯中能推出的結(jié)論,現(xiàn)在在超協(xié)調(diào)邏輯中不能推出。而在經(jīng)典邏輯中不能推出的結(jié)論,在非單調(diào)邏輯中照樣不能推出。
非單調(diào)性的解決方法是:對不完全知識的擴充。常用的非單調(diào)方法有限制、缺省理論、自知邏輯等。超協(xié)調(diào)性的解決方法是:維護協(xié)調(diào)性。常用的超協(xié)調(diào)方法有分域邏輯DL、超協(xié)調(diào)系統(tǒng)Cn和悖論邏輯LP等。
當應(yīng)用這些概念到多元一次方程組的求解中時,我們同樣發(fā)現(xiàn)當滿秩時方程組是完備和不矛盾的,即在第一種情況下,方程組同樣具有單調(diào)性和協(xié)調(diào)性;而在第二種情況下,方程組存在矛盾,這時如果對方程組進行處理,我們同樣定義為超協(xié)調(diào)性;在第三種情況下,方程組有無窮多組解,這時的方程組是不完備的,這時如果對方程組進行處理,我們同樣定義為非單調(diào)性。對于單個變量,我們定義有且只有唯一解的變量是單調(diào)和協(xié)調(diào)的;若它同時取兩個以上的解,則我們稱該變量是超協(xié)調(diào)的,若它無唯一解(既有無窮解),則稱該變量是非單調(diào)的。
這樣我們發(fā)現(xiàn)對高斯消元法的改進,也就是使只能處理單調(diào)、協(xié)調(diào)的方程組的高斯消元法能夠同樣處理超協(xié)調(diào)和非單調(diào)的情形。方程組的非單調(diào)性說明方程不足,方程組的超協(xié)調(diào)性說明方程之間沖突。這與邏輯推理中知識不完全和知識矛盾是類似的,應(yīng)用非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想,我們可得到如下改進的高斯消元法。
1.2改進后的高斯消元法
改進后的高斯消元法的算法分為如下四個步驟:
(1)用改進后的消下三角矩陣法進行處理。
對消下三角矩陣法的改進在于設(shè)置i=1, j=1,若第j列中aij以下部分(含aij)有非零值時,將非零值放到aij,消去該列其它值(向下),然后i加1, j加1,對下一列進行處理;當一列中aij以下部分(含aij)無非零值時, j加1,而i不變,對下一列進行處理。當i>m或j>n時中止。
(2)用改進后的消上三角矩陣法進行處理。
對消上三角矩陣法的改進在于設(shè)置i=m, j=n,在第j列從aij往上找,直至找到一個非零值或者找遍該列aij以上部分(含aij)都為零值。若找到的非零值為aij,則將非零值放到aij,消去該列其它值(向上),然后i減1, j減1,對下一列進行處理;若該列aij以上部分(含aij)都為零值時, j減1,而i不變,對下一列進行處理。當i=0或j=0時中止。
(3)分析新方程。
可以看出經(jīng)過消元后的系數(shù)矩陣在左下方和右上方有一片零值區(qū)。消元后的新的方程組中的方程分為4種情況:
●系數(shù)矩陣對應(yīng)的一行中只有一項非零,則該項對應(yīng)的變量有唯一解;
●系數(shù)矩陣對應(yīng)的一行中不只一項非零,則非零項對應(yīng)的變量有無窮解,該變量具有非單調(diào)性;
●系數(shù)矩陣對應(yīng)的一行中均為零,而常數(shù)項矩陣對應(yīng)的那一行不為零,則方程組中存在超協(xié)調(diào)的情況,即某個變量同時取兩個值;
●系數(shù)矩陣對應(yīng)的一行中均為零,而常數(shù)項矩陣對應(yīng)的那一行也為零,說明方程組中有冗余情況。
對第一種情況,求解與傳統(tǒng)的高斯消元法相同,然后刪去該行。
對第四種情況,刪去該行即可。
重要的是對第二種、第三種情況的處理。不同的處理體現(xiàn)了不同的非單調(diào)、超協(xié)調(diào)策略。首先對第三種情況進行處理。對超協(xié)調(diào)性的解決方法是維護協(xié)調(diào)性。最簡單的處理方法是刪去該行,則方程組中消除了超協(xié)調(diào)的情況。則相當于當變量同時取兩個值時,任意刪除其中的一個賦值。
(4)處理無窮解的情況。
處理完第一、第三、第四種情況后,則新的方程組中就只剩下第二種情況。對非單調(diào)的解決方法是擴充不完全的知識。給出一批缺省規(guī)則(一般是對每個變量給一個缺省值)和相應(yīng)的優(yōu)先級,對于有無窮解的變量組,選擇與該變量組中變量相關(guān)的優(yōu)先級最高的缺省規(guī)則(優(yōu)先級相同時可按變量順序選擇或隨機選擇),加入方程組中。若無窮解的變量組為空,則所有變量都已有唯一解,算法結(jié)束。否則轉(zhuǎn)到步驟1繼續(xù)處理。
由上述算法可知,當所有變量都有唯一解時,運算與高斯消元法一樣。只是在非單調(diào)、超協(xié)調(diào)的情況下,采取了相應(yīng)的處理策略。具體來說,在新方程中對第二種情形的處理即是對非單調(diào)知識的處理,借用了非單調(diào)邏輯中缺省理論的方法。而對第三種情形的處理即是對超協(xié)調(diào)知識的處理,則是超協(xié)調(diào)邏輯中分域邏輯的一種簡化。
從理論上講,改進的高斯消元法實質(zhì)是建立在一種新的公理體系的基礎(chǔ)上,因為它限制了方程的和差乘除仍為方程的公理的運用范圍,從而達到能處理非單調(diào)、超協(xié)調(diào)的情形。傳統(tǒng)的高斯消元法實質(zhì)就是不斷應(yīng)用不同行相消產(chǎn)生新方程,最終產(chǎn)生只含一個變量的方程,而在非單調(diào)和超協(xié)調(diào)的情況下(即滿秩情形),或者會出現(xiàn)無論如何變換最終仍含多個變量的方程,這時必須停止不同行相消,利用缺省規(guī)則加入新的方程后再繼續(xù)計算;或者會出現(xiàn)矛盾方程(即方程左端無變量而右端不為零的方程),這時必須禁止矛盾方程與其它行相消。以上所述即是要限制公理的使用范圍,這種思想是從非單調(diào)、超協(xié)調(diào)邏輯中借用來的。而在單調(diào)、協(xié)調(diào)的情況下,它與傳統(tǒng)的高斯消元法完全一致。
定理1:該算法在滿秩時等價于傳統(tǒng)的高斯消元法。
證明:在滿秩時, m=n。
對于改進后的消下三角矩陣法, i、j均從0出發(fā),由于矩陣中不會出現(xiàn)一列中無非零值的情形(否則矩陣不滿秩),則每列操作i、j均加1,當處理完n列時, i=m=n, j=n,消下三角矩陣法中止。故與改進前的消下三角矩陣法完全相同。
對于改進后的消上三角矩陣法,由于m=n , i、j均視為從m出發(fā),由于矩陣中不會出現(xiàn)一列中無非零值的情形(否則矩陣不滿秩),則每列操作i、j均減1,當處理完n列時, i=0, j=0,消上三角矩陣法中止。故與改進前的消上三角矩陣法完全相同。
分析新方程時,只存在第一種情形,處理也同傳統(tǒng)的高斯消元法相同。不存在處理無窮解的情況。
綜上所述,該算法在滿秩時等價于傳統(tǒng)的高斯消元法。
定理2:該算法在非滿秩時能保證對單調(diào)、協(xié)調(diào)的變量的求解的正確性。
證明:改進后的消下三角矩陣法和消上三角矩陣法中采用的不同列相消不會影響變量的值(否則變量就不是單調(diào)、協(xié)調(diào)的)。
消元后的變量處于新方程組的第一種情況中,采用的求解方法與傳統(tǒng)的高斯消元法一致,故能保證它的正確性。
綜上所述,該算法在非滿秩時能保證對單調(diào)、協(xié)調(diào)的變量的求解的正確性。
2 應(yīng) 用
在工程設(shè)計的參數(shù)化造型中,圖紙的繪制是由基本拓撲結(jié)構(gòu)的繪制和長度、角度等約束關(guān)系的加入兩個構(gòu)成的,然后計算機自動根據(jù)長度、角度等約束關(guān)系(即數(shù)據(jù))修正原草圖,形成精確的工程圖紙。在基本拓撲結(jié)構(gòu)的繪制過程中,長度、角度等具體尺寸不必精確,這樣大大節(jié)省了繪制時間,并便于修改。
以下我介紹改進的高斯消元法在參數(shù)化造型中的應(yīng)用。
在工程上,一些尺寸是要求精確的,而有些尺寸卻不要求精確,這時往往希望不輸入這些尺寸值而利用原始草圖中的粗略值,這在工程上就是處理約束不足的情形。另一方面,由于圖紙的復(fù)雜,輸入的各種尺寸或約束關(guān)系很可能出錯,這在工程上是約束沖突,這時希望能發(fā)現(xiàn)錯誤。
在工程上,約束大多以方程的方式表示,約束的處理從另一個方面看就是對求解方程組,而方程大多可通過求導(dǎo)、求積等形式化為多元一次方程。方程組的非單調(diào)性說明約束不足,方程組的超協(xié)調(diào)性說明約束沖突。約束不足就應(yīng)該加入新的約束,約束沖突就應(yīng)該刪去某些約束,維護其協(xié)調(diào)性,都是對約束的增減。
傳統(tǒng)的高斯消元法無法解決約束不足和約束沖突的問題。而改進后的高斯消元法卻能很容易解決這類問題。只要將原始草圖中的粗略值定為這些尺寸變量的缺省值并指定優(yōu)先級,在輸入精確值時尺寸變量會按照精確值進行處理,而未輸入精確值時尺寸變量會按照缺省值(原始草圖中的粗略值)進行處理。
而約束沖突時,會出現(xiàn)方程組中的第三種情況。這時根據(jù)工程上的不同需要,有兩種處理辦法:
(1)按改進的高斯消元法中的方法刪去第三種情況的方程,以消除約束沖突情況;
(2)中止處理,提示是由哪個尺寸變量或哪幾個約束方程引起的約束沖突,由用戶修改。
3 結(jié) 論
用非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想改進高斯消元法,是邏輯思想在代數(shù)領(lǐng)域的應(yīng)用。改進后的高斯消元法時間復(fù)雜度與傳統(tǒng)的高斯消元法相同,在單調(diào)、協(xié)調(diào)的情形下等價于傳統(tǒng)的高斯消元法,具有很好的應(yīng)用價值。另外,算法中對非單調(diào)、超協(xié)調(diào)情況的處理并不是唯一的,如應(yīng)用其它非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想,可擴大算法的應(yīng)用范圍。同時,該方法將非單調(diào)思想和超協(xié)調(diào)思想有機地結(jié)合在一起,對于研究如何結(jié)合當前的非單調(diào)邏輯和超協(xié)調(diào)邏輯構(gòu)造出新的非單調(diào)超協(xié)調(diào)邏輯有一定的啟發(fā)意義。
參考文獻
1 武漢大學(xué)、山東大學(xué)計算數(shù)學(xué)教研室。計算方法。人民教育出版社, 1979
2 D. W. Etherington. Reasoning with Incomplete Information。Morgan Kaufman, 1988
3 林作銓,石純一。非單調(diào)推理十年進展。計算機科學(xué), 17 (6), 1990
4 Roos N. A Logic to Reasoning with Inconsistent Knowledge。Artificial Intelligence, 57, 1992
【對高斯消元法的改進以及在工程上的應(yīng)用】相關(guān)文章：
公允價值、預(yù)期現(xiàn)值法及其應(yīng)用06-01
多網(wǎng)融合對通信工程的應(yīng)用論文04-11
法與正義06-05
多網(wǎng)融合在通信工程的應(yīng)用論文04-12
談灌注樁在水利工程中的應(yīng)用08-22
纖維增強材料在土木工程之應(yīng)用05-02
改進我國企業(yè)知識治理08-28
多網(wǎng)融合應(yīng)用于通信工程的研究08-15