數(shù)值分析第三章線性方程組的迭代法_第1頁
數(shù)值分析第三章線性方程組的迭代法_第2頁
數(shù)值分析第三章線性方程組的迭代法_第3頁
數(shù)值分析第三章線性方程組的迭代法_第4頁
數(shù)值分析第三章線性方程組的迭代法_第5頁
已閱讀5頁,還剩39頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

數(shù)值分析第三章線性方程組的迭代法第一頁,共四十四頁,2022年,8月28日§3.1迭代法的基本思想

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

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

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

第五頁,共四十四頁,2022年,8月28日§3.2雅可比(Jacobi)迭代法§3.2.1雅可比迭代法算法構(gòu)造例2用雅可比迭代法求解方程組解:從方程組的三個方程中分離出和建立迭代公式精確解x*=(3,2,1)T第六頁,共四十四頁,2022年,8月28日取初始向量進行迭代,可以逐步得出一個近似解的序列:(k=1,2,…)直到求得的近似解能達到預(yù)先要求的精度,則迭代過程終止,以最后得到的近似解作為線性方程組的解。當?shù)降?0次有計算結(jié)果表明,此迭代過程收斂于方程組的精確解x*=(3,2,1)T。第七頁,共四十四頁,2022年,8月28日考察一般的方程組,將n元線性方程組寫成若,分離出變量據(jù)此建立迭代公式上式稱為解方程組的Jacobi迭代公式。第八頁,共四十四頁,2022年,8月28日§3.2.2雅可比迭代法的矩陣表示設(shè)方程組的系數(shù)矩陣A非奇異,且主對角元素,則可將A分裂成

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

,則這樣便得到一個迭代公式令則有(k=0,1,2…)稱為雅可比迭代公式,B稱為雅可比迭代矩陣第十頁,共四十四頁,2022年,8月28日雅可比迭代矩陣表示法,主要是用來討論其收斂性,實際計算中,要用雅可比迭代法公式的分量形式。即(k=0,1,2,…)第十一頁,共四十四頁,2022年,8月28日3.2.1雅可比迭代法的算法實現(xiàn)第十二頁,共四十四頁,2022年,8月28日§3.3高斯-塞德爾(Gauss-Seidel)迭代法§

3.3.1高斯-塞德爾迭代法的基本思想

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

(i=1,2,…,nk=0,1,2,…)第十三頁,共四十四頁,2022年,8月28日例3用GaussSeidel迭代格式解方程組

精確要求為ε=0.005

解GaussSeidel迭代格式為取初始迭代向量,迭代結(jié)果為:x*≈第十四頁,共四十四頁,2022年,8月28日§

3.3.2Gauss—Seidel迭代法的矩陣表示將A分裂成A=D+L+U,則

等價于(D+L+U)x=b于是,則高斯—塞德爾迭代過程因為,所以

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

令第十五頁,共四十四頁,2022年,8月28日§

3.3.3高斯—塞德爾迭代算法實現(xiàn)

高斯-塞德爾迭代算法的計算步驟與流程圖與雅可比迭代法大致相同,只是一旦求出變元的某個新值后,就改用新值替代老值

,再進行這一步剩下的計算。

第十六頁,共四十四頁,2022年,8月28日§3.4超松弛迭代法(SOR方法)

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

第十七頁,共四十四頁,2022年,8月28日§

3.4.1超松弛迭代法的基本思想

超松弛迭代法目的是為了提高迭代法的收斂速度,在高斯—塞德爾迭代公式的基礎(chǔ)上作一些修改。這種方法是將前一步的結(jié)果

與高斯-塞德爾迭代方法的迭代值適當加權(quán)平均,期望獲得更好的近似值。是解大型稀疏矩陣方程組的有效方法之一,有著廣泛的應(yīng)用。其具體計算公式如下:⑴用高斯—塞德爾迭代法定義輔助量。第十八頁,共四十四頁,2022年,8月28日⑵把取為與的加權(quán)平均,即

合并表示為:式中系數(shù)ω稱為松弛因子,當ω=1時,便為高斯-塞德爾迭代法。為了保證迭代過程收斂,要求0<ω<2。當0<ω<1時,低松弛法;當1<ω<2時稱為超松弛法。但通常統(tǒng)稱為超松弛法(SOR)。第十九頁,共四十四頁,2022年,8月28日§

3.4.2超松弛迭代法的矩陣表示設(shè)線性方程組Ax=b的系數(shù)矩陣A非奇異,且主對角元素,則將A分裂成A=d+L+U,則超松弛迭代公式用矩陣表示為或故

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

取ω=1.46,要求解:SOR迭代公式

k=0,1,2,…,

初值該方程組的精確解只需迭代20次便可達到精度要求如果取ω=1(即高斯—塞德爾迭代法)和同一初值,要達到同樣精度,需要迭代110次第二十二頁,共四十四頁,2022年,8月28日

§

3.5迭代法的收斂性我們知道,對于給定的方程組可以構(gòu)造成簡單迭代公式、雅可比迭代公式、高斯-塞德爾迭代公式和超松弛迭代公式,但并非一定收斂?,F(xiàn)在分析它們的收斂性。對于方程組經(jīng)過等價變換構(gòu)造出的等價方程組

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

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

于是

由于可以是任意向量,故收斂于0當且僅當收斂于零矩陣,即當時

于是

所以必有

第二十四頁,共四十四頁,2022年,8月28日充分性:設(shè),則必存在正數(shù)ε,使則存在某種范數(shù)

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

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

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

第二十七頁,共四十四頁,2022年,8月28日由迭代格式,有

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

第二十九頁,共四十四頁,2022年,8月28日⑵

將系數(shù)矩陣分解

則高斯-塞德爾迭代矩陣

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

第三十頁,共四十四頁,2022年,8月28日定義3.2設(shè)矩陣每一行對角元素的絕對值都大于同行其他元素絕對值之和

則稱A為弱對角占優(yōu)矩陣。若上式中不等號均嚴格成立,則稱A為嚴格對角占優(yōu)矩陣。

定理8設(shè)n階方陣

為嚴格對角占優(yōu)陣,則A非奇異。第三十一頁,共四十四頁,2022年,8月28日定理9

若矩陣A按行(或列)嚴格對角占優(yōu),或按行(或列)弱對角占優(yōu)不可約;則Jacobi迭代、Gauss-Seidel迭代都收斂。第三十二頁,共四十四頁,2022年,8月28日例6考察用雅可比迭代法和高斯-塞德爾迭代法解線性方程組Ax=b的收斂性,其中解:先計算迭代矩陣第三十三頁,共四十四頁,2022年,8月28日求特征值雅可比矩陣

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

∴用高斯-塞德爾迭代法求解時,迭代過程發(fā)散高斯-塞德爾迭代矩陣求特征值第三十五頁,共四十四頁,2022年,8月28日當時a<1時,Jacobi矩陣GJ∞<1,對初值x(0)均收斂例7設(shè)方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并討論迭代收斂的條件。寫出解方程組的Gauss-Seidel迭代矩陣,并討論迭代收斂的條件。解①Jacobi迭代公式和Jacobi矩陣分別為

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

當時a<1時,Gauss-Seidel矩陣Gs∞<1,所以對任意初值x(0)均收斂。也可用矩陣的譜半徑p(GS)<1來討論第三十七頁,共四十四頁,2022年,8月28日解:先計算迭代矩陣例8討論用雅可比迭代法和高斯-塞德爾迭代法解線性方程組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,當取何值時迭代收斂?解:所給迭代公式的迭代矩陣為例9給定線性方程組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-

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論