chap3解線性方程組的迭代法

第三 解線性方程組的迭代3‐1：取0,10,1u u f22sin(x)sin(y，使用有限元法求解此4X4169

c1 c

2 000000 000000 000000000000 00000000000 000000 c 4 c 5 c

7

一般情形：對(duì)區(qū)域進(jìn)行64X64劃分；求所有節(jié)點(diǎn)上近似數(shù)據(jù)，最后化歸為求解內(nèi)部節(jié)點(diǎn)滿足的稀疏方程例3‐2：現(xiàn)實(shí)中的問(wèn)題大多數(shù)是連續(xù)的，例如工程中求解結(jié)§3.1迭代法直接法適用于中小型方程組對(duì)高階方程組,量大,程序復(fù)雜,運(yùn)算量巨大.矩陣稀疏性,計(jì)算簡(jiǎn)單,程序編制容易.迭代法基本思想：構(gòu)造向量序列xk,使得它的極限x是Axb的解迭代法的一般其中AM為n階方陣，xg ：x(k1)Mx(k)

k0,1,2,M為迭代矩陣，{x(k)}為迭代序列結(jié)論：若迭 x(k

Mx(k

g產(chǎn)生的迭代序列收斂于AxxMx則必有xAxxMx此類(lèi)方法稱(chēng)為單步定長(zhǎng)線性迭代法向量序列與矩陣序列的收斂定義3.1：設(shè){x{k}}為Rn中的向量序列,xRn,如果：limx(k)xk其中為Rn中的向量范數(shù),則稱(chēng)序列{xk)}收斂于記 limx(k)k定理 limx(k)xlimx(k)x(i1,2, k 其 x(k)(x(k),x(k),...,x(k))T

x(x,x,...x 定義3.2：設(shè)Ak為n階方陣序列,A為n階方陣,如果 A(k)Ak其中為矩陣范數(shù),則稱(chēng)序列Ak)}收斂于A記作limA(k)k定理3.2 limA(k)Alima(k)a(i,j1,2,k k

其 A(k)(ak A(a定理3.1,3.2說(shuō)明向量和矩陣序列的收斂等價(jià)于對(duì)應(yīng)分量 幾種基本的迭 雅可比（Jacobi）a11x1a12x2a1nxna21a

a22

a2n

Ax xMx

annxnx1

m1nx1

g1x

x g2 2n22

xmxmx xxn

mnnxn gn

21

若aii (i1,2,,n)方程組可同解變形為x

xa1n

x

x

ann1

xMx

x(k1)Mx(k) k0,1,nJacobi迭代法的計(jì) n

x(k)

nn

x(k)

22

n n即

i

n

ix(k1)i

ba x(k)

x(k)

(i1,2,,ai ai

ji

記 g

ba

(ij i,j1,2,,(i1,2,,n

g1

gM

2n

g 2bb

0 0

g g nx(k1)Mx(k)Jacobi迭代法的矩陣形式 x(k1)Mx(k)選取初始向量x(0),按以上 產(chǎn)生的迭代序列稱(chēng)為Jacobi迭代（簡(jiǎn)單迭代法）Jacobi MI g

Ddiag(a 算法3.1(Jacobi迭代、輸入Aab(bb,...b)Tx(0)

(x(0),x(0),...x(0))T 誤差,最大允許迭代次數(shù)N2、取k

i

(0

(03、對(duì)i1,2,..., xi (bi

aijxj

ji

aijx 4、若

xx(

,輸出,停止.否則轉(zhuǎn)5、若kN,取k1kxx(0i12 轉(zhuǎn)3,否則輸出失敗信息functionM%用途：Jacobi迭代求解方程組n=length(b);N=500;ep=1e-x=ones(n,1k=0;whilek<Nfor%[kx’] ifnorm(x-x0,inf)<ep,break;endifk==N,Warning(‘已達(dá)最大迭代次數(shù)');enddisp([‘k=’,num2str(k)]) 10x1x22x3x10 2 2x 5 2310x1x22x3解：Jacobi迭代計(jì)

x10 2 3x 5 31x(k112x(k12x (k1x

0.1x(k)0.2x(k 0.1x(k)0.2x(k 0.2x(k)0.2x(k

788x(0)0,0,0)T

x(1)(7.2,8.3,1x(2)0.831.687.212x(2)0.721.688.323x(2)1.441.668.43依次下去收斂于真解x(11, kJacobimethodx

10x1x22x3 10 2 5 0.1

MID1A

0gD1b

令x(k1)Mx(k)

x(0)(0得x(1)Mx(0)g 8.4)Tx(9)(10.9994,11.9994,依次下去，x(k1)Mx(k) 收斂于精確x(11,12,13)T －賽德?tīng)?Gauss－Seidel)Jacobi迭代的計(jì) x(k

x(k

x(k

a a

nx(k n

21x(k

a2

x(k

2x(k2

x(k

an

x(k

ann

x(k

a a

i

n

n

x(k1) baijx(k)

aijx(k)

(i1,2,,ii jii

ji Gauss-Seidel迭代的計(jì) x(k

x(k

x(k

a a

nx(k n

21x(k

x(k

2x(k2

x(k

an

x(k

x(k

a a即

x(k

b

i

ax(k1)

ax(k)

(i1,2,,na na

j

ji 0 0

0La

a 00 0 an an

0

a1n0 a 0

2nU

a3n00

Ddiag(a11,a22,,annADL(k 1

i

(k

(k)a a

aijxj

aijx ji

(i1,2,,x(k1)D1(Lx(k1)Ux(k

(DL)x(k1)Ux(k)x(k1)(DL)1Ux(k)(DL)1迭代矩陣為

Ms(D functionM%用途：Gauss-Seidel迭代求解方程組whilefor ifx(1)=(b(1)-elseifx(i)=(b(i)-A(i,1:i-1)*x(1:i-1)-ifnorm(x-x0,inf)<ep,break;end10x1x22x3 10 2 5 10x1x22x3解：G-S迭代計(jì)

x10x2 xx5 x(k 0.1x(k

0.2x(k)

2x(k2

0.1x(k

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

取x(0)(0,0,0)T x(1)(7.2,9.02,1x(2)0.9022.32887.212x(2)1.043082.32888.323x(2)2.086162.334388.43依次下去收斂于真 x(11, er(A,b,20,1e- 0,1e-Gauss_seidelmethodxJacobimethodconvergedx=10x1x22x3 10 2 寫(xiě)成G-S迭代矩陣

2 5 23

01

0.2

0.22MS(D

g(DL)1b S令xk1)MxkS

x(0)(0,依次下去,x(k)收斂于真解 逐次超松弛法（SOR法換個(gè)角度看GaussSeidelx(k1) 1

i

x(k1)

(k)

aijx

j1

i

jin

r(kix(k) bax(ki

ax(k)x(k

aii

iij

j

r(k x(k1)x(k

a通過(guò)選取合適的來(lái)加速收斂1時(shí)即為Gauss-SeidelSOR計(jì) (k

(k

i

(k

(k

(i

(bia

aijx

aijx j

i

j (1)x(k)

(b

ax(k

ax(k)a a j

ji

(k1)

b

i ax(k1)

(k)

aij ji x(k

(1-)x(k

(

x(k

x(k

b1

x(k

(1-)x(k

(

x(k

a2

x(k

b2SOR:

x(k

(1-)x(k

(

x(k1)ann

x(k

bn

n (k

(k)

i (k

(k (1)

(bi

aijxj

aijxj ji

(ix(k1)(1)x(k)D1(bLx(k1)Ux(k)Dx(k1)(1)Dx(k)(bLx(k得

Ux(k)xx(k1)(DL)1(1)DUx(k)(D迭代矩陣為

M(DL)1(1)DUfunctionM%用途：SOR迭代求解方程組while for ifx1(1)=(b(1)-elseifx1(i)=(b(i)-A(i,1:i-1)*x(1:i-1)-ifnorm(x0-x,inf)<ep,break;end松弛因子的選取對(duì)收斂速度影響極大,最優(yōu)松弛因子A為對(duì)稱(chēng)正定的三對(duì)角矩陣時(shí),有：1 11 1(B)22其中(B)為Jacibi迭代矩陣的譜半徑 迭代方法評(píng)JacobiG-S:減少 量,要求計(jì)算順SORG-SG-SJacobi

x(k1)D1(LU)x(k

x(k1)(DL)1Ux(k)(D x(k1)(DL)1[(1)DU]x(k)(D矩 再探討：Ax xMx AE

E1存在且方程組Exd容易求解AxAxbExFx xE1(Fx

a1n

0

a1n

0 a

2n

2n

nn

nn AAD(LU

Axb Dx(LU)xb

x(k1)D1(LU)x(k)A(DL)

Axb (DL)xUxG-S:x(k1)(DL)1Ux(k)(DA1DL1DU AxbAxb

A(DL)[(1)DU(DL)x[(1)DU]x

x(k1)(DL)1[(1)DU]x(k)(DA1D1DA JOR:x(k1)(ID1A)x(k)A1I1IA

Richardson

x(k1)(IA)x(k)GeneralRichardson

diag(1,2,,nx(k1)(IA)x(k)A1DL1DU 1DU1DL

x(k1)Sx(kSM

M(DU)1[(1)DN(DL)1[(1)DUg(2)(DU)1(DL)1 矩陣的譜定義3.3設(shè)A為方陣，i(i12,n)為A的特征值，稱(chēng)特征值模的最大值為矩陣的譜半徑，記為：(A)max結(jié)論：、Ak)、(A) A其中為任意由向量范數(shù)誘導(dǎo)出的矩陣范數(shù)3、0,存在一種矩陣范數(shù),使得A(A) 2當(dāng)A為對(duì)稱(chēng)矩陣時(shí),有(A) 2

(A)(A)4An

limAk(A)k4、設(shè)A為n階方陣limAkA)k證明

Ak

[(A)]k (Ak)

(A)""對(duì)任意存在一種范數(shù)，使A(A)(A)1，存在范數(shù)，使 A而

A

limAk limAkx,xk k迭代法的收斂定理3.6對(duì)任意初始向量x0右端項(xiàng)x(k1)Mx(k

(k0,1,2,)產(chǎn)生的向量序列{xk)}收斂的充要條件是：(M)推論：若 則對(duì)任意初始向量x( 右端項(xiàng)x(k1)Mx(k)

(k0,12,產(chǎn)生的序列x(k)收斂定理3.6:xk1收斂(M)

x(k1)Mx(k)limAkx,xRnlimAkk k

limAk(A)k"若xk1)x*

x*Mx*x(k

x*Mx(k)

Mk(x(0)x*Mk (M

(M)

（IM）xg存在唯一解xk1x*Mx(k)Mx*Mkx0)x*(M)1Mk x(k1)x*推論：逐次松弛法收斂的必要條件是：0證明：逐次超松弛法的迭代矩陣為M(DL)-1[(1-)DUdet(M)(DL)- (1-)D (1-)n (1-)na11

det(M

[(M

由定理 (M)det(M

(1)n 得0 x12x22x3x 2x2 2 2A

2L

U 2

0 00DL (DL)1 00

2 ID1A1

0IMJ

3MJ0Jacobi迭代法 0

2 0 2M

0

2

0

2I

2

(2)2定義：若n階方陣A(aij)滿足n

j

(i1,2,,且至少有一個(gè)i值，使上式不等號(hào)嚴(yán)格成立，則稱(chēng)A為弱對(duì)角占優(yōu)陣。若對(duì)所有i,上式中不等號(hào)均嚴(yán)格成立，則稱(chēng)A為嚴(yán)格對(duì)角占優(yōu)陣。

5 5 A

65 A65

定義3.5---不可約矩陣如果矩陣A不能通過(guò)行的互換和相應(yīng)列的互換成為形 22其中 A22為方陣，則稱(chēng)矩陣A不可約不存在排列矩陣P,使PTAP

A12 22 0

A

B1 2結(jié)論若A沒(méi)有零元素,則A

n3時(shí)A只有一個(gè)零元素A不可設(shè)A(aij)為n階矩陣(n2若存在非空集合I1,2,使得當(dāng)iIjI時(shí)，有aij0則A是可約陣。幾種常用的判別收斂條件：已知Ax1、若A為嚴(yán)格對(duì)角占優(yōu)陣或不可約弱對(duì)角占優(yōu)陣，則Jacobi迭代法與G-S迭代法收斂。2、若A為嚴(yán)格對(duì)角占優(yōu)陣，01則SOR法收斂3、若A為對(duì)稱(chēng)正定矩陣,則SOR法收斂的充要條件是02.、Jacobi:A為嚴(yán)格對(duì)角占優(yōu)或不可約弱對(duì)角2、G-SA為嚴(yán)格對(duì)角占優(yōu)不可約弱對(duì)角占優(yōu)3、SORA為對(duì)稱(chēng)正定矩陣(0嚴(yán)格對(duì)角占優(yōu)(0

判別迭代法收斂的步驟1、先觀察系數(shù)矩陣A是否對(duì)稱(chēng)正定或?qū)钦?、給出迭 ,討論迭代矩陣的譜半例：JacobiGauss-SeidelAxb,

A b

-1 A 1

A對(duì)稱(chēng)正定，G-S迭代法收 12 22 1Jacobi的迭代矩陣B

1(LU) 21 1 0 IB03－5－3 B)1Jacobi迭代發(fā)散。

A為不可約弱對(duì)角占優(yōu),Jacobi和G-S迭代法均收例

Ax 1 A 0.5 b 2 0.5

2

2 3

1A1Jacobi,G-S01的SORJacobi迭 x(k1)0.9x(k

0.05x(k) x(k

0.25x(k

0.5x(k

x(k1)0.1x(k(k(k

G-S迭 1x(k1)0.9x(k1

0.05x(k)x(k

0.25x(k

0.5x(k)(k

1(k

3(k

2323

01x(k1

(1)x(k

(0.9x(k)0.05x(k

1x(k1

(1)x(k

(0.25x(k

0.5x(k)(k

2(k

1(k

3(k1)1

(1)x3

誤差估定理3.7設(shè)有迭代格式xk1)Mx(k)Mk收斂于x,且有誤差估Mk

g若M1,則x(kx(k

1

x(1)x(

(3 M1(M)3.6,limx(k)xxMxx(k

xM(xk1x)Mk(x(0)x兩邊取范

x(k

M

x(

x* x(0)

x(0)x*Mk又 Mk

1,所以有：

x(0

x

x x(01 即：xk1

1

x(1)x(0

證畢。注 由定理3.7易得 M越小,{x(k)}收斂越若給定精度(誤差限),由(322)(1(1Mx(1)x(0)lnM定理3在定理3.7的條件下Mx(k)

1

x(k)x(k證明：x(k)兩邊取

xM(x(k1)xx(k)

x(k

M同時(shí)由M

x(k

x(k1)x(k

x(k

當(dāng) 1時(shí)

x(k

1

x(k)x(k注2.

x(k)x(k

作為停止準(zhǔn) 最速下降法與共軛梯求解Axb,

其中A對(duì)稱(chēng)正定可轉(zhuǎn)化為極值問(wèn) (x)1xTAxbTx1Ax,xb,x 因 (x)Ax求解Axb求x)的極小值 Ax*b min(x)1x*TAx*bT

(x)1xTAxbTx1Ax,xb,x 函數(shù)(x)具有以下性質(zhì)：梯 (x)Axx,yRn,2(x+y)1A(x+y),(x+y)b,(x+y)2=(x)Axb,y2 Ay,2Ax*，則x*)1bx*1Ax*,x* 且xRn,xx*)1Axxbx1bx* =1A(xx*),(xx*)23.：(x*)min(證明：必要性.Ax*b,由性質(zhì)(3)及對(duì)稱(chēng)正(x)(x*)1A(xx*),(xx*)2即x*)min充分性

i

ai2

ain

)

i1,2,,=Ax若(x*)min( 則(x)在x*處從而Ax*b證最速下

(x)1xTAxbT2(x)Axstep1:從初始點(diǎn)x0)出發(fā)找負(fù)梯度方向r0)r0)x0bAx0搜索方向step2:在r0方向上求x)的極小值點(diǎn)x(1(x(1))min(x(0)r(0)