計(jì)算方法課件

北京科技大學(xué)應(yīng)用學(xué)院數(shù)力系衛(wèi)宏儒Weihr168@

計(jì)算方法課程性質(zhì)和計(jì)劃（續(xù)）計(jì)算方法概論泛函分析中若干概念矩陣特征值與特征向量的計(jì)算最佳平方逼近數(shù)值逼近方法方程組及非線性方程的數(shù)值解法常微分方程初值問(wèn)題的數(shù)值解法非線性方程的求根方法插值法數(shù)值積分與數(shù)值微分線性方程組的解法第三章：線性方程組的解法一、線性方程組的直接解法

(一)引言

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

使方程組(1)中每一個(gè)方程都成立的一組數(shù)x1*,x2*,…,xn*稱為式(1)的解，把它記為向量的形式，稱為解向量。

我們總是希望方程組有解,且有唯一解.由線性代數(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).也就是說(shuō),用這個(gè)辦法求解就要做

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

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

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

消去法可以引出幾種計(jì)算方法,下面按三角形方程組和一般線性方程組的順序來(lái)討論。因?yàn)榭傻玫谝徊较蟮姆匠探M為：i,j=2,3,…,ni,j=2,3,…,n第二步:設(shè),取做(消去第i個(gè)方程組的x2,i=3,4,…n)mi2第二個(gè)方程+第i個(gè)方程i=3,4,…n類似可得第二步消元后的方程組為：第k步:設(shè),取做(消去第i個(gè)方程組的xk,i=k+1,k+2,…,n)mik第k個(gè)方程+第i個(gè)方程

i=k+1,k+2,…n類似可得第k步消元后的方程組為：繼續(xù)下去到第n-1步消元，可將線性方程組化為如下上三角方程組:3.主元消元法例1:考慮如下線性方程組的Gauss消元法求解性2x2=12x1+3x2=2解:因?yàn)閍11=0,故此題不能用Gauss消元法求解,但交換方程組的順序后,就可用Gauss消元法求解了.

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

用高斯消去法求解線性方程組時(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è)過(guò)程為選主元.由于只在第k列元素中選主元,通常也稱為按列選主元(或稱部分選主元).

如果在第k步消去前,在第k個(gè)方程到第n個(gè)方程所有的xk到xn的系數(shù)a(i=k,…,n;j=k,…,n)中,找出絕對(duì)值最大者,例如 ∣a∣=max∣a∣再交換第k,p兩個(gè)方程和第k,q兩個(gè)未知量的次序,使a成為主元.稱這個(gè)過(guò)程為完全選主元。不論是哪種方式選出主元,而后再按上面介紹的計(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

用列主元消去法解線性方程組AX=b的程序框圖見(jiàn)右圖.圖中w作控制常數(shù),通常為比較小的正實(shí)數(shù),當(dāng)某個(gè)選出的主元或完成消元后的系數(shù)ann的絕對(duì)值小于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)是否是是否

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/3

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

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

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

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

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

2、A0,b=0一般情形

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

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

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

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

定義：

1.LU分解:將系數(shù)矩陣A轉(zhuǎn)變成等價(jià)兩個(gè)矩陣L和U的乘積，其中L和U分別是下三角和上三角矩陣，而且要求U的對(duì)角元素都是1。2.緊湊格式:由于可以把L和U兩個(gè)矩陣壓縮到一個(gè)數(shù)組中，而且還可以存儲(chǔ)在原來(lái)的系數(shù)矩陣A的數(shù)組中。這種LU分解常被稱為緊湊格式.由LU=A及對(duì)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………第j個(gè)分量第i個(gè)分量根據(jù)矩陣乘法及相等的定義,有

得公式u1j=a1jj=1,2,…,nli1=ai1/u11i=2,3,…,n

在計(jì)算機(jī)程序中常常用這種方法解線性代數(shù)方程組。它的優(yōu)點(diǎn)是存儲(chǔ)量很省。L和U中的三角零元素都不必存儲(chǔ)，就是U的對(duì)角元素也因?yàn)槎际?沒(méi)有必要再記錄在程序中，這樣只用一個(gè)n階方陣就可以把L和U貯存起來(lái)。即：下三角（包括對(duì)角元）存儲(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)采用LU分解有如下特點(diǎn)：（1）LU分解與右端向量無(wú)關(guān)。先分解，后回代。一般說(shuō)來(lái)，分解的運(yùn)算次數(shù)正比于n回代求解正比與n。求解遇到多次回代時(shí)，分解的工作不必重新做。這樣節(jié)省計(jì)算時(shí)間。（2）分解按步進(jìn)行，前邊分解得到的信息為后邊所用。（3）[A]陣的存儲(chǔ)空間可利用，節(jié)省存儲(chǔ)。322、特殊方程組的解法（1）.追趕法（2）.LDLT分解法---平方根法（1）.追趕法---追趕法與稀疏線性方程組

追趕法仍然保持LU分解特性，它是一種特殊的LU分解。充