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

1、用高斯消元法解線性方程組北京景山學(xué)校 何江舟 GPA排名系統(tǒng)（CTSC2001） 高等院校往往采用GPA來(lái)評(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門(mén)課的每一個(gè)學(xué)生的成績(jī)加上一個(gè)特定的修正值di（調(diào)整后的成績(jī)不按照百分制），使得經(jīng)過(guò)調(diào)整后，該課的平均分等于選該課的所有學(xué)生的所有課的平均分。對(duì)每一門(mén)課都這樣調(diào)整，使得上述條件對(duì)所有課程都滿足。 你的任務(wù)是根據(jù)一個(gè)年級(jí)學(xué)生某學(xué)年的成績(jī)，通過(guò)上述調(diào)整，得出他們的排名

2、簡(jiǎn)要分析Ai：選修第i門(mén)課的學(xué)生的集合Bj：第j個(gè)學(xué)生選修課程的集合Gi,j：第j個(gè)學(xué)生第I門(mén)課的成績(jī)di：第i門(mén)課的修正值對(duì)于第p門(mén)課，可列出如下關(guān)系式： 這是關(guān)于di（i=1,2,n）的線性方程，我們可以整理出n個(gè)這樣的方程。線性方程組的一般形式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先看一個(gè)例子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消元過(guò)程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）消元過(guò)程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步消元的主元素回代過(guò)程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。如果按照自然順序消元的過(guò)程中出現(xiàn)的ak,k(k)=0，那么消元無(wú)法繼續(xù)進(jìn)行下去?；蛘遼 ak,k(k) |很小，也會(huì)嚴(yán)重影響計(jì)算精度。為什么要選主元素例如（假設(shè)運(yùn)算過(guò)程中使用單精度實(shí)數(shù)）：10-101111210-1011-1010-1010解得：x

6、1=0，x2=1 這個(gè)解與第二個(gè)方程差異很大。究其原因，因?yàn)橄^(guò)程中第一個(gè)方程所乘的系數(shù)過(guò)大，使得上式“吃掉”了下式，所以在結(jié)果中根本無(wú)法體現(xiàn)下式。但如果調(diào)整一下順序：11210-101111211解得：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í)，將a

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

8、900-0.5-0.5000.50.5 只能夠把第3列的元素作為第2次消元的主元素，進(jìn)行消元：423900-0.5-0.50000 第2次消元得到的元素全部為0，所以第三行元素已失去意義。x2沒(méi)有做過(guò)主元素，可隨意取值，再進(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ù)的值在回代過(guò)程中確定。性能分析時(shí)間復(fù)雜度： O(n3

9、) 消元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ì)于一般線性方程組通過(guò)實(shí)數(shù)運(yùn)算得到近似解的算法。而在一些問(wèn)題中，常常要求精確解，這里討論一下系數(shù)、常數(shù)項(xiàng)和解均為整數(shù)的線性方程組的精確解法。 前面是用這種方法消元的： ai,j(k+1)=ai,j

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

11、一套玩具，包括許多不同尺寸的齒輪（至多20種，假定每一種齒輪有無(wú)限多個(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ù)量分別

12、為f1、f2、fn。有如下關(guān)系： 這時(shí)候我們不難發(fā)現(xiàn)，一種齒輪同時(shí)當(dāng)作C類、D類使用是一種浪費(fèi)。設(shè)xi=ei-fi，xi0表示這種齒輪只作為C類，xi0表示這種齒輪只作為D類。這就轉(zhuǎn)化為解xi問(wèn)題。 我們可以將c、d、ai這些值分解質(zhì)因數(shù)。由于ai不超過(guò)100，所以a1an能夠分解為的質(zhì)因數(shù)不超過(guò)25種。另外，如果c或d中包括這以外的質(zhì)因數(shù)，顯然問(wèn)題無(wú)解。簡(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-d2 g3,1x1+g3,2x2+g3,nxn=c3-d3 g97,1x1+g97,