4線性方程組的直接解法課件

北京科技大學(xué)數(shù)理學(xué)院衛(wèi)宏儒weihr@計(jì)算方法北京科技大學(xué)數(shù)理學(xué)院計(jì)算方法第4章:線性方程組的直接解法第4章:線性方程組的直接解法關(guān)鍵詞：高斯消元法主元消元法高斯消元法與主元消元法

高斯消元法是一個(gè)古老的直接法,由它改進(jìn)得到的選主元的消元法,是目前計(jì)算機(jī)上常用于求低階稠密矩陣方程組的有效方法,其特點(diǎn)就是通過消元將一般線性方程組的求解問題轉(zhuǎn)化為三角方程組的求解問題關(guān)鍵詞：高斯消元法與主元消元法

(一)引言

為便于以下討論,把涉及到的有關(guān)名詞及問題的引出暫介紹如下:

如果未知量的個(gè)數(shù)為n,而且關(guān)于這些未知量x1,x2,…,xn

的冪次都是一次的(線性的),那么,n個(gè)方程

a11x1+a12x2+…+a1nxn=b1

┆┆

┆(1)an1x1+an2x2+…+annxn=bn

構(gòu)成一個(gè)含n個(gè)未知量的線性方程組,稱為n階線性方程組。其中,系數(shù)a11,…,a1n,a21,…,a2n,…,an1,…,ann

是給定的常數(shù);b1,…,bn

也是給定的常數(shù),通常稱為常數(shù)項(xiàng),或稱為方程組的右端.

方程組(1)也常用矩陣的形式表示,寫為

Ax=b(一)引言為便于以下討論,把涉及到的有關(guān)名詞及問題的其中,A是由系數(shù)按次序排列構(gòu)成的一個(gè)n階矩陣，稱為方程組的系數(shù)矩陣，x和b都是n維向量，稱為方程組的右端向量。.

使方程組(1)中每一個(gè)方程都成立的一組數(shù)x1*,x2*,…,xn*

稱為式(1)的解，把它記為向量的形式，稱為解向量。其中,A是由系數(shù)按次序排列構(gòu)成的一個(gè)n階矩陣，稱為方程組的系

我們總是希望方程組有解,且有唯一解.由線性代數(shù)的克萊姆(cramer)規(guī)則可知,如果方程組(1)的系數(shù)矩陣A的行列式(一般記為D=ⅠAⅠ)不等于零,那么,這個(gè)方程組有唯一解,而且它們可以表示為

xi=Di/D(i=1,…,n)

這里,Di是指D中第i列元素用右端b1,…bn代替構(gòu)成的行列式.

如果方程組(1)有唯一解,我們按上面的等式求解,就必須計(jì)算n+1個(gè)n階行列式.由行列式的定義,n階行列式包含有n!項(xiàng),每一項(xiàng)含有n個(gè)因子,計(jì)算一個(gè)n階行列式就需要做(n-1)n!次乘法.而我們一共要計(jì)算n+1個(gè)n階行列式,共需做(n2-1)n!次乘法.此外,還要做n次除法才能算出xi(i=1,…n).也就是說,用這個(gè)辦法求解就要做

N=(n2-1)n!+n次乘除法運(yùn)算,這個(gè)計(jì)算量是大得驚人的.例如,當(dāng)n=10(即求解一個(gè)含10個(gè)未知量的方程組),乘除法的運(yùn)算次數(shù)共為32659210次;我們總是希望方程組有解,且有唯一解.由線性代數(shù)的克萊當(dāng)n=40，乘除法運(yùn)算次數(shù)可達(dá)3.181049次。對于上百個(gè)未知量的方程組，次數(shù)運(yùn)算量就更大了。因此可萊姆規(guī)則在理論上盡管是完善的，但在實(shí)際計(jì)算中卻沒有什么實(shí)用價(jià)值。我們將重點(diǎn)討論求解線性方程組的一種有效的數(shù)值方法。

(二)求解線性方程組的消元法

消(元)去法是求解線性方程組

Ax=b(2)和滿秩矩陣的逆陣A-1的一種直接方法.盡管它比較古老,但它具有演算步驟,推算公式都系統(tǒng)化的特點(diǎn)(對其中選主元消去法,還可以證明是穩(wěn)定的).因此,它至今仍然是求解方程組的一種有效的方法.

消去法可以引出幾種計(jì)算方法,下面按三角形方程組和一般線性方程組的順序來討論。當(dāng)n=40，乘除法運(yùn)算次數(shù)可達(dá)3.181049次。對于上1.三角形方程組的解法

三角形方程組包括上三角形方程組和下三角形方程組，是最簡單的線性方程組之一，實(shí)際上消元法就是通過簡化一般線性方程組為三角形方程組后再求解的。上三角方程組的一般形式是：

1.三角形方程組的解法4線性方程組的直接解法課件4線性方程組的直接解法課件4線性方程組的直接解法課件2.Gauss消元法

(一)高斯消去法的求解過程：分為兩個(gè)階段:首先，把原方程組化為上三角形方程組，稱之為“消去”過程；然后，用逆次序逐一求出三角方程組(原方程組的等價(jià)方程組)的解，并稱之為“回代”過程。下面分別寫出“消去”和“回代”

兩個(gè)過程的計(jì)算步驟。

消去過程:第一步:設(shè)a110,取

做(消去第i個(gè)方程組的x1)mi1第一個(gè)方程+第i個(gè)方程

i=2,3,…n則第i個(gè)方程變?yōu)椋?.Gauss消元法(一)高斯消去法的求解過程：分為兩個(gè)因?yàn)榭傻玫谝徊较蟮姆匠探M為：i,j=2,3,…,ni,j=2,3,…,n因?yàn)閕,j=2,3,…,ni,j=2,3,…,n第二步:設(shè),取

做(消去第i個(gè)方程組的x2,i=3,4,…n)mi2第二個(gè)方程+第i個(gè)方程

i=3,4,…n類似可得第二步消元后的方程組為：第二步:設(shè),取第k步:設(shè),取

做(消去第i個(gè)方程組的xk,i=k+1,k+2,…,n)mik第k個(gè)方程+第i個(gè)方程

i=k+1,k+2,…n類似可得第k步消元后的方程組為：第k步:設(shè),取繼續(xù)下去到第n-1步消元，可將線性方程組化為如下上三角方程組:繼續(xù)下去到第n-1步消元，可將線性方程組化為如下上三角方程組4線性方程組的直接解法課件4線性方程組的直接解法課件4線性方程組的直接解法課件3.主元消元法例1:考慮如下線性方程組的Gauss消元法

求解性

2x2=12x1+3x2=2解:因?yàn)閍11=0,故此題不能用Gauss消元法求解,但交換方程組的順序后,就可用Gauss消元法求解了.3.主元消元法例1:考慮如下線性方程組的Gauss消元法例題2:討論下面方程組的解法0.0001x1+x2=1x1+x2=2

假設(shè)求解是在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上進(jìn)行。0.100010-3x1+0.1000101x2=0.10001010.1000101x1

+0.1000101x2=0.2000101解:本題的計(jì)算機(jī)機(jī)內(nèi)形式為

因?yàn)閍11=0.00010,故可用Gauss消元法求解,進(jìn)行第一次消元時(shí)有a22(1)=0.1000101-1040.1000101

(m21=a21/a11=1/0.0001=104)=0.00001105-0.1000105

(對階計(jì)算)=0.0000-0.1000105=

-0.1000105,得三角方程組

0.100010-3x1+0.1000101x2=0.1000101-0.1000105x2=-0.1000105

回代解得x2=1,x1=0

嚴(yán)重失真!

(因?yàn)楸绢}的準(zhǔn)確解為x1=10000/9999,x2=9998/9999）例題2:討論下面方程組的解法0.0001x1+x2=1

列主元基本思想及程序框圖

用高斯消去法求解線性方程組時(shí),應(yīng)避免小的主元.在實(shí)際計(jì)算中,進(jìn)行第k步消去前,應(yīng)該在第k列元素aik

(i=k,…,n)中找出絕大值最大者,例如∣a∣=max∣a∣再把第p個(gè)方程與第k個(gè)方程組進(jìn)行交換,使apk(k-1)成為主元.我們稱這個(gè)過程為選主元.由于只在第k列元素中選主元,通常也稱為按列選主元(或稱部分選主元).

如果在第k步消去前,在第k個(gè)方程到第n個(gè)方程所有的xk到xn的系數(shù)a(i=k,…,n;j=k,…,n)中,找出絕對值最大者,例如 ∣a∣=max∣a∣再交換第k,p兩個(gè)方程和第k,q兩個(gè)未知量的次序,使a成為主元.稱這個(gè)過程為完全選主元。不論是哪種方式選出主元,而后再按上面介紹的計(jì)算步驟進(jìn)行消去的計(jì)算,一般都稱為選主元的高斯消去法。在實(shí)際計(jì)算中,常用按列選主元的高斯消去法。

(k-1)(k-1)pk(k-1)ikk≦i≦n(k-1)pq(k-1)ijk≦i,j≦n(k-1)ij(k-1)pq列主元基本思想及程序框圖(k-1)(k-1)pk(k-1

用列主元消去法解線性方程組AX=b的程序框圖見右圖.圖中w作控制常數(shù),通常為比較小的正實(shí)數(shù),當(dāng)某個(gè)選出的主元或完成消元后的系數(shù)ann的絕對值小于w時(shí),就認(rèn)為detA≈0,從而終止計(jì)算.為了節(jié)省工作單元圖中還用A(k)

沖掉A,b(k)沖掉b,并注意A到的下三角部分都應(yīng)變?yōu)榱?而且在第k次消元計(jì)算式算出乘數(shù)mik后aik不再起作用,故用mik沖掉aik,回代后所得到的解放在數(shù)組b內(nèi)。k<n-1輸入n,A,b,wk=1,2,…,n-1選主元,確定ik使|aik,k(k)|=max|ai,k(k)|(k≤i≤n)ik=k|aik,k(k)|<w交換行aik,kakj(j=1,2,…n)bikbk

消元計(jì)算aikaik/akkaijaij-aikakjbibi-aikbk(i=k+1,…n)(j=k+1,..n)|ann|<wStop輸出detA=0輸出結(jié)果bi(i=1,2,…n)回代求解bnbn/annbi(bi-∑aijxj)/aii(i=n-1,..,2,1)是否是是否用列主元消去法解線性方程組AX=b的程序框圖例三用列主元消去法解方程組解

第一次消元對

因列主元素為a31(1),故先作行變換r1__r3,然后進(jìn)行消元計(jì)算可得

第二次消元對[A(2)|b(2)],因列主元素為a32(2),故先作行變換r2__r3,然后進(jìn)行消元計(jì)算可得

由此回代,得x=(1.9272,-0.69841,0.90038)T與精確解

x=(1.9273,-0.69850,0.90042)T相比較是比較準(zhǔn)確的.-0.002x1+2x2+2x3=0.4x1+0.78125x2=1.38163.996x1+5.5625x2+4x3=7.4178-0.002220.4[A(1)|b(1)]=10.7812501.38163.9965.562547.41783.9965.562547.4178[A(2)|b(2)]=0-0.61077-1.0010-0.4747102.00292.00200.40371

3.9965.562547.4178[A(3)|b(3)]=02.00292.00200.4037100-0.39050-0.35160例三用列主元消去法解方程組解第一次消元對

4、高斯消去法的計(jì)算量分析

高斯消去法的乘除總運(yùn)算分析如下：消元次數(shù)k消元乘法次數(shù)消元除法次數(shù)回代乘除法總次數(shù)

1n(n-1)n-12(n-1)(n-2)n-2...k(n-k+1)(n-k)n-k..n-12*11n(n+1)/2

故高斯消去法的計(jì)算量為N=n(n2-1)/3+n(n-1)/2+n(n+1)/2=n3/3+n2-n/3當(dāng)N充分大時(shí)為n3/34、高斯消去法的計(jì)算量分析4線性方程組的直接解法課件

5、方法的特點(diǎn)

由具體計(jì)算結(jié)果可知,全主元素法的精度優(yōu)于主元素法,這是由于全主元素是在全體系數(shù)中選主元,故它對控制舍入誤差十分有效.但全主元素法在計(jì)算過程中,需同時(shí)作行與列的互換,因而程序比較復(fù)雜,計(jì)算時(shí)間較長.列主元素法的精度雖稍低于全主元素法,但其計(jì)算簡單工作量大為減少,且計(jì)算經(jīng)驗(yàn)與理論分析均表明,它與全主元素法同樣具有良好的數(shù)值穩(wěn)定性,列主元素法是求解中小型稠密性方程組的最好方法之一。

選主元消去法(包括解線性方程組的所有直接的方法)比較適用于中小型方程組.對高階方程組,即使奇數(shù)矩陣是稀疏的,但在計(jì)算中很難保持稀疏性,因而有存儲(chǔ)量大，程序復(fù)雜等不足,所幸的是這一缺點(diǎn)可用迭代法解決.

另外,高斯選主元消去法還可技巧性的解決一些特殊線性方程組。

由于誤差的影響,計(jì)算過程中可能出現(xiàn)一些壞現(xiàn)象,要盡可能防止,表現(xiàn)在求解線性方程組的消元法比較上,則應(yīng)該注意要簡化運(yùn)算,減小運(yùn)算次數(shù),提高效率;提高數(shù)值穩(wěn)定性等.

5、方法的特點(diǎn)（三）線性方程組解對系數(shù)的敏感性

在計(jì)算過程中，由于計(jì)算機(jī)字長的有限性，不可避免地產(chǎn)生所謂的舍入誤差。同時(shí)，由于所求問題的初始數(shù)據(jù)（例如線形方程組的系數(shù)矩陣和右端項(xiàng)系數(shù)）往往是帶有一定誤差的。因此計(jì)算結(jié)果總是不可避免地帶有誤差，或者說，如果初始數(shù)據(jù)有擾動(dòng)，勢必將帶來具有一定誤差的計(jì)算結(jié)果。就拿Ax=b來說，由于觀測或計(jì)算等原因，線性方程組兩端的系數(shù)A和b都帶有誤差A(yù)和b，這樣實(shí)際建立的方程組是近似方程組(A+A)(x+x)=b+b。對近似方程組求出的解是原問題的真解x加上誤差x,即x+x。而

x是由A及b引起的，它的大小將直接影響所求解的可靠性。這種解依賴于方程組系數(shù)的誤差A(yù)及b的問題，稱為線性方程組解對系數(shù)的敏感性。（三）線性方程組解對系數(shù)的敏感性在計(jì)算過程中

方程組的系數(shù)矩陣發(fā)生微小擾動(dòng)，就有可能引起方程組性質(zhì)上的變化，這是方程組本身的“條件問題”。相對誤差關(guān)系式：設(shè)原線形方程組Ax=b

和近似方程組(A+A)(x+x)=b+b在1、A=0,b0

2、A0,b=0方程組的系數(shù)矩陣發(fā)生微小擾動(dòng)，就有可能引起方程組性一般情形

由這些關(guān)系式可看到，帶有擾動(dòng)的近似方程組中，擾動(dòng)的大小直接影響著所求解的相對誤差，故可作如下定義：定義：設(shè)A非奇異，稱||A-1||||A||為矩陣A的條件數(shù)，記為Cond(A)，即Cond(A)=||A-1||||A||.Cond(A)可反映出方程組解對系數(shù)的敏感性。對此，可通過下面的例子加以理解。一般情形由這些關(guān)系式可看到，帶有擾動(dòng)的近似方方程組

此方程組的準(zhǔn)確解為x1=0,x2=-1?，F(xiàn)將其右端加以微小的擾動(dòng)使之變?yōu)椋?/p>

經(jīng)計(jì)算可得準(zhǔn)確解為x1=2,x2=-3.

這兩個(gè)方程組的解相差很大，說明方程組的解對常數(shù)項(xiàng)b的擾動(dòng)很敏感。同時(shí)注意到||A||=4.0001,||A-1||=3.0001104,故有Cond(A)=1.23105,可見條件數(shù)很大。方程組一般來說，方程組的條件數(shù)越小，求得的解就越可靠；反之，解的可靠性就越差。通常當(dāng)從方程組Ax=b求出計(jì)算解x**后，有時(shí)用殘向量

r=b-Ax**

的大小來檢驗(yàn)x**的精度，認(rèn)為如果對某種范數(shù)||r||很小，就說明是好的。不過要記住這種處理在某些情況下是不準(zhǔn)確的。例如，對上述舉例的方程組，當(dāng)用某種方法求得計(jì)算解后，則有，顯然||r||是很小的，但與其真實(shí)解相差很大。為說明這方面的原因，我們可以把殘向量r看成是Ax=b的右端有擾動(dòng)的b，由相對誤差關(guān)系式，有：不可輕易用殘向量||r||的大小來判斷計(jì)算解的精度。一般來說，方程組的條件數(shù)越小，求得的解就越可靠；反之，解的可（四）病態(tài)方程組：如果方程組AX=b由于A或b的小擾動(dòng)而導(dǎo)致解嚴(yán)重失真，則此方程組稱為病態(tài)方程組，否則稱為良態(tài)方程組。判定一個(gè)病態(tài)方程組的簡單方法；病態(tài)方程組一般不能用解方程組的常有方法求解，而采用“迭代求精法”來計(jì)算。（列主元消元法的應(yīng)用）（四）病態(tài)方程組：如果方程組AX=b由于A或b的小擾動(dòng)而導(dǎo)致(五)、LU分解法

1、LU分解法的基本思想假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU其中L為下三角矩陣，U為上三角矩陣。這樣我們可以把線性方程組Ax=b寫成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y，則原線性方程組Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,從而求解線性方程組Ax=b的目的。(五)、LU分解法

定義：

1.LU分解:將系數(shù)矩陣A轉(zhuǎn)變成等價(jià)兩個(gè)矩陣L和U的乘積，其中L和U分別是下三角和上三角矩陣，而且要求U的對角元素都是1。2.緊湊格式:由于可以把L和U兩個(gè)矩陣壓縮到一個(gè)數(shù)組中，而且還可以存儲(chǔ)在原來的系數(shù)矩陣A的數(shù)組中。這種LU分解常被稱為緊湊格式.

由LU=A及對L和U的要求可以得到分解的計(jì)算公式。根據(jù)下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及對L和U的要求可以得到分解的計(jì)算公式。根據(jù)下式(第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量根據(jù)矩陣乘法及相等的定義,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n根據(jù)矩陣乘法及相等的定義,有得公式u1j=a1j4線性方程組的直接解法課件

在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。它的優(yōu)點(diǎn)是存儲(chǔ)量很省。L和U中的三角零元素都不必存儲(chǔ)，就是U的對角元素也因?yàn)槎际?沒有必要再記錄在程序中，這樣只用一個(gè)n階方陣就可以把L和U貯存起來。即：下三角（包括對角元）存儲(chǔ)L各元素而上三角存儲(chǔ)U的元素。再考察公式S會(huì)發(fā)現(xiàn)A中任一元素只在計(jì)算（j<=i）和（j>i)中用到一次以后就不再出現(xiàn)了，因而完全可以利用原始數(shù)組A的單元，一個(gè)個(gè)逐次貯存L或U中的相應(yīng)元素，即：

a11

a12a13…a1nu11u12u13…u1na21a22a23…a2nl21u22u23…u2na31a32a33…a3nl31l32u33…u3n

an1an2an3…annln1ln2ln3…unn………...…………......(1)(3)(5)(2n-1)(2)(4)(6)(2n)在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組?！?..采用LU分解有如下特點(diǎn)：（1）LU分解與右端向量無關(guān)。先分解，后回代。一般說來，分解的運(yùn)算次數(shù)正比于n回代求解正比與n。求解遇到多次回代時(shí)，分解的工作不必重新做。這樣節(jié)省計(jì)算時(shí)間。（2）分解按步進(jìn)行，前邊分解得到的信息為后邊所用。（3）[A]陣的存儲(chǔ)空間可利用，節(jié)省存儲(chǔ)。32采用LU分解有如下特點(diǎn)：322、特殊方程組的解法（1）追趕法（2）分解法---平方根法2、特殊方程組的解法（1）追趕法（1）追趕法---追趕法與稀疏線性方程組

追趕法仍然保持LU分解特性，它是一種特殊的LU分解。充分利用了系數(shù)矩陣的特點(diǎn)，而且使之分解更簡單，得到對三對角線性方程組的快速解法。因三對角矩陣的非零元素呈“帶狀”，我們也因此將它叫做帶狀矩陣。

（1）追趕法---追趕法與稀疏線性方程組三對角線性方程組：三對角線性方程組：設(shè)有方程組Ax=d，其中A為三對角矩陣。假設(shè)系數(shù)矩陣A滿足條件：對A作Crout分解形式為：設(shè)有方程組Ax=d，其中A為三對角矩陣。第i個(gè)分量第j個(gè)分量第i個(gè)分量第j個(gè)分量追趕法計(jì)算公式追趕法計(jì)算公式4線性方程組的直接解法課件定理

如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Doolittle分解。A=LU，則L是下帶寬為p的單位下三角矩陣，U是上帶寬為q的上三角矩陣。

定理如果上帶寬為q，下帶寬為p的n階帶狀矩陣A有Dooli4線性方程組的直接解法課件下面舉實(shí)例用追趕法來解三對角方程組。下面舉實(shí)例用追趕法來解三對角方程組。4線性方程組的直接解法課件

實(shí)際問題中，當(dāng)求解方程組的系數(shù)矩陣是對稱矩陣時(shí)，則用下面介紹的分解法可以簡化程序設(shè)計(jì)并減少計(jì)算量。從定理可知，當(dāng)矩陣A的各階順序主子式不為零時(shí)，A有唯一的Doolittle分解A=LU。此時(shí)，當(dāng)然有矩陣U的對角線元素uii

0,(i=1,2,,n),將矩陣U的每行依此提出uii，（2）.分解法實(shí)際問題中，當(dāng)求解方程組的系數(shù)矩陣是對稱矩陣時(shí)，由A=AT，得由分解的唯一性有，即：于是可得下面的結(jié)論。

由A=AT，得定理3：若對稱矩陣A各階順序主子式不為零時(shí),

則

A可以唯一分解為A=LDLT

，這里L(fēng)T為L的轉(zhuǎn)置矩陣。當(dāng)A有LDLT分解時(shí)，利用矩陣運(yùn)算法則及相等原理易得計(jì)算ljk及dk的公式為：定理3：若對稱矩陣A各階順序主子式不為零時(shí),則

A可以唯一

k=1,2,,n;j=k+1,k+2,,n為減少乘法次數(shù)，引入輔助量ujk=ljkdk,則上面公式可寫成k=1,2,,n;j=k+1,k+2,,n為減少乘法4線性方程組的直接解法課件4線性方程組的直接解法課件平方根法

設(shè)A為正定矩陣，則它的各階順序主子式均為正。由前面的定理知，A必有唯一的LDLT分解式

A=LDLT

在解對稱正定線性方程組時(shí)，系數(shù)矩陣A的LDLT分解中D又可分解為D=D1/2D1/2，這里D1/2也是對角矩陣。平方根法應(yīng)用實(shí)例與Matlab應(yīng)用實(shí)例與Matlab4線性方程組的直接解法課件見例4-12；4-13，應(yīng)用實(shí)例4-14見例4-12；4-13，應(yīng)用實(shí)例4-144線性方程組的直接解法課件北京科技大學(xué)數(shù)理學(xué)院衛(wèi)宏儒weihr@計(jì)算方法北京科技大學(xué)數(shù)理學(xué)院計(jì)算方法第4章:線性方程組的直接解法第4章:線性方程組的直接解法關(guān)鍵詞：高斯消元法主元消元法高斯消元法與主元消元法

高斯消元法是一個(gè)古老的直接法,由它改進(jìn)得到的選主元的消元法,是目前計(jì)算機(jī)上常用于求低階稠密矩陣方程組的有效方法,其特點(diǎn)就是通過消元將一般線性方程組的求解問題轉(zhuǎn)化為三角方程組的求解問題關(guān)鍵詞：高斯消元法與主元消元法

(一)引言

為便于以下討論,把涉及到的有關(guān)名詞及問題的引出暫介紹如下:

如果未知量的個(gè)數(shù)為n,而且關(guān)于這些未知量x1,x2,…,xn

的冪次都是一次的(線性的),那么,n個(gè)方程

a11x1+a12x2+…+a1nxn=b1

┆┆

┆(1)an1x1+an2x2+…+annxn=bn

構(gòu)成一個(gè)含n個(gè)未知量的線性方程組,稱為n階線性方程組。其中,系數(shù)a11,…,a1n,a21,…,a2n,…,an1,…,ann

是給定的常數(shù);b1,…,bn

也是給定的常數(shù),通常稱為常數(shù)項(xiàng),或稱為方程組的右端.

方程組(1)也常用矩陣的形式表示,寫為

Ax=b(一)引言為便于以下討論,把涉及到的有關(guān)名詞及問題的其中,A是由系數(shù)按次序排列構(gòu)成的一個(gè)n階矩陣，稱為方程組的系數(shù)矩陣，x和b都是n維向量，稱為方程組的右端向量。.

使方程組(1)中每一個(gè)方程都成立的一組數(shù)x1*,x2*,…,xn*

稱為式(1)的解，把它記為向量的形式，稱為解向量。其中,A是由系數(shù)按次序排列構(gòu)成的一個(gè)n階矩陣，稱為方程組的系

我們總是希望方程組有解,且有唯一解.由線性代數(shù)的克萊姆(cramer)規(guī)則可知,如果方程組(1)的系數(shù)矩陣A的行列式(一般記為D=ⅠAⅠ)不等于零,那么,這個(gè)方程組有唯一解,而且它們可以表示為

xi=Di/D(i=1,…,n)

這里,Di是指D中第i列元素用右端b1,…bn代替構(gòu)成的行列式.

如果方程組(1)有唯一解,我們按上面的等式求解,就必須計(jì)算n+1個(gè)n階行列式.由行列式的定義,n階行列式包含有n!項(xiàng),每一項(xiàng)含有n個(gè)因子,計(jì)算一個(gè)n階行列式就需要做(n-1)n!次乘法.而我們一共要計(jì)算n+1個(gè)n階行列式,共需做(n2-1)n!次乘法.此外,還要做n次除法才能算出xi(i=1,…n).也就是說,用這個(gè)辦法求解就要做

N=(n2-1)n!+n次乘除法運(yùn)算,這個(gè)計(jì)算量是大得驚人的.例如,當(dāng)n=10(即求解一個(gè)含10個(gè)未知量的方程組),乘除法的運(yùn)算次數(shù)共為32659210次;我們總是希望方程組有解,且有唯一解.由線性代數(shù)的克萊當(dāng)n=40，乘除法運(yùn)算次數(shù)可達(dá)3.181049次。對于上百個(gè)未知量的方程組，次數(shù)運(yùn)算量就更大了。因此可萊姆規(guī)則在理論上盡管是完善的，但在實(shí)際計(jì)算中卻沒有什么實(shí)用價(jià)值。我們將重點(diǎn)討論求解線性方程組的一種有效的數(shù)值方法。

(二)求解線性方程組的消元法

消(元)去法是求解線性方程組

Ax=b(2)和滿秩矩陣的逆陣A-1的一種直接方法.盡管它比較古老,但它具有演算步驟,推算公式都系統(tǒng)化的特點(diǎn)(對其中選主元消去法,還可以證明是穩(wěn)定的).因此,它至今仍然是求解方程組的一種有效的方法.

消去法可以引出幾種計(jì)算方法,下面按三角形方程組和一般線性方程組的順序來討論。當(dāng)n=40，乘除法運(yùn)算次數(shù)可達(dá)3.181049次。對于上1.三角形方程組的解法

三角形方程組包括上三角形方程組和下三角形方程組，是最簡單的線性方程組之一，實(shí)際上消元法就是通過簡化一般線性方程組為三角形方程組后再求解的。上三角方程組的一般形式是：

1.三角形方程組的解法4線性方程組的直接解法課件4線性方程組的直接解法課件4線性方程組的直接解法課件2.Gauss消元法

(一)高斯消去法的求解過程：分為兩個(gè)階段:首先，把原方程組化為上三角形方程組，稱之為“消去”過程；然后，用逆次序逐一求出三角方程組(原方程組的等價(jià)方程組)的解，并稱之為“回代”過程。下面分別寫出“消去”和“回代”

兩個(gè)過程的計(jì)算步驟。

消去過程:第一步:設(shè)a110,取

做(消去第i個(gè)方程組的x1)mi1第一個(gè)方程+第i個(gè)方程

i=2,3,…n則第i個(gè)方程變?yōu)椋?.Gauss消元法(一)高斯消去法的求解過程：分為兩個(gè)因?yàn)榭傻玫谝徊较蟮姆匠探M為：i,j=2,3,…,ni,j=2,3,…,n因?yàn)閕,j=2,3,…,ni,j=2,3,…,n第二步:設(shè),取

做(消去第i個(gè)方程組的x2,i=3,4,…n)mi2第二個(gè)方程+第i個(gè)方程

i=3,4,…n類似可得第二步消元后的方程組為：第二步:設(shè),取第k步:設(shè),取

做(消去第i個(gè)方程組的xk,i=k+1,k+2,…,n)mik第k個(gè)方程+第i個(gè)方程

i=k+1,k+2,…n類似可得第k步消元后的方程組為：第k步:設(shè),取繼續(xù)下去到第n-1步消元，可將線性方程組化為如下上三角方程組:繼續(xù)下去到第n-1步消元，可將線性方程組化為如下上三角方程組4線性方程組的直接解法課件4線性方程組的直接解法課件4線性方程組的直接解法課件3.主元消元法例1:考慮如下線性方程組的Gauss消元法

求解性

2x2=12x1+3x2=2解:因?yàn)閍11=0,故此題不能用Gauss消元法求解,但交換方程組的順序后,就可用Gauss消元法求解了.3.主元消元法例1:考慮如下線性方程組的Gauss消元法例題2:討論下面方程組的解法0.0001x1+x2=1x1+x2=2

假設(shè)求解是在四位浮點(diǎn)十進(jìn)制數(shù)的計(jì)算機(jī)上進(jìn)行。0.100010-3x1+0.1000101x2=0.10001010.1000101x1

+0.1000101x2=0.2000101解:本題的計(jì)算機(jī)機(jī)內(nèi)形式為

因?yàn)閍11=0.00010,故可用Gauss消元法求解,進(jìn)行第一次消元時(shí)有a22(1)=0.1000101-1040.1000101

(m21=a21/a11=1/0.0001=104)=0.00001105-0.1000105

(對階計(jì)算)=0.0000-0.1000105=

-0.1000105,得三角方程組

0.100010-3x1+0.1000101x2=0.1000101-0.1000105x2=-0.1000105

回代解得x2=1,x1=0

嚴(yán)重失真!

(因?yàn)楸绢}的準(zhǔn)確解為x1=10000/9999,x2=9998/9999）例題2:討論下面方程組的解法0.0001x1+x2=1

列主元基本思想及程序框圖

用高斯消去法求解線性方程組時(shí),應(yīng)避免小的主元.在實(shí)際計(jì)算中,進(jìn)行第k步消去前,應(yīng)該在第k列元素aik

(i=k,…,n)中找出絕大值最大者,例如∣a∣=max∣a∣再把第p個(gè)方程與第k個(gè)方程組進(jìn)行交換,使apk(k-1)成為主元.我們稱這個(gè)過程為選主元.由于只在第k列元素中選主元,通常也稱為按列選主元(或稱部分選主元).

如果在第k步消去前,在第k個(gè)方程到第n個(gè)方程所有的xk到xn的系數(shù)a(i=k,…,n;j=k,…,n)中,找出絕對值最大者,例如 ∣a∣=max∣a∣再交換第k,p兩個(gè)方程和第k,q兩個(gè)未知量的次序,使a成為主元.稱這個(gè)過程為完全選主元。不論是哪種方式選出主元,而后再按上面介紹的計(jì)算步驟進(jìn)行消去的計(jì)算,一般都稱為選主元的高斯消去法。在實(shí)際計(jì)算中,常用按列選主元的高斯消去法。

(k-1)(k-1)pk(k-1)ikk≦i≦n(k-1)pq(k-1)ijk≦i,j≦n(k-1)ij(k-1)pq列主元基本思想及程序框圖(k-1)(k-1)pk(k-1

用列主元消去法解線性方程組AX=b的程序框圖見右圖.圖中w作控制常數(shù),通常為比較小的正實(shí)數(shù),當(dāng)某個(gè)選出的主元或完成消元后的系數(shù)ann的絕對值小于w時(shí),就認(rèn)為detA≈0,從而終止計(jì)算.為了節(jié)省工作單元圖中還用A(k)

沖掉A,b(k)沖掉b,并注意A到的下三角部分都應(yīng)變?yōu)榱?而且在第k次消元計(jì)算式算出乘數(shù)mik后aik不再起作用,故用mik沖掉aik,回代后所得到的解放在數(shù)組b內(nèi)。k<n-1輸入n,A,b,wk=1,2,…,n-1選主元,確定ik使|aik,k(k)|=max|ai,k(k)|(k≤i≤n)ik=k|aik,k(k)|<w交換行aik,kakj(j=1,2,…n)bikbk

消元計(jì)算aikaik/akkaijaij-aikakjbibi-aikbk(i=k+1,…n)(j=k+1,..n)|ann|<wStop輸出detA=0輸出結(jié)果bi(i=1,2,…n)回代求解bnbn/annbi(bi-∑aijxj)/aii(i=n-1,..,2,1)是否是是否用列主元消去法解線性方程組AX=b的程序框圖例三用列主元消去法解方程組解

第一次消元對

因列主元素為a31(1),故先作行變換r1__r3,然后進(jìn)行消元計(jì)算可得

第二次消元對[A(2)|b(2)],因列主元素為a32(2),故先作行變換r2__r3,然后進(jìn)行消元計(jì)算可得

由此回代,得x=(1.9272,-0.69841,0.90038)T與精確解

x=(1.9273,-0.69850,0.90042)T相比較是比較準(zhǔn)確的.-0.002x1+2x2+2x3=0.4x1+0.78125x2=1.38163.996x1+5.5625x2+4x3=7.4178-0.002220.4[A(1)|b(1)]=10.7812501.38163.9965.562547.41783.9965.562547.4178[A(2)|b(2)]=0-0.61077-1.0010-0.4747102.00292.00200.40371

3.9965.562547.4178[A(3)|b(3)]=02.00292.00200.4037100-0.39050-0.35160例三用列主元消去法解方程組解第一次消元對

4、高斯消去法的計(jì)算量分析

高斯消去法的乘除總運(yùn)算分析如下：消元次數(shù)k消元乘法次數(shù)消元除法次數(shù)回代乘除法總次數(shù)

1n(n-1)n-12(n-1)(n-2)n-2...k(n-k+1)(n-k)n-k..n-12*11n(n+1)/2

故高斯消去法的計(jì)算量為N=n(n2-1)/3+n(n-1)/2+n(n+1)/2=n3/3+n2-n/3當(dāng)N充分大時(shí)為n3/34、高斯消去法的計(jì)算量分析4線性方程組的直接解法課件

5、方法的特點(diǎn)

由具體計(jì)算結(jié)果可知,全主元素法的精度優(yōu)于主元素法,這是由于全主元素是在全體系數(shù)中選主元,故它對控制舍入誤差十分有效.但全主元素法在計(jì)算過程中,需同時(shí)作行與列的互換,因而程序比較復(fù)雜,計(jì)算時(shí)間較長.列主元素法的精度雖稍低于全主元素法,但其計(jì)算簡單工作量大為減少,且計(jì)算經(jīng)驗(yàn)與理論分析均表明,它與全主元素法同樣具有良好的數(shù)值穩(wěn)定性,列主元素法是求解中小型稠密性方程組的最好方法之一。

選主元消去法(包括解線性方程組的所有直接的方法)比較適用于中小型方程組.對高階方程組,即使奇數(shù)矩陣是稀疏的,但在計(jì)算中很難保持稀疏性,因而有存儲(chǔ)量大，程序復(fù)雜等不足,所幸的是這一缺點(diǎn)可用迭代法解決.

另外,高斯選主元消去法還可技巧性的解決一些特殊線性方程組。

由于誤差的影響,計(jì)算過程中可能出現(xiàn)一些壞現(xiàn)象,要盡可能防止,表現(xiàn)在求解線性方程組的消元法比較上,則應(yīng)該注意要簡化運(yùn)算,減小運(yùn)算次數(shù),提高效率;提高數(shù)值穩(wěn)定性等.

5、方法的特點(diǎn)（三）線性方程組解對系數(shù)的敏感性

在計(jì)算過程中，由于計(jì)算機(jī)字長的有限性，不可避免地產(chǎn)生所謂的舍入誤差。同時(shí)，由于所求問題的初始數(shù)據(jù)（例如線形方程組的系數(shù)矩陣和右端項(xiàng)系數(shù)）往往是帶有一定誤差的。因此計(jì)算結(jié)果總是不可避免地帶有誤差，或者說，如果初始數(shù)據(jù)有擾動(dòng)，勢必將帶來具有一定誤差的計(jì)算結(jié)果。就拿Ax=b來說，由于觀測或計(jì)算等原因，線性方程組兩端的系數(shù)A和b都帶有誤差A(yù)和b，這樣實(shí)際建立的方程組是近似方程組(A+A)(x+x)=b+b。對近似方程組求出的解是原問題的真解x加上誤差x,即x+x。而

x是由A及b引起的，它的大小將直接影響所求解的可靠性。這種解依賴于方程組系數(shù)的誤差A(yù)及b的問題，稱為線性方程組解對系數(shù)的敏感性。（三）線性方程組解對系數(shù)的敏感性在計(jì)算過程中

方程組的系數(shù)矩陣發(fā)生微小擾動(dòng)，就有可能引起方程組性質(zhì)上的變化，這是方程組本身的“條件問題”。相對誤差關(guān)系式：設(shè)原線形方程組Ax=b

和近似方程組(A+A)(x+x)=b+b在1、A=0,b0

2、A0,b=0方程組的系數(shù)矩陣發(fā)生微小擾動(dòng)，就有可能引起方程組性一般情形

由這些關(guān)系式可看到，帶有擾動(dòng)的近似方程組中，擾動(dòng)的大小直接影響著所求解的相對誤差，故可作如下定義：定義：設(shè)A非奇異，稱||A-1||||A||為矩陣A的條件數(shù)，記為Cond(A)，即Cond(A)=||A-1||||A||.Cond(A)可反映出方程組解對系數(shù)的敏感性。對此，可通過下面的例子加以理解。一般情形由這些關(guān)系式可看到，帶有擾動(dòng)的近似方方程組

此方程組的準(zhǔn)確解為x1=0,x2=-1?，F(xiàn)將其右端加以微小的擾動(dòng)使之變?yōu)椋?/p>

經(jīng)計(jì)算可得準(zhǔn)確解為x1=2,x2=-3.

這兩個(gè)方程組的解相差很大，說明方程組的解對常數(shù)項(xiàng)b的擾動(dòng)很敏感。同時(shí)注意到||A||=4.0001,||A-1||=3.0001104,故有Cond(A)=1.23105,可見條件數(shù)很大。方程組一般來說，方程組的條件數(shù)越小，求得的解就越可靠；反之，解的可靠性就越差。通常當(dāng)從方程組Ax=b求出計(jì)算解x**后，有時(shí)用殘向量

r=b-Ax**

的大小來檢驗(yàn)x**的精度，認(rèn)為如果對某種范數(shù)||r||很小，就說明是好的。不過要記住這種處理在某些情況下是不準(zhǔn)確的。例如，對上述舉例的方程組，當(dāng)用某種方法求得計(jì)算解后，則有，顯然||r||是很小的，但與其真實(shí)解相差很大。為說明這方面的原因，我們可以把殘向量r看成是Ax=b的右端有擾動(dòng)的b，由相對誤差關(guān)系式，有：不可輕易用殘向量||r||的大小來判斷計(jì)算解的精度。一般來說，方程組的條件數(shù)越小，求得的解就越可靠；反之，解的可（四）病態(tài)方程組：如果方程組AX=b由于A或b的小擾動(dòng)而導(dǎo)致解嚴(yán)重失真，則此方程組稱為病態(tài)方程組，否則稱為良態(tài)方程組。判定一個(gè)病態(tài)方程組的簡單方法；病態(tài)方程組一般不能用解方程組的常有方法求解，而采用“迭代求精法”來計(jì)算。（列主元消元法的應(yīng)用）（四）病態(tài)方程組：如果方程組AX=b由于A或b的小擾動(dòng)而導(dǎo)致(五)、LU分解法

1、LU分解法的基本思想假定我們能把矩陣A寫成下列兩個(gè)矩陣相乘的形式：A=LU其中L為下三角矩陣，U為上三角矩陣。這樣我們可以把線性方程組Ax=b寫成

Ax=（LU)x=L(Ux)=bLy=b令Ux=y，則原線性方程組Ax=bUx=y于是可首先求解向量y使Ly=b然后求解Ux=y,從而求解線性方程組Ax=b的目的。(五)、LU分解法

定義：

1.LU分解:將系數(shù)矩陣A轉(zhuǎn)變成等價(jià)兩個(gè)矩陣L和U的乘積，其中L和U分別是下三角和上三角矩陣，而且要求U的對角元素都是1。2.緊湊格式:由于可以把L和U兩個(gè)矩陣壓縮到一個(gè)數(shù)組中，而且還可以存儲(chǔ)在原來的系數(shù)矩陣A的數(shù)組中。這種LU分解常被稱為緊湊格式.

由LU=A及對L和U的要求可以得到分解的計(jì)算公式。根據(jù)下式(Doolittle分解)：1

l211

l31l321

………ln1ln2…

lnn-11

u11u12u13…u1nu22u23…u2n

…un-1nu(n-1)n

unn=…………aannLUn1an3…a11a12a13…a1na21a22

a23…a2na31a32

a33…

a3n

an2A………由LU=A及對L和U的要求可以得到分解的計(jì)算公式。根據(jù)下式(第j個(gè)分量第i個(gè)分量第j個(gè)分量第i個(gè)分量根據(jù)矩陣乘法及相等的定義,有

得公式