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

1計(jì)算方法第四章解線性方程組的迭代解法醫(yī)學(xué)技術(shù)學(xué)院醫(yī)學(xué)信息工程教研室賴小波博士，副教授，碩士研究生導(dǎo)師

在第2章中我們知道，凡是迭代法都有一個(gè)收斂問題，有時(shí)某種方法對一類方程組迭代收斂，而對另一類方程組進(jìn)行迭代時(shí)就會發(fā)散。一個(gè)收斂的迭代法不僅具有程序設(shè)計(jì)簡單，適于自動計(jì)算，而且較直接法更少的計(jì)算量就可獲得滿意的解。因此，迭代法亦是求解線性方程組，尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一。第4章解線性方程組的迭代法上一章我們介紹了解線性方程組AX=b的直接法：對于給定的方程組，在沒有舍入誤差的假設(shè)下，能在預(yù)定的運(yùn)算次數(shù)內(nèi)求得精確解。最基本的直接法是Gauss消去法，其余的的方法全都受到Gauss消去法的啟發(fā)。計(jì)算代價(jià)高。本章介紹解線性方程組的另一種方法：迭代法。它基于一定的遞推格式，產(chǎn)生逼近方程組精確解的近似序列.收斂性是其為迭代法的前提，此外，存在收斂速度與誤差估計(jì)問題。

簡單實(shí)用,誘人。第4章解線性方程組的迭代法問題引入用迭代法求解線性方程組

解構(gòu)造方程組的等價(jià)方程組據(jù)此建立迭代公式取計(jì)算得

迭代解離精確解越來越遠(yuǎn)迭代不收斂

取計(jì)算得

迭代解離精確解越來越近，迭代收斂

構(gòu)造方程組等價(jià)方程組據(jù)此建立迭代公式考慮解方程組準(zhǔn)確解建立與上式等價(jià)的形式據(jù)此建立迭代格式迭代結(jié)果如下表迭代次數(shù)

x1

x2

x3000010.720.830.8420.9711.071.1531.05711.15711.248241.085351.185341.2828251.0950981.1950991.29413861.0983381.1983371.29803971.0994421.194421.29933581.0998111.1998111.29977791.0999361.1999361.299924101.0999761.1999791.199975111.0999931.1999931.299991121.0999981.1999981.299997131.0999991.1999991.2999999141.11.21.3151.11.21.3迭代次數(shù) x1

x2

x34.2迭代法的基本思想迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價(jià)方程組，對任選一組初始值，按某種計(jì)算規(guī)則，不斷地對所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組的近似解。與解f(x)=0

的非線性方程相似，將方程組等價(jià)改寫成形式，從而建立迭代格式，從出發(fā)，生成迭代序列設(shè)非奇異，，則線性方程組有惟一解，經(jīng)過變換構(gòu)造出一個(gè)等價(jià)同解方程組將上式改寫成迭代式選定初始向量,反復(fù)不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法迭代法是一種逐次逼近的方法,與直接法比較,具有:程序簡單,存儲量小的優(yōu)點(diǎn)。特別適用于求解系數(shù)矩陣為大型稀疏矩陣的方程組。

如果存在極限則稱迭代法是收斂的，否則就是發(fā)散的。對于給定的方程組可以構(gòu)造各種迭代公式。并非全部收斂收斂時(shí)，在迭代公式中當(dāng)時(shí)則故是方程組的解4.3雅可比（Jacobi）迭代法4.3.1雅可比迭代法算法構(gòu)造例4.2用雅可比迭代法求解方程組解：從方程組的三個(gè)方程中分離出和建立迭代公式

取初始向量進(jìn)行迭代,可以逐步得出一個(gè)近似解的序列：（k=1,2,…）直到求得的近似解能達(dá)到預(yù)先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。當(dāng)?shù)降?0次有計(jì)算結(jié)果表明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T?？疾煲话愕姆匠探M，將n元線性方程組

寫成若,分離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式。4.3.2雅可比迭代法的矩陣表示設(shè)方程組的系數(shù)矩陣A非奇異，且主對角元素，則可將A分裂成

記作A=L+D+U則等價(jià)于即因?yàn)?/p>

，則這樣便得到一個(gè)迭代公式令則有（k=0,1,2…）稱為雅可比迭代公式,B稱為雅可比迭代矩陣其中在例4.2中,由迭代公式寫出雅可比迭代矩陣為雅可比迭代矩陣表示法，主要是用來討論其收斂性，實(shí)際計(jì)算中，要用雅可比迭代法公式的分量形式。即

(k=0,1,2,…)4.4高斯-塞德爾（Gauss-Seidel）迭代法4.4.1高斯-塞德爾迭代法的基本思想

在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求時(shí)用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

(i=1,2,…,n

k=0,1,2,…)例4.3用GaussSeidel迭代格式解方程組

精確要求為ε=0.005

解GaussSeidel迭代格式為取初始迭代向量,迭代結(jié)果為：x*≈例4.4用Jacobi和Gauss-Seidel迭代法求解方程組解：Jacobi迭代格式G-S迭代格式計(jì)算結(jié)果取初值Jacobi迭代法要求精度迭代次數(shù)

0.001

9(1.00025071.00006941.0002507)

0.0001

10(0.99995411.00012530.9999541)0.00001

14(0.99999811.00000200.9999981)方程組的近似解Gauss-Seidel迭代法

要求精度迭代次數(shù)

0.001

5(0.99979160.99984791.0000664)

0.0001

7(0.99999290.99999491.0000022)0.00001

8(1.00000131.00000090.9999996)方程組的近似解取初值計(jì)算結(jié)果4.4.2Gauss—Seidel迭代法的矩陣表示將A分裂成A=L+D+U，則等價(jià)于(L+D+U)x

=b于是,則高斯—塞德爾迭代過程因?yàn)?所以

則高斯-塞德爾迭代形式為：

故

令

4.4.3高斯—塞德爾迭代算法實(shí)現(xiàn)高斯-塞德爾迭代算法的計(jì)算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變元的某個(gè)新值后,就改用新值替代老值進(jìn)行這一步剩下的計(jì)算。

高斯-塞德爾迭代算法的程序?qū)崿F(xiàn)(見附錄AA-7用高斯—塞德爾迭代法求解線性方程組）4.6雅可比（Jacobi）算法構(gòu)造設(shè)n階方程組的系數(shù)矩陣A非奇異,主對角元素非零，從方程組的第i

個(gè)方程中解出，得到等價(jià)的方程組

由上式構(gòu)造迭代公式

初始值任取。其算法實(shí)現(xiàn)步驟為：雅可比迭代算法實(shí)現(xiàn)步驟（1）輸入方程組的階數(shù)n，系數(shù)矩陣A，右端常數(shù)矩陣b，最大迭代次數(shù)MAX_N以及容許誤差；（2）k=0；（3）對，計(jì)算：（4），成立轉(zhuǎn)（6），否則繼續(xù)；（5）成立，，轉(zhuǎn)（3）；否則輸出失敗信息，轉(zhuǎn)（7）（6）輸出；（7）結(jié)束。雅可比迭代法的流程圖描述

例4.5用雅可比迭代法求解線性方程組，式中#include<stdio.h>#include<math.h>#defineN3/*N為方程組系數(shù)矩陣的階數(shù)*/#defineMAX_N100/*最大迭代次數(shù)*/#defineepsilon1e-6/*容許誤差*/intyacobi(floata[N][N],floatb[N],floatx[N]){floatd,s,max,y[N];inti,j,k,flag;k=0;for(i=0;i<N;i++)x[i]=0.0;while(1){max=0.0;k++;for(i=0;i<N;i++){s=0.0; for(j=0;j<N;j++) if(j!=i)s=s+a[i][j]*x[j];y[i]=(b[i]-s)/a[i][i]; d=fabs(y[i]-x[i]);if(max<d)max=d;/*將循環(huán)過程中最大的d值賦值給max*/}for(i=0;i<N;i++)x[i]=y[i];if(max<eps)/*當(dāng)max<eps時(shí)結(jié)束迭代*/{flag=1;break;}if(k>=MAX_N)/*當(dāng)k>=MAX_N時(shí)反饋失敗信息，結(jié)束迭代*/{flag=0;break;}}return(flag);}

voidzg_matric(floata[N][N],floatb[N])/*輸出增廣矩陣*/{inti,j;for(i=0;i<N;i++){for(j=0;j<N;j++) printf("%10f",a[i][j]);printf("%12f",b[i]);printf("\n");}printf("\n");}

main(){floata[N][N]={{10,1,-2},{-2,10,-1},{1,-2,5}};floatb[N]={9,7,4};floatx[N];inti,k;zg_matric(a,b);k=yacobi(a,b,x);if(k==1)for(i=0;i<N;i++)/*輸出方程組的解*/printf("x%d=%11.7f\n",i+1,x[i]);elseprintf("TheMethodisdisconvergent!\n");/*輸出失敗信息*/}程序運(yùn)行結(jié)果：

10.0000001.000000-2.0000009.000000-2.00000010.000000-1.0000007.0000001.000000-2.0000005.0000004.000000x1=1.0000002x2=0.9999999x3=0.9999996

4.7迭代法的收斂性我們知道,對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂。現(xiàn)在分析它們的收斂性。在什么條件下迭代序列收斂？先引入如下定理

對于方程組

經(jīng)過等價(jià)變換構(gòu)造出的等價(jià)方程組定理4.1對給定方陣G,若,則為非奇異矩陣,且證:用反證法,若為奇異矩陣,則存在非零向量x,使,即有由相容性條件得又由于即有由于,兩端消去,有,與已知條件矛盾,假設(shè)不成立,命題得證。將G分別取成G和-G，再取范數(shù)定理4.2迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證:充分性設(shè)迭代公式收斂,當(dāng)k→∞時(shí),則在迭代公式兩端同時(shí)取極限得記,則收斂于0(零向量),且有于是

由于可以是任意向量,故收斂于0當(dāng)且僅當(dāng)收斂于零矩陣，即當(dāng)時(shí)于是

所以必有

由此定理可知，不論是雅可比迭代法、高斯—塞德爾迭代法還是超松弛迭代法，它們收斂的充要條件是其迭代矩陣的譜半徑。

事實(shí)上,在例4.1中,迭代矩陣G=其特征多項(xiàng)式為,特征值為-2，-3，,所以迭代發(fā)散

必要性:設(shè),則必存在正數(shù)ε,使則存在某種范數(shù),使,則所以則收斂于即故收斂于0定理4.3(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計(jì)式,且有誤差估計(jì)式及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),已知,因此,根據(jù)定理4.2可知迭代公式收斂又因?yàn)?則det(I-G)≠0,I-G為非奇異矩陣,故x＝Gx＋d有惟一解,即與迭代過程相比較,有∴

兩邊取范數(shù)由迭代格式，有

兩邊取范數(shù),代入上式證畢

由定理知，當(dāng)時(shí)，其值越小，迭代收斂越快，在程序設(shè)計(jì)中通常用相鄰兩次迭代（ε為給定的精度要求）作為控制迭代結(jié)束的條件即復(fù)習(xí)：1.雅可比（Jacobi）算法設(shè)n階方程組的系數(shù)矩陣A非奇異,主對角元素非零，從方程組的第i

個(gè)方程中解出，得到等價(jià)的方程組

由上式構(gòu)造迭代公式

初始值任取。2.高斯-塞德爾（Gauss-Seidel）迭代法在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求時(shí)用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

(i=1,2,…,n

k=0,1,2,…)例4.8已知線性方程組考察用Jacobi迭代和G-S迭代求解時(shí)的收斂性故Jacobi迭代收斂

解:⑴雅可比迭代矩陣⑵

將系數(shù)矩陣分解

則高斯-塞德爾迭代矩陣

故高斯—塞德爾迭代收斂。

則高斯-塞德爾迭代矩陣

定理4.4設(shè)n階方陣為對角占優(yōu)陣,則非奇異證:因A為對角占優(yōu)陣,其主對角元素的絕對值大于同行其它元素絕對值之和,且主對角元素全不為0,故對角陣為非奇異。作矩陣?yán)脤钦純?yōu)知

由定理4.1知非奇異,從而A非奇異,證畢系數(shù)矩陣為對角占優(yōu)陣的線性方程組稱作對角占優(yōu)方程組。定理4.5對角占優(yōu)線性方程組的雅可比迭代公式和高斯-賽德爾迭代公式均收斂證明:略例4.7設(shè)求解線性方程組的雅可比迭代

求證：當(dāng)<1時(shí),相應(yīng)的高斯-塞德爾迭代收斂

又<1,故有則證:由于B是雅可比迭代的迭代矩陣,故有所以Ax=b的系數(shù)距陣為對角占優(yōu)距陣,故G-S迭代收斂例4.8

設(shè),證明,求解方程組的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散

證:雅可比迭代矩陣其譜半徑

例4.8

設(shè),證明,求解方程組的Jacobi迭代與G-S迭代同時(shí)收斂或發(fā)散

證:G-S迭代矩陣

其譜半徑

顯然,和同時(shí)小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性

例4.9

考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中解：先計(jì)算迭代矩陣求特征值雅可比矩陣

(B)=0<1∴用雅可比迭代法求解時(shí)，迭代過程收斂1=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時(shí)，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值∴Ax=b的系數(shù)矩陣按行嚴(yán)格對角占優(yōu),故高斯-塞德爾迭代收斂例4.10設(shè)有迭代格式

X(k+1)=BX(k)+g(k=0,1,2……）其中B=I-A,如果A和B的特征值全為正數(shù)，試證：該迭代格式收斂。分析:根據(jù)A，B和單位矩陣I之間的特征值的關(guān)系導(dǎo)出()<1,從而說明迭代格式收斂。證:因?yàn)锽=I-A,故(B)=(I)-(A)=1-(A)

(A)+(B)=1由于已知(A)和(B)全為正數(shù)，故0<(B)<1,從而(B)<1所以該迭代格式收斂。例4.11設(shè)方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為當(dāng)時(shí),對初值x(0)均收斂例4.12設(shè)方程組寫出解方程組的Gauss-Seidel迭代矩陣，并討論迭代收斂的條件。解②Gauss-Seidel矩陣為

時(shí),對任意初值均收斂。當(dāng)求解AX=b,當(dāng)取何值時(shí)迭代收斂？

例4.13給定線性方程組AX=b

用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1,…）解:所給迭代公式可化為迭代公式的迭代矩陣為即

2-(2-5)+1-5+4

2=0

2-(2-5)+(1-)(1-4)=0

[-(1-)][-(1-4)]=0

1=1-2=1-4(B)=max{|1-|,|1-4|}<1取0<<1/2迭代收斂JacobiG-S判斷收斂迭代求解判斷收斂迭代求解總結(jié)本章小結(jié)

本章介紹了解線性方程組迭代法的一些基本理論和具體方法。迭代法是一種逐次逼近的方法，即對任意給定的初始近似解向量，按照某種方法逐步生成近似解序列，使解序列的極限為方程組的解。注意到在使用迭代法解方程組時(shí)，其迭代矩陣B和迭代向量f在計(jì)算過程中始終不變,迭代法具有循環(huán)的計(jì)算公式,方法簡單，程序?qū)崿F(xiàn)方便，它的優(yōu)點(diǎn)是能充分利用系數(shù)的稀疏性,適宜解大型稀疏系數(shù)矩陣的方程組。

迭代法不存在誤差累積問題。使用迭代法的關(guān)鍵問題是其收斂性與收斂速度，收斂性與迭代初值的選取無關(guān)，這是比一般非線性方程求根的優(yōu)越之處。在實(shí)際計(jì)算中，判斷一種迭代格式收斂性較麻煩，由于求迭代的譜半徑時(shí)需要求特征值，當(dāng)矩陣的階數(shù)較大時(shí)，特征值不易求出，通常采用矩陣的任一種范數(shù)都小于1或?qū)钦純?yōu)來判斷收斂性。有時(shí)也可邊計(jì)算邊觀察其收斂性。如何加快迭代過程的收斂速度是一個(gè)很重要的問題，實(shí)用中更多的采用SOR法，選擇適當(dāng)?shù)乃神Y因子ω有賴于實(shí)際經(jīng)驗(yàn)。我們應(yīng)針對不同的實(shí)際問題，采用適當(dāng)?shù)臄?shù)值算法。例4.15設(shè)求解線性方程組Ax=b的簡單迭代法