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

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