數(shù)值分析 第四章 基于MATLAB的科學(xué)計(jì)算—解線性方程組的迭代法

1、科學(xué)計(jì)算理論、方法及其基于MATLAB的程序?qū)崿F(xiàn)與分析三、 解線性方程組的迭代法（Iteration）線性方程組的理論求解公式x=Ab-1 （）在應(yīng)用于實(shí)際問題的計(jì)算時(shí)，通常面臨兩方面的問題、計(jì)算過程復(fù)雜，、不能保證算法的穩(wěn)定性；此外，當(dāng)初始數(shù)據(jù)（可能）存在誤差時(shí)，按公式（）即使求出了“精確解”意義也不大，因此，對(duì)于存在初始數(shù)據(jù)誤差、特別是大型的線性方程組求解，需要尋求能達(dá)到精度要求的、操作和計(jì)算過程相對(duì)簡(jiǎn)單的求解方法。下面將要介紹的迭代法就屬于這類方法。迭代法求解線性方程組的基本思想是） 不追求“一下子”得到方程組的解，而是在逐步逼近方程組的精確解的迭代過程中獲得滿足精度要求的近似解，這一點(diǎn)

2、與直接法不同；） 通過對(duì)問題的轉(zhuǎn)化，避免（困難的）矩陣求逆運(yùn)算。用迭代法求解線性方程組，首先要把線性方程組寫成等價(jià)的形式Ax=bx=Mx+f （）式（）的右端稱為迭代格式，由迭代格式（）確定如下的迭代算法：xk+1=Mxk+fxRn0k=1,2, （）對(duì)于給定的線性方程組，可以寫成不同的（無窮多）迭代格式，有意義的（可用的）迭代格式應(yīng)具有收斂性生成的解向量序列xn收斂于方程組的解；而好的迭代法應(yīng)具有較高的收斂速度。關(guān)于迭代法收斂性的兩個(gè)判別條件：a、充分必要條件是：矩陣M的譜半徑(M)=maxiii=1,2, ,n<1M<1。b、充分條件是：矩陣M的某個(gè)算子范數(shù)設(shè)x是方程組（）的解

3、，xm是迭代法（）生成的任一序列，因?yàn)閤=Mx+f，xm+1=Mxm+f所以x-xm=M(x-xm-1)=M(x-xm-2)= =Mm(x-x0) （）設(shè)T-1MT=JM=TJTm-1，其中矩陣J是矩陣M的Jordan標(biāo)準(zhǔn)型，那么，并且m容易驗(yàn)證M=TJTm-1m+limxm=xlimMTlimJm+mn+mT)mm+-1(x-x0)=0(x-x0)limi=0lim(Mm+i=1,2, n=0（）(M)<1此外，因?yàn)閤-xm=M(x-xm-1)MM Mm2x-xm-1x-xm-2（）x-x0所以M<1limm+Mm=0limm+x-xm=0limxm=xm+（）注：迭代格式（）所

4、確定的迭代法收斂與否，完全由系數(shù)矩陣M決定，而與常數(shù)項(xiàng)f無關(guān)常用的迭代法、Jacobian 迭代法:a11a21A= an1a110= 00a22 a12a22 an2a1na2n ann0a21 an1-ann-100- 00-a120-a1n-an-1n00 -0ann-=D-L-UAx=b-1-1xm+1=D(L+U)xm+DbA=D-L-UM=D-1(L+U-1f=Db)（）例1 解下面方程組（精確解為x*=(1,1,1)T）.10x1+3x2+x3=14,2x1-10x2+3x3=-5, x+3x+10x=14.231解 1） 改寫成等價(jià)形式1x=110(14-3x2-x3),11x

5、=-(-5-2x-3x)=(5+2x1+3x2), 21310101x=310(14-x1-3x2).2） 構(gòu)造迭代公式，即為雅可比迭代公式1(k+1)(k)(k)x=(14-3x-x),123101(k+1)(k)(k)x=(5+2x1+3x2), 2101(k+1)(k)(k)x=(14-x-3x),k=0,1,2, .312103） 取初始向量x(0)=(0,0,0)T，即x1(0)=x2(0)=x3(0)=0,代入上式，求出x1(1)=1410=1.4,x2(1)510=0.5,x3=(1)1410=1.4.再代回公式中，求出x1(2)=110110110(14-30.5-1.4)=1

6、.11， ，x2(2)=(5+21.4+30.5)=1.2x3(2)=(14-1.11-31.2)=1.11.依次迭代，計(jì)算結(jié)果如表4-1.Example intera_j.mitera_j2、Gauss-Seidel 迭代法:Ax=b-1-1xn+1=(D-L)Uxn+(D-L)bA=D-L-UM=(D-L)U-1()f=D-Lb-1（9）根據(jù)GS迭代法（9），可進(jìn)一步得到xn+1=(D-L)Uxn+(D-L)b-1-1(D-L)xn+1=Uxn+bxn+1=D-1（10）-1(Lxn+1+Uxn)+Db即x1n+12- xn+1-1=D xN-n+10a21 an100-ann-10x10

7、n+120 xn+10+ N0 xn+10-a120-a1nx1n 2xn -an-1n N0 xn+b（11）式（11）表明：Gauss-Seidel 迭代法在計(jì)算第k個(gè)迭代值x地利用了在此步迭代中得到的新的迭代值：xin+1kn+1時(shí)，及時(shí)，i=1,2, ,k-1，由于第n+1步的迭代值通常比第n步的迭代值更接近方程組的精確解，所以，在Jacobian迭代法和Gauss-Seidel迭代法都收斂的情況下，Gauss-Seidel迭代法的收斂速度比Jacobian迭代法的收斂速度快。例2 解下面方程組（與例1相同，精確解為x*=(1,1,1)T）.10x1+3x2+x3=14,2x1-10x

8、2+3x3=-5, x+3x+10x=14.231解 1） 原方程組改為等價(jià)方程組1x=110(14-3x2-x3),1x=(5+2x1+3x2),. 2101x=310(14-x1-3x2).2） 構(gòu)造迭代公式，即為高斯-賽德爾迭代公式1(k+1)(k)(k)x=(14-3x-x),231101(k+1)(k+1)(k)=(5+2x1+3x2),. x2101(k+1)(k+1)(k+1)x=(14-x-3x),k=0,1,2, .123103） 取初始向量x(0)=(0,0,0)T，即x1(0)=x2(0)=x3(0)=0,代入上式，求出x1(1)=1101110(14-30-0)=1.4

9、， ， .x2=(1)(5+21.4+30)=0.78x3=(1)10(14-1.4-30.78)=1.026迭代計(jì)算下去，得表4-2.Example itera_gs.mitera_gs對(duì)Gauss-Seidel迭代法做進(jìn)一步的研究，式（）還可以寫成如下的形式：xn+1=(D-L)Uxn+(D-L)b-1-1(D-L)xn+1=Uxn+bxn+1=Dxn+1=Dxn+1G_S-1-1J(Lxn+1+Lxn+Uxn-Lxn)+Db(L+U)xn+Db+D-1-1-1-1（12）L(xn+1-xn)=xn+DL(xn+1-xn)即Gauss-Seidel迭代法是在Jacobian迭代法的基礎(chǔ)上增

10、加了一個(gè)修正項(xiàng)：D-1L(xn+1-xn)并且這個(gè)修正項(xiàng)起到了加速的作用，受這一事實(shí)的啟發(fā)，為獲得更快的收斂速度，我們對(duì)Gauss-Seidel迭代法再做進(jìn)一步的研究xn+1=(D-L)Uxn+(D-L)b-1-1(D-L)xn+1=Uxn+bDxn+1=Dxn+Lxn+1+(U-D)xn+bxn+1=xn+D-1（13）(Lxn+1+(U-D)xn+b)式（13）表明Gauss-Seidel迭代法的第n+1步迭代值是在第n步迭代值的基礎(chǔ)上增加了一個(gè)修正項(xiàng)：D-1(Lxn+1+(U-D)xn+b) （14）并且這個(gè)修正項(xiàng)使第n+1步迭代值更接近方程組的精確解，受這一事實(shí)的啟發(fā)，我們希望通過用一

11、個(gè)適當(dāng)?shù)囊蜃映诵拚?xiàng)（14）的辦法達(dá)到獲得更快收斂速度的目的：xn+1=xn+wD(Lxn+1+(U-D)xn+b)Dxn+1=Dxn+w(Lxn+1+(U-D)xn+b)(D-wL)x=(1-w)D+wUx+wb-1（15）n+1nxn+1=(D-wL)-1(1-w)D+wUx-1n+w(D-wL)b從而得到3、SOR（Successive Over Relaxation Method） 迭代法:xn+1=(D-wL)-1(1-w)D+wUxn+w(D-wL)-1b 其中w稱為松弛因子，由于M=(D-wL)-1(1-w)D+wUa0 0-1(1-w)a1111-wa12-wa1n=wa21a

12、22 0(1-w)a22 0 -wan-1nwan1wann-1ann(1-w)ann(n1-w)nakkndet(M)=k=1n=(1-w)n=k(M) ak=1kkk=1-wn>1w<0<w>2nk(M)>1k(M)>1k=1所以，為保證SOR迭代法的收斂性，要求0<w<2。例3 用超松馳迭代法解下面方程組，取松馳因子=1.4.2-100x-12-1011x200-12-1x=1. 0-123x40（16）（17） 1）1） （ （解 方程組的精確解為：x=(1.2,1.4,1.6,0.8)T.取初值x(0)=(1,1,1,1)T，用高斯-賽

13、德爾迭代10次，得x(10)=(1.1966324,1.3955917,1.5964336,0.798216)T.利用SOR方法，構(gòu)造迭代公式(k+1)x1x(k+1)2x(k+1)3(k+1)x4=x1(k)+2(1-2x1(x1(k+1)(k)+x2),(k)(k)=x2=x3(k)2-2x2+x3),(k)(k)2(1+x2(x3(k+1)(k+1)-2x3(k)(k)+x4),(k)=x4(k)2-2x4).與高斯-賽德爾方法相同，初值為x(0)=(1,1,1,1)T.迭代計(jì)算結(jié)果列于表4-3.表4-3 SOR迭代的數(shù)值結(jié)果k1 1x1(k)1x2(k)x3(k)x1(k)1 2 3

14、4 51.7 1.616 1.65095 1.60198150.79 0.8152 0.829585 0.789553 0.79991291.49 1.4753 1.402361.343 1.195451.203472 1.4028735 1.5939059由表4-3可知，用超松馳迭代法只迭代了5次，結(jié)果與G-S法迭代10次的結(jié)果大體相同，可見，SOR方法的松馳因子起到了加速收斂的重要作用.Example itera_sor.mitera_sor關(guān)于迭代法收斂性的兩個(gè)判別條件：a、充分必要條件是：矩陣M的譜半徑(M)=maxiii=1,2, ,n<1M<1。b、充分條件是：矩陣M的某個(gè)算子范數(shù)特例：對(duì)于下面方程組，證明：雅可比迭代法收斂而高斯-賽德爾迭代法發(fā)散.11 2212-211X11X2=1. X31證明 1) 對(duì)于雅可比迭代矩陣0-1BJ=D(L+U)=-1-2BJ-20-22-1， 0的特征方程為det(I-BJ)=122-21=0.2BJ的特征多項(xiàng)式f()=3=0，所以=0為BJ的特征根，顯然(BJ)=0<1,因此，由迭代收斂基本定理可知雅可比迭代法收斂.2) 對(duì)于高斯-賽德爾迭代法，其迭代矩陣為0-1=(