關(guān)于線性方程組的迭代法引言直接法是通過有限步運(yùn)算后得到線性方程組的解,解線性方程組還有另一種解法，稱為迭代法,它的基本思想是將線性方程組Ax=b化為

x=Bx+f

再由此構(gòu)造向量序列{x(k)}:

x(k+1)=Bx(k)+f若{x(k)}收斂至某個(gè)向量x*,則可得向量x*就是所求方程組AX=b的準(zhǔn)確解.線性方程組的迭代法主要有Jocobi迭代法、Seidel迭代法和超松弛(Sor)迭代法.第2頁(yè),共35頁(yè)，2024年2月25日，星期天迭代法的特點(diǎn)

若在求解過程中xk

x*(k)，由xk+1=(xk)產(chǎn)生的迭代xk向x*的逼近，在數(shù)次迭代求解之后，由于機(jī)器跳動(dòng)產(chǎn)生的xk值誤差或是有效數(shù)字產(chǎn)生的舍入誤差，都會(huì)在第k+1次迭代計(jì)算中自動(dòng)彌補(bǔ)過來或逐步糾正過來。因此，在迭代求解過程中產(chǎn)生的各種誤差是可以忽略的，即迭代求解無(wú)累積誤差，實(shí)際上，xk只是解的一個(gè)近似，機(jī)器的舍入誤差并不改變它的此性質(zhì)。

迭代過程中經(jīng)常要遇到向量范數(shù)，矩陣范數(shù)以及序列極限的概念。為此，下面先介紹這方面的知識(shí)和有關(guān)概念。

單擊此處即可第3頁(yè),共35頁(yè)，2024年2月25日，星期天幾個(gè)基本概念及性質(zhì)1.向量范數(shù)：

對(duì)任一向量X，按一定規(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||。（3）對(duì)任意向量YRn，||X+Y||

||X||+||Y||。則稱該實(shí)數(shù)||X||為向量X的范數(shù)2.矩陣范數(shù)：設(shè)A是NN階矩陣，定義||A||=Max

（||AX||/||X||）=Max||AX||x0,xRn

||x||=1,xRn

為矩陣A的(算子）范數(shù)。

||Ax||

||A||||x||第4頁(yè),共35頁(yè)，2024年2月25日，星期天三種常用的向量范數(shù)：例：設(shè)x=(1,-4,0,2)T求它的向量范數(shù)第5頁(yè),共35頁(yè)，2024年2月25日，星期天三種常用的矩陣范數(shù)：例：設(shè)A，求它的矩陣范數(shù)第6頁(yè),共35頁(yè)，2024年2月25日，星期天矩陣范數(shù)的性質(zhì)：（1）對(duì)任意非零矩陣A,有||A||恒為正數(shù)，當(dāng)且僅當(dāng)A=0，||A||=0.（2）||aA||=|a|||A||（a為任意實(shí)數(shù)）（3）對(duì)于任意兩個(gè)階相同的矩陣A，B恒有||A+B||

||A||+||B||.（4）對(duì)于與矩陣A有相同維數(shù)的向量X，恒有||AX||

||A||

||X||.（5）對(duì)于同階矩陣A，B恒有||AB||

.||A||

||B||譜半徑：

設(shè)nn階矩陣A的特征值為

i(i=1,2,3……n),則稱

(A)=MAX|

i|

為矩陣A的譜半徑.

1

in矩陣范數(shù)與譜半徑之間的關(guān)系為:

(A)

||A||.單擊此處試做例題第7頁(yè),共35頁(yè)，2024年2月25日，星期天5幾個(gè)定理及定義設(shè){x(k)}為Rn中的向量序列,x(*)為Rn中的向量對(duì)矩陣也有類似的結(jié)論

下一頁(yè)第8頁(yè),共35頁(yè)，2024年2月25日，星期天

如果矩陣A=(aij)滿足 n|aii|>

|aij|i=1,2,……n,

j=1,ji

則稱方陣A是嚴(yán)格(行)對(duì)角占優(yōu)的.

a11a12a13…a1n

a21

a22

a23…a2n

A=……………=L+D+U

an1an3an4…ann-421例矩陣A=1-972-610ULD第9頁(yè),共35頁(yè)，2024年2月25日，星期天Jacobi迭代一：設(shè)有方程組

a11x1+a12x2+····+a1nxn=b1a21x1+a22x2+····+a2nxn=b2

.....................

an1x1+an2x2+····+annxn=bn用矩陣表示：Ax=b（A為系數(shù)矩陣，非奇異；b為右端，x為解向量）}

上一頁(yè)第10頁(yè),共35頁(yè)，2024年2月25日，星期天假設(shè)aii0令cij=-aij/aii(ij)

gi=bi/aij,i=1,2,3,n

則

x1(k+1)=c12x2(k)+c13x3(k)++c1nxn(k)+g1

x2(k+1)=c21x1(k)+c23x3(k)++c2nxn(k)+g2。。。。。。。。。。。。。。。。。。。。。。。。。。。。

xn(k+1)=cn1x1(k)+cn2x2(k)++cn(n-1)xn-1(k)

+gn

Jacobi迭代格式若令

0c12c13…c1n

x1c210c23…c2n

x2BJ=……………x=..cn1cn3cn4…0xn

a11

g1

a22

g=g2易看出：BJ=D-1(D-A)=I-D-1,D=....

anngn

把方程組寫成容易迭代的形式：{第11頁(yè),共35頁(yè)，2024年2月25日，星期天Jacobi迭代公式第12頁(yè),共35頁(yè)，2024年2月25日，星期天Seidel迭代法為了加快收斂速度，同時(shí)為了節(jié)省計(jì)算機(jī)的內(nèi)存，我們作如下的改進(jìn)：每算出一個(gè)分量的近似值，立即用到下一個(gè)分量的計(jì)算中去，即用迭代格式：這樣所得的迭代法就稱為Gauss-Seidel迭代法，也稱為“異步迭代法”，簡(jiǎn)稱為GS迭代法．利用Ax=b及A=L+D+U,其中D為對(duì)角矩陣,L,U分別為嚴(yán)格下，上三角矩陣．則有，GS迭代法的矩陣形式為:

第13頁(yè),共35頁(yè)，2024年2月25日，星期天Seidel迭代法的具體形式Seidel迭代格式x1(k+1)=c12x2(k)+c13x3(k)++c1nxn(k)+g1

x2(k+1)=c21x1(k+1)+c23x3(k)++c2nxn(k)+g2。。。。。。。。。。。。。。。。。。。。。。。。。。。。

xn(k+1)=cn1x1(k+1)+cn2x2(k+1)++cn(n-1)xn-1(k+1)

+gn

假設(shè)aii0令cij=-aij/aii(ij)

gi=bi/aij,i=1,2,3,n

第14頁(yè),共35頁(yè)，2024年2月25日，星期天．收斂性及誤差估計(jì)Jacobi迭代和GS迭代格式可表述為統(tǒng)一形式:對(duì)于其收斂性，我們有如下定理：定理１：對(duì)任意初始向量x(0)及任意右段向量g，由此產(chǎn)生的迭代向量序列{x(k)}收斂的充要條件是證明：必要性：設(shè)｛x(k)｝收斂，其極限為x*，則第15頁(yè),共35頁(yè)，2024年2月25日，星期天因上式對(duì)任意均成立，故Bk0(k

),(B)<1

充分性：設(shè)

(B)<1,則I－B為非奇異陣,且=0,所以有唯一解,記為則

定理２：若||B||<1,則迭代法收斂.推論１若滿足下列條件之一：（１）第16頁(yè),共35頁(yè)，2024年2月25日，星期天(2)(3)

則迭代法收斂。

推論2：如果A為嚴(yán)格對(duì)角占優(yōu)陣，則其Jacobi迭代和Seidel迭代對(duì)任何初始向量x(0)都收斂。

推論3：如果A為對(duì)稱正定陣，則其Seidel迭代對(duì)任何初始向量x(0)都收斂。

第17頁(yè),共35頁(yè)，2024年2月25日，星期天下面給出

迭代法的誤差估計(jì)定理３：若，則對(duì)迭代法有實(shí)用的第18頁(yè),共35頁(yè)，2024年2月25日，星期天證明:第19頁(yè),共35頁(yè)，2024年2月25日，星期天三．例題及求解例：用迭代法解方程組AX=b,其中[已知該方程的解為]

解：本題分別用簡(jiǎn)單迭代法（Jacobi迭代法）和GS迭代法來解(1)簡(jiǎn)單迭代法

第20頁(yè),共35頁(yè)，2024年2月25日，星期天表１第21頁(yè),共35頁(yè)，2024年2月25日，星期天第22頁(yè),共35頁(yè)，2024年2月25日，星期天表2返回第23頁(yè),共35頁(yè)，2024年2月25日，星期天四.相關(guān)程序設(shè)計(jì)原始數(shù)據(jù)（A,b)可用一個(gè)二維數(shù)組存儲(chǔ)，也可將A用一個(gè)二維數(shù)組，b用一個(gè)一維數(shù)組分別存儲(chǔ)，存儲(chǔ)需要一個(gè)一維數(shù)組．程序中應(yīng)方便地對(duì)迭代方法和終止條件的選擇以及對(duì)初始向量和值的設(shè)置．在迭代過程中，為反映迭代情況，可設(shè)置一些中間數(shù)據(jù)的輸出，如迭帶次數(shù)，迭代向量，迭代殘向量等．當(dāng)然不需要每迭代一次都作輸出．這可作為收斂情況或不收斂情況的分析．作為不收斂的判定，可設(shè)置一個(gè)大的整數(shù)，當(dāng)?shù)鼛Т螖?shù)超過該數(shù)時(shí)作為不收斂處理．GS迭代法的計(jì)算公式為：第24頁(yè),共35頁(yè)，2024年2月25日，星期天開始TFTFT第25頁(yè),共35頁(yè)，2024年2月25日，星期天下面給出一個(gè)應(yīng)用BASIC程序解方程組的例子：程序如下運(yùn)行：5REMGAUSS-SELDEL10INPUTN,E,M20DIMA(N,N),B(N),X(N),Y(N)30FORI=1,TON40FORJ=1,TON50READA(I,J)第26頁(yè),共35頁(yè)，2024年2月25日，星期天

60NEXTJ70READB(I)80NEXTI90FORI=1TON100READX(I)110NEXTI120FORK=1TOM130R=0140FORI=1TON150S=0160T=X(I)170FORJ=1TON

第27頁(yè),共35頁(yè)，2024年2月25日，星期天180IFJ=1THEN210190P=A(I,J)*X(S)200S=STP210NEXTJ220X(I)=(B(I)-S)/A(I,I)230IFABS(X(I0-T)>RTHENR=ABS(S(I)-T)240NEXTI250PRINTK;”-”;:FORI=1TON:PRINT“X(‘;I;”)=“;INT((X(I)*100000+0.5)/100000;:NEXTI:PRINT255IFR<1THEN280260NEXTK..:第28頁(yè),共35頁(yè)，2024年2月25日，星期天270PRINT“DREDAISHBAI”280 END290 DATA10,-1,-2,7.2300 DATA-1,10,-2,8.3310 DATA-1,-1,5,4.2320 DATA0,0,0 RUN ?3,10E-6,20返回第29頁(yè),共35頁(yè)，2024年2月25日，星期天五.方法優(yōu)缺點(diǎn)討論

由以上例題的求解過程可明顯看出GS迭代法的收斂速度比簡(jiǎn)單迭代法快，但對(duì)于任意給定的一個(gè)方程組分別用簡(jiǎn)單迭代法和GS迭代