淺談高斯消元法的改進(jìn)以及在工程上的應用

　　論文關(guān)鍵詞：高斯消元法 非單調邏輯 超協(xié)調邏輯 約束

　　論文摘要：傳統的高斯消元法只能處理多元一次方程組滿(mǎn)秩的情況,本文應用人工智能中非單調邏輯和超協(xié)調邏輯的思想,通過(guò)對高斯消元法的改進(jìn),使其對所有的多元一次方程組都能進(jìn)行有效的處理,從而擴展了在工程上的應用范圍。

　　0 引言

　　傳統的高斯消元法只能處理多元一次方程組滿(mǎn)秩的情況,從而限制了它的應用范圍。而近年來(lái)人工智能的發(fā)展,為改進(jìn)高斯消元法提供了新的思路,改進(jìn)后的算法編程簡(jiǎn)單,能處理所有的多元一次方程組,并在一個(gè)建筑CAD軟件中進(jìn)行了應用,取得了很好的效果。

　　1 對高斯消元法的改進(jìn)

　　首先介紹一下高斯消元法。

　　則給定線(xiàn)性方程組的矩陣形式為Ax=b

　　A 稱(chēng)為方程組的系數矩陣, 稱(chēng)為方程組的增廣矩陣。

　　以r (A)和r (C)分別表示系數矩陣A與增廣矩陣C的秩,則有

　　(1)當m=n且r (A) =r (C) =n時(shí)(即方程組滿(mǎn)秩時(shí)),方程組有唯一解。

　　(2)當r (A)<r (C)時(shí),方程組無(wú)解,這時(shí)的方程組稱(chēng)為矛盾方程組。

　　(3)當r (A) =r (C) =r<n時(shí),方程組有無(wú)窮多組解。

　　1. 1傳統的高斯消元法[1]

　　高斯消元法只能用于處理第一種情況,它的核心是消下三角矩陣法和消上三角矩陣法。經(jīng)過(guò)消元后,增廣矩陣變?yōu)閷τ诘诙�、第三種情況,高斯消元法則無(wú)法處理。在第二種情況下,方程組存在矛盾,但并不是每個(gè)方程之間都存在矛盾,某些變量還可能只存在唯一解;同樣,在第三種情況下,方程組有無(wú)窮多組解,并不等于每個(gè)變量都有無(wú)窮多組解,某些變量可能只存在唯一解。而要找出在第二、第三種情況下的變量的唯一解,則必須對高斯消元法進(jìn)行改進(jìn)。而第二種情況下,方程組中必然存在一個(gè)變量同時(shí)取兩個(gè)以上的值,即必須在超協(xié)調的情況下進(jìn)行處理;在第三種情況下,方程組中必然存在一個(gè)變量無(wú)唯一解(即有無(wú)窮解),即必須在非單調的情況下進(jìn)行處理。

　　以下我簡(jiǎn)單介紹一下超協(xié)調和非單調的概念。這兩個(gè)概念最初是在人工智能中針對經(jīng)典邏輯的單調性和協(xié)調性的概念提出的,在經(jīng)典邏輯中知識是完備和不矛盾的,這時(shí)對知識的處理具有單調性和協(xié)調性,而現實(shí)生活中的知識是不完備的,并且可能存在矛盾。于是人們把知識不完備時(shí)對知識的處理稱(chēng)為非單調性,而把知識存在矛盾時(shí)對知識的處理稱(chēng)為超協(xié)調性。

　　隨著(zhù)人工智能對非單調知識和超協(xié)調知識處理的發(fā)展,逐步形成了不同于經(jīng)典邏輯的新的邏輯體系——非單調邏輯和超協(xié)調邏輯。

　　非單調邏輯是經(jīng)典邏輯的強化,因為在非單調邏輯中,一些原來(lái)在經(jīng)典邏輯中推不出來(lái)的結論,現在可以在非單調邏輯中推出。而在經(jīng)典邏輯中能推出的結論,在非單調邏輯中照樣可以推出。

　　超協(xié)調邏輯是經(jīng)典邏輯的弱化,因為在超協(xié)調邏輯中,一些原來(lái)在經(jīng)典邏輯中能推出的結論,現在在超協(xié)調邏輯中不能推出。而在經(jīng)典邏輯中不能推出的結論,在非單調邏輯中照樣不能推出。

　　非單調性的解決方法是:對不完全知識的擴充。常用的非單調方法有限制、缺省理論、自知邏輯等。超協(xié)調性的解決方法是:維護協(xié)調性。常用的超協(xié)調方法有分域邏輯DL、超協(xié)調 系統Cn和悖論邏輯LP等。

　　當應用這些概念到多元一次方程組的求解中時(shí),我們同樣發(fā)現當滿(mǎn)秩時(shí)方程組是完備和不矛盾的,即在第一種情況下,方程組同樣具有單調性和協(xié)調性;而在第二種情況下,方程組存在矛盾,這時(shí)如果對方程組進(jìn)行處理,我們同樣定義為超協(xié)調性;在第三種情況下,方程組有無(wú)窮多組解,這時(shí)的方程組是不完備的,這時(shí)如果對方程組進(jìn)行處理,我們同樣定義為非單調性。對于單個(gè)變量,我們定義有且只有唯一解的變量是單調和協(xié)調的;若它同時(shí)取兩個(gè)以上的解,則我們稱(chēng)該變量是超協(xié)調的,若它無(wú)唯一解(既有無(wú)窮解),則稱(chēng)該變量是非單調的。

　　這樣我們發(fā)現對高斯消元法的改進(jìn),也就是使只能處理單調、協(xié)調的方程組的高斯消元法能夠同樣處理超協(xié)調和非單調的情形。方程組的非單調性說(shuō)明方程不足,方程組的超協(xié)調性說(shuō)明方程之間沖突。這與邏輯推理中知識不完全和知識矛盾是類(lèi)似的,應用非單調邏輯和超協(xié)調邏輯的思想,我們可得到如下改進(jìn)的高斯消元法。

　　改進(jìn)后的高斯消元法的算法分為如下四個(gè)步驟:

　　(1)用改進(jìn)后的消下三角矩陣法進(jìn)行處理。

　　對消下三角矩陣法的改進(jìn)在于設置i=1, j=1,若第j列中aij以下部分(含aij)有非零值時(shí),將非零值放到aij,消去該列其它值(向下),然后i加1, j加1,對下一列進(jìn)行處理;當一列中aij以下部分(含aij)無(wú)非零值時(shí), j加1,而i不變,對下一列進(jìn)行處理。當i>m或j>n時(shí)中止。

　　(2)用改進(jìn)后的消上三角矩陣法進(jìn)行處理。

　　對消上三角矩陣法的改進(jìn)在于設置i=m, j=n,在第j列從aij往上找,直至找到一個(gè)非零值或者找遍該列aij以上部分(含aij)都為零值。若找到的非零值為aij,則將非零值放到aij,消去該列其它值(向上),然后i減1, j減1,對下一列進(jìn)行處理;若該列aij以上部分(含aij)都為零值時(shí), j減1,而i不變,對下一列進(jìn)行處理。當i=0或j=0時(shí)中止。

　　(3)分析新方程。

　　可以看出經(jīng)過(guò)消元后的系數矩陣在左下方和右上方有一片零值區。消元后的新的方程組中的方程分為4種情況:

　　●系數矩陣對應的一行中只有一項非零,則該項對應的變量有唯一解;

　　●系數矩陣對應的一行中不只一項非零,則非零項對應的變量有無(wú)窮解,該變量具有非單調性;

　　●系數矩陣對應的一行中均為零,而常數項矩陣對應的那一行不為零,則方程組中存在超協(xié)調的情況,即某個(gè)變量同時(shí)取兩個(gè)值;

　　●系數矩陣對應的一行中均為零,而常數項矩陣對應的那一行也為零,說(shuō)明方程組中有冗余情況。

　　對第一種情況,求解與傳統的高斯消元法相同,然后刪去該行。

　　對第四種情況,刪去該行即可。

　　重要的是對第二種、第三種情況的處理。不同的處理體現了不同的非單調、超協(xié)調策略。首先對第三種情況進(jìn)行處理。對超協(xié)調性的解決方法是維護協(xié)調性。最簡(jiǎn)單的處理方法是刪去該行,則方程組中消除了超協(xié)調的情況。則相當于當變量同時(shí)取兩個(gè)值時(shí),任意刪除其中的一個(gè)賦值。

　　(4)處理無(wú)窮解的情況。

　　處理完第一、第三、第四種情況后,則新的方程組中就只剩下第二種情況。對非單調的解決方法是擴充不完全的知識。給出一批缺省規則(一般是對每個(gè)變量給一個(gè)缺省值)和相應的優(yōu)先級,對于有無(wú)窮解的變量組,選擇與該變量組中變量相關(guān)的優(yōu)先級最高的缺省規則(優(yōu)先級相同時(shí)可按變量順序選擇或隨機選擇),加入方程組中。若無(wú)窮解的變量組為空,則所有變量都已有唯一解,算法結束。否則轉到步驟1繼續處理。

　　由上述算法可知,當所有變量都有唯一解時(shí),運算與高斯消元法一樣。只是在非單調、超協(xié)調的情況下,采取了相應的處理策略。具體來(lái)說(shuō),在新方程中對第二種情形的處理即是對非單調知識的處理,借用了非單調邏輯中缺省理論的方法。而對第三種情形的處理即是對超協(xié)調知識的處理,則是超協(xié)調邏輯中分域邏輯的一種簡(jiǎn)化。

　　從理論上講,改進(jìn)的高斯消元法實(shí)質(zhì)是建立在一種新的公理體系的基礎上,因為它限制了方程的和差乘除仍為方程的公理的運用范圍,從而達到能處理非單調、超協(xié)調的情形。傳統的高斯消元法實(shí)質(zhì)就是不斷應用不同行相消產(chǎn)生新方程,最終產(chǎn)生只含一個(gè)變量的方程,而在非單調和超協(xié)調的情況下(即滿(mǎn)秩情形),或者會(huì )出現無(wú)論如何變換最終仍含多個(gè)變量的方程,這時(shí)必須停止不同行相消,利用缺省規則加入新的方程后再繼續計算;或者會(huì )出現矛盾方程(即方程左端無(wú)變量而右端不為零的方程),這時(shí)必須禁止矛盾方程與其它行相消。以上所述即是要限制公理的使用范圍,這種思想是從非單調、超協(xié)調邏輯中借用來(lái)的。而在單調、協(xié)調的情況下,它與傳統的高斯消元法完全一致。

　　定理1:該算法在滿(mǎn)秩時(shí)等價(jià)于傳統的高斯消元法。

　　證明:在滿(mǎn)秩時(shí), m=n。

　　對于改進(jìn)后的消下三角矩陣法, i、j均從0出發(fā),由于矩陣中不會(huì )出現一列中無(wú)非零值的情形(否則矩陣不滿(mǎn)秩),則每列操作i、j均加1,當處理完n列時(shí), i=m=n, j=n,消下三角矩陣法中止。故與改進(jìn)前的消下三角矩陣法完全相同。

　　對于改進(jìn)后的消上三角矩陣法,由于m=n , i、j均視為從m出發(fā),由于矩陣中不會(huì )出現一列中無(wú)非零值的情形(否則矩陣不滿(mǎn)秩),則每列操作i、j均減1,當處理完n列時(shí), i=0, j=0,消上三角矩陣法中止。故與改進(jìn)前的消上三角矩陣法完全相同。

　　分析新方程時(shí),只存在第一種情形,處理也同傳統的高斯消元法相同。不存在處理無(wú)窮解的情況。

　　綜上所述,該算法在滿(mǎn)秩時(shí)等價(jià)于傳統的高斯消元法。

　　定理2:該算法在非滿(mǎn)秩時(shí)能保證對單調、協(xié)調的變量的求解的正確性。

　　證明:改進(jìn)后的消下三角矩陣法和消上三角矩陣法中采用的不同列相消不會(huì )影響變量的值(否則變量就不是單調、協(xié)調的)。

　　消元后的變量處于新方程組的第一種情況中,采用的求解方法與傳統的高斯消元法一致,故能保證它的正確性。

　　綜上所述,該算法在非滿(mǎn)秩時(shí)能保證對單調、協(xié)調的變量的求解的正確性。

　　2 應 用

　　在工程設計的參數化造型中,圖紙的繪制是由基本拓撲結構的繪制和長(cháng)度、角度等約束關(guān)系的加入兩個(gè)構成的,然后計算機自動(dòng)根據長(cháng)度、角度等約束關(guān)系(即數據)修正原草圖,形成精確的工程圖紙。在基本拓撲結構的繪制過(guò)程中,長(cháng)度、角度等具體尺寸不必精確,這樣大大節省了繪制時(shí)間,并便于修改。

　　以下我介紹改進(jìn)的高斯消元法在參數化造型中的應用。

　　在工程上,一些尺寸是要求精確的,而有些尺寸卻不要求精確,這時(shí)往往希望不輸入這些尺寸值而利用原始草圖中的粗略值,這在工程上就是處理約束不足的情形。另一方面,由于圖紙的復雜,輸入的各種尺寸或約束關(guān)系很可能出錯,這在工程上是約束沖突,這時(shí)希望能發(fā)現錯誤。

　　在工程上,約束大多以方程的方式表示,約束的處理從另一個(gè)方面看就是對求解方程組,而方程大多可通過(guò)求導、求積等形式化為多元一次方程。方程組的非單調性說(shuō)明約束不足,方程組的超協(xié)調性說(shuō)明約束沖突。約束不足就應該加入新的約束,約束沖突就應該刪去某些約束,維護其協(xié)調性,都是對約束的增減。

　　傳統的高斯消元法無(wú)法解決約束不足和約束沖突的問(wèn)題。而改進(jìn)后的高斯消元法卻能很容易解決這類(lèi)問(wèn)題。只要將原始草圖中的粗略值定為這些尺寸變量的缺省值并指定優(yōu)先級,在輸入精確值時(shí)尺寸變量會(huì )按照精確值進(jìn)行處理,而未輸入精確值時(shí)尺寸變量會(huì )按照缺省值(原始草圖中的粗略值)進(jìn)行處理。

　　而約束沖突時(shí),會(huì )出現方程組中的第三種情況。這時(shí)根據工程上的不同需要,有兩種處理辦法:

　　(1)按改進(jìn)的高斯消元法中的方法刪去第三種情況的方程,以消除約束沖突情況;

　　(2)中止處理,提示是由哪個(gè)尺寸變量或哪幾個(gè)約束方程引起的約束沖突,由用戶(hù)修改。

　　3 結 論

　　用非單調邏輯和超協(xié)調邏輯的思想改進(jìn)高斯消元法,是邏輯思想在代數領(lǐng)域的應用。改進(jìn)后的高斯消元法時(shí)間復雜度與傳統的高斯消元法相同,在單調、協(xié)調的情形下等價(jià)于傳統的高斯消元法,具有很好的應用價(jià)值。另外,算法中對非單調、超協(xié)調情況的處理并不是唯一的,如應用其它非單調邏輯和超協(xié)調邏輯的思想,可擴大算法的應用范圍。同時(shí),該方法將非單調思想和超協(xié)調思想有機地結合在一起,對于研究如何結合當前的非單調邏輯和超協(xié)調邏輯構造出新的非單調超協(xié)調邏輯有一定的啟發(fā)意義。

　　參考文獻

　　1 武漢大學(xué)、山東大學(xué)計算數學(xué)教研室。計算方法。人民教育出版社, 1979

　　2 D. W. Etherington. Reasoning with Incomplete Information。Morgan Kaufman, 1988

　　3 林作銓,石純一。非單調推理十年進(jìn)展。計算機科學(xué), 17 (6), 1990

　　4 Roos N. A Logic to Reasoning with Inconsistent Knowledge。Artificial Intelligence, 57, 1992

【淺談高斯消元法的改進(jìn)以及在工程上的應用】相關(guān)文章：

對高斯消元法的改進(jìn)以及在工程上的應用03-02

淺談持票人票據法上的權利03-18

淺談類(lèi)比法在初中物理教學(xué)中的應用12-02

淺談比較法在地理教學(xué)中的應用06-01

數學(xué)歸納法的教學(xué)設計以及它的拓廣應用03-07

淺談防雷器在電源系統中原理以及應用03-23

淺談房地產(chǎn)市場(chǎng)營(yíng)銷(xiāo)的策略以及應用12-02

淺談圖像法在中學(xué)物理實(shí)驗中的應用11-23

淺談全過(guò)程跟蹤審計法在工程造價(jià)審計中的應用03-02

矩陣分解以及應用03-07