對高斯消元法的改進(jìn)以及在工程上的應(yīng)用

1、對高斯消元法的改良以及在工程上的應(yīng)用論文關(guān)鍵詞：高斯消元法非單調(diào)邏輯超協(xié)調(diào)邏輯約束論文摘要：傳統(tǒng)的高斯消元法只能處理多元一次方程組滿秩的情況,本文應(yīng)用人工智能中非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想,通過對高斯消元法的改良,使其對所有的多元一次方程組都能進(jìn)展有效的處理,從而擴(kuò)展了在工程上的應(yīng)用范圍。0引言傳統(tǒng)的高斯消元法只能處理多元一次方程組滿秩的情況,從而限制了它的應(yīng)用范圍。而近年來人工智能的開展,為改良高斯消元法提供了新的思路,改良后的算法編程簡單,能處理所有的多元一次方程組,并在一個(gè)建筑ad軟件中進(jìn)展了應(yīng)用,獲得了很好的效果。1對高斯消元法的改良首先介紹一下高斯消元法。那么給定線性方程組的矩陣形式

2、為ax=ba稱為方程組的系數(shù)矩陣,稱為方程組的增廣矩陣。以r(a)和r()分別表示系數(shù)矩陣a與增廣矩陣的秩,那么有(1)當(dāng)=n且r(a)=r()=n時(shí)(即方程組滿秩時(shí)),方程組有唯一解。(2)當(dāng)r(a)r()時(shí),方程組無解,這時(shí)的方程組稱為矛盾方程組。(3)當(dāng)r(a)=r()=rn時(shí),方程組有無窮多組解。1.1傳統(tǒng)的高斯消元法1高斯消元法只能用于處理第一種情況,它的核心是消下三角矩陣法和消上三角矩陣法。經(jīng)過消元后,增廣矩陣變?yōu)閷τ诘诙⒌谌N情況,高斯消元法那么無法處理。在第二種情況下,方程組存在矛盾,但并不是每個(gè)方程之間都存在矛盾,某些變量還可能只存在唯一解;同樣,在第三種情況下,方程組有無

3、窮多組解,并不等于每個(gè)變量都有無窮多組解,某些變量可能只存在唯一解。而要找出在第二、第三種情況下的變量的唯一解,那么必須對高斯消元法進(jìn)展改良。而第二種情況下,方程組中必然存在一個(gè)變量同時(shí)取兩個(gè)以上的值,即必須在超協(xié)調(diào)的情況下進(jìn)展處理;在第三種情況下,方程組中必然存在一個(gè)變量無唯一解(即有無窮解),即必須在非單調(diào)的情況下進(jìn)展處理。以下我簡單介紹一下超協(xié)調(diào)和非單調(diào)的概念。這兩個(gè)概念最初是在人工智能中針對經(jīng)典邏輯的單調(diào)性和協(xié)調(diào)性的概念提出的,在經(jīng)典邏輯中知識是完備和不矛盾的,這時(shí)對知識的處理具有單調(diào)性和協(xié)調(diào)性,而現(xiàn)實(shí)生活中的知識是不完備的,并且可能存在矛盾。于是人們把知識不完備時(shí)對知識的處理稱為非單

4、調(diào)性,而把知識存在矛盾時(shí)對知識的處理稱為超協(xié)調(diào)性。隨著人工智能對非單調(diào)知識和超協(xié)調(diào)知識處理的開展,逐步形成了不同于經(jīng)典邏輯的新的邏輯體系非單調(diào)邏輯和超協(xié)調(diào)邏輯。非單調(diào)邏輯是經(jīng)典邏輯的強(qiáng)化,因?yàn)樵诜菃握{(diào)邏輯中,一些原來在經(jīng)典邏輯中推不出來的結(jié)論,如今可以在非單調(diào)邏輯中推出。而在經(jīng)典邏輯中能推出的結(jié)論,在非單調(diào)邏輯中照樣可以推出。超協(xié)調(diào)邏輯是經(jīng)典邏輯的弱化,因?yàn)樵诔瑓f(xié)調(diào)邏輯中,一些原來在經(jīng)典邏輯中能推出的結(jié)論,如今在超協(xié)調(diào)邏輯中不能推出。而在經(jīng)典邏輯中不能推出的結(jié)論,在非單調(diào)邏輯中照樣不能推出。非單調(diào)性的解決方法是:對不完全知識的擴(kuò)大。常用的非單調(diào)方法有限制、缺省理論、自知邏輯等。超協(xié)調(diào)性的解決方

5、法是:維護(hù)協(xié)調(diào)性。常用的超協(xié)調(diào)方法有分域邏輯dl、超協(xié)調(diào)系統(tǒng)n和悖論邏輯lp等。當(dāng)應(yīng)用這些概念到多元一次方程組的求解中時(shí),我們同樣發(fā)現(xiàn)當(dāng)滿秩時(shí)方程組是完備和不矛盾的,即在第一種情況下,方程組同樣具有單調(diào)性和協(xié)調(diào)性;而在第二種情況下,方程組存在矛盾,這時(shí)假如對方程組進(jìn)展處理,我們同樣定義為超協(xié)調(diào)性;在第三種情況下,方程組有無窮多組解,這時(shí)的方程組是不完備的,這時(shí)假如對方程組進(jìn)展處理,我們同樣定義為非單調(diào)性。對于單個(gè)變量,我們定義有且只有唯一解的變量是單調(diào)和協(xié)調(diào)的;假設(shè)它同時(shí)取兩個(gè)以上的解,那么我們稱該變量是超協(xié)調(diào)的,假設(shè)它無唯一解(既有無窮解),那么稱該變量是非單調(diào)的。這樣我們發(fā)現(xiàn)對高斯消元法的

6、改良,也就是使只能處理單調(diào)、協(xié)調(diào)的方程組的高斯消元法可以同樣處理超協(xié)調(diào)和非單調(diào)的情形。方程組的非單調(diào)性說明方程缺乏,方程組的超協(xié)調(diào)性說明方程之間沖突。這與邏輯推理中知識不完全和知識矛盾是類似的,應(yīng)用非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想,我們可得到如下改良的高斯消元法。1.2改良后的高斯消元法改良后的高斯消元法的算法分為如下四個(gè)步驟:(1)用改良后的消下三角矩陣法進(jìn)展處理。對消下三角矩陣法的改良在于設(shè)置i=1,j=1,假設(shè)第j列中aij以下局部(含aij)有非零值時(shí),將非零值放到aij,消去該列其它值(向下),然后i加1,j加1,對下一列進(jìn)展處理;當(dāng)一列中aij以下局部(含aij)無非零值時(shí),j加1,而

7、i不變,對下一列進(jìn)展處理。當(dāng)i或jn時(shí)中止。(2)用改良后的消上三角矩陣法進(jìn)展處理。對消上三角矩陣法的改良在于設(shè)置i=,j=n,在第j列從aij往上找,直至找到一個(gè)非零值或者找遍該列aij以上局部(含aij)都為零值。假設(shè)找到的非零值為aij,那么將非零值放到aij,消去該列其它值(向上),然后i減1,j減1,對下一列進(jìn)展處理;假設(shè)該列aij以上局部(含aij)都為零值時(shí),j減1,而i不變,對下一列進(jìn)展處理。當(dāng)i=0或j=0時(shí)中止。(3)分析新方程。可以看出經(jīng)過消元后的系數(shù)矩陣在左下方和右上方有一片零值區(qū)。消元后的新的方程組中的方程分為4種情況:系數(shù)矩陣對應(yīng)的一行中只有一項(xiàng)非零,那么該項(xiàng)對應(yīng)的

8、變量有唯一解;系數(shù)矩陣對應(yīng)的一行中不只一項(xiàng)非零,那么非零項(xiàng)對應(yīng)的變量有無窮解,該變量具有非單調(diào)性;系數(shù)矩陣對應(yīng)的一行中均為零,而常數(shù)項(xiàng)矩陣對應(yīng)的那一行不為零,那么方程組中存在超協(xié)調(diào)的情況,即某個(gè)變量同時(shí)取兩個(gè)值;系數(shù)矩陣對應(yīng)的一行中均為零,而常數(shù)項(xiàng)矩陣對應(yīng)的那一行也為零,說明方程組中有冗余情況。對第一種情況,求解與傳統(tǒng)的高斯消元法一樣,然后刪去該行。對第四種情況,刪去該行即可。重要的是對第二種、第三種情況的處理。不同的處理表達(dá)了不同的非單調(diào)、超協(xié)調(diào)策略。首先對第三種情況進(jìn)展處理。對超協(xié)調(diào)性的解決方法是維護(hù)協(xié)調(diào)性。最簡單的處理方法是刪去該行,那么方程組中消除了超協(xié)調(diào)的情況。那么相當(dāng)于當(dāng)變量同時(shí)取

9、兩個(gè)值時(shí),任意刪除其中的一個(gè)賦值。(4)處理無窮解的情況。處理完第一、第三、第四種情況后,那么新的方程組中就只剩下第二種情況。對非單調(diào)的解決方法是擴(kuò)大不完全的知識。給出一批缺省規(guī)那么(一般是對每個(gè)變量給一個(gè)缺省值)和相應(yīng)的優(yōu)先級,對于有無窮解的變量組,選擇與該變量組中變量相關(guān)的優(yōu)先級最高的缺省規(guī)那么(優(yōu)先級一樣時(shí)可按變量順序選擇或隨機(jī)選擇),參加方程組中。假設(shè)無窮解的變量組為空,那么所有變量都已有唯一解,算法完畢。否那么轉(zhuǎn)到步驟1繼續(xù)處理。由上述算法可知,當(dāng)所有變量都有唯一解時(shí),運(yùn)算與高斯消元法一樣。只是在非單調(diào)、超協(xié)調(diào)的情況下,采取了相應(yīng)的處理策略。詳細(xì)來說,在新方程中對第二種情形的處理即是

10、對非單調(diào)知識的處理,借用了非單調(diào)邏輯中缺省理論的方法。而對第三種情形的處理即是對超協(xié)調(diào)知識的處理,那么是超協(xié)調(diào)邏輯中分域邏輯的一種簡化。從理論上講,改良的高斯消元法本質(zhì)是建立在一種新的公理體系的根底上,因?yàn)樗拗屏朔匠痰暮筒畛顺詾榉匠痰墓淼倪\(yùn)用范圍,從而到達(dá)能處理非單調(diào)、超協(xié)調(diào)的情形。傳統(tǒng)的高斯消元法本質(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í)必須制止矛盾方

11、程與其它行相消。以上所述即是要限制公理的使用范圍,這種思想是從非單調(diào)、超協(xié)調(diào)邏輯中借用來的。而在單調(diào)、協(xié)調(diào)的情況下,它與傳統(tǒng)的高斯消元法完全一致。定理1:該算法在滿秩時(shí)等價(jià)于傳統(tǒng)的高斯消元法。證明:在滿秩時(shí),=n。對于改良后的消下三角矩陣法,i、j均從0出發(fā),由于矩陣中不會(huì)出現(xiàn)一列中無非零值的情形(否那么矩陣不滿秩),那么每列操作i、j均加1,當(dāng)處理完n列時(shí),i=n,j=n,消下三角矩陣法中止。故與改良前的消下三角矩陣法完全一樣。對于改良后的消上三角矩陣法,由于=n,i、j均視為從出發(fā),由于矩陣中不會(huì)出現(xiàn)一列中無非零值的情形(否那么矩陣不滿秩),那么每列操作i、j均減1,當(dāng)處理完n列時(shí),i=0

12、,j=0,消上三角矩陣法中止。故與改良前的消上三角矩陣法完全一樣。分析新方程時(shí),只存在第一種情形,處理也同傳統(tǒng)的高斯消元法一樣。不存在處理無窮解的情況。綜上所述,該算法在滿秩時(shí)等價(jià)于傳統(tǒng)的高斯消元法。定理2:該算法在非滿秩時(shí)能保證對單調(diào)、協(xié)調(diào)的變量的求解的正確性。證明:改良后的消下三角矩陣法和消上三角矩陣法中采用的不同列相消不會(huì)影響變量的值(否那么變量就不是單調(diào)、協(xié)調(diào)的)。消元后的變量處于新方程組的第一種情況中,采用的求解方法與傳統(tǒng)的高斯消元法一致,故能保證它的正確性。綜上所述,該算法在非滿秩時(shí)能保證對單調(diào)、協(xié)調(diào)的變量的求解的正確性。2應(yīng)用在工程設(shè)計(jì)的參數(shù)化造型中,圖紙的繪制是由根本拓?fù)錁?gòu)造的

13、繪制和長度、角度等約束關(guān)系的參加兩個(gè)構(gòu)成的,然后計(jì)算機(jī)自動(dòng)根據(jù)長度、角度等約束關(guān)系(即數(shù)據(jù))修正原草圖,形成準(zhǔn)確的工程圖紙。在根本拓?fù)錁?gòu)造的繪制過程中,長度、角度等詳細(xì)尺寸不必準(zhǔn)確,這樣大大節(jié)省了繪制時(shí)間,并便于修改。以下我介紹改良的高斯消元法在參數(shù)化造型中的應(yīng)用。在工程上,一些尺寸是要求準(zhǔn)確的,而有些尺寸卻不要求準(zhǔn)確,這時(shí)往往希望不輸入這些尺寸值而利用原始草圖中的粗略值,這在工程上就是處理約束缺乏的情形。另一方面,由于圖紙的復(fù)雜,輸入的各種尺寸或約束關(guān)系很可能出錯(cuò),這在工程上是約束沖突,這時(shí)希望能發(fā)現(xiàn)錯(cuò)誤。在工程上,約束大多以方程的方式表示,約束的處理從另一個(gè)方面看就是對求解方程組,而方程大

14、多可通過求導(dǎo)、求積等形式化為多元一次方程。方程組的非單調(diào)性說明約束缺乏,方程組的超協(xié)調(diào)性說明約束沖突。約束缺乏就應(yīng)該參加新的約束,約束沖突就應(yīng)該刪去某些約束,維護(hù)其協(xié)調(diào)性,都是對約束的增減。傳統(tǒng)的高斯消元法無法解決約束缺乏和約束沖突的問題。而改良后的高斯消元法卻能很容易解決這類問題。只要將原始草圖中的粗略值定為這些尺寸變量的缺省值并指定優(yōu)先級,在輸入準(zhǔn)確值時(shí)尺寸變量會(huì)按照準(zhǔn)確值進(jìn)展處理,而未輸入準(zhǔn)確值時(shí)尺寸變量會(huì)按照缺省值(原始草圖中的粗略值)進(jìn)展處理。而約束沖突時(shí),會(huì)出現(xiàn)方程組中的第三種情況。這時(shí)根據(jù)工程上的不同需要,有兩種處理方法:(1)按改良的高斯消元法中的方法刪去第三種情況的方程,以消除約束沖突情況;(2)中止處理,提示是由哪個(gè)尺寸變量或哪幾個(gè)約束方程引起的約束沖突,由用戶修改。3結(jié)論用非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想改良高斯消元法,是邏輯思想在代數(shù)領(lǐng)域的應(yīng)用。改良后的高斯消元法時(shí)間復(fù)雜度與傳統(tǒng)的高斯消元法一樣,在單調(diào)、協(xié)調(diào)的情形下等價(jià)于傳統(tǒng)的高斯消元法,具有很好的應(yīng)用價(jià)值。另外,算法中對非單調(diào)、超協(xié)調(diào)情況的處理并不是唯一的,如應(yīng)用其它非單調(diào)邏輯和超協(xié)調(diào)邏輯的思想,可擴(kuò)大算法的應(yīng)用范圍。同時(shí),該方法將非單調(diào)思想和超協(xié)調(diào)思想有機(jī)地結(jié)合在一起,對于研究如何結(jié)合