數(shù)值分析第三章解線性方程組的迭代法第一頁，共三十三頁，2022年，8月28日由此建立方程組的迭代公式

x(k+1)=Mx(k)+g,k=0,1,2,…(3.2)其中M稱為迭代矩陣。對(duì)任意取定的初始向量x(0),由(3.2)式可逐次算出迭代向量x(k),k=1,2,…,如果向量序列{x(k)}收斂于x*,由(3.2)式可得x*=Mx*+g

從而x*是方程組x=Mx+g的解,也就是方程組Ax=b的解.這種求解線性方程組的方法稱為迭代法

,若迭代序列{x(k)}收斂,則稱迭代法收斂,否則稱迭代法發(fā)散.§1Jacobi迭代法和Gauss-Seidel迭代法Jacobi方法是由方程組(3.1)中第k個(gè)方程解出x(k),得到等價(jià)方程組:第二頁，共三十三頁，2022年，8月28日從而得迭代公式第三頁，共三十三頁，2022年，8月28日式(3.3)稱為Jacobi迭代法,簡(jiǎn)稱為J迭代法.,則J迭代法可寫成

x(k+1)=Bx(k)+gk=0,1,2,…可見,J迭代法的迭代矩陣為若記

J法也記為第四頁，共三十三頁，2022年，8月28日G-S迭代法也可記為式(3.4)稱為Gauss-Seidel迭代法,簡(jiǎn)稱為G-S迭代法.若在J迭代法中,充分利用新值,則可以得到如下的迭代公式第五頁，共三十三頁，2022年，8月28日方程組的精確解為x*=(1,1,1)T.

解J迭代法計(jì)算公式為例1用J法和G-S法求解線性方程組取初始向量x(0)=(0,0,0)T,迭代可得計(jì)算結(jié)果列表如下:第六頁，共三十三頁，2022年，8月28日可見,迭代序列逐次收斂于方程組的解,而切迭代7次得到精確到小數(shù)點(diǎn)后兩位的近似解.kx1(k)x2(k)x3(k)‖x(k)-x*‖0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636G-S迭代法的計(jì)算公式為:第七頁，共三十三頁，2022年，8月28日同樣取初始向量x(0)=(0,0,0)T,計(jì)算結(jié)果為由計(jì)算結(jié)果可見,G-S迭代法收斂較快.取精確到小數(shù)點(diǎn)后兩位的近似解,G-S迭代法只需迭代3次,而J迭代法需要迭代7次.kx1(k)x2(k)x3(k)‖x(k)-x*‖012301.41.06340.995104400.781.020480.9952756801.0260.9875161.0019068610.40.06340.0048956第八頁，共三十三頁，2022年，8月28日為了進(jìn)一步研究,從矩陣角度來討論上述迭代法.對(duì)線性方程組Ax=b,記

D=diag(a11,a22,…,ann)則有A=D-L-U于是線性方程組Ax=b可寫成(D-L-U)x=b等價(jià)于

Dx=(L+U)x+b或x=D-1(L+U)x+D-1b第九頁，共三十三頁，2022年，8月28日由此建立J迭代法迭代公式

x(k+1)=D-1(L+U)x(k)+D-1bk=0,1,2,…或?qū)懗?/p>

x(k+1)=Bx(k)+gk=0,1,2,…其中G-S迭代法迭代公式可寫成

x(k+1)=D-1Lx(k+1)+D-1Ux(k)+D-1b第十頁，共三十三頁，2022年，8月28日討論迭代法

x(k+1)=Mx(k)+gk=0,1,2,…

Dx(k+1)=Lx(k+1)+Ux(k)+b

(D-L)x(k+1)=Ux(k)+bx(k+1)=(D-L)-1Ux(k)+(D-L)-1b所以G-S迭代法可以寫成

x(k+1)=Gx(k)+gk=0,1,2,…其中G=(D-L)-1U,g=(D-L)-1b§2迭代法的收斂性的收斂性.第十一頁，共三十三頁，2022年，8月28日記誤差向量e(k)=x(k)-x*,則迭代法收斂就是e(k)0.由于

x(k+1)=Mx(k)+gk=0,1,2,…

x*=Mx*+gk=0,1,2,…所以

e(k+1)=Me(k),

k=0,1,2,…遞推可得

e(k)=Mke(0),

k=0,1,2,…可見,當(dāng)k時(shí),e(k)0MkO.對(duì)任意初始向量x(0),迭代法收斂(M)<1.定理3.1

證若‖Mk‖0,則k(M)=(Mk)‖Mk‖0,所以(M)<1.若(M)<1,則存在>0,使得(M)+<1.則‖Mk‖‖M‖k((M)+)k0.第十二頁，共三十三頁，2022年，8月28日

若‖M‖<1,則對(duì)任意x(0),迭代法收斂,而且

定理3.2

證由于

x(k+1)=Mx(k)+gx(k)=Mx(k-1)+gx*=Mx*+g所以

x(k+1)-x(k)=M(x(k)-x(k-1)),x(k+1)–x*=M(x(k)–x*)于是有

‖x(k+1)-x(k)‖‖M‖‖x(k)-x(k-1)‖

‖x(k+1)–x*‖‖M‖‖x(k)–x*‖

‖x(k)–x*‖=‖(x(k)–x(k+1))+(x(k+1)–x*)‖‖x(k)–x(k+1)‖+‖x(k+1)–x*‖第十三頁，共三十三頁，2022年，8月28日

‖x(k)–x*‖‖M‖‖x(k)–x(k-1)‖+‖M‖‖x(k)–x*‖所以定理3.2只是收斂的充分條件,并不必要,如則‖M‖1=1.2,‖M‖=1.3,‖M‖2=1.09,‖M‖F(xiàn)=1.17但(M)=0.8<1,所以對(duì)應(yīng)的迭代法是收斂的.由(3.5)式可見,‖x(k)-x(k-1)‖很小時(shí),‖x(k)–x*‖就很小,實(shí)際上用‖x(k)-x(k-1)‖<作為迭代終止的條件。第十四頁，共三十三頁，2022年，8月28日例如，例1中J-法計(jì)算結(jié)果如下：kx1(k)x2(k)x3(k)‖x(k)-x*‖0123456701.41.110.9290.99061.011591.0002510.998236400.51.201.0550.96450.99531.0057951.000125501.41.110.9290.99061.011591.0002510.998236410.50.20.0710.03550.011590.0057950.0017636‖x(6)-x(5)‖=0.011339,‖x(7)–x(6)‖=0.0056695由(3.6)式可得:第十五頁，共三十三頁，2022年，8月28日若使‖x(k)–x*‖<,只需可以事先估計(jì)達(dá)到某一精度需要迭代多少步。,即

用J迭代法求例1中方程組的解,取x(0)=(0,0,0)T,若使誤差x(k)-x*<10-5,問需要迭代多少次?

解由例1知,x(1)=(1.4,0.5,1.4)T,于是有,x(1)-x(0)=1.4,B=0.5.例2k應(yīng)滿足故取k=19,即需要迭代19次.第十六頁，共三十三頁，2022年，8月28日§3J迭代法和G-S迭代法的收斂性

定理3.3

J迭代法收斂(B)<1;若‖B‖<1J迭代法收斂;G-S迭代法收斂(G)<1;若‖G‖<1G-S迭代法收斂;

定義3.1若n階矩陣A=(aij)滿足:則稱矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣.

引理若A是嚴(yán)格對(duì)角占優(yōu)矩陣,則det(A)0.

證

A=D-L-U=D(E-D-1(L+U))=D(E-B)第十七頁，共三十三頁，2022年，8月28日因此,(B)‖B‖<1,故=1不是B的特征值,det(E-B)0。

定理3.4設(shè)A是嚴(yán)格對(duì)角占優(yōu)矩陣,則解線性方程組Ax=b的J迭代法和G-S迭代法均收斂。因?yàn)锳是嚴(yán)格對(duì)角占優(yōu)矩陣,所以det(D)0,而且所以,det(A)0.

證由于‖B‖<1,所以J迭代法收斂。設(shè)是G的任一特征值,則滿足特征方程第十八頁，共三十三頁，2022年，8月28日

det(E-G)=det(E-(D-L)-1U)所以有det((D-L)-U)=0若||1,則矩陣(D-L)-U是嚴(yán)格對(duì)角占優(yōu)矩陣,這與det((D-L)-U)=0矛盾,所以||<1,于是(G)<1.定理3.5設(shè)A是對(duì)稱正定矩陣,則解方程組Ax=b的(1)J迭代法收斂2D-A也正定;(2)G-S迭代法必收斂.=det((D-L)-1)((D-L)-U)=det((D-L)-1)det((D-L)-U)=0第十九頁，共三十三頁，2022年，8月28日試建立一個(gè)收斂的迭代格式,并說明收斂性.

解按如下方法建立迭代格式例3已知解線性方程組由于迭代矩陣的行范數(shù)小于1,故此迭代法收斂.第二十頁，共三十三頁，2022年，8月28日改寫成將Jacobi迭代法§4逐次超松弛迭代法---SOR方法寫成向量形式就是

x（k+1）=x（k）+D-1(b-Ax(k)),k=0,1,2,…Gauss-Seidel迭代法也可寫成或?qū)懗上蛄啃问?/p>

x（k+1）=x（k）+D-1(b+Lx(k+1)+(U-D)x(k)),k=0,1,2,…第二十一頁，共三十三頁，2022年，8月28日構(gòu)造迭代公式此迭代法稱為SOR方法,其中參數(shù)稱為松弛因子,當(dāng)>1時(shí)稱為超松弛迭代,當(dāng)<1時(shí)稱為欠松弛迭代.其矩陣形式

x(k+1)=x(k)+D-1(b+Lx(k+1)+(U-D)x(k)),k=0,1,2,…于是有

Dx(k+1)=Dx(k)+(b+Lx(k+1)+(U-D)x(k))所以

x(k+1)=(D-L)-1[(1-)D+U]x(k)+(D-L)-1b,k=0,1,2,…因此,SOR方法的迭代矩陣為

￡=(D-L)-1[(1-)D+U]第二十二頁，共三十三頁，2022年，8月28日

SOR方法收斂(￡)<1;若‖￡‖<1,則SOR方法收斂.

定理3.7若SOR方法收斂,則0<<2.定理3.6

證設(shè)SOR方法收斂,則(￡)<1,所以|det(￡)|=|12…n|<1而det(￡)=det[(D-L)-1((1-)D+U)]

=det[(E-D-1L)-1]det[(1-)E+D-1U)]

=(1-)n于是|1-|<1,或0<<2第二十三頁，共三十三頁，2022年，8月28日定理3.8設(shè)A是嚴(yán)格對(duì)角占優(yōu)矩陣,則解方程組Ax=b的SOR方法,當(dāng)0<1時(shí)收斂.

定理3.9設(shè)A是對(duì)稱正定矩陣,則解方程組Ax=b的SOR方法,當(dāng)0<<2時(shí)收斂.

證設(shè)是￡的任一特征值,y是對(duì)應(yīng)的特征向量,則[(1-)D+U]y=(D-L)y于是(1-)(Dy,y)+(Uy,y)=[(Dy,y)-(Ly,y)]由于A=D-L-U是對(duì)稱正定的,所以D是正定矩陣,且L=UT.若記(Ly,y)=+i,則有第二十四頁，共三十三頁，2022年，8月28日(Dy,y)=>0(Uy,y)=(y,Ly)=(Ly,y)=-i0<(Ay,y)=(Dy,y)-(Ly,y)-(Uy,y)=-2所以當(dāng)0<<2時(shí),有(-+)2-(-)2=(2-)(2-)=(2-)(2-)<0所以||2<1,因此(￡)<1,即S0R方法收斂.第二十五頁，共三十三頁，2022年，8月28日可得=2/設(shè)是B的任一特征值,y是對(duì)應(yīng)的特征向量,則(L+U)y=Dy于是(Ly,y)+(Uy,y)=(Dy,y)當(dāng)A對(duì)稱正定時(shí),即2-<0時(shí),||<12+>0而((2D-A)y,y)=(Dy,y)+(Ly,y)+(Uy,y)=+2即,當(dāng)A對(duì)稱正定時(shí),Jacobi迭代法收斂2D-A正定.

SOR方法收斂的快慢與松弛因子的選擇有密切關(guān)系.但是如何選取最佳松弛因子,即選取=*,使(￡)達(dá)到最小,是一個(gè)尚未很好解決的問題.實(shí)際上可采用試算的方法來確定較好的松弛因子.經(jīng)驗(yàn)上可取1.4<<1.6.第二十六頁，共三十三頁，2022年，8月28日

用SOR方法解線性方程組

解SOR方法迭代公式為方程組的精確解是x*=(2,1,-1)T.例4取x(0)=(0,0,0)T,=1.46,計(jì)算結(jié)果如下: