數(shù)值方法第三章1 線性方程組

第3章

解線性方程組的直接方法

本章要點(diǎn)高斯消元法、高斯列主元素消去法。矩陣三角分解法。迭代法。3.1引言

在工程技術(shù)、自然科學(xué)和社會(huì)科學(xué)中，經(jīng)常遇到的許多問題最終都可歸結(jié)為解線性方程組，如電學(xué)中網(wǎng)絡(luò)問題、用最小二乘法求實(shí)驗(yàn)數(shù)據(jù)的曲線擬合問題，工程中的三次樣條函數(shù)的插值問題，經(jīng)濟(jì)運(yùn)行中的投入產(chǎn)出問題以及大地測(cè)量、機(jī)械與建筑結(jié)構(gòu)的設(shè)計(jì)計(jì)算問題等等，都?xì)w結(jié)為求解線性方程組或非線性方程組的數(shù)學(xué)問題。因此線性方程組的求解對(duì)于實(shí)際問題是極其重要的。

3.1工程實(shí)例火警系統(tǒng)：如果要求解這個(gè)公式，那么，至少n次測(cè)量，形成n個(gè)方程

每個(gè)節(jié)點(diǎn)作用不一致,需要有加權(quán)。

第3章解線性方程組的直接法

常見的線性方程組是方程個(gè)數(shù)和未知量個(gè)數(shù)相同的n階線性方程組，一般形式為

簡(jiǎn)記為

Ax=b，其中

(3.1)

一般b≠0,當(dāng)系數(shù)矩陣A非奇異(即detA≠0)時(shí)，方程組〔3.1〕有惟一解。線性方程組的數(shù)值解法一般有兩類：直接法：就是經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組精確解的方法〔假設(shè)計(jì)算過程中沒有舍入誤差〕，如克萊姆法那么就是一種直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。迭代法:就是用某種極限過程去逐步逼近線性方程組的精確解的方法。也就是從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。(一般有限步內(nèi)得不到精確解)3.2解線性方程組的直接法〔高斯消去法〕

首先，克萊姆法那么在理論上有著重大意義，但在實(shí)際應(yīng)用中存在很大的困難，在線性代數(shù)中，為解決這一困難給出了高斯消元法。3.2解線性方程組的直接法〔高斯消去法〕3.2.1高斯消去法的根本思想先用一個(gè)簡(jiǎn)單實(shí)例來說明Gauss法的根本思想例3.1解線性方程組①②③解:該方程組的求解過程實(shí)際上是將一個(gè)方程乘或除以某個(gè)常數(shù),然后將兩個(gè)方程相加減,逐步減少方程中的未知數(shù),最終使每個(gè)方程只含有一個(gè)未知數(shù),從而得出所求的解。整個(gè)過程分為消元和回代兩個(gè)局部?！?〕消元過程第1步:將方程①乘上(-2)加到方程②上去,將方程①乘上加到方程③上去,這樣就消去了第2、3個(gè)方程的項(xiàng),于是就得到等價(jià)方程組④⑤第2步：將方程

④乘上加到方程

⑤上去，這樣就消去了第3個(gè)方程的項(xiàng)，于是就得到等價(jià)方程組

⑥這樣，消元過程就是把原方程組化為上三角形方程組，其系數(shù)矩陣是上三角矩陣。

〔2〕回代過程回代過程是將上述三角形方程組自下而上求解，從而求得原方程組的解：前述的消元過程相當(dāng)于對(duì)原方程組

的增廣矩陣進(jìn)行以下變換(表示增廣矩陣的第行〕同樣可得到與原方程組等價(jià)的方程組⑥由此看出,高斯消去法解方程組根本思想是設(shè)法消去方程組的系數(shù)矩陣A的主對(duì)角線下的元素,而將Ax=b化為等價(jià)的上三角形方程組,然后再通過回代過程便可獲得方程組的解。換一種說法就是用矩陣行的初等變換將原方程組系數(shù)矩陣化為上三角形矩陣,而以上三角形矩陣為系數(shù)的方程組的求解比較簡(jiǎn)單,可以從最后一個(gè)方程開始,依次向前代入求出未知變量。這種求解上三角方程組的方法稱為回代,通過一個(gè)方程乘或除以某個(gè)常數(shù),以及將兩個(gè)方程相加減,逐步減少方程中的變?cè)獢?shù),最終將方程組化成上三角方程組,一般將這一過程稱為消元,然后再回代求解。通常把按照先消元,后回代兩個(gè)步驟求解線性方程組的方法稱為高斯〔Gauss〕消去法。3.2.2高斯消去法算法構(gòu)造

我們知道,線性方程組(3.1)用矩陣形式表示為

(3.3)解線性方程組〔3.1〕的高斯〔Gauss〕消去法的消元過程就是對(duì)(3.3)的增廣矩陣進(jìn)行初等行變換。將例3.1中解三階線性方程組的消去法推廣到一般的階線性方程組并記那么高斯消去法的算法構(gòu)造歸納為：⑴消元過程,高斯消去法的消元過程由n-1步組成：第1步設(shè),把(3.3)中的第一列中元素消為零,令用乘以第1個(gè)方程后加到第個(gè)方程上去,消去第2～n個(gè)方程的未知數(shù),得到即

其中

第k步〔k=2,3,…,n-1〕繼續(xù)上述消元過程，設(shè)第k-1次消元已經(jīng)完成，得到與原方程組等價(jià)的方程組記為其中設(shè)，計(jì)算乘數(shù)用乘以第k個(gè)方后加到第i個(gè)到第n個(gè)方程中，消去第i個(gè)到第n個(gè)方程的未知數(shù)，得到只要,消元過程就可以進(jìn)行下去,直到經(jīng)過n-1次消元之后，消元過程結(jié)束，得到與原方程組等價(jià)的上三角形方程組,記為

或者寫成

即

(3.7)〔2〕回代過程就是對(duì)上三角方程組〔3.7〕自下而上逐步回代解方程組計(jì)算，即〔3〕高斯消去法的計(jì)算步驟：①消元過程;設(shè)計(jì)算②回代過程

高斯消元算法FORk=1TOn-1{ FORi=k+1TOn{ ; FORj=k+1TOn{ ;} ; }}Output………回代算法FORi=nTO1{ s=bi; FORj=iTOn{ ;} ; }}Output………選列主元算法……(4)高斯消去法流程圖(5)

Gauss消去法計(jì)算量≈①消元計(jì)算:aij(k+1)=aij(k)-mikakj(k)(i,j=k+1,k+2,…,n)第一步計(jì)算乘數(shù)mi1,mi1=ai1/a11(i=2,3,…,n)需要n-1次除法運(yùn)算,計(jì)算aij(2〕(i,j=2,3,…,n)需要(n-1)2次乘法運(yùn)算及(n-1)2次加減法運(yùn)算,消元過程：乘：

除：回代過程：運(yùn)算量：消元過程：乘：

FORk=1TOn-1{ FORi=k+1TOn{ ; FORj=k+1TOn{ ;} ; }}消元過程：乘：

除：回代過程：運(yùn)算量：3.2.3高斯消去法的適用條件定理3.1方程組系數(shù)矩陣的順序主子式全不為零那么高斯消去法能實(shí)現(xiàn)方程組的求解。證明上三角形方程組是從原方程組出發(fā)，通過逐次進(jìn)行“一行乘一數(shù)加到另一行〞而得出的，該變換不改變系數(shù)矩陣順序主子式的值。設(shè)方程組系數(shù)矩陣，其順序主子式〔m=1,2,…，n〕經(jīng)變換得到的上三角形方程組的順序主子式所以能實(shí)現(xiàn)高斯消去法求解

〔m=1,2,…，n〕定義3.1設(shè)矩陣每一行對(duì)角元素的絕對(duì)值都大于同行其他元素絕對(duì)值之和

那么稱A為嚴(yán)格對(duì)角占優(yōu)矩陣。定理3.2假設(shè)方程組的系數(shù)矩陣A為嚴(yán)格對(duì)角占優(yōu)，那么用高斯消去法求解時(shí)，全不為零。證:先考察消元過程的第1步,因A為嚴(yán)格對(duì)角占優(yōu),故故,又根據(jù)高斯消去公式得

于是再利用方程組的對(duì)角占優(yōu)性,由上式可進(jìn)一步得又由證明：

故有當(dāng)A為嚴(yán)格對(duì)角占優(yōu)時(shí),,余下的子陣仍是對(duì)角占優(yōu)的，從而又有。依次類推全不為零。定理證畢。一般線性方程組使用高斯消去法求解時(shí)，在消元過程中可能會(huì)出現(xiàn)的情況，這時(shí)消去法將無法進(jìn)行；即使，但它的絕對(duì)值很小時(shí)，用其作除數(shù)，會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長(zhǎng)和舍入誤差的擴(kuò)散，將嚴(yán)重影響計(jì)算結(jié)果的精度。實(shí)際計(jì)算時(shí)必須防止這類情況的發(fā)生。主元素消去法就可彌補(bǔ)這一缺陷。根本思想：每次消元之前在系數(shù)矩陣中按一定的范圍選取絕對(duì)值最大的元素作為主元素，以便減少舍入誤差的影響。交換原那么：通過方程或變量次序的交換，使在對(duì)角線位置上獲得絕對(duì)值盡可能大的系數(shù)作為akk(k)，稱這樣的akk(k)為主元素，并稱使用主元素的消元法為主元素法根據(jù)主元素選取范圍分為：列主元素法、行主元素法、全主元素法列主元素法：在待消元的所在列中選擇主元，經(jīng)方程的變換，置主元素于對(duì)角線位置后進(jìn)行消元的方法。全主元素：在全體待選系數(shù)中選取主元，那么得全主元素法。記筆記3.2.4高斯主元素消去法主元素法的意義例3.2用高斯消去法求以下方程組的解解：確定乘數(shù)，再計(jì)算系數(shù)假設(shè)計(jì)算在4位浮點(diǎn)十進(jìn)值的計(jì)算機(jī)上求解,那么有這時(shí)方程組的實(shí)際形式是

由此回代解出,但這個(gè)解不滿足原方程組,解是錯(cuò)誤的。這是因?yàn)樗玫某龜?shù)太小使得上式在消元過程中“吃掉〞了下式，解決這個(gè)問題的方法之一就是采用列選主元高斯消元法。即按列選絕對(duì)值大的系數(shù)作為主元素，那么將方程組中的兩個(gè)方程相交換，原方程組變?yōu)榈玫较蟮姆匠探M這時(shí)

因而方程組的實(shí)際形式是由此回代解出,這個(gè)結(jié)果是正確的可見用高斯消去法解方程組時(shí),小主元可能導(dǎo)致計(jì)算失敗,因?yàn)橛媒^對(duì)值很小的數(shù)作除數(shù),乘數(shù)很大,引起約化中間結(jié)果數(shù)量級(jí)嚴(yán)重增長(zhǎng),再舍入就使得計(jì)算結(jié)果不可靠了,故防止采用絕對(duì)值很小的主元素。以便減少計(jì)算過程中舍入誤差對(duì)計(jì)算解的影響。每一步選絕對(duì)值最大的元素為主元素，保證。Stepk:①選取②Ifik

k

then交換第k行與第ik

行;Ifjk

k

then交換第k列與第jk

列;③消元全主元素法不是按列選主元素，而是在全體待選系數(shù)中選取，那么得全主元素法。例3.3用全主元素法解以下線組

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)解：選擇所有系數(shù)中絕對(duì)值最大的40作為主元素，交換第一、二行和交換第一、二列使該主元素位于對(duì)角線的第一個(gè)位置上，得40x2-20x1+

x3=4(4)-19x2+10x1-2x3=3(5)

4x2+x1+5x3=5(6)記筆記計(jì)算m21=-19/40=0.475，m31=4/40=0.1(5)-m21(4),(6)-m31(4)消去x2

得0.5x1–1.525x3=4.9(7)3x1+4.9

x3=4.6(8)選4.9為主元素

4.9x3+3x1=4.6(9)1.525x3+0.5x1=4.9(10)計(jì)算m32=-1.525/4.9=-0.31122，(10)-m32(9)消去x2得1.43366x1=6.33161(11)記筆記保存有主元素的方程40x2-20x1+

x3=4(4)

4.9x3+3x1=4.6(9)

1.43366x1=6.33161(11)進(jìn)行回代x1=4.41634

x3=-1.76511x2=2.352303.2.4.1列主元素法列主元素法就是在待消元的所在列中選取主元，經(jīng)方程的行交換，置主元素于對(duì)角線位置后進(jìn)行消元的方法。即：在高斯消元第k步之前，做如下的事情：假設(shè)交換k行和j行行的交換，不改變方程組的解，同時(shí)又有效地克服了高斯消元的缺陷。例3.4用列主元素法解以下線性方程組

10x1-19x2-2x3=3(1)-20x1+40x2+x3=4(2)x1+4x2+5x3=5(3)解：選擇-20作為該列的主元素，-20x1+40x2+x3=3(4)

10x1-19x2-2x3=4(5)x1+4x2+5x3=5(6)計(jì)算m21

=10/-20=-0.5m31=1/-20=-0.05(5)-m21(4),(6)-m31(4)得x2–1.5x3=5(7)6x2+5.05x3=5.2(8)選6為主元素6x2+5.05x3=5.2(9)x2–1.5x3=5(10)計(jì)算m32=1/6=0.16667，

(10)-m32(9)得-2.34168x3=4.13332(11)記筆記保存有主元素的方程-20x1+40x2+x3=4(4)6x2+5.05x3=5.2(9)-2.34168x3=4.13332