第8章解線性方程組的迭代法

第八線性方程組的迭代一、簡(jiǎn)單迭代法（Jacobi迭代

10x1x22x3x x 其準(zhǔn)確解是：x*1.1,x*1.2,x* 解：把方程組改寫成如下x1 0.1x20.2x3

x(0)x(0)

代入上面方程的右端，得x(1)0.72,x(1)0.83,x(1) 采用如下迭代公1x(k1) 0.1x(k)0.2x(k1

x(k

0.1x(k 0.2x(k

x(k1)0.2x(k)0.2x(k

直至

x(k1)x(k

計(jì)算結(jié)果如下所示，近似解向收斂，并以準(zhǔn)確解為其極限，這就是Jacobi迭代k00001…………9下面就一般方法來敘述這一方

a12x2a1nxn設(shè)方程組a21x1a22x2a2nxn設(shè)方程組用矩陣表示

an2x2annxn假設(shè)aii

bijaij/ (i b/ i 方程組變x1 b12x2b13x3 b1nxn b bx x

bn,n1xn1若

b1n

B

2n

0

g1

g2aDa

g 3

nn

n容易BD1(DA)ID1A,gD1bxBxg 選取初始向x(0)x(0)x(0

代入方,x(0))Tn右端XBX,x(0))Tn,x(1))Tn x(1),x(1))Tn

再把x（1）代入方程右端此下去，迭代格式可以寫

g,n當(dāng)kx(k)收斂到x*,x*就是方程組的x*=x*則x*=（I－B）x*=（I－B）x*=g=D-即AX*算法輸入矩陣。置33對(duì)nbin

aij

xxjix j1, i若||x-x(0)||<ε,輸出x，否則轉(zhuǎn)步驟若k<N,k+1=>k,x=>x(0),轉(zhuǎn)步驟3；否則輸出失敗信息，停機(jī)Gauss-Seidel迭代從簡(jiǎn)單迭代法看到，用x(k)計(jì)算x(k+1)時(shí)，需要保留x(k)x(k+1)兩個(gè)分量，實(shí)際上，假若我們采用(x(kx(kxk)T 入第一個(gè)方程，計(jì)算出x(k1)，然后用新計(jì)算出來的x(k 1 1

(x(k1),x(k),x(k)

代入第二個(gè)方程，計(jì)2出新x(k2

，再用(x(k1)x(k1x(k,x(k)

代入第三個(gè)，計(jì)

，如此等等，直到全部分量都用x(k 取代x(kx 程為：xx(k1) bx(k)bx(k) bx(k)

x(k1)bx(k bx(k)

x(k) 21

x(k1)bx(k1)

x(k

x(k1) n1

0

L

U

0bn1,n n 矩陣x(k1)Lx(k1)Ux(k) k0,1,2,因(IL)1存在，上面的x(k1)(IL)1Ux(k)(IL)11稱B(I1

為Gauss-Seidel算法。 置

x

a1

x(0))/n n

11njxij

aijxj

aij

x(0))/

,i2,3,...,n xn(bn anjxj)/ann若||x-x(0)||<ε,輸出x，否則轉(zhuǎn)步驟若k<N,k+1=>k,x=>x(0),轉(zhuǎn)步驟3；否則輸出失敗信息，停三、松馳法可以看成是Gauss-Seidel迭代法的加速，Seidel迭代是松馳法的特例，Gauss-Seidel迭代格x(k1)Lx(k1)Ux(k)現(xiàn)在令xx(k1)x(k)Lx(k1)Ux(k)gx(k于 x(k1)x(k)若在修正項(xiàng)Δx前面加上一個(gè)參數(shù)ωx(k1)x(k)x(1)x(k)(Lx(k1)Ux(k)ω稱為松弛因子當(dāng)ω＜1時(shí)，稱低松馳法當(dāng)ω=1時(shí)，顯然就是Gauss-Seidel方法x(k (1)x(k)(Lx(k1)Ux(k g)因(IL)1存在，松弛x(k1)(IL)1((1)IU)x(k)(IL)1其中

B(IL)1((1)I叫做松馳法的迭代矩陣算法輸入矩陣。置（3）計(jì)x1(1（3）計(jì)

xx1

(b1

aa )/1 xi(1

xxi

(bi

xj

aa )/ xn(1

anj

xj)/ann 若||x-x(0)||<ε,輸出x，否則轉(zhuǎn)步驟

若k<N,k+1=>k,x=>x(0),轉(zhuǎn)步驟3；否則輸出失敗信息，停機(jī)前面介紹的幾種迭代格式，可以統(tǒng)一表示成下面x(k1)Mx(k)其中，M是迭代矩陣，f對(duì)簡(jiǎn)單迭代法（Jacobi迭代法）來說M=B=I-D- f=g=D-對(duì)Gauss-Seidel迭代法M=B1=(I-L)- f=g=(I-L)-對(duì)松弛法來說M=Bω=(I-ωL)-1((1-ω)I+ f=ω(I-ωL)-1迭代法的收斂從任意選取的初始向量x0)出發(fā)，構(gòu)造x(k，

10x1x22x3x x 3其準(zhǔn)確解是x*1.1，x(*)1.2，x(* 例方程

x110x220x310x 5x 其準(zhǔn)確解

x*x(*)x(*) x1

10x220x3把方程組改

取初始向量x(0)x(0)x(0) ，采用Jacobi迭代法，下 可以看出，向量序列發(fā)散，除了初始值取x(0)x(0)x(0) k00001--2-3---定理8.1對(duì)任何初始向量x(0)和常數(shù)項(xiàng)f，由迭代格x(k1)Mx(k

f,k產(chǎn)生的向量序列x(k)收斂且極限(M)其中，ρ(M)是矩陣M證明:先證必要性，假設(shè)x(k)收斂到 ，limx(k)k則x*Mx*則

x(k

x*表示第kx(k1)x(*)Mx(k

Mx*M(x(k)k 所以 M,k 或者寫

k

M k

Mk0對(duì)于任意初始向量ε0，要,向量序列Mk收斂于零向00必須由定理6.4

limMkk(M)0再證充分性，假設(shè)(M)0

,則I-M非奇異，從而方程組k kM)x＝f有唯一解，現(xiàn)記為x*，于是 k k

Mk成立

limMk0limx(k)xk k

，定理證畢補(bǔ)充(A)max為矩陣A的譜補(bǔ)充向量范向量范數(shù)是n維Eucli空間中長(zhǎng)度概念的推廣，其任一xRn，按照一定規(guī)則確定一個(gè)（1）正定性：‖x‖≥0，當(dāng)且僅當(dāng)x=0，‖x‖=0三角不等式：對(duì)任意向量yRn,‖x+y‖‖x‖那么稱該實(shí)數(shù)‖x‖補(bǔ)充矩陣范矩陣范數(shù)具有下面的性正定性：對(duì)任意非零矩陣A，‖A‖恒為正數(shù)，當(dāng)且當(dāng)矩陣為零時(shí)，其范數(shù)為零齊次性：對(duì)任意實(shí)數(shù),有A＝ 三角不等式：對(duì)任意兩個(gè)階相同的矩陣A，BABA相容性：對(duì)同階矩陣A,B

AB

A

中，常用的幾種范nxn x xn

nx2x2x2x212ni2

x2)1/ maxx,

,,

x1x2,

分別是x的n個(gè)分以上三種范數(shù)形式都滿足范數(shù)定義的三個(gè)在Rnn中，常用的幾nA1maxn

(aij是矩陣A的元素1 2

（1是A的最大特征值

nn

下面用定理8.1來檢驗(yàn)上面的幾個(gè)10x1x22x3

x1

0.1x20.2x3例：x

迭代矩

00.10.2 M0.100.20.20.2矩陣M的特征方IM30.090.008計(jì)算得1

2,3

0.33)/也就是說(M1，故迭代收x110x220x3

例 10x1x25x3

x2

5x3

010

迭代矩

M10 5 0矩陣M的特征方

IM35450

(M)1課堂練

22A 1 2 1證明：（1）對(duì)于Jacobi迭代法，其迭 2M 1 0 0矩陣M的特征方

計(jì)算 即(M

，故Jacobi迭代收斂（2）對(duì)于Gauss-Seidel迭法 0

0 2L 0

U 1 0 0

0 2其迭代矩

M(IL)1U 1 2矩陣M的特征方

計(jì)算得1 (M

，故Gauss-Seidel迭代收斂，證畢判別收斂的幾個(gè)常用 A12 A22其中A11,A22為方陣，則稱A為不可約對(duì)角優(yōu)若矩陣A＝(aij)nxn

(aij)(i1,,ni1,i,n且至少有一個(gè)i值，使上式中嚴(yán)格的不等號(hào)成立，則。定理8.3 若系數(shù)矩陣A具有嚴(yán)格對(duì)角優(yōu)勢(shì)，或者不可