《11.線性方程組的迭代法-雅可比、高斯塞德爾和超松弛迭代.ppt》由會員分享，可在線閱讀，更多相關《11.線性方程組的迭代法-雅可比、高斯塞德爾和超松弛迭代.ppt（55頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 我們知道 凡是迭代法都有一個收斂問題 有時某種方法對一類方程組迭代收斂 而對另一類方程組進行迭代時就會發(fā)散 一個收斂的迭代法不僅具有程序設計簡單 適于自動計算 而且較直接法更少的計算量就可獲得滿意的解 因此 迭代法亦是求解線性方程組 尤其是求解具有大型稀疏矩陣的線性方程組的重要方法之一 第六章解線性方程組的迭代法 6 1迭代法的基本思想迭代法的基本思想是將線性方程組轉化為便于迭代的等價方程組 對任選一組初始值 按某種計算規(guī)則 不斷地對所得到的值進行修正 最終獲得滿足精度要求的方程組的近似解 設非奇異 則線性方程組有惟一解 經(jīng)過變換構造出一個等價同解方程組將上式改寫成迭代式 選定初始向量 反復

2、不斷地使用迭代式逐步逼近方程組的精確解 直到滿足精度要求為止 這種方法稱為迭代法 如果存在極限則稱迭代法是收斂的 否則就是發(fā)散的 收斂時 在迭代公式中當時 則 故是方程組的解 對于給定的方程組可以構造各種迭代公式 并非全部收斂 例1用迭代法求解線性方程組 解構造方程組的等價方程組 據(jù)此建立迭代公式 取計算得 迭代解離精確解越來越遠迭代不收斂 6 2雅可比與高斯 塞德爾迭代法 6 2 1雅可比迭代法算法 例2用雅可比迭代法求解方程組 解 從方程組的三個方程中分離出和 建立迭代公式 取初始向量進行迭代 可以逐步得出一個近似解的序列 k 1 2 直到求得的近似解能達到預先要求的精度 則迭代過程終止

3、以最后得到的近似解作為線性方程組的解 當?shù)降?0次有計算結果表明 此迭代過程收斂于方程組的精確解x 3 2 1 T 考察一般的方程組 將n元線性方程組 寫成 若 分離出變量 據(jù)此建立迭代公式 上式稱為解方程組的Jacobi迭代公式 6 2 2雅可比迭代法的矩陣表示設方程組的系數(shù)矩陣A非奇異 且主對角元素 則可將A分裂成 記作A D L U 則等價于 即 因為 則 這樣便得到一個迭代公式 令 則有 k 0 1 2 稱為雅可比迭代公式 B稱為雅可比迭代矩陣 雅可比迭代矩陣表示法 主要是用來討論其收斂性 實際計算中 要用雅可比迭代法公式的分量形式 即 k 0 1 2 6 2 1雅可比迭代法的算法

4、實現(xiàn) 6 2 2高斯 塞德爾 Gauss Seidel 迭代法高斯 塞德爾迭代法的基本思想在Jacobi迭代法中 每次迭代只用到前一次的迭代值 若每次迭代充分利用當前最新的迭代值 即在求時用新分量代替舊分量 就得到高斯 賽德爾迭代法 其迭代法格式為 i 1 2 nk 0 1 2 例3用Gauss Seidel迭代格式解方程組 精確要求為 0 005 解Gauss Seidel迭代格式為 取初始迭代向量 迭代結果為 x Gauss Seidel迭代法的矩陣表示將A分裂成A D L U 則等價于 D L U x b于是 則高斯 塞德爾迭代過程 因為 所以 則高斯 塞德爾迭代形式為 故 令 定義 設

5、如果A的元素滿足稱A為嚴格對角占優(yōu)陣 2 如果A的元素滿足且至少一個不等式嚴格成立 稱A為弱對角占優(yōu)陣 6 2 3雅可比和高斯 塞德爾迭代收斂性 定義 設如果存在置換矩陣P 使得其中 A11為r階方陣 A22為n r階方陣 則稱A為可約矩陣 否則稱A為不可約矩陣 定理9 設如果1 A為嚴格對角占優(yōu)陣 則雅可比和高斯 塞德爾迭代法均收斂 2 A為弱對角占優(yōu)陣 且A為不可約矩陣 則雅可比和高斯 塞德爾迭代法均收斂 定理10 設矩陣A對稱 且 1 雅可比迭代法收斂的充要條件 A和2D A均為正定矩陣 其中D diag A 2 高斯 塞德爾迭代法收斂的充分條件 A正定 6 3超松弛迭代法 SOR方法

6、使用迭代法的困難在于難以估計其計算量 有時迭代過程雖然收斂 但由于收斂速度緩慢 使計算量變得很大而失去使用價值 因此 迭代過程的加速具有重要意義 逐次超松弛迭代 SuccessiveOverrelaxaticMethod 簡稱SOR方法 法 可以看作是帶參數(shù)的高斯 塞德爾迭代法 實質上是高斯 塞德爾迭代的一種加速方法 6 3 1超松弛迭代法的基本思想超松弛迭代法目的是為了提高迭代法的收斂速度 在高斯 塞德爾迭代公式的基礎上作一些修改 這種方法是將前一步的結果與高斯 塞德爾迭代方法的迭代值適當加權平均 期望獲得更好的近似值 是解大型稀疏矩陣方程組的有效方法之一 有著廣泛的應用 其具體計算公式如下

7、 用高斯 塞德爾迭代法定義輔助量 把取為與的加權平均 即 合并表示為 式中系數(shù) 稱為松弛因子 當 1時 便為高斯 塞德爾迭代法 為了保證迭代過程收斂 要求0 2 當0 1時 低松弛法 當1 2時稱為超松弛法 但通常統(tǒng)稱為超松弛法 SOR 6 3 2超松弛迭代法的矩陣表示設線性方程組Ax b的系數(shù)矩陣A非奇異 且主對角元素 則將A分裂成A d L U 則超松弛迭代公式用矩陣表示為 或 故 顯然對任何一個 值 D L 非奇異 因為假設 于是超松弛迭代公式為 令 則超松弛迭代公式可寫成 例4用SOR法求解線性方程組 取 1 46 要求 解 SOR迭代公式 k 0 1 2 初值 該方程組的精確解只需迭

8、代20次便可達到精度要求 如果取 1 即高斯 塞德爾迭代法 和同一初值 要達到同樣精度 需要迭代110次 6 3 2迭代法的收斂性我們知道 對于給定的方程組可以構造成簡單迭代公式 雅可比迭代公式 高斯 塞德爾迭代公式和超松弛迭代公式 但并非一定收斂 現(xiàn)在分析它們的收斂性 對于方程組經(jīng)過等價變換構造出的等價方程組 在什么條件下迭代序列收斂 基本定理5迭代公式收斂的充分必要條件是迭代矩陣G的譜半徑證 必要性設迭代公式收斂 當k 時 則在迭代公式兩端同時取極限得記 則收斂于0 零向量 且有 于是 由于可以是任意向量 故收斂于0當且僅當收斂于零矩陣 即當時 于是 所以必有 充分性 設 則必存在正數(shù) 使

9、則存在某種范數(shù) 使 則 所以 即 故收斂于0 收斂于由此定理可知 不論是雅可比迭代法 高斯 塞德爾迭代法還是超松弛迭代法 它們收斂的充要條件是其迭代矩陣的譜半徑 事實上 在例1中 迭代矩陣G 其特征多項式為 特征值為 2 3 所以迭代發(fā)散 定理6 迭代法收斂的充分條件 若迭代矩陣G的一種范數(shù) 則迭代公式收斂 且有誤差估計式 及 證 矩陣的譜半徑不超過矩陣的任一種范數(shù) 已知 因此 根據(jù)定理4 9可知迭代公式收斂 又因為 則det I G 0 I G為非奇異矩陣 故x Gx d有惟一解 即與迭代過程相比較 有兩邊取范數(shù) 由迭代格式 有 兩邊取范數(shù) 代入上式 得 證畢 由定理知 當時 其值越小 迭代

10、收斂越快 在程序設計中通常用相鄰兩次迭代 為給定的精度要求 作為控制迭代結束的條件 例5已知線性方程組 考察用Jacobi迭代和G S迭代求解時的收斂性解 雅可比迭代矩陣 故Jacobi迭代收斂 將系數(shù)矩陣分解 則高斯 塞德爾迭代矩陣 故高斯 塞德爾迭代收斂 33 例 給出方程組其中 問 分別利用Jacobi迭代法和Gauss Seidel迭代法是否收斂 解 對 而 即 所以 對 Jacobi方法收斂 G S方法發(fā)散 同理 對于 其中 即得 而 則 定理12對于線性方程組Ax b 若A為對稱正定矩陣 則當0 2時 SOR迭代收斂 證明只需證明 1 其中 為L 的任一特征值 定理13對于線性代數(shù)

11、方程組Ax b 若A按行 或列 嚴格對角占優(yōu) 或按行 或列 弱對角占優(yōu)不可約 則當0 w 1時 SOR迭代收斂 例6設 證明 求解方程組 的Jacobi迭代與G S迭代同時收斂或發(fā)散 證 雅可比迭代矩陣 其譜半徑 例6設 證明 求解方程組 的Jacobi迭代與G S迭代同時收斂或發(fā)散 證 G S迭代矩陣 其譜半徑 顯然 和同時小于 等于或大于1 因而Jacobi迭代法與G S迭代法具有相同的收斂性 例7考察用雅可比迭代法和高斯 塞德爾迭代法解線性方程組Ax b的收斂性 其中 解 先計算迭代矩陣 求特征值 雅可比矩陣 B 0 1 用雅可比迭代法求解時 迭代過程收斂 1 0 2 2 3 2 G1

12、2 1 用高斯 塞德爾迭代法求解時 迭代過程發(fā)散 高斯 塞德爾迭代矩陣 求特征值 Ax b的系數(shù)矩陣按行嚴格對角占優(yōu) 故高斯 塞德爾迭代收斂 例9設有迭代格式X k 1 BX k g k 0 1 2 其中B I A 如果A和B的特征值全為正數(shù) 試證 該迭代格式收斂 分析 根據(jù)A B和單位矩陣I之間的特征值的關系導出 1 從而說明迭代格式收斂 證 因為B I A 故 B I A 1 A A B 1由于已知 A 和 B 全為正數(shù) 故0 B 1 從而 B 1所以該迭代格式收斂 當 a 1時 Jacobi矩陣 GJ 1 對初值x 0 均收斂 例10設方程組寫出解方程組的Jacobi迭代公式和迭代矩陣并

13、討論迭代收斂的條件 寫出解方程組的Gauss Seidel迭代矩陣 并討論迭代收斂的條件 解 Jacobi迭代公式和Jacobi矩陣分別為 例10設方程組寫出解方程組的Gauss Seidel迭代矩陣 并討論迭代收斂的條件 解 Gauss Seidel矩陣為 當時 a 1時 Gauss Seidel矩陣 Gs 1 所以對任意初值x 0 均收斂 也可用矩陣的譜半徑p GS 1來討論 解 先計算迭代矩陣 例11討論用雅可比迭代法和高斯 塞德爾迭代法解線性方程組Ax b的收斂性 求特征值 雅可比矩陣 B 1 用雅可比迭代法求解時 迭代過程不收斂 1 1 2 3 1 2 求特征值 高斯 塞德爾迭代矩陣

14、 G1 0 3536 1 用高斯 塞德爾迭代法求解時 迭代過程收斂 1 0 求解AX b 當 取何值時迭代收斂 解 所給迭代公式的迭代矩陣為 例12給定線性方程組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迭代收斂 本章小結本章介紹了解線性方程組迭代法的一些基本理論和具體方法 迭代法是一種逐次逼近的方法 即對任意給定的初始近似解向量 按照某種方法逐步生成近似解序列 使解序列的極限為方程組的解 注意到在使用迭代法解方程組時 其迭代矩陣B和

15、迭代向量f在計算過程中始終不變 迭代法具有循環(huán)的計算公式 方法簡單 程序實現(xiàn)方便 它的優(yōu)點是能充分利用系數(shù)的稀疏性 適宜解大型稀疏系數(shù)矩陣的方程組 迭代法不存在誤差累積問題 使用迭代法的關鍵問題是其收斂性與收斂速度 收斂性與迭代初值的選取無關 這是比一般非線性方程求根的優(yōu)越之處 在實際計算中 判斷一種迭代格式收斂性較麻煩 由于求迭代的譜半徑時需要求特征值 當矩陣的階數(shù)較大時 特征值不易求出 通常采用矩陣的任一種范數(shù)都小于1或對角占優(yōu)來判斷收斂性 有時也可邊計算邊觀察其收斂性 如何加快迭代過程的收斂速度是一個很重要的問題 實用中更多的采用SOR法 選擇適當?shù)乃神Y因子 有賴于實際經(jīng)驗 我們應針對不同的實際問題 采用適當?shù)臄?shù)值算法