第四章線性代數(shù)方程組的迭代解法

第四章線性代數(shù)方程組的迭代解法第一頁，共五十四頁，2022年，8月28日4.2迭代法的基本思想迭代法的基本思想是將線性方程組轉(zhuǎn)化為便于迭代的等價方程組，對任選一組初始值，按某種計算規(guī)則，不斷地對所得到的值進(jìn)行修正，最終獲得滿足精度要求的方程組的近似解。

第二頁，共五十四頁，2022年，8月28日設(shè)非奇異，，則線性方程組

有惟一解，經(jīng)過變換構(gòu)造出一個等價同解方程組將上式改寫成迭代式選定初始向量,反復(fù)不斷地使用迭代式逐步逼近方程組的精確解,直到滿足精度要求為止。這種方法稱為迭代法第三頁，共五十四頁，2022年，8月28日如果存在極限則稱迭代法是收斂的，否則就是發(fā)散的。收斂時，在迭代公式中當(dāng)時，,則,故是方程組的解。對于給定的方程組可以構(gòu)造各種迭代公式。并非全部收斂

第四頁，共五十四頁，2022年，8月28日例4.1用迭代法求解線性方程組

解構(gòu)造方程組的等價方程組據(jù)此建立迭代公式取計算得迭代解離精確解越來越遠(yuǎn)迭代不收斂

第五頁，共五十四頁，2022年，8月28日4.3雅可比（Jacobi）迭代法4.3.1雅可比迭代法算法構(gòu)造

例4.2用雅可比迭代法求解方程組解：從方程組的三個方程中分離出和建立迭代公式第六頁，共五十四頁，2022年，8月28日取初始向量進(jìn)行迭代,可以逐步得出一個近似解的序列：（k=1,2,…）直到求得的近似解能達(dá)到預(yù)先要求的精度，則迭代過程終止，以最后得到的近似解作為線性方程組的解。當(dāng)?shù)降?0次有計算結(jié)果表明，此迭代過程收斂于方程組的精確解x*=(3,2,1)T。

第七頁，共五十四頁，2022年，8月28日考察一般的方程組，將n元線性方程組

寫成若,分離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式。第八頁，共五十四頁，2022年，8月28日4.3.2雅可比迭代法的矩陣表示

設(shè)方程組的系數(shù)矩陣A非奇異，且主對角元素，則可將A分裂成

記作A=L+D+U第九頁，共五十四頁，2022年，8月28日則等價于即因為

，則這樣便得到一個迭代公式令則有（k=0,1,2…）稱為雅可比迭代公式,B稱為雅可比迭代矩陣第十頁，共五十四頁，2022年，8月28日其中

在例4.2中,由迭代公式寫出雅可比迭代矩陣為第十一頁，共五十四頁，2022年，8月28日雅可比迭代矩陣表示法，主要是用來討論其收斂性，實際計算中，要用雅可比迭代法公式的分量形式。即

(k=0,1,2,…)第十二頁，共五十四頁，2022年，8月28日

雅可比迭代法的算法實現(xiàn)

第十三頁，共五十四頁，2022年，8月28日4.4高斯-塞德爾（Gauss-Seidel）迭代法4.4.1高斯-塞德爾迭代法的基本思想在Jacobi迭代法中，每次迭代只用到前一次的迭代值，若每次迭代充分利用當(dāng)前最新的迭代值，即在求時用新分量代替舊分量,就得到高斯-賽德爾迭代法。其迭代法格式為：

(i=1,2,…,n

k=0,1,2,…)第十四頁，共五十四頁，2022年，8月28日例4.3用GaussSeidel迭代格式解方程組

精確要求為ε=0.005

解GaussSeidel迭代格式為取初始迭代向量,迭代結(jié)果為：x*≈第十五頁，共五十四頁，2022年，8月28日4.4.2Gauss—Seidel迭代法的矩陣表示將A分裂成A=L+D+U，則等價于

(L+D+U)x=b

于是,則高斯—塞德爾迭代過程

因為,所以

則高斯-塞德爾迭代形式為：故令第十六頁，共五十四頁，2022年，8月28日4.4.3高斯—塞德爾迭代算法實現(xiàn)高斯-塞德爾迭代算法的計算步驟與流程圖與雅可比迭代法大致相同，只是一旦求出變元的某個新值后,就改用新值替代老值進(jìn)行這一步剩下的計算。

高斯-塞德爾迭代算法的程序?qū)崿F(xiàn)(見附錄AA-7

用高斯—塞德爾迭代法求解線性方程組

）

第十七頁，共五十四頁，2022年，8月28日4.5

超松弛迭代法（SOR方法）使用迭代法的困難在于難以估計其計算量。有時迭代過程雖然收斂，但由于收斂速度緩慢，使計算量變得很大而失去使用價值。因此，迭代過程的加速具有重要意義。逐次超松弛迭代（SuccessiveOverrelaxaticMethod，簡稱SOR方法）法，可以看作是帶參數(shù)的高斯—塞德爾迭代法，實質(zhì)上是高斯-塞德爾迭代的一種加速方法。

第十八頁，共五十四頁，2022年，8月28日4.5.1超松弛迭代法的基本思想

超松弛迭代法目的是為了提高迭代法的收斂速度，在高斯—塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果與高斯-塞德爾迭代方法的迭代值適當(dāng)加權(quán)平均，期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一，有著廣泛的應(yīng)用。其具體計算公式如下：

⑴用高斯—塞德爾迭代法定義輔助量。第十九頁，共五十四頁，2022年，8月28日⑵把取為與的加權(quán)平均，即

合并表示為：

式中系數(shù)ω稱為松弛因子，當(dāng)ω=1時，便為高斯-塞德爾迭代法。為了保證迭代過程收斂，要求0<ω<2。

當(dāng)0<ω<1時，低松弛法；當(dāng)1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。

第二十頁，共五十四頁，2022年，8月28日4.5.2超松弛迭代法的矩陣表示設(shè)線性方程組的系數(shù)矩陣A非奇異,且主對角元素,則將A分裂成A=L+D+U,則超松弛迭代公式用矩陣表示為或故

顯然對任何一個ω值,(D+ωL)非奇異,(因為假設(shè))于是超松弛迭代公式為令則超松弛迭代公式可寫成第二十一頁，共五十四頁，2022年，8月28日例4.4用SOR法求解線性方程組

取ω=1.46，要求解：SOR迭代公式

k=0,1,2,…，

初值該方程組的精確解只需迭代20次便可達(dá)到精度要求如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要達(dá)到同樣精度,需要迭代110次第二十二頁，共五十四頁，2022年，8月28日4.6迭代法的收斂性我們知道,對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式，但并非一定收斂。現(xiàn)在分析它們的收斂性。對于方程組經(jīng)過等價變換構(gòu)造出的等價方程組

在什么條件下迭代序列收斂？先引入如下定理

第二十三頁，共五十四頁，2022年，8月28日定理4.1對給定方陣G,若,則為非奇異矩陣,且

證:用反證法,若為奇異矩陣,則存在非零向量x,使,即有由相容性條件得

由于,兩端消去,有,與已知條件矛盾,假設(shè)不成立,命題得證。又由于有

即

將G分別取成G和-G，再取范數(shù)

又已知，有

第二十四頁，共五十四頁，2022年，8月28日定理4.2迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證:必要性設(shè)迭代公式收斂,當(dāng)k→∞時,則在迭代公式兩端同時取極限得記,則收斂于0(零向量),且有

于是由于可以是任意向量,故收斂于0當(dāng)且僅當(dāng)收斂于零矩陣，即當(dāng)時于是所以必有第二十五頁，共五十四頁，2022年，8月28日充分性:設(shè),則必存在正數(shù)ε,使則存在某種范數(shù)

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

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

第二十六頁，共五十四頁，2022年，8月28日定理4.3(迭代法收斂的充分條件)若迭代矩陣G的一種范數(shù),則迭代公式收斂,且有誤差估計式,且有誤差估計式及證:矩陣的譜半徑不超過矩陣的任一種范數(shù),已知,因此,根據(jù)定理4.2可知迭代公式收斂第二十七頁，共五十四頁，2022年，8月28日又因為,則det(I-G)≠0,I-G為非奇異矩陣,故x＝Gx＋d有惟一解,即與迭代過程相比較,有兩邊取范數(shù)

∴

第二十八頁，共五十四頁，2022年，8月28日由迭代格式，有

兩邊取范數(shù)，代入上式，得證畢由定理知，當(dāng)時，其值越小，迭代收斂越快，在程序設(shè)計中通常用相鄰兩次迭代（ε為給定的精度要求）作為控制迭代結(jié)束的條件第二十九頁，共五十四頁，2022年，8月28日例4.5已知線性方程組考察用Jacobi迭代和G-S迭代求解時的收斂性解:⑴雅可比迭代矩陣故Jacobi迭代收斂

第三十頁，共五十四頁，2022年，8月28日⑵

將系數(shù)矩陣分解

則高斯-塞德爾迭代矩陣

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

第三十一頁，共五十四頁，2022年，8月28日定理4.4設(shè)n階方陣為對角占優(yōu)陣,則非奇異證:因A為對角占優(yōu)陣,其主對角元素的絕對值大于同行其它元素絕對值之和,且主對角元素全不為0,故對角陣為非奇異。作矩陣第三十二頁，共五十四頁，2022年，8月28日利用對角占優(yōu)知由定理4.1知非奇異,從而A非奇異,證畢

系數(shù)矩陣為對角占優(yōu)陣的線性方程組稱作對角占優(yōu)方程組。

第三十三頁，共五十四頁，2022年，8月28日定理4.5對角占優(yōu)線性方程組的雅可比迭代公式和高斯-賽德爾迭代公式均收斂。證:雅可比迭代公式的迭代矩陣為

由定理4.4知,這時,再由定理4.3知迭代收斂再考察高斯-賽德爾迭代公式的迭代矩陣令，則有即寫出分量形式有第三十四頁，共五十四頁，2022年，8月28日設(shè)

而由上式得由此整理得利用對角占優(yōu)條件知上式右端小于1,(如果右端大于1,則得出與對角占優(yōu)條件矛盾的結(jié)果)故有據(jù)定理4.3知G-S收斂第三十五頁，共五十四頁，2022年，8月28日例4.6設(shè)求解線性方程組的雅可比迭代

求證當(dāng)<1時,相應(yīng)的高斯-塞德爾迭代收斂證:由于B是雅可比迭代的迭代矩陣,故有又<1,故有則∴系數(shù)矩陣為對角占優(yōu)陣,故G-S迭代收斂第三十六頁，共五十四頁，2022年，8月28日例4.7

設(shè),證明,求解方程組

的Jacobi迭代與G-S迭代同時收斂或發(fā)散證:雅可比迭代矩陣其譜半徑第三十七頁，共五十四頁，2022年，8月28日例4.7

設(shè),證明,求解方程組

的Jacobi迭代與G-S迭代同時收斂或發(fā)散證:G-S迭代矩陣其譜半徑顯然,和同時小于、等于或大于1,因而Jacobi迭代法與G-S迭代法具有相同的收斂性第三十八頁，共五十四頁，2022年，8月28日例4.8設(shè)求解線性方程組的雅可比迭代

x(k+1)=Bx(k)+fk=0,1,…

求證當(dāng)‖B‖<1時,相應(yīng)的G-S迭代收斂證這里以‖B‖

為例,‖B‖1類似由于B是雅可比迭代的迭代矩陣，故有

∴Ax=b的系數(shù)矩陣按行嚴(yán)格對角占優(yōu),故高斯-塞德爾迭代收斂第三十九頁，共五十四頁，2022年，8月28日例4.9考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性，其中解：先計算迭代矩陣第四十頁，共五十四頁，2022年，8月28日求特征值雅可比矩陣

(B)=0<1∴用雅可比迭代法求解時，迭代過程收斂第四十一頁，共五十四頁，2022年，8月28日1=0,2=2,3=2(G1)=2>1

∴用高斯-塞德爾迭代法求解時，迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值第四十二頁，共五十四頁，2022年，8月28日∴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,從而說明迭代格式收斂。證:因為B=I-A,故(B)=(I)-(A)=1-(A)

(A)+(B)=1由于已知(A)和(B)全為正數(shù)，故0<(B)<1,從而(B)<1所以該迭代格式收斂。第四十三頁，共五十四頁，2022年，8月28日當(dāng)時a<1時,Jacobi矩陣GJ∞<1,對初值x(0)均收斂例4.11設(shè)方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

第四十四頁，共五十四頁，2022年，8月28日例4.11設(shè)方程組寫出解方程組的Gauss-Seidel迭代矩陣，并討論迭代收斂的條件。解②Gauss-Seidel矩陣為

當(dāng)時a<1時,Gauss-Seidel矩陣Gs∞<1,所以對任意初值x(0)均收斂。也可用矩陣的譜半徑p(GS)<1來討論第四十五頁，共五十四頁，2022年，8月28日解：先計算迭代矩陣?yán)?.12討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性。第四十六頁，共五十四頁，2022年，8月28日求特征值雅可比矩陣

(B)=1∴用雅可比迭代法求解時，迭代過程不收斂1=-1，2,3=1/2第四十七頁，共五十四頁，2022年，8月28日求特征值高斯-塞德爾迭代矩陣(G1)=0.3536<1∴用高斯-塞德爾迭代法求解時，迭代過程收斂1=0,第四十八頁，共五十四頁，2022年，8月28日求解AX=b,當(dāng)取何值時迭代收斂？解:所給迭代公式的迭代矩陣為例4.13給定線性方程組AX=b

用迭代公式X(K+1)=X(K)+(b-AX(K))(k=0,1,…）第四十九頁，共五十四頁，2022年，8月28日即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迭代收斂第五十頁，共五十四頁，2022年，8月28日例4.14設(shè)求解線性方程組Ax=b的簡單迭代法

x(k+1)=Bx(k)+g(k=0,1,2,……)

收斂,求證:對0<<1,迭代法

x(k+1)=[(1-)I+B]x(k)+g(k=0,1,2,…)