用高斯消元發(fā)解線性方程組.ppt

用高斯消元法解線性方程組,北京景山學(xué)校何江舟,GPA排名系統(tǒng)（CTSC2001）,高等院校往往采用GPA來評(píng)價(jià)學(xué)生的學(xué)術(shù)表現(xiàn)。傳統(tǒng)的排名方式是求每一個(gè)學(xué)生的平均成績(jī)，以平均成績(jī)作為依據(jù)進(jìn)行排名。對(duì)于不同的課程，選課學(xué)生的平均成績(jī)會(huì)受到課程的難易程度等因素的影響，因此這種排名方式不夠合理。為此，我們需要對(duì)排名系統(tǒng)進(jìn)行這樣的改進(jìn)：對(duì)第i門課的每一個(gè)學(xué)生的成績(jī)加上一個(gè)特定的修正值di（調(diào)整后的成績(jī)不按照百分制），使得經(jīng)過調(diào)整后，該課的平均分等于選該課的所有學(xué)生的所有課的平均分。對(duì)每一門課都這樣調(diào)整，使得上述條件對(duì)所有課程都滿足。你的任務(wù)是根據(jù)一個(gè)年級(jí)學(xué)生某學(xué)年的成績(jī)，通過上述調(diào)整，得出他們的排名。,簡(jiǎn)要分析,Ai：選修第i門課的學(xué)生的集合Bj：第j個(gè)學(xué)生選修課程的集合Gi,j：第j個(gè)學(xué)生第I門課的成績(jī)di：第i門課的修正值對(duì)于第p門課，可列出如下關(guān)系式：,這是關(guān)于di（i=1,2,n）的線性方程，我們可以整理出n個(gè)這樣的方程。,線性方程組的一般形式,先看一個(gè)例子,2-13142541207,2-1314-122.5-1.56.5,2-1314-12-0.8755.25,20.5,2.5,得出：x3=5.25/(-0.875)=-6x2=(2-(-1)x3)/4=-1x1=(1-(-1)x2-3x3)/2=9,消元過程,a1,1(1)a1,2(1)a1,n(1)b1(1)a2,1(1)a2,2(1)a2,n(1)b2(1)an,1(1)an,2(1)an,n(1)bn(1),注：用上標(biāo)(k)表示第k次消元前的狀態(tài),第1次消元，第1行的乘數(shù)：（i=2,3,n）,a1,1(1)a1,2(1)a1,n(1)b1(1)a2,2(2)a2,n(2)b2(2)an,2(2)an,n(2)bn(2),得到新的增廣矩陣：,（i,j=2,3,n）,第k次消元，第k行的乘數(shù)：（i=k+1,k+2,n）,消元過程,a1,1(1)a1,2(1)a1,n(1)b1(1)a2,2(2)a2,n(2)b2(2)ak,k(k)ak,n(k)bk(k)an,k(k)an,n(k)bn(k),第k次消元前的增廣矩陣：,增廣矩陣的變化：（i,j=k+1,k+2,n）,回代過程,a1,1(1)a1,2(1)a1,n(1)b1(1)a2,2(2)a2,n(2)b2(2)an,n(n)bn(n),最后得到的增廣矩陣：,最終結(jié)果的計(jì)算：,為什么要選主元素,前面介紹的消元法都是按照自然順序，即x1、x2、xn的順序消元的。有：,所以每一次消元的主元素都不能為0。如果按照自然順序消元的過程中出現(xiàn)的ak,k(k)=0，那么消元無法繼續(xù)進(jìn)行下去?；蛘遼ak,k(k)|很小，也會(huì)嚴(yán)重影響計(jì)算精度。,為什么要選主元素,例如（假設(shè)運(yùn)算過程中使用單精度實(shí)數(shù)）：,10-1011112,10-1011-1010-1010,解得：x1=0，x2=1這個(gè)解與第二個(gè)方程差異很大。究其原因，因?yàn)橄^程中第一個(gè)方程所乘的系數(shù)過大，使得上式“吃掉”了下式，所以在結(jié)果中根本無法體現(xiàn)下式。但如果調(diào)整一下順序：,11210-1011,11211,解得：x1=1，x2=1，這個(gè)解基本符合原方程所以每次消元的主元素的絕對(duì)值應(yīng)該盡可能大，使得與主行相乘的乘數(shù)盡可能小。,選主元素,a1,1(1)a1,2(1)a1,n(1)b1(1)a2,2(2)a2,n(2)b2(2)ak,k(k)ak,n(k)bk(k)al,k(k)al,n(k)bl(k)an,k(k)an,n(k)bn(k),進(jìn)行第k次消元時(shí)，將ak,k一下各元素（包括ak,k）進(jìn)行比較，將其中的最大者所在行與第k行交換。,無解的情況,如果在消元的過程中，增廣矩陣出現(xiàn)這樣一行：左側(cè)各未知數(shù)的系數(shù)都為0，而右側(cè)的常數(shù)項(xiàng)不為0，則意味著方程組無解。,無數(shù)組解的情況,在消元過程中，出現(xiàn)這樣一行：各未知數(shù)的系數(shù)和常數(shù)項(xiàng)都為0。這相當(dāng)于少了一個(gè)方程，也就是接下來的消元過程中，方程的個(gè)數(shù)少于未知數(shù)的個(gè)數(shù)，方程要么無解，要么有無數(shù)組解。下面討論對(duì)于這樣的方程，如何得到一組解。先看這樣一個(gè)方程：,423921142125,423900-0.5-0.5000.50.5,如果繼續(xù)消元（消第2列），必須保證a2,20，可是第2列中不存在非0的項(xiàng)。,無數(shù)組解的情況,423900-0.5-0.5000.50.5,只能夠把第3列的元素作為第2次消元的主元素，進(jìn)行消元：,423900-0.5-0.50000,第2次消元得到的元素全部為0，所以第三行元素已失去意義。x2沒有做過主元素，可隨意取值，再進(jìn)行回代，得到一組可行解。如令x2=0，x3=1，x1=1.5。對(duì)于一般的線性方程組，先進(jìn)行消元，每次消元前找到系數(shù)不完全為0的列，相應(yīng)的元素作為此次消元的主元素，直至第k次消元時(shí)，得到的新元素全部為0，這時(shí)把各未知數(shù)分為兩種：第k+1列至第n列對(duì)應(yīng)的未知數(shù)，可以將這些未知數(shù)隨意取值；第1列至第k列對(duì)應(yīng)的未知數(shù)，這些未知數(shù)的值在回代過程中確定。,性能分析,時(shí)間復(fù)雜度：O(n3)消元O(n3)選主元素：O(n2)回代O(n2),空間復(fù)雜度：O(n2)增廣矩陣O(n2)如使用全選主元素，還需一個(gè)存儲(chǔ)列與元素對(duì)應(yīng)信息的表，為O(n),精度：由于采用實(shí)數(shù)運(yùn)算，另外每一次（第一次除外）消元都要使用以前消元產(chǎn)生的結(jié)果，每一次回代都要使用消元結(jié)果和其它回代結(jié)果，所以累積誤差比較嚴(yán)重，該方法只能夠求得近似解。但是可以根據(jù)具體需要進(jìn)行相應(yīng)改進(jìn)。,整數(shù)線性方程組的精確解法,前面討論了對(duì)于一般線性方程組通過實(shí)數(shù)運(yùn)算得到近似解的算法。而在一些問題中，常常要求精確解，這里討論一下系數(shù)、常數(shù)項(xiàng)和解均為整數(shù)的線性方程組的精確解法。前面是用這種方法消元的：,顯然這里進(jìn)行的是實(shí)數(shù)運(yùn)算。,整數(shù)線性方程組的精確解法,由于不能夠保證ai,k(k)是ak,k(k)的倍數(shù)，要想消元，必須使兩行分別乘以一個(gè)乘數(shù)。,方程較多時(shí)，系數(shù)有可能越來越大，到一定程度有可能導(dǎo)致系數(shù)越界，因此要隨時(shí)對(duì)各行化簡(jiǎn)，即把這一行中所有元素除以這些元素的最大公約數(shù)。但是，無論如何，這也保證不了不會(huì)發(fā)生越界，因此這種算法一般適用于系數(shù)、未知數(shù)范圍較小，未知數(shù)個(gè)數(shù)較少的方程。,齒輪,你有一套玩具，包括許多不同尺寸的齒輪（至多20種，假定每一種齒輪有無限多個(gè)），每個(gè)齒輪最多100齒。你希望用它們構(gòu)造不同比例的傳動(dòng)裝置。一個(gè)傳動(dòng)裝置包括偶數(shù)個(gè)齒輪，這些齒輪兩兩一組互相咬合，每一組齒輪都與下一組用軸承相連。用c1、c2、cm表示每組第一個(gè)齒輪的齒數(shù)，用d1、d2、dm表示每組第二個(gè)齒輪的齒數(shù)。,例如你有3種齒輪：6齒、12齒、30齒，你需要實(shí)現(xiàn)4:5的傳動(dòng)比例，一種可行的方案是：使用4個(gè)齒輪，分2組，第1組的兩個(gè)分別為12齒、6齒，第2組的兩個(gè)分別為12齒、30齒。,簡(jiǎn)要分析,把這些齒輪的齒數(shù)設(shè)為a1、a2、an，設(shè)它們作為C類齒輪的數(shù)量分別為e1、e2、en，作為D類齒輪的數(shù)量分別為f1、f2、fn。有如下關(guān)系：,這時(shí)候我們不難發(fā)現(xiàn)，一種齒輪同時(shí)當(dāng)作C類、D類使用是一種浪費(fèi)。設(shè)xi=ei-fi，xi>0表示這種齒輪只作為C類，xi<0表示這種齒輪只作為D類。這就轉(zhuǎn)化為解xi問題。我們可以將c、d、ai這些值分解質(zhì)因數(shù)。由于ai不超過100，所以a1an能夠分解為的質(zhì)因數(shù)不超過25種。另外，如果c或d中包括這以外的質(zhì)因數(shù)，顯然問題無解。,簡(jiǎn)要分析,設(shè)gr,i為質(zhì)數(shù)r在ai的質(zhì)因數(shù)分解中的指數(shù)，cr、dr分別為質(zhì)數(shù)r在c、d中的質(zhì)因數(shù)分解中的指數(shù)。有如下關(guān)系：2(x1g2,1+x2g2,2+xng2,n)=2(c2-d2)3(x1g3,1+x2g3,2+xng3,n)=3(c3-d3)這完全可以表示為關(guān)于指數(shù)的等式，即：g2,1x1+g2,2x2+g2,nxn=c2-d2g3,1x1+g3,2x2+g3,nxn=c3-d3g97,1x1+g97,2x2+g97,nxn=c97-d97當(dāng)然還有一個(gè)約束條件：x1+x2+xn=0這就完全轉(zhuǎn)化為了解線性方程組的問題，而且這需要精確地解出這個(gè)整數(shù)線性方程組，并且還要面臨不定方程的問題，如果能夠得出整數(shù)解，則問題有解。,小結(jié),高斯消元法是一種比較簡(jiǎn)單、適用范圍較廣的有效算法，但在實(shí)際應(yīng)用中，我們往往需要具體問題具體分析，對(duì)這樣的標(biāo)準(zhǔn)算法進(jìn)行改進(jìn)，才能滿足我們的需要。,謝謝,請(qǐng)多提寶貴意見,