數(shù)值積分（基于MATLAB）課件 chapter3 解線性方程組的直接方法；chapter3 線性代數(shù)方程組的迭代法；chapter4-數(shù)值積分與數(shù)值微分

第3章

解線性方程組的直接方法

內(nèi)容要點(diǎn)高斯消元法、高斯列主元素消去法。矩陣三角分解法、追趕法。向量和矩陣的范數(shù)。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)出問題以及大地測量、機(jī)械與建筑結(jié)構(gòu)的設(shè)計(jì)計(jì)算問題等等，都?xì)w結(jié)為求解線性方程組或非線性方程組的數(shù)學(xué)問題。因此線性方程組的求解對(duì)于實(shí)際問題是極其重要的。

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

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

簡記為

Ax=b，其中

(3.1)

一般b≠0,當(dāng)系數(shù)矩陣A非奇異(即detA≠0)

時(shí)，方程組（3.1）有惟一解。

線性方程組的數(shù)值解法一般有兩類：直接法：經(jīng)過有限步算術(shù)運(yùn)算，可求得方程組精確解的方法（若計(jì)算過程中沒有舍入誤差），如克萊姆法則就是一種直接法，直接法中具有代表性的算法是高斯(Gauss)消去法。迭代法:

用某種極限過程去逐步逼近線性方程組的精確解的方法。也就是從解的某個(gè)近似值出發(fā)，通過構(gòu)造一個(gè)無窮序列去逼近精確解的方法。(一般有限步內(nèi)得不到精確解)3.2高斯消去法

高斯消去法的基本思想先用一個(gè)簡單實(shí)例來說明Gauss法的基本思想例3.1解線性方程組

①②③解:

該方程組的求解過程實(shí)際上是將一個(gè)方程乘或除以某個(gè)常數(shù),然后將兩個(gè)方程相加減,逐步減少方程中的未知數(shù),最終使每個(gè)方程只含有一個(gè)未知數(shù),從而得出所求的解。整個(gè)過程分為消元和回代兩個(gè)部分。

（1）消元過程第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ù)的方程組的求解比較簡單,可以從最后一個(gè)方程開始,依次向前代入求出未知變量。這種求解上三角方程組的方法稱為回代,通過一個(gè)方程乘或除以某個(gè)常數(shù),以及將兩個(gè)方程相加減,逐步減少方程中的變元數(shù),最終將方程組化成上三角方程組,一般將這一過程稱為消元,然后再回代求解。通常把按照先消元,后回代兩個(gè)步驟求解線性方程組的方法稱為高斯（Gauss）消去法。

高斯消去法算法

我們知道,線性方程組(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ì)算②回代過程

(4)Gauss消去法計(jì)算量≈

消元計(jì)算:aij(k+1)=aij(k)-mik

akj(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)算第k步加減法次數(shù)乘法次數(shù)除法次數(shù)123…n-1(n-1)2(n-2)2(n-3)2…1(n-1)2(n-2)2(n-3)2…1(n-1)(n-2)(n-3)…1合計(jì)n(n-1)(2n-1)/6n(n-1)(2n-1)/6n(n-1)/2乘除法次數(shù)：MD=n(n-1)(2n-1)/6+n(n-1)/2=1/3n(n2-1)加減法次數(shù)：AS=n(n-1)(2n-1)/6高斯消去法的適用條件

定理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ù)矩陣A為嚴(yán)格對(duì)角占優(yōu)，則用高斯消去法求解時(shí)，全不為零。

一般線性方程組使用高斯消去法求解時(shí)，在消元過程中可能會(huì)出現(xiàn)的情況，這時(shí)消去法將無法進(jìn)行；即使，但它的絕對(duì)值很小時(shí)，用其作除數(shù)，會(huì)導(dǎo)致其他元素?cái)?shù)量級(jí)的嚴(yán)重增長和舍入誤差的擴(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.2高斯主元素消去法主元素法的意義例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)?/p>

得到消元后的方程組這時(shí)

因而方程組的實(shí)際形式是由此回代解出,這個(gè)結(jié)果是正確的

可見用高斯消去法解方程組時(shí),小主元可能導(dǎo)致計(jì)算失敗,因?yàn)橛媒^對(duì)值很小的數(shù)作除數(shù),乘數(shù)很大,引起約化中間結(jié)果數(shù)量級(jí)嚴(yán)重增長,再舍入就使得計(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.35230

列主元素法列主元素法就是在待消元的所在列中選取主元，經(jīng)方程的行交換，置主元素于對(duì)角線位置后進(jìn)行消元的方法。即：在高斯消元第k步之前，做如下的事情：若交換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(11)進(jìn)行回代x3=-1.76511x2=2.35230x1=4.41634記筆記

列選主元素的計(jì)算方法與高斯消去法完全一樣,不同的是在每步消元之前要按列選出主元。例3.5用矩陣的初等行變換求解解方程組

解:用矩陣的初等行變換求解,對(duì)增廣矩陣

(下面帶下劃線元素為主元素)所以，等價(jià)的三角形方程組為：回代求解，得：3.3矩陣三角分解法

矩陣三角分解法是高斯消去法解線性方程組的一種變形解法

3.3.1矩陣三角分解原理

應(yīng)用高斯消去法解n階線性方程組Ax=b,經(jīng)過n步消元之后,得出一個(gè)等價(jià)的上三角型方程組A(n)x=b(n),對(duì)上三角形方程組用逐步回代就可以求出解來。上述過程可通過矩陣分解來實(shí)現(xiàn)。將非奇異陣A分解成一個(gè)下三角陣L和一個(gè)上三角陣U的乘積

A=LU

稱為對(duì)矩陣A的三角分解，又稱LU分解其中方程組Ax=b的系數(shù)矩陣A經(jīng)過順序消元逐步化為上三角型A(n),相當(dāng)于用一系列初等變換左乘A的結(jié)果。事實(shí)上，第1列消元將A(1)=A化為A(2)，若令：則根據(jù)距陣左乘有L1A(1)=A(2)第2列消元將A(2)化為A(3)，若令：經(jīng)計(jì)算可知L2A(2)=A(3),依此類推,一般有LkA(k)=A(k+1)mi1=a(1)

i1/a(1)

11i=2,3,……n于是矩陣經(jīng)過消元化為上三角陣的過程可表示為上述矩陣是一類初等矩陣,它們都是單位下三角陣，且其逆矩陣也是單位下三角陣,只需將改為,就得到。即

于是有

其中L為由乘數(shù)構(gòu)成的單位下三角陣，U為上三角陣，由此可見，在的條件下，高斯消去法實(shí)質(zhì)上是將方程組的系數(shù)矩陣A分解為兩個(gè)三角矩陣的乘積A=LU。這種把非奇異矩陣A分解成一個(gè)下三角矩陣L和一個(gè)上三角矩陣U的乘積稱為矩陣的三角分解，又稱LU分解。顯然，如果,由行列式的性質(zhì)知，方程組系數(shù)矩陣A的前n-1個(gè)順序主子矩陣非奇異，即順序主子式不等于零，即其中（A的主子陣）

反之,可用歸納法證明,如果A的順序主子式則于是得到下述定理：

定理3.5設(shè)。如果A順序各階主子式,,則A可惟一地分解成一個(gè)單位下三角陣L和一個(gè)非奇異的上三角陣U的乘積。證：由于A各階主子式不為零,則消元過程能進(jìn)行到底,前面已證明將方程組的系數(shù)矩陣A用初等變換的方法分解成兩個(gè)三角矩陣的乘積A=LU的過程。

現(xiàn)僅證明分解的惟一性。設(shè)A有兩種LU分解其中為單位下三角陣，為上三角陣

∵A的行列式均為非奇異矩陣,有上式兩邊左邊同乘，右邊同乘得上式左邊為單位下三角陣,右邊為上三角陣,故應(yīng)為單位陣,即惟一性得證。

把A分解成一個(gè)單位下三角陣L和一個(gè)上三角陣U的乘積稱為杜利特爾（Doolittle）分解。其中

3.3.2用三角分解法解方程組求解線性方程組Ax=b時(shí),先對(duì)非奇異矩陣A進(jìn)行LU分解使A=LU，那么方程組就化為

LUx=b從而使問題轉(zhuǎn)化為求解兩個(gè)簡單的的三角方程組

Ly=b求解yUx=y求解x這就是求解線性方程組的三角分解法的基本思想。下面只介紹杜利特爾（Doolittle）分解法。設(shè)A=LU為

由矩陣乘法規(guī)則

由此可得U的第1行元素和L的第1列元素

再確定U的第k行元素與L的第k列元素,對(duì)于k=2,3,…,n計(jì)算：①

計(jì)算U的第k行元素

（j=k,k+1,…,n）

②計(jì)算L的第k列元素（i=k,k+1,…,n）

（j=k,k+1,…,n）

①計(jì)算U的第k行元素

固定k，對(duì)j=i,i+1,…,n

有（j=k,k+1,…,n）

②計(jì)算L的第k列元素同理，固定k，對(duì)i=k,k+1,…,n

有（i=k,k+1,…,n）

利用上述計(jì)算公式便可逐步求出U與L的各元素求解Ly=b,即計(jì)算:

求解Ux=y,即計(jì)算：

顯然,當(dāng)時(shí),解Ax=b直接三角分解法計(jì)算才能完成。設(shè)A為非奇異矩陣,當(dāng)時(shí)計(jì)算將中斷或者當(dāng)絕對(duì)值很小時(shí)，按分解公式計(jì)算可能引起舍入誤差的積累，因此可采用與列主元消去法類似的方法，對(duì)矩陣進(jìn)行行交換，則再實(shí)現(xiàn)矩陣的三角分解。用直接三角分解法解Ax=b大約需要次乘除法。

三角分解法的存放元素的方法：的元素存放在A的，即uuuuuuUlllLúúú?ùêêê?é=úúú?ùêêê?é=332322131211323121111相應(yīng)位置。優(yōu)點(diǎn)：不用存儲(chǔ)中間量，適合于計(jì)算機(jī)計(jì)算。說明：以上計(jì)算方法實(shí)際上是消去法的變形—

緊湊格式。例3.8用三角分解法解方程組

求解

Ly=b得

y=[

2，2，1]T

求解Ux=y得x=[-1，0，1]T所以方程組的解為

設(shè)，試將A進(jìn)行三角分解。解：由高斯消去法得到

用直接三角分解法解方程組。解：記筆記3.4向量和矩陣的范數(shù)

為了研究線性方程組近似解的誤差估計(jì)和迭代法的收斂性,有必要對(duì)向量及矩陣的“大小”引進(jìn)某種度量----范數(shù)的概念。向量范數(shù)是用來度量向量長度的,它可以看成是二、三維解析幾何中向量長度概念的推廣。用Rn表示n維實(shí)向量空間。記筆記3.4向量和矩陣的范數(shù)定義3.2

對(duì)任一向量XRn,按照一定規(guī)則確定一個(gè)實(shí)數(shù)與它對(duì)應(yīng),該實(shí)數(shù)記為||X||,若||X||滿足下面三個(gè)性質(zhì):(1)||X||

0；||X||=0當(dāng)且僅當(dāng)X=0；(2)對(duì)任意實(shí)數(shù)，||X||=|

|||X||；對(duì)任意向量YRn，||X+Y||||X||+||Y||

則稱該實(shí)數(shù)||X||為向量X的范數(shù)在Rn中，常用的幾種范數(shù)有：記筆記其中x1,x2,…,xn分別是X的n個(gè)分量。以上定義的范數(shù)分別稱為1-范數(shù)，2-范數(shù)和-范數(shù)可以驗(yàn)證它們都是滿足范數(shù)性質(zhì)的，其中是由內(nèi)積導(dǎo)出的向量范數(shù)。3.4向量和矩陣的范數(shù)當(dāng)不需要指明使用哪一種向量范數(shù)時(shí)，就用記號(hào)||.||泛指任何一種向量范數(shù)。有了向量的范數(shù)就可以用它來衡量向量的大小和表示向量的誤差。設(shè)x*為Ax=b的精確解，x為其近似解，則其絕對(duì)誤差可表示成||x-x*||，其相對(duì)誤差可表示成記筆記3.4向量和矩陣的范數(shù)或例3.10設(shè)x=(1,0,-1,2)T,計(jì)算

解:=1+0+|-1|+2=4定理7對(duì)于任意向量x,有證:∵

∴即

當(dāng)p→∞，

∴定義3.4(向量序列的極限)設(shè)為中的一向量序列，,記。如果(i=1,2,…,n)，則稱收斂于向量，記為

定理8（向量范數(shù)的等價(jià)性）設(shè)為上任意兩種向量范數(shù),則存在常數(shù)C1,C2>0,使得對(duì)任意恒有定理

9

其中為向量中的任一種范數(shù)。

證由于

而對(duì)于上的任一種范數(shù),由定理7知存在常數(shù)C1，C2，使于是可得從而定理得證。定義3.5（矩陣的范數(shù)）如果矩陣的某個(gè)

非負(fù)的實(shí)值函數(shù)，滿足則稱是上的一個(gè)矩陣范數(shù)(或模)定義3.6（矩陣的算子范數(shù)）設(shè)n維向量X和

n階方陣A，當(dāng)給定一種向量范數(shù)||X||

時(shí)，則定義

為矩陣的范數(shù)，并稱為矩陣的算子范數(shù)。矩陣范數(shù)定義的另一種方法從定義可以看出，矩陣范數(shù)和向量范數(shù)密切相關(guān)。矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗(yàn)證。(1)設(shè)A≠0,x≠0,使Ax≠0,根據(jù)向量范數(shù)的性質(zhì)

Ax>0,所以>0x≠0,使

Ax=0,則=0當(dāng)A=0時(shí),矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗(yàn)證∴(2)根據(jù)向量范數(shù)的性質(zhì)矩陣范數(shù)的性質(zhì)可由向量范數(shù)定義直接驗(yàn)證(3)定義3.7（矩陣的譜半徑）設(shè)的特征值為,稱為A的譜半徑。例3.11計(jì)算方陣

的三種常用范數(shù)例3.12計(jì)算方陣

的三種范數(shù)

解先計(jì)算

所以

,從而

定理11設(shè)A為n階方陣,則對(duì)任意矩陣范數(shù)都有證:設(shè)為A的特征值，x是對(duì)應(yīng)于的特征向量,則λx=Ax。兩端取范數(shù)并依據(jù)其性質(zhì)得由于x≠0，故，所以本章小結(jié)

本章介紹了解線性方程組的直接法。直接法是一種計(jì)算量小而精度高的方法。直接法中具有代表性的算法是高斯（Gauss）消去法（在第一章提到的克萊姆算法也是一種直接法，但該算法用于高階方程組時(shí)計(jì)算量太大而不實(shí)用），其它算法大都是它的變型，這類方法是解具有稠密矩陣或非結(jié)構(gòu)矩陣（零元分布無規(guī)律）方程組的有效方法。

選主元的算法有很好的數(shù)值穩(wěn)定性。從計(jì)算簡單出發(fā)實(shí)際中多選用列主元法。解三對(duì)角矩陣方程組（A的對(duì)角元占優(yōu)）的追趕法，解對(duì)稱正定矩陣方程組的平方根法都是三角分解法，且都是數(shù)值穩(wěn)定的方法，這些方法不選主元素，也具有較高的精度。向量、矩陣的范數(shù)、矩陣的條件數(shù)和病態(tài)方程組的概念，是數(shù)值計(jì)算中一些基本概念。線性方程組的病態(tài)程度是其本身的固有特性，因此即使用數(shù)值穩(wěn)定的方法求解，也難以克服嚴(yán)重病態(tài)導(dǎo)致的解的失真。在病態(tài)不十分嚴(yán)重時(shí)，用雙精度求解可減輕病態(tài)的影響

在實(shí)際應(yīng)用中如何選擇算法是一個(gè)重要問題，往往從三個(gè)方面考慮：

①解的精度高；

②計(jì)算量?。?/p>

③所需計(jì)算機(jī)內(nèi)存小。但這些條件相互間是矛盾而不能兼顧的，因此實(shí)際計(jì)算時(shí)應(yīng)根據(jù)問題的特點(diǎn)和要求及所用計(jì)算機(jī)的性能來選擇算法。一般說，系數(shù)矩陣為中、小型滿矩陣，用直接法較好；當(dāng)系數(shù)矩陣為大型、稀疏矩陣時(shí)，有效的解法是第四章要討論的迭代法。

第3章3.5迭代法迭代法基礎(chǔ)

問題

在實(shí)際應(yīng)用中遇到的系數(shù)矩陣多為大型稀疏矩陣，如用求解線性方程組的直接法求解，在計(jì)算機(jī)上會(huì)耗費(fèi)大量的時(shí)間和存儲(chǔ)單元。在許多應(yīng)用問題中使用迭代法。思路將改寫為等價(jià)形式，建立迭代。從初值出發(fā)，得到序列。研究內(nèi)容：

如何建立迭代格式？

收斂速度？

向量序列的收斂條件？

誤差估計(jì)？一般迭代法迭代格式的構(gòu)造把矩陣A分裂為

則將上式寫為迭代過程這種迭代過程稱為逐次逼近法，B稱為迭代矩陣。收斂性定義：若稱逐次逼近法收斂，否則，稱逐次逼近法不收斂或發(fā)散。給定初值就得到向量序列問題：定理1

任意給定初始向量x0，如果由逐次逼近法產(chǎn)生的向量序列收斂于向量x*，那么，x*是方程組x=Bx+g的解。證明：是否為方程組Ax=b的解？迭代法的收斂條件定理

當(dāng)k

時(shí)，Bk0

(B)<1定理2

設(shè)線性方程組x=Bx+g有惟一解，那么逐次逼近法對(duì)任意初始向量X０收斂的充分必要條件是迭代矩陣B的譜半徑

(B)<1。

證明：因此，注：要檢驗(yàn)一個(gè)矩陣的譜半徑小于1比較困難，所以我們希望用別的辦法判斷收斂性。

定理3

若逐次逼近法的迭代矩陣滿足‖B‖<1，那么逐次逼近法收斂。Remark:因?yàn)榫仃嚪稊?shù)都可以直接用矩陣的元素計(jì)算，因此,用定理3，很容易判別逐次逼近法的收斂性。第3章3.6迭代法的收斂性定理3.3

（充分條件）若存在一個(gè)矩陣范數(shù)使得||B||<1,

則迭代收斂，且有下列誤差估計(jì)：②①證明：②迭代法的誤差估計(jì)誤差表達(dá)式及收斂速度。停機(jī)準(zhǔn)則。①（1）

1．雅克比（Jacobi）迭代法設(shè)有n階方程組幾種常用的迭代格式若系數(shù)矩陣非奇異，且

(i=1,2,…,n)，將方程組（1）改寫成然后寫成迭代格式（2）（2）式也可以簡單地寫為（3）寫成矩陣形式：A=LUDBJacobi迭代陣(4)Algorithm:JacobiIterativeMethodSolve.Givenaninitialapproximation.Input:thenumberofequationsandunknownsn;thematrixentriesa[][];theentriesb[];theinitialapproximationX0[];toleranceTOL;maximumnumberofiterationsMmax.Output:approximatesolutionX[]oramessageoffailure.Step1Setk=1;Step2While(k

Mmax)dosteps3-6

Step3Fori=1,…,n

Set;/*computexk*/

Step4IfthenOutput(X[]);STOP;/*successful*/

Step5Fori=1,…,nSetX0[]=X[];/*updateX0*/

Step6Setk++;Step7Output(Maximumnumberofiterationsexceeded);STOP./*unsuccessful*/Whatifaii

=0?迭代過程中，A

的元素不改變，故可以事先調(diào)整好A

使得aii

0，否則

A不可逆。必須等X(k)完全計(jì)算好了才能計(jì)算X(k+1)，因此需要兩組向量存儲(chǔ)。Abitwasteful,isn’tit?…………只存一組向量即可。寫成矩陣形式：BGauss-Seidel

迭代陣2．高斯――賽得爾(Gauss-Seidel)迭代法(5)(6)BG-SGauss-Seidel

迭代陣其迭代格式的矩陣形式為事實(shí)上，這相當(dāng)于對(duì)系數(shù)矩陣A作的另一個(gè)分裂：

定理5n階矩陣A是按行嚴(yán)格對(duì)角占優(yōu)矩陣的充分必要