數(shù)學(xué)基礎(chǔ)數(shù)論消

1、用高斯消元法解線性方程組北京景山學(xué)校 何江舟 GPA排名系統(tǒng)（CTSC2001） 高等院校往往采用GPA來評價學(xué)生的學(xué)術(shù)表現(xiàn)。傳統(tǒng)的排名方式是求每一個學(xué)生的平均成績，以平均成績作為依據(jù)進行排名。對于不同的課程，選課學(xué)生的平均成績會受到課程的難易程度等因素的影響，因此這種排名方式不夠合理。 為此，我們需要對排名系統(tǒng)進行這樣的改進：對第i門課的每一個學(xué)生的成績加上一個特定的修正值di（調(diào)整后的成績不按照百分制），使得經(jīng)過調(diào)整后，該課的平均分等于選該課的所有學(xué)生的所有課的平均分。對每一門課都這樣調(diào)整，使得上述條件對所有課程都滿足。 你的任務(wù)是根據(jù)一個年級學(xué)生某學(xué)年的成績，通過上述調(diào)整，得出他們的排名

2、簡要分析Ai：選修第i門課的學(xué)生的集合Bj：第j個學(xué)生選修課程的集合Gi,j：第j個學(xué)生第I門課的成績di：第i門課的修正值對于第p門課，可列出如下關(guān)系式： 這是關(guān)于di（i=1,2,n）的線性方程，我們可以整理出n個這樣的方程。線性方程組的一般形式a1,1x1+a1,2x2+a1,nxn=b1a2,1x1+a2,2x2+a2,nxn=b2an,1x1+an,2x2+an,nxn=bn下面是n元線性方程組的一般形式：我們可以把它表示為增廣矩陣的形式：a1,1a1,2a1,nb1a2,1a2,2a2,nb2an,1an,2an,nbn先看一個例子2-131425412072-1314-122.5

3、-1.56.52-1314-12 -0.8755.252 0.52.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)

4、 an,n (2) bn (2)得到新的增廣矩陣：ai,j(2)=ai,j(1)-mi,1a1,j(1)bi(2)=bi(1)-mi,1b1(1)（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次消元前的增廣矩陣：ai,j(k+1)=ai,j(k) -mi,kak,j(k)bi(k+1)=bi(k) -mi,kbk(k)增廣矩陣的變化：（i,j=k+1,k+

5、2,n）第k步消元的主行第k步消元的主元素回代過程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é)果的計算：為什么要選主元素 前面介紹的消元法都是按照自然順序，即x1、x2、xn的順序消元的。有： 所以每一次消元的主元素都不能為0。如果按照自然順序消元的過程中出現(xiàn)的ak,k(k)=0，那么消元無法繼續(xù)進行下去?；蛘遼 ak,k(k) |很小，也會嚴(yán)重影響計算精度。為什么要選主元素例如（假設(shè)運算過程中使用單精度實數(shù)）：10-101111210-1011-1010-1010解得：x

6、1=0，x2=1 這個解與第二個方程差異很大。究其原因，因為消元過程中第一個方程所乘的系數(shù)過大，使得上式“吃掉”了下式，所以在結(jié)果中根本無法體現(xiàn)下式。但如果調(diào)整一下順序：11210-101111211解得：x1=1，x2=1，這個解基本符合原方程 所以每次消元的主元素的絕對值應(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) 進行第k次消元時，將a

7、k,k一下各元素（包括ak,k）進行比較，將其中的最大者所在行與第k行交換。無解的情況 如果在消元的過程中，增廣矩陣出現(xiàn)這樣一行：左側(cè)各未知數(shù)的系數(shù)都為0，而右側(cè)的常數(shù)項不為0，則意味著方程組無解。無數(shù)組解的情況 在消元過程中，出現(xiàn)這樣一行：各未知數(shù)的系數(shù)和常數(shù)項都為0。這相當(dāng)于少了一個方程，也就是接下來的消元過程中，方程的個數(shù)少于未知數(shù)的個數(shù)，方程要么無解，要么有無數(shù)組解。下面討論對于這樣的方程，如何得到一組解。先看這樣一個方程：423921142125423900-0.5-0.5000.50.5 如果繼續(xù)消元（消第2列），必須保證a2,20，可是第2列中不存在非0的項。無數(shù)組解的情況423

8、900-0.5-0.5000.50.5 只能夠把第3列的元素作為第2次消元的主元素，進行消元：423900-0.5-0.50000 第2次消元得到的元素全部為0，所以第三行元素已失去意義。x2沒有做過主元素，可隨意取值，再進行回代，得到一組可行解。如令x2=0，x3=1，x1=1.5。 對于一般的線性方程組，先進行消元，每次消元前找到系數(shù)不完全為0的列，相應(yīng)的元素作為此次消元的主元素，直至第k次消元時，得到的新元素全部為0，這時把各未知數(shù)分為兩種：第k+1列至第n列對應(yīng)的未知數(shù)，可以將這些未知數(shù)隨意取值；第1列至第k列對應(yīng)的未知數(shù)，這些未知數(shù)的值在回代過程中確定。性能分析時間復(fù)雜度： O(n3

9、) 消元O(n3) 選主元素：O(n2) 回代O(n2)空間復(fù)雜度： O(n2) 增廣矩陣O(n2) 如使用全選主元素，還需一個存儲列與元素對應(yīng)信息的表，為O(n)精度： 由于采用實數(shù)運算，另外每一次（第一次除外）消元都要使用以前消元產(chǎn)生的結(jié)果，每一次回代都要使用消元結(jié)果和其它回代結(jié)果，所以累積誤差比較嚴(yán)重，該方法只能夠求得近似解。但是可以根據(jù)具體需要進行相應(yīng)改進。整數(shù)線性方程組的精確解法 前面討論了對于一般線性方程組通過實數(shù)運算得到近似解的算法。而在一些問題中，常常要求精確解，這里討論一下系數(shù)、常數(shù)項和解均為整數(shù)的線性方程組的精確解法。 前面是用這種方法消元的： ai,j(k+1)=ai,j

10、(k) -mi,kak,j(k)bi(k+1)=bi(k) -mi,kbk(k) 顯然這里進行的是實數(shù)運算。整數(shù)線性方程組的精確解法 由于不能夠保證ai,k(k)是ak,k(k)的倍數(shù)，要想消元，必須使兩行分別乘以一個乘數(shù)。ai,j(k+1)=mi,kai,j(k) -mi,kak,j(k)bi(k+1)=mi,kbi(k) -mi,kbk(k) 方程較多時，系數(shù)有可能越來越大，到一定程度有可能導(dǎo)致系數(shù)越界，因此要隨時對各行化簡，即把這一行中所有元素除以這些元素的最大公約數(shù)。 但是，無論如何，這也保證不了不會發(fā)生越界，因此這種算法一般適用于系數(shù)、未知數(shù)范圍較小，未知數(shù)個數(shù)較少的方程。齒輪 你有

11、一套玩具，包括許多不同尺寸的齒輪（至多20種，假定每一種齒輪有無限多個），每個齒輪最多100齒。你希望用它們構(gòu)造不同比例的傳動裝置。一個傳動裝置包括偶數(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ù)設(shè)為a1、a2、an，設(shè)它們作為C類齒輪的數(shù)量分別為e1、e2、en，作為D類齒輪的數(shù)量分別

12、為f1、f2、fn。有如下關(guān)系： 這時候我們不難發(fā)現(xiàn)，一種齒輪同時當(dāng)作C類、D類使用是一種浪費。設(shè)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ù)，顯然問題無解。簡要分析 設(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-d2 g3,1x1+g3,2x2+g3,nxn=c3-d3 g97,1x1+g97,