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