對高斯消元法的改進以及在工程上的應用

時間：2023-03-02 05:21:47 數學畢業論文我要投稿

相關推薦

對高斯消元法的改進以及在工程上的應用

論文關鍵詞：高斯消元法非單調邏輯超協調邏輯約束

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

　　0　引言

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

　　1　對高斯消元法的改進

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

　　則給定線性方程組的矩陣形式為Ax=b

　　A　　稱為方程組的系數矩陣, 稱為方程組的增廣矩陣。

　　以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種情況:

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

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

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

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

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

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

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

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

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

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

定理1:該算法在滿秩時等價于傳統的高斯消元法。

　　證明:在滿秩時, m=n。

　　對于改進后的消下三角矩陣法, 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

【對高斯消元法的改進以及在工程上的應用】相關文章：

法與正義06-05

關于通信工程傳輸技術的應用分析（精選8篇）07-26

談多網融合在通信工程的應用論文04-11