第3章 線性方程組的數(shù)值解法

第3章線性方程組的數(shù)值解法§1高斯消去法§2高斯―約當(dāng)消去法§3解實(shí)三對(duì)角線性方程組的追趕法§4矩陣的三角分解§5行列式和逆矩陣的計(jì)算§6迭代法

§7迭代法的收斂性§1高斯消去法1.1順序消去法如果線性方程組(3―1)的系數(shù)矩陣A具備某特殊形式,例如其為上三角矩陣且aii≠0,i=1,2,…,n這時(shí)方程組(3―1)實(shí)際為(3―4)由方程組(3―4)的最后一個(gè)方程直接可得將其代入倒數(shù)第二個(gè)方程可求得如此再解出xn-2,…,x2,x1,一般有(3―5)其中規(guī)定以上討論告訴我們,對(duì)具有上三角形系數(shù)矩陣的方程組(3―4)求解極為方便。當(dāng)然,若方程組(3―1)的系數(shù)矩陣為下三角形,則求解也很方便。于是對(duì)于一般形式的方程組(3―1),我們總設(shè)法把它化為系數(shù)矩陣呈上(或下)三角形的方程組來(lái)求解。為了達(dá)到目的,可利用消去法進(jìn)行。現(xiàn)舉例如下:解方程組①②③(3―6)作②-①消去②中的x1,作③-①×4消去③中的x1,則方程組(3―6)化為①②③(3―6′)對(duì)方程組(3―6′)作③-②×,得到三角形方程組①②③(3―6")從方程組(3―6“)的方程③解出x3,將所得的結(jié)果代入方程②求出x2,再把x3、x2同時(shí)代入方程①解出x1。這樣可求出方程組的解為

上述求解方程組的方法就是高斯(Gauss)消去法。從式(3―6)到(3―6")的過(guò)程稱為消元過(guò)程而由(3―6")求出x3、x2、x1的過(guò)程稱為回代過(guò)程。因此用高斯消去法求解性方程組要經(jīng)過(guò)消元和回代兩個(gè)過(guò)程。在計(jì)算機(jī)上實(shí)現(xiàn)時(shí),我們常把方程組右端的常數(shù)項(xiàng)排于系數(shù)矩陣的第n+1列,這樣順序高斯消去法的計(jì)算步驟為:1.消元過(guò)程對(duì)于k=1,2,…,n-1,若按順序有某一ark≠0,r≥k,則交換k與r行,然后計(jì)算

(3―11)2.回代過(guò)程對(duì)于k=n,n-1,…,2,1,計(jì)算(3―12)1.2主元素消去法前述順序消去法是按序通過(guò)用a11,a(1)22,…,a(n-2)n-1(a(k-1)kk≠0)作為除數(shù)來(lái)達(dá)到消元目的的。在

實(shí)際計(jì)算時(shí),由于舍入誤差的影響,計(jì)算結(jié)果會(huì)改變很大,甚至于完全失真。例如用高斯消去法求解下列方程組(用四位有效數(shù)字計(jì)算):①②②-①×105得(1.000-1.000×105)x2=1.000-6.000×104化簡(jiǎn)可得

x2=0.6000回代求得

x1=105(0.6-0.6000)=0而方程組的解應(yīng)為

x1=04000x2=06000顯然用上述方法求出的解x1與方程組的實(shí)際解相差很大。若改變兩個(gè)方程的順序,即

x1+x2=1

①10-5x1+x2=0.6②②-①×10-5得(1000-1000×10-5)x2=0.6-1.000×10-5

化簡(jiǎn)得

x2=0.6000

回代求得

x1=(1-0.6000)=0.4000高斯主元素消去法是順序消去法的一種改進(jìn)。它的基本思想是在逐次消元時(shí)總是選絕對(duì)值最大的元素(稱之為主元)做除數(shù),按順序消去法的步驟消元。這里主要介紹求解線性方程組最常用的列主元素消去法和全主元素消去法。1.列主元素消去法所謂列主元素消去法就是在每一步消元過(guò)程中取系數(shù)子矩陣的第一列元素中絕對(duì)值最大者作主元。對(duì)線性方程組(3―1)進(jìn)行n-1次消元后,可得到上三角形方程組必須指出的是方程組(3―13)中的系數(shù)aij(i≤j)和右端的bi已經(jīng)改變了,并非與原來(lái)相同。這樣就可對(duì)方程組(3―13)回代求解。例1用列主元素消去法解方程組(3―13)取四位有效數(shù)字計(jì)算。解②中-18為主元,交換②和①得①②③①②③②+①×12/18,③+①×1/18得①②③第二列消元時(shí),主元為1167,交換方程②和③得①②③③+②×1/1167得①②③回代求得

x1=1000,x2=2000,x3=3001方程組的實(shí)際解

x1=1,x2=2,x3=3在計(jì)算機(jī)上求解時(shí),前面已經(jīng)講過(guò),常把右端常數(shù)項(xiàng)b作為系數(shù)矩陣A的第n+1列,從而得到增廣矩陣(A,b),仍記為A,于是,列主元素消去法的計(jì)算過(guò)程為:(1)消元過(guò)程。對(duì)于k=1,2,…,n-1進(jìn)行下述運(yùn)算:①選主元,確定r,使得若ark=0,說(shuō)明系數(shù)矩陣為奇異,則停止計(jì)算否則進(jìn)行下一步。②交換A的r、k兩行③對(duì)i=k+1,k+2,…,n,j=k+1,k+2,…,n+1計(jì)算(3―14)

aij-aik·akj/akkaij

(3―15)(2)回代過(guò)程。對(duì)于k=n,n-1,…,1計(jì)算(3―16)2.全主元素消去法所謂全主元素消去法,就是每步消元時(shí)選取系數(shù)子矩陣中絕對(duì)值最大的元素作主元。經(jīng)過(guò)n-1次消元后,方程組(3―1)可化為上三角形方程組(3―17)這里方程組(3―17)中的系數(shù)aij(i≤j)及bi一般改變了。特別是未知數(shù)的排列順序,由于全主元素的消元過(guò)程中,其系數(shù)矩陣可能進(jìn)行了列對(duì)調(diào),那么未知數(shù)也相應(yīng)地作了對(duì)調(diào)。例如,若矩陣第i列與第j列對(duì)調(diào),則未知數(shù)xi與xj也相應(yīng)地對(duì)調(diào)了,xi的結(jié)果實(shí)質(zhì)上為xj的結(jié)果。圖3.1圖3.1例2用全主元素消去法求解方程組①②③解這里主元為-18,交換方程①與方程②得①②③再全選主元,主元為2333,交換x2和x3所在的兩列,同時(shí)改變兩未知數(shù)的排列號(hào)得①②③③-②×0944/2333得①②③已經(jīng)化為三角方程組,回代求解

x1=1000,x2=3000,x3=2000

這里未知數(shù)x2與x3已對(duì)調(diào),所以應(yīng)恢復(fù)解的順序,方程組的實(shí)際精確解為

x1=1000,x2=2000,x3=3000

在計(jì)算機(jī)上求解時(shí),我們?nèi)园言鰪V矩陣(A,b)記為A,具體計(jì)算過(guò)程為(1)消元過(guò)程。對(duì)k=1,2,…,n-1進(jìn)行下列運(yùn)算:圖3.2圖3.2①選主元,確定r,t使得若art=0,則系數(shù)矩陣為奇異的,停止計(jì)算否則進(jìn)行下一步。②交換A中的r、t兩行及t、k兩列,并記下交換的足碼t、k。③對(duì)i=k+1,k+2,…,n,j=k+1,k+2,…,n+1計(jì)算(2)回代過(guò)程。對(duì)k=n,n-1,…,1計(jì)算(3―18)(3―19)(3―20)§2高斯―約當(dāng)消去法前面所述的消去法均要進(jìn)行兩個(gè)過(guò)程,即消元過(guò)程和回代過(guò)程。但對(duì)消元過(guò)程稍加改變可以把方程組(3―1)化為對(duì)角形(3―21)此時(shí)求解就不要回代了。這種無(wú)回代過(guò)程的主元素消去法稱為高斯―約當(dāng)(Jordan)消去法。特別是方程組(3―21)還可化為(3―22)顯然等號(hào)右端即為方程組的解。對(duì)于n階線性方程組(3―1),其增廣矩陣為首先把主元素(按列選主元或全選主元)調(diào)換到主對(duì)角線上,并化為1,再將主元素所在列的其它元素消為0,則第一次消元后增廣矩陣化為顯見(jiàn)經(jīng)n步消元后即得方程組的解。其具體計(jì)算步驟為:對(duì)k=1,2,…,n①選主元(列選或全選主元)②對(duì)j=k,k+1,…,n+1計(jì)算(3―23)③對(duì)i=1,2,…,n(i≠k),j=k+1,k+2,…,n+1計(jì)算

aij-aikakjaij

(3―24)④計(jì)算

xk=a

kn+1

還得指出,若用到全選主元,最后應(yīng)注意恢復(fù)解的順序?！?解實(shí)三對(duì)角線性方程組的追趕法實(shí)三對(duì)角線性方程組是一類特殊的方程組。我們將利用所謂“追趕法”解決。設(shè)所給的實(shí)三對(duì)角線性方程組為其中｜a1｜＞｜c(diǎn)1｜＞0｜ak｜≥｜bk｜+｜c(diǎn)k｜,bkck≠0,k=2,3,…,n-1｜an｜＞｜bn｜＞0

則三對(duì)角矩陣A的各階主子式都不等于0,也即A為非奇異。用數(shù)學(xué)歸納法證明:令A(yù)的k階主子式為Δk,Δ2=a1a2-b2c1≠0

其中因?yàn)樗苑匠淌?3―26)右端的k-1階行列式滿足假設(shè)的條件,由此可得Δk≠0,即矩陣A的各階主子式都不等于0。由于實(shí)三對(duì)角線性方程組的系數(shù)矩陣A為非奇異,則有唯一的一組解。下面來(lái)求解。從方程組(3―25)的第一個(gè)方程解得令(3―27)(3―28)將式(3―28)代入(3―25)式的第二個(gè)方程解出x2(3―29)令則再將(3―29)式代入(3―25)式的第三個(gè)方程解出x3,一般有

xk=uk-vkx

k+1,k=1,2,…,n-1(3―30)

其中k=2,3,…,n-1(3―31)當(dāng)k=n時(shí),因?yàn)?/p>

bnx

n-1+anxn=rn又

xn-1=un-1-vn-1xn于是(3―32)例3解線性方程組解依公式(3―27)、(3―31)求得v3=0(一般v3不必算)再由式(3―32)、(3―30)求得方程組的解圖3.3圖3.3

§4矩陣的三角分解

對(duì)于線性方程組(3―1),若其系數(shù)矩陣A能夠分解成兩個(gè)三角形矩陣相乘,譬如,

A=LUL為下三角矩陣,U為上三角矩陣,則求解方程組(3―1)就化為求解

LUx=b令

Ux=y(3―34)(3―35)則Ly=b(3―35)、(3―36)都為三角形方程組,先求出(3―36)中的y,然后代入(3―35)就可以求出原方程組(3―1)的解x。(3―36)4.1消去法與矩陣的初等變換從矩陣的初等變換來(lái)看,前面所述的主元素消去法(假定主元素經(jīng)過(guò)行列調(diào)換以后均在對(duì)角線上),就是通過(guò)一系列的初等變換將方程組(3―1)的系數(shù)矩陣A化為三角矩陣。其每一步的消元過(guò)程相當(dāng)于對(duì)增廣矩陣(A,b)作一次初等變換。令在消去第一列中的ai1(i=2,3,…,n)時(shí),左乘的矩陣為這樣就把A化為一個(gè)上三角矩陣U，即在需要進(jìn)行行交換時(shí)，還得左乘某些排列矩陣Pij

A=LU(3―37)

稱式(3―37)為矩陣A的LU分解或三角分解。由上述討論,只要系數(shù)矩陣A非奇異,經(jīng)過(guò)適當(dāng)?shù)男薪粨Q后總可以將A分解為一個(gè)下三角矩陣L和一個(gè)上三角矩陣U之積。下面首先討論矩陣三角分解的唯一性。4.2矩陣三角分解的唯一性設(shè)非奇異矩陣A存在一種三角分解LU,一般這種分解未必唯一,這是因?yàn)槿我庖粋€(gè)同階的非奇異對(duì)角矩陣D總有(LD)(D-1U)=L1U1

它也是矩陣A的一種三角分解。為了確保三角分解的唯一性,需對(duì)分解加以規(guī)格化。為使LU分解規(guī)格化,可以把矩陣U換成DU,其中L為單位下三角矩陣,U為單位上三角矩陣,D為對(duì)角矩陣,即我們稱

A=LDU(3―38)

為矩陣A的一種LDU分解。關(guān)于矩陣A的LDU分解有如下定理:定理1對(duì)于n×n階矩陣A存在唯一的LDU分解的必要充分條件是A的各階主子矩陣A1,A2,…,An均非奇異。證先證必要性。設(shè)A有唯一的LDU分解,即

A=LDU

由于

Ak=LkDkUk

其中Ak、Lk、Dk、Uk分別表示A、L、D、U的k階主子矩陣。因?yàn)長(zhǎng)、U是單位三角矩陣,D為非奇異對(duì)角矩陣,所以Lk、Uk、Dk均非奇異,從而知Ak必為非奇異矩陣。再證充分性。用數(shù)學(xué)歸納法證明:當(dāng)k=1時(shí),A1顯然有這種三角分解且是唯一的,即

A1=L1D1U1=l11d1u11

其中

l11=1,d1=a11,u11=1設(shè)對(duì)k=n-1時(shí)結(jié)論成立,將A按下面方式分塊:這里

s=(a1n,a2n,…,an-1n)T

rT=(an1,an2,…,a

nn-1)a=ann再將A、D、U仿照A分塊:這里設(shè)若通過(guò)A的元素能唯一地定出L中的IT,U中的u及D中的d,就可確認(rèn)A唯一地有LDU分解了。因?yàn)槠渲衦、s、a均為已知,于是有

Ln-1Dn-1u=s(Dn-1Un-1)TI=rITDn-1u+d=a由于A的各階主子矩陣非奇異,因而Ln-1、Dn-1、Un-1

均為非奇異,于是可以唯一地求出

所以,A存在唯一的LDU分解。證畢。由定理1不難得到定理2(證明留給讀者)。定理2n×n階矩陣A非奇異的必要充分條件為A(或A經(jīng)行、列變換后)存在LDU分解。推論1奇異矩陣不能進(jìn)行LDU分解。推論2若方陣A有奇異主子矩陣,則A不能直接進(jìn)行LDU分解。證用反證法。若A能直接進(jìn)行LDU分解,即A=LDU。設(shè)A的k(k≤n)階主子矩陣Ak奇異,則按分塊矩陣的乘法有

Ak=LkDkUk

而Lk為單位下三角矩陣,Dk為非奇異對(duì)角矩陣,Uk為單位上三角矩陣,顯然與推論1矛盾,所以結(jié)論成立。可驗(yàn)證A為非奇異矩陣,但其左上角二階主子矩陣奇異,故由推論2不能直接進(jìn)行LDU分解。因A為非奇異,由定理2,經(jīng)適當(dāng)行變換后存在LDU分解。若經(jīng)行變換例設(shè)則LDU分解為A1=LDU若經(jīng)列變換則A2的LDU分解為4.3LU分解方法我們已經(jīng)知道,若矩陣A的各階主子矩陣非奇異,則存在唯一的LDU分解,即

A=LDU

常常稱(LD)U=L1U,L(DU)=LU1(3―39)

分別為矩陣A的克勞特(Crout)分解和杜利特爾(Doolittle)分解。仍記為

A=LU只不過(guò)若是克勞特分解,則L為下三角矩陣,U為單位上三角矩陣若是杜利特爾分解,此時(shí)L為單位下三角矩陣,U為上三角矩陣。顯然這兩種分解均是唯一的?，F(xiàn)分別介紹求解線性方程組的兩種LU分解方法。1.克勞特分解方法設(shè)A為n×n階非奇異矩陣,且各階主子矩陣為非奇異,則矩陣A的克勞特分解為

A=LU(3―40)

其中

L、U中元素的確定,可不用消去法,而直接由式(3―40)來(lái)求得。按矩陣乘法規(guī)則有因?yàn)閡11=1,所以

ai1=li1u11=li1,i=1,2,…,n

于是可求得L的第一列元素為

li1=ai1,i=1,2,…,n(3―42)

又因?yàn)?/p>

a1j=l11u1j,j=2,3,…,n

所以

u1j=a1j/l11,j=2,3,…,n(3―43)(3―41)于是U的第一行元素也就由式(3―43)計(jì)算出來(lái)了。假定L的前k-1列以及U的前k-1行元素都已算出,由于ukk=1,于是從式(3―41)有(3―44)(3―45)這樣,L、U中的元素都已求出。計(jì)算L的各列與U的各行的次序如圖3。4所示。圖3.4對(duì)方程組(3―1)的系數(shù)矩陣A作出LU分解后,方程組便化為

LUx=b

則求解上列方程組就化為依次解方程組

Ly=b(3―46)

Ux=y(3―47)

由于L為下三角矩陣,U為單位上三角矩陣,故方程組(3―46)、(3―47)的求解極為方便。先由(3―46)式解出y,然后代入(3―47)式求得x,亦即求得了方程組(3―1)的解。而求解(3―46)、(3―47)式的計(jì)算公式分別為用克勞特分解求解線性方程組(3―1)的計(jì)算過(guò)程為:①LU分解過(guò)程:對(duì)于k=1,2,…,n依次計(jì)算(3―48)(3―49)從上述計(jì)算過(guò)程還可看出,求解yk的公式完全可以插在計(jì)算L、U元素的兩個(gè)公式之間。其計(jì)算框圖見(jiàn)圖3.5。圖3.5圖3.5例4用克勞特分解方法求解下列方程組解令利用矩陣乘法可得到這樣原方程組就化為依次求下列兩個(gè)三角形方程組代入第二個(gè)方程組可求得原方程組的解為2.杜利特爾分解方法杜利特爾分解方法是令

A=LU

這里關(guān)于L、U的元素可按以下公式計(jì)算:對(duì)于k=1,2,…,n進(jìn)行(3―50)(3―51)在L與U的元素算出后就可以按

Ly=b(3―52)

Ux=y(3―53)解方程組LUx=b,從而求得方程組(3―1)的解。例5用杜利特爾分解方法求解下列方程組的解:解利用式(3―50)、(3―51)可求得再由式(3―52)、(3―53)求得原方程組的解為從上面的討論我們可以看到,用LU分解方法解線性方程組(3―1),就是將其化為依次求解下面兩個(gè)三角形方程組:

Ly=b

Ux=y顯然求解Ly=b的過(guò)程即為消元過(guò)程,它只不過(guò)是對(duì)

LUx=b

兩端左乘L-1而得,即

Ux=L-1b=y

而求解Ux=y的過(guò)程即為回代過(guò)程。因此三角分解方法實(shí)質(zhì)上還是高斯消去法。而克勞特分解方法中的元素lii(i=1,2,…,n)和杜利特爾分解方法中的元素uii(i=1,2,…,n)實(shí)際上就是高斯消去法中的各次主元素。4.4喬累斯基(Cholesky)分解方法設(shè)A為n×n階正定矩陣,記為A＞0。根據(jù)前節(jié)的討論,其有唯一的分解式

A=LDU

其中L為單位下三角矩陣,D為非奇異對(duì)角矩陣,U為單位上三角矩陣。由于A是對(duì)稱的,于是有

U=LT

從而A的LDU分解式可寫成

A=LDLT(3―54)

又因A為正定矩陣,故D的主對(duì)角元素均為正數(shù)。記則A可以表示成

為簡(jiǎn)便起見(jiàn),我們?nèi)サ鬖1的下標(biāo),仍把A的這種分解記作

A=LLT(3―55)

其中L是一個(gè)下三角矩陣。分解式(3―55)便是通常所說(shuō)的正定矩陣A的喬累斯基分解。下面介紹兩種具體的喬累斯基分解方法。1.LLT分解方法(平方根法)對(duì)于分解式由矩陣乘法規(guī)則從而得(3―56)(3―57)當(dāng)i=j時(shí)也即于是這樣由式(3―56)、(3―57)確定L的元素后,就可按

Ly=b(3―58)

LTx=y

(3―59)解方程組

LLTx=b(3―60)其解x即為方程組

Ax=b的解。由式(3―58)、(3―59)依次計(jì)算y和x可按下列遞推公式進(jìn)行:(3―61)(3―62)例6用LLT分解方法解線性方程組取四位小數(shù)計(jì)算。解用公式(3―57)、(3―56)依次計(jì)算由式(3―61)求得

y1≈1.3416,y2≈-0.4474,y3≈1.7320再由式(3―62)求得原方程組的解為

x1≈0.9993,x2≈0.9989,x3≈0.9999實(shí)際上,原方程組的準(zhǔn)確解為

x1=1,x2=1,x3=1LLT分解方法的計(jì)算框圖見(jiàn)圖36。2.LDLT分解方法

LLT分解方法的計(jì)算中含有開方運(yùn)算,而LDLT分解方法就避免了這一點(diǎn)。設(shè)A＞0,則其有唯一的分解式

A=LDLT

其中圖3.6圖3.6類似于前面的討論,由矩陣乘法規(guī)則可得(3―63)也即因?yàn)閘jj=1,從而有故有當(dāng)i=j時(shí)(3―64)根據(jù)式(3―63)、(3―64)求出矩陣L、D的元素后,就可按照

Ly=b(3―65)

LTx=D-1y(3―66)解方程組LDLTx=b

其解x就是線性方程組(3―1)的解。具體計(jì)算x和y的遞推公式為(3―67)(3―68)圖3.7圖3.7§5行列式和逆矩陣的計(jì)算5.1行列式的計(jì)算行列式的數(shù)值計(jì)算,只要將行列式化為三角形式(上三角或下三角),求解就很方便了。因此,前面所述的解線性方程組的方法都可以用來(lái)化行列式detA為三角形式。1.高斯消去法設(shè)detA為n階行列式,即按矩陣A經(jīng)若干次初等變換以后,其主元素分別為r11,r22,…,rnn,于是2.LU分解法①克勞特分解法:detA=detL·detU=detL=l11l22…lnn②杜利特爾分解法:detA=detL·detU=detU=u11u22…unn③喬累斯基分解法:這里A為正定矩陣。detA=detL·detLT=l211l222…l2nn或者detA=detL·detD·detLT=detD=d1d2…dn5.２逆矩陣的計(jì)算設(shè)A為非奇異矩陣,則A可逆,即有AA-1=I令A(yù)-1=X=(x1,x2,…,xn)于是有AA-1=A(x1,x2,…,xn)=(e1,e2,…,en)從而求逆矩陣A-1的問(wèn)題就化為求解下列幾個(gè)有相同系數(shù)矩陣A的線性方程組問(wèn)題

Axi=ei,i=1,2,…,n(3―69)

因此,前面介紹的求解線性方程組的方法均可用來(lái)計(jì)算逆矩陣。例7設(shè)求A-1。解將方程組寫成同一個(gè)增廣矩陣,即先對(duì)第一列消元,將a11化為1,a21、a31化為0,有再將第二列a32化為0,得將a33化為1,并將a23、a13化為0,得最后將a13化為0,得所以§6迭代法6.1簡(jiǎn)單迭代法設(shè)所給的線性方程組為

Mx=g(3―70)

其中且系數(shù)矩陣M為非奇異,g≠0。將方程組(3―70)改寫成等價(jià)形式

x=Ax+f(3―71)

這種改寫的方法很多,例如將M分解為兩個(gè)矩陣之差

M=B-C

其中矩陣B可逆,于是方程組(3―70)成為

Bx=Cx+gx=B-1Cx+B-1g

令

A=B-1C,f=B-1g即得(3―71)式。當(dāng)然選取的B應(yīng)該便于求逆,如B為單位矩陣或?qū)蔷仃嚨?。?duì)任意給定的初始向量x(0),根據(jù)(3―71)構(gòu)造迭代公式

x(k+1)=Ax(k)+f,k=0,1,2,…(3―72)

這里A稱為迭代矩陣。用分量形式可寫成(3―73)算出迭代公式(3―72)的解的各次近似值x(1),x(2),…,x(k),…。這種迭代求解的方法稱為簡(jiǎn)單迭代法。式(3―72)稱為簡(jiǎn)單迭代公式。特別當(dāng)M的對(duì)角元素均不為零且按絕對(duì)值來(lái)說(shuō)較大時(shí),常取則

A=D-1C,f=D-1g例8用簡(jiǎn)單迭代法解下列方程組解將方程組寫成等價(jià)形式取初始值x(0)=0,按迭代公式表3―1圖3.86.2賽德?tīng)?Seidel)迭代法從簡(jiǎn)單迭代法看到,已知x(k)計(jì)算x(k+1)時(shí),需要保留x(k)和x(k+1)兩個(gè)分量。逐次用前面算出的新分量來(lái)計(jì)算下一個(gè)分量,這就是賽德?tīng)柕ǖ幕舅枷?。設(shè)方程組(3―70)的等價(jià)形式為

x=Ax+f

將矩陣A分解為

A=B+C

其中于是

x=Bx+Cx+f

(3―74)x(k+1)=Bx(k+1)+Cx(k)+f,k=0,1,2,…(3―75)例9用賽德?tīng)柕ń夥匠探M解將原方程組寫成等價(jià)形式并按(3―75)構(gòu)造賽德?tīng)柕奖?―2由式(3―75)可得(I-B)x(k+1)=Cx(k)+f

因?yàn)榫仃嘔-B是非奇異矩陣,則I-B可逆,所以迭代公式(3―75)可寫成

x(k+1)=(I-B)-1Cx(k)+(I-B)-1f,k=0,1,2,…(3―77)

這里迭代矩陣

A=(I-B)-1C

由此看出,對(duì)方程組(3―70)用公式(3―75)作賽德?tīng)柕喈?dāng)于對(duì)方程組(3―70)用(3―77)式作簡(jiǎn)單迭代。因此,賽德?tīng)柕▽?shí)際上是某種簡(jiǎn)單迭代法。6.3松馳法賽德?tīng)柕?3―75)為

x(k+1)=Bx(k+1)+Cx(k)+f

現(xiàn)令

Δx=x(k+1)-x(k)=Bx(k+1)+Cx(k)+f-x(k)于是

x(k+1)=x(k)+Δx(3―78)

x(k+1)可以看作在向量x(k)上加修正項(xiàng)Δx而得到。若在修正項(xiàng)的前面加上一個(gè)參數(shù)ω,便得到松馳法的迭代公式

x(k+1)=x(k)+ωΔx=(1-ω)x(k)+ω(Bx(k+1)+Cx(k)+f)k=0,1,2,…(3―79)

或者用分量形式寫成(3―80)其中ω叫做松馳因子,當(dāng)ω＞1時(shí)叫超松馳,ω＜1時(shí)叫低松馳,ω=1時(shí)就是賽德?tīng)柕?。松馳因子ω的選取直接影響到松弛法的收斂性。因?yàn)?I-ωB)-1存在,所以還可以把(3―79)改寫成

x(k+1)=(I-ωB)-1((1-ω)I+ωC)x(k)+ω(I-ωB)-1f(3―81)

這是簡(jiǎn)單迭代公式,迭代矩陣為

A=(I-ωB)-1((1-ω)I+ωC)

實(shí)際上,賽德?tīng)柕ɑ蛩沙诜ǘ际悄撤N簡(jiǎn)單迭代法,它們僅是迭代矩陣A不同?！?迭代法的收斂性前面介紹的例7、例8分別用簡(jiǎn)單迭代法和賽德?tīng)柕ǘ嫉玫搅溯^好的迭代效果。若將原方程組改寫成如下等價(jià)形式:表3―3可見(jiàn)當(dāng)k越大時(shí),其迭代值與準(zhǔn)確解

x1=1.1,x2=1.2,x3=1.3

相差越大,即向量序列｛x(k)｝不收斂。此例如用賽德?tīng)柕ǖ蠼?得到的結(jié)果也令人失望。為此,很有必要討論迭代法的收斂性。也就是研究等價(jià)方程

x=Ax+f

的收斂條件。為了達(dá)到此目的,我們首先介紹向量范數(shù)、矩陣范數(shù)等基本