![數(shù)值分析ppt第6章-解線性方程組的迭代法_第1頁](http://file4.renrendoc.com/view/aa192d73bd744a3f12bb6074d006d557/aa192d73bd744a3f12bb6074d006d5571.gif)
![數(shù)值分析ppt第6章-解線性方程組的迭代法_第2頁](http://file4.renrendoc.com/view/aa192d73bd744a3f12bb6074d006d557/aa192d73bd744a3f12bb6074d006d5572.gif)
![數(shù)值分析ppt第6章-解線性方程組的迭代法_第3頁](http://file4.renrendoc.com/view/aa192d73bd744a3f12bb6074d006d557/aa192d73bd744a3f12bb6074d006d5573.gif)
![數(shù)值分析ppt第6章-解線性方程組的迭代法_第4頁](http://file4.renrendoc.com/view/aa192d73bd744a3f12bb6074d006d557/aa192d73bd744a3f12bb6074d006d5574.gif)
![數(shù)值分析ppt第6章-解線性方程組的迭代法_第5頁](http://file4.renrendoc.com/view/aa192d73bd744a3f12bb6074d006d557/aa192d73bd744a3f12bb6074d006d5575.gif)
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
第6章解線性方程組的迭代方法6.1引言6.2基本迭代法6.3迭代法的收斂性6.4*
分塊迭代法其中A為非奇異矩陣
選主元消去法:A為低階稠密矩陣迭代法:大型稀疏矩陣方程組(A的階數(shù)n很大,但零元素較多),迭代法:雅可比迭代法
高斯-賽德爾迭代法
超松弛迭代法
對線性方程組Ax=b,(1.1)6.1引言
例1
求解方程組記為Ax=b,其中方程組的精確解是x*=(3,2,1)T.現(xiàn)將改寫為或?qū)憺閤=B0x+f,其中
我們?nèi)稳〕跏贾?,例如取x(0)=(0,0,0)T.將這些值代入(1.3)式右邊(若(1.3)式為等式即求得方程組的解,但一般不滿足),得到新的值x(1)=(x1(1),x2(1),x3(1))T
=(3.5,3,3)T
,再將x(1)分量代入(1.3)式右邊得到x(2),反復(fù)利用這個計算程序,得到一向量序列和一般的計算公式(迭代公式)簡寫為x(k+1)=B0x(k)
+f,其中k表示迭代次數(shù)(k=0,1,2,).
迭代到第10次有從此例看出,由迭代法產(chǎn)生的向量序列x(k)逐步逼近方程組的精確解是x*=(3,2,1)T.即有對于任何一個方程組x=Bx+f(由Ax=b變形得到的等價方程組),由迭代法產(chǎn)生的向量序列x(k)是否一定逐步逼近方程組的解x*呢?回答是不一定.請同學(xué)們考慮用迭代法解下述方程組但x(k)并不是所有的都收斂到解x*!對于給定方程組x=Bx+f,設(shè)有唯一解x*,則
x*=Bx*+f.
(1.5)又設(shè)x(0)為任取的初始向量,按下述公式構(gòu)造向量序列
x(k+1)=Bx(k)+f,k=0,1,2,.
(1.6)其中k表示迭代次數(shù).
定義1(1)對于給定的方程組x=Bx+f,用公式(1.6)逐步代入求近似解的方法稱為迭代法(或稱為一階定常迭代法,這里B與k無關(guān)).B稱為迭代矩陣.(2)如果limx(k)(k→∞)存在(記為x*),稱此迭代法收斂,顯然x*就是方程組的解,否則稱此迭代法發(fā)散.
由上述討論,需要研究{x(k)}的收斂性.引進誤差向量
由(1.6)減去(1.5)式,得ε(k+1)=Bε(k)(k=0,1,2,),遞推得
要考察{x(k)}的收斂性,就要研究B在什么條件下有l(wèi)imε(k)=0(k→∞),亦即要研究B滿足什么條件時有Bk→0(零向量)(k→∞).6.2基本迭代法其中,A=(aij)∈Rn×n為非奇異矩陣,下面研究任何建立Ax=b的各種迭代法.
設(shè)線性方程組Ax=b,(2.1)其中,M為可選擇的非奇異矩陣,且使Mx=d容易求解,一般選擇A的某種近似,稱M為分裂矩陣.
將A分裂為A=M-N.(2.2)
于是,求解Ax=b轉(zhuǎn)化為求解Mx=Nx+b
,即求解可構(gòu)造一階定常迭代法其中B=M-1N=M-1(M-A)=I-M-1A,f=M-1b.稱B=I-M-1A為迭代法的迭代矩陣,選取M矩陣,就得到解Ax=b的各種迭代法.
設(shè)aii0(i=1,2,,n),并將A寫成三部分即A=D-L-U6.2.1雅可比(Jacobi)迭代法
設(shè)aii0(i=1,2,,n),選取M為A的對角元素部分,即選取M=D(對角陣),A=D-N,由(2.3)式得到解方程組Ax=b的雅可比(Jacobi)迭代法.又稱簡單迭代法.其中B=I-D-1A=D-1(L+U)=J,f=D-1b.稱J為解Ax=b的雅可比迭代法的迭代矩陣.于是雅可比迭代法可寫為矩陣形式其Jacobi迭代矩陣為下面給出雅可比迭代法(2.5)的分量計算公式,記由雅可比迭代法(2.5)有每一個分量寫出來為即當(dāng)aii0時,有等價方程組其中
aii(i)0(i=1,2,,n)即由方程組Ax=b得到的建立的雅可比迭代格式為于是,解Ax=b的雅可比迭代法的計算公式為
由(2.6)式可知,雅可比迭代法計算公式簡單,每迭代一次只需計算一次矩陣和向量的乘法且計算過程中原始矩陣A始終不變.6.2.2高斯-賽德爾迭代法在Jacobi
迭代中,計算xi(k+1)(2in)時,使用xj(k+1)代替xj(k)(1ji-1),即有建立迭代格式或縮寫為稱為高斯—塞德爾(Gauss—Seidel)迭代法.其Gauss—Seidel迭代矩陣為BG=(D-L)-1U于是高斯—塞德爾迭代法可寫為矩陣形式
這就是說,選取分裂矩陣M為A的下三角部分,即選取M=D-L(下三角陣),A=M-N,由(2.3)式得到解Ax=b的高斯—塞德爾(Gauss—Seidel)迭代法.其中B=I-(D-L)-1A=(D-L)-1U=G,f=(D-L)-1b.稱矩陣G=(D-L)-1U為解Ax=b的高斯—塞德爾迭代法的迭代矩陣.由高斯—塞德爾迭代法(2.7)有每一個分量寫出來為即當(dāng)aii0時,有(與前面一樣的式子)或于是,解Ax=b的高斯—塞德爾迭代法的計算公式為或
雅可比迭代法不使用變量的最新信息計算xi(k+1),而由高斯—塞德爾迭代公式(2.8)可知,計算x(k+1)的第i個分量xi(k+1)時,利用了已經(jīng)計算出的最新分量xj(k+1)(j=1,2,,i-1).
可看作雅可比迭代法的一種改進.由(2.8)可知,高斯—塞德爾迭代公式每迭代一次只需計算一次矩陣與向量的乘法.
算法1(高斯—塞德爾迭代法)見書p139.
例2
用高斯—塞德爾迭代法解例1的方程組(1.2).
解用高斯—塞德爾迭代公式:取x(0)=(0,0,0)T.迭代到第7次有
由此例可知,用高斯—塞德爾迭代法,雅可比迭代法解線性方程組(1.2)(且取x(0)=0)均收斂,而高斯—塞德爾迭代法比雅可比迭代法收斂較快(即取相同的x(0),達到同樣精度所需迭代次數(shù)較少),但這結(jié)論只當(dāng)A滿足一定條件時才是對的.
例1
用雅可比迭代法解方程組
解:Jacobi
迭代格式為kx1(k)x2(k)x3(k)10.720.830.8420.9711.071.15…………111.0999931.1999931.299991121.0999981.1999981.299997取x(0)=(0,0,0)T
計算結(jié)果如下:
解:Gauss-Seidel
迭代格式為
例2
用Gauss—Seidel迭代法解上題.取x(0)=(0,0,0)T
計算結(jié)果如下:kx1(k)
x2(k)x3(k)10.720.9021.1644…………81.0999981.1999991.36.2.3解大型稀疏線性方程組的逐次超松弛法(SOR方法)
我們?nèi)?gt;0為松弛因子,建立迭代格式如下即或改寫為
其逐次超松弛迭代矩陣為
逐次超松弛法可寫為矩陣形式稱為逐次超松弛迭代法,簡稱SOR方法.
顯然,=1就是Gauss—Seidel迭代法.
下面用矩陣方法推導(dǎo),選取分裂矩陣M為帶參數(shù)的下三角矩陣從而得到解Ax=b的逐次超松弛迭代法(SuccessiveOverRelaxationMethod,簡稱SOR方法).其中>0為可選擇的松弛因子.
于是,由(2.3)可構(gòu)造一個迭代法,其迭代矩陣為
解Ax=b的SOR方法為.其中
下面給出解Ax=b的SOR方法的分量計算公式.記由(2.10)式可得由此,得到解Ax=b的SOR方法的計算公式或(1)顯然,當(dāng)=1時即為Gauss—Seidel迭代法.(2)SOR方法每迭代一次主要運算量是計算一次矩陣與向量的乘法.(3)當(dāng)>1時,稱為超松弛法;當(dāng)<1時,稱為低松弛法.(4)在計算機實現(xiàn)時可用控制迭代終止,或用控制迭代終止.
SOR迭代法是Gauss—Seidel迭代法的一種修正,可由下述思想得到.
設(shè)已知x(k)及已計算x(k+1)的分量xj(k+1)(j=1,2,,i-1).(1)首先用Gauss—Seidel迭代法定義輔助量,(2)再由與加權(quán)平均定義,即將(2.13)代入(2.14)得到解Ax=b的SOR迭代(2.11)式.例3
用SOR迭代法解方程組.見書p195.6.3迭代法的收斂性6.3.1一階定常迭代法的基本定理其中,A=(aij)∈Rn×n為非奇異矩陣,記x*為(3.1)精確解,且設(shè)有等價的方程組
設(shè)線性方程組Ax=b,(3.1)于是設(shè)有解Ax=b的一階定常迭代法有意義的問題是:迭代矩陣B滿足什么條件時,由迭代法產(chǎn)生的向量序列{x(k)}收斂到x*.
引進誤差向量由(3.3)式減(3.2)得到誤差向量的遞推公式由6.1節(jié)可知,研究迭代法(3.3)收斂性問題就是要研究迭代矩陣B滿足什么條件時,有.
定義2
設(shè)有矩陣序列Ak=(aij(k))∈Rn×n
及A=(aij)∈Rn×n,如果n2個數(shù)列極限存在且有則{Ak}稱收斂于A,記為lim(k→∞).
例4
設(shè)有矩陣序列{Ak},其中Ak=Bk,而且設(shè)|λ|<1,考查矩陣序列極限.
解顯然,當(dāng)|λ|<1時,則有矩陣序列極限概念可以用矩陣算子范數(shù)來描述.
定理1
其中||·||為矩陣的任意一種算子范數(shù).
定理2
定理3
設(shè)B=(bij)∈Rn×n,則limBk=0(k→∞)(零矩陣)的充分必要條件是矩陣B的譜半徑(B)<1.
定理4(迭代法基本定理)
設(shè)有方程組x=Bx+f.(6.4)及一階定常迭代法x(k+1)=Bx(k)+f.(6.5)對任意選擇初始向量x(0),迭代法(3.5)收斂的充要條件是矩陣B的譜半徑(B)<1.定理4是一階定常迭代法的基本理論.
定理3和定理4的結(jié)論和起來即為(1)迭代法x(k+1)=Bx(k)+f
收斂limBk=O;(2)迭代法x(k+1)=Bx(k)+f
收斂(B)<1.
推論設(shè)Ax=b,其中A=D-L-U為非奇異矩陣且D非奇異矩陣,則有(1)Jacobi迭代法收斂(J)<1,其中J=D-1(L+U).(2)G-S迭代法收斂(G)<1,其中G=(D-L)-1U.(3)SOR迭代法收斂(Lω)<1,其中Lω=(D-ωL)-1[(1-ω)D+ωU].
例5
考察用Jacobi方法解方程組(1.2)的收斂性.
解因為方程組(1.2)的矩陣A及迭代矩陣J為解得即(J)<1.所以用Jacobi方法解方程組(1.2)是收斂的.得迭代矩陣J的特征方程為
例6
考察用迭代法解方程組的收斂性.其中
解方程組的迭代矩陣B的特征方程為矩陣B的特征值為即(B)>1.這說明用迭代法解此方程組不收斂.
迭代法的基本定理在理論上是重要的,根據(jù)譜半徑的性質(zhì)(B)≤||B||,下面利用矩陣B的范數(shù)建立判別迭代法收斂的充分條件.思考:A為n階實對稱矩陣時,應(yīng)如何處理.
定理5(迭代法收斂的充分條件)
設(shè)有方程組x=Bx+f,B=(bij)∈Rn×n,及一階定常迭代法x(k+1)=Bx(k)+f.如果有B的某種算子范數(shù)||B||=q<1
,則(1)迭代法收斂,即對任取x(0)有6.3.2關(guān)于解某些特殊方程組迭代法的收斂性
在科學(xué)及工程計算中,要求解方程組Ax=b,其矩陣A常常具有某些特性.例如,A具有對角占優(yōu)性質(zhì)或A為不可約陣,或A是對稱正定陣,下面討論用基本迭代法解這些方程組的收斂性.
定義3(對角占優(yōu)陣)
設(shè)A=(aij)n×n
.(1)
如果A的元素滿足稱A為嚴格(按行)對角占優(yōu)陣.(2)
如果A的元素滿足且上式至少有一個不等式成立,稱A為弱(按行)對角占優(yōu)陣.
定義4(可約與不可約矩陣)
設(shè)A=(aij)n×n
(n≥2),如果存在置換陣P使其中A11為r階方陣,A22為n-r階方陣(1≤r≤n),則稱A為可約矩陣.否則,如果不存在這樣置換陣P使(3.6)式成立,則稱A為不可約矩陣.
A為可約矩陣意即A可經(jīng)過若干行列重排化為(3.6)或Ax=b可化為兩個低階方程組求解(如果A經(jīng)過兩行交換的同時進行相應(yīng)兩列的交換,稱對A進行一次行列重排).
事實上,由Ax=b可化為PTAP(PTx)=PTb.于是,求解Ax=b化為求解且記,其中yi,di為r維向量.由上式第2個方程組求出y2,再代入第1個方程組求出y1.
顯然,如果A所有元素都非零,則A為不可約陣.
例7
設(shè)有矩陣則A,B都是不可約矩陣.
定理6(對角占優(yōu)定理)
如果A=(aij)n×n為嚴格對角占優(yōu)矩陣或A為不可約弱對角占優(yōu)矩陣,則A為非奇異矩陣.嚴格對角占優(yōu)矩陣:如果A的每個對角元的絕對值
都比所在行的非對角元的絕對值的和要大不可約:不能化成兩個方陣其他位置為0的矩陣
定理7設(shè)方程組Ax=b,如果
(1)A為嚴格對角占優(yōu)陣,則解Ax=b的Jacobi迭代法,Gauss-Seidel
迭代法均收斂.
(2)A為弱對角占優(yōu)陣,且A為不可約矩陣,則解Ax=b的Jacobi迭代法,Gauss-Seidel
迭代法均收斂.定理若A為正定矩陣,則方程組Ax=b的Gauss-Seidel迭代法收斂.定理8(SOR方法收斂的必要條件)
設(shè)解方程組Ax=b的SOR迭代法收斂,則0<<2.定理9(SOR方法收斂的充分條件)
設(shè)有方程組Ax=b,如果:
(1)A為對稱正定矩陣,A=D-L-LT;
(2)0<<2.則解方程組Ax=b的SOR迭代法收斂.
由定理3證明中可知,如果(B)<1且(B)越小時,迭代法收斂越快.現(xiàn)設(shè)有方程組下面討論迭代法的收斂速度.x=Bx+f,B=(bij)∈Rn×n,及一階定常迭代法x(k+1)=Bx(k)+f
(k=0,1,),
由基本定理有0<(B)<1,且誤差向量ε(k)=x(k)-x*滿足且設(shè)迭代法收斂,即
溫馨提示
- 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)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 人教版小學(xué)語文二年下冊全冊教案(帶表格)
- 第23章 旋轉(zhuǎn) 人教版九年級數(shù)學(xué)寒假巧練習(xí)(含答案)
- 2024-2025年秋季第一學(xué)期小學(xué)三年級語文教學(xué)計劃及教學(xué)進度表
- 保育員培訓(xùn)衛(wèi)生清潔與消毒
- 微創(chuàng)顱內(nèi)血腫清除術(shù)治療高血壓腦出血的護理課件
- 正確認識中華傳統(tǒng)文化+學(xué)案 高中政治統(tǒng)編版必修四哲學(xué)與文化+
- 第1-3課+單詞句子默寫同步測試 初中日語人教版七年級第一冊
- 應(yīng)用文寫作+宣傳稿+你參加了學(xué)校舉辦的剪紙比賽活動+講義 高三上學(xué)期新高考聯(lián)合質(zhì)量測評9月聯(lián)考英語試題
- 多邊投資擔(dān)保協(xié)議(標(biāo)準版)
- 假期教師培訓(xùn)的心得體會
- 新人教版高一英語必修一-課本聽力與視頻材料原文
- 光伏發(fā)電項目編制依據(jù)及編制原則
- 第一課-筆墨千秋
- 實驗小學(xué)新蘇教版四年級科學(xué)上冊10.《摩擦力》第1課時教案
- 高壓電纜直埋技術(shù)要求
- 最新人教版三年級上冊數(shù)學(xué)《4.2.2 三位數(shù)減兩位數(shù)(連續(xù)退位)》PPT課件
- 智慧農(nóng)業(yè)田地綠色鄉(xiāng)村PPT模板
- 外科體液代謝失衡病人的護理
- 青島版(六年制)二年級上冊數(shù)學(xué)《 3.1 角的初步認識》課件
- 軸承鋼絲的現(xiàn)狀與發(fā)展
- 市場營銷-茶顏悅色的市場營銷策略研究論文
評論
0/150
提交評論