數(shù)值分析解線性方程組的迭代法市公開課獲獎?wù)n件

1、第三章 解線性方程組迭代法 Jacobi迭代法 Gauss-Seidel迭代法 迭代法收斂條件(充要條件, 充足條件)求 迭代法概述1第1頁第1頁 迭代法概述等價線性方程組取初始向量 x(0)Rn, 結(jié)構(gòu)下列單步定常線性迭代公式以此來產(chǎn)生近似向量序列 x(1), x(2), .當(dāng)k充足大時， 基本思想等價變形如何做收斂性條件M: 迭代矩陣2第2頁第2頁定義 對于Rn中向量序列 x(k), 假如則稱向量序列x(k)收斂于 Rn中向量 x.定義對于n階方陣序列 A(k), 假如則稱方陣序列A(k)收斂于n階方陣A. 上面兩式通常表示成 向量序列與矩陣序列收斂概念3第3頁第3頁定理 Rn中向量序列x

2、(k)收斂于Rn中向量x充足必要條件是其中xj(k)和 xj分別表示 x(k)和 x中第 j個分量.定理 n階方陣序列A(k)收斂于n階方陣A充足必要條件是 向量序列與矩陣序列收斂充足必要條件 向量序列和矩陣序列收斂可歸結(jié)為相應(yīng)分量或相應(yīng)元素序列收斂性.4第4頁第4頁 若由迭代公式產(chǎn)生向量序列 x(k) 收斂于向量 x，則即向量 x 是 方程 Ax=b 解. 單步定常線性迭代法產(chǎn)生向量序列若收斂則必收斂到原線性方程組解.5第5頁第5頁 n=4Jacobi迭代法把方程組改寫成下列等價形式6第6頁第6頁 n=4Jacobi迭代法計算公式已知 用上述迭代公式可算得 7第7頁第7頁 n=4Jacobi

3、迭代法矩陣表示8第8頁第8頁 Jacobi迭代法(k)(k)(k)(k)(k+1) 9第9頁第9頁 設(shè)D為由A對角線元素構(gòu)成對角矩陣Jacobi迭代公式 Jacobi迭代法矩陣表示 迭代矩陣10第10頁第10頁例 用Jacobi迭代法求解線性方程組解 將方程組改寫成下列等價形式11第11頁第11頁Jacobi迭代法計算公式為假設(shè)初始向量取 x(0)=(0, 0, 0)T.第一次迭代第二次迭代12第12頁第12頁 實際計算時，迭代法中斷條件其中 為給定要求精度.13第13頁第13頁 n=4Gauss-Seidel迭代法把方程組改寫成下列等價形式14第14頁第14頁 n=4Gauss-Seidel

4、迭代法15第15頁第15頁 Gauss-Seidel迭代法(k)(k)(k+1)(k+1)(k+1) 16第16頁第16頁在迭代每一步設(shè)定計算順序并且，在計算迭代值 充足利用它前面新信息這樣設(shè)計出來迭代公式稱為高斯塞德爾迭代公式. Gauss-Seidel迭代法17第17頁第17頁 Gauss-Seidel迭代法矩陣表示 設(shè)將系數(shù)矩陣A 分裂為其中D為對角陣, L 和U分別為嚴(yán)格下三角和嚴(yán)格上三角陣. 迭代矩陣GaussSeidel迭代公式18第18頁第18頁例 用Gauss-Seidel迭代法求解線性方程組解 將方程組改寫成下列等價形式19第19頁第19頁Gauss-Seidel迭代法計算公

5、式為假設(shè)初始向量取 x(0)=(0, 0, 0)T.第一次迭代20第20頁第20頁第二次迭代Gauss-Seidel迭代法計算公式為假設(shè)初始向量取 x(0)=(0, 0, 0)T.21第21頁第21頁 Jacobi迭代法：x(k+1)分量計算能夠同時進(jìn)行，無先后順序 Gauss-Seidel迭代法：x(k+1)分量計算有先后順序，必須先計算x(k+1)前面分量然后再計算下一分量.22第22頁第22頁 Jacobi迭代法與Gauss-Seidel迭代法計算效果哪一個更加好？ 前例計算結(jié)果表明, 用Gauss-Seidel迭代法比用Jacobi迭代法效果好. 但對普通情形, 有些問題Gauss-S

6、eidel迭代法確實比Jacobi迭代法收斂得快, 但也有Gauss-Seidel迭代法比Jacobi迭代法收斂得慢, 甚至尚有Jacobi迭代法收斂, 但Gauss-Seidel迭代法發(fā)散情形.23第23頁第23頁 迭代法收斂條件定義(譜半徑) 設(shè)n階方陣A特性值為i (i=1,2,n)，則稱為矩陣A譜半徑. Ak 特性值為故24第24頁第24頁 矩陣范數(shù)和譜半徑有下列關(guān)系設(shè)A任一特性值為i , 相應(yīng)特性向量為ui , 則由任意性可知結(jié)論成立. 矩陣A譜半徑不超出它任何一個由向量范數(shù)誘導(dǎo)出范數(shù)，即|A|是A特性值上界.證故從而25第25頁第25頁 設(shè)A為n階方陣，則 由于2-范數(shù)含有上面關(guān)系

7、式，因此稱 |A|2 為譜范數(shù).26第26頁第26頁定理 設(shè)A是任意n階方陣，由A各次冪所構(gòu)成矩陣序列收斂于零矩陣，即充足必要條件是27第27頁第27頁定理 對任何初始向量 x(0)和右端項g，由迭代公式 x(k+1) =Mx(k)+g (k=0, 1, 2, )產(chǎn)生向量序列x(k)收斂充足必要條件是(M)1其中(M)是迭代矩陣M譜半徑. 迭代法收斂充足必要條件 迭代法收斂性只與迭代矩陣譜半徑相關(guān), 而迭代矩陣是由A演變來, 因此迭代法是否收斂只與系數(shù)矩陣A以及演變方式相關(guān), 與常數(shù)項和初始向量選擇無關(guān).28第28頁第28頁證實 必要性. 設(shè)序列x(k)收斂于 x*，則有 迭代法收斂充足必要條

8、件任意收斂故由于x(0)為任意n維向量,即29第29頁第29頁 迭代法收斂充足必要條件任意收斂充足性. 若(M)1, 則 =1不是M特性值, 故方程 (IM)x=g有唯一解, 記為x*, 即又且故對任意初始向量x(0), 都有證實30第30頁第30頁推論1 若迭代矩陣M滿足|M|1, 則下列迭代公式對任意初始向量x(0)收斂 31第31頁第31頁例 解方程組討論Jacobi迭代法與Gauss-Seidel迭代法收斂性.解迭代法是否收斂等價于迭代矩陣譜半徑是否小于1，故先求迭代矩陣32第32頁第32頁 Jacobi迭代法迭代矩陣為其特性方程為特性值譜半徑故Jacobi迭代法收斂.33第33頁第3

9、3頁 Gauss-Seidel迭代法迭代矩陣為34第34頁第34頁其特性方程為特性值譜半徑故Gauss-Seidel迭代法發(fā)散.35第35頁第35頁 普通來說, 計算矩陣譜半徑比較困難, 故用迭代法收斂充足必要條件來判斷迭代法是否收斂往往不太容易, 下列簡介用其它辦法判別迭代法收斂充足條件.36第36頁第36頁定義(嚴(yán)格對角占優(yōu)陣) 稱n 階方陣 是嚴(yán)格對角占優(yōu)，假如其主對角線元素絕對值不小于同行其它元素絕對值之和：若線性方程組系數(shù)矩陣為嚴(yán)格對角占優(yōu)陣，則稱這個線性方程組為嚴(yán)格對角占優(yōu)方程組.37第37頁第37頁 迭代法收斂充足條件定理 若A為嚴(yán)格對角占優(yōu)陣, 則求解Ax=b Jacobi迭代

10、法和Gauss-Seidel迭代法均收斂.定理 若A為對稱正定陣, 則求解Ax=bGauss-Seidel迭代法收斂.38第38頁第38頁例 方程組Ax=b系數(shù)矩陣為嚴(yán)格對角占優(yōu)陣.故Jacobi迭代法與Gauss-Sidel迭代法均收斂.39第39頁第39頁例 方程組Ax=b系數(shù)矩陣為非對角占優(yōu)陣互換兩個方程順序，得原方程組同解方程組 它是一個嚴(yán)格對角占優(yōu)方程組，對此方程組Jacobi迭代法和Gauss-Seidel迭代法均收斂. 當(dāng)所給方程組不滿足迭代法收斂條件時, 適當(dāng)調(diào)整方程組中方程順序, 有時可得到滿足迭代法收斂條件同解方程組.40第40頁第40頁例 方程組Ax=b系數(shù)矩陣為但A為對稱正定矩陣，Gauss-Seidel迭代法收斂.非嚴(yán)格對角占優(yōu)41第41頁第41頁例 設(shè)有方程組Ax=b, 其中討論用兩種迭代法求解收斂性.解 A是對稱正定陣故Gauss-Seidel迭代法收斂. A不是嚴(yán)格對角占優(yōu)陣42第42頁第42頁Jacobi迭代法迭代矩陣為其特性方程為特性值為故迭代矩陣譜半徑為 由迭代法收斂充足必要條件知Jacobi迭代法發(fā)散.43第43頁第43頁 誤差預(yù)計定理 設(shè)由迭代格式 x(k+1)=M x(k)+g, 若|M|1,則 x(k)收斂于 x*, 且有誤差預(yù)