新版線性方程組的迭代解法市公開課獲獎課件

1、第 4 章線性方程組迭代解法基礎教學部數(shù)學教研室 彭 曉 華立體化教學資源系列數(shù)值分析第1頁第1頁線性方程組迭代解法4.1 引言當A為低階稠密矩陣時，選主元消去法是有效辦法。對于大型稀疏線性方程組迭代法是適當。迭代法基本環(huán)節(jié)（1）等價形式B稱為迭代矩陣。（2）迭代公式線性方程組 A為非奇異矩陣。基本思想:用某種極限過程逐步迫近方程組準確解 。（3）任取向量,由上式生成向量序列 。若，則迭代過程收斂。第2頁第2頁線性方程組迭代解法（3）計算機算法？本章討論（2）迭代法收斂性與收斂速度？誤差預計？（1）慣用迭代辦法及詳細形式？4.2 基本迭代法4.2.1 雅可比迭代法一、三階方程組雅可比（Jaco

2、bi）迭代法例1 解方程組 第3頁第3頁線性方程組迭代解法解 1）等價形式 2）雅可比迭代公式3）取初始向量 第4頁第4頁.終止條件 線性方程組迭代解法顯然迭代序列逐步迫近準確解迭代計算結(jié)果如表 第5頁第5頁二、n 階方程組雅可比迭代法線性方程組迭代解法第i個方程 對于n階線性方程組 Ax =b,A為非奇異矩陣，且 等價方程 雅可比(Jacobi)迭代公式：對于 任取 x(0) ,計算得第6頁第6頁三、雅可比迭代法矩陣描述，其中， 線性方程組迭代解法終止條件為滿足精度 近似值。第7頁第7頁，即 雅可比迭代公式矩陣形式:線性方程組迭代解法其中，稱為雅可比迭代矩陣， 第8頁第8頁調(diào)用函數(shù)Jacob

3、i.m解例1.線性方程組迭代解法計算得到輸入A=10 3 1;2 -10 3;1 3 10;b=14 -5 14;ep=0.005;x,k,index=Jacobi(A,b,ep)x = 0.9982 k = 7 index = 1 迭代成功，收斂。 1.0001 0.9982第9頁第9頁4.2.2 高斯塞德爾(G-S)迭代法線性方程組迭代解法例2 解下面方程組（與例1相同，準確解 ）解 1） 等價方程組 第10頁第10頁2） 高斯-賽德爾迭代公式 線性方程組迭代解法3） 取初始向量 第11頁第11頁線性方程組迭代解法迭代計算，得 【注】高斯-賽德爾迭代法比雅可比迭代法收斂快。 第12頁第12

4、頁線性方程組迭代解法二、n階方程組高斯塞德爾迭代法第i個方程 等價方程組 任取初始解向量 計算得迭代序列 高斯-賽德爾(G-S)迭代公式對于 終止條件 第13頁第13頁G-S迭代矩陣形式 線性方程組迭代解法【注】（1）迭代法分量形式:用于計算編程；矩陣形式:用于研究迭代序列是否收斂等理論分析。（2）Jacobi適合并行計算. 不足:需存儲兩個向量。（3）G-S迭代法只需一個向量存儲空間。三、高斯塞德爾迭代法矩陣描述矩陣表示 第14頁第14頁調(diào)用函數(shù) Gauss_Seidel.m 解例1.線性方程組迭代解法x = 0.9998 k = 4 index = 1 迭代成功，收斂。 0.9998 1.

5、0001得到輸入A=10 3 1;2 -10 3;1 3 10;b=14 -5 14;ep=0.005;x,k,index=Gauss_Seidel(A,b,ep) （4）在一些情況下，G-S迭代法加速收斂，但它是一個典型串行算法。 第15頁第15頁例3 分別用雅可比和高斯-賽德爾迭代法解方程組，均取相同初值1） Jacobi迭代4次達到精度G-S發(fā)散。 線性方程組迭代解法2） Jacobi發(fā)散， G-S發(fā)散。 第16頁第16頁3） Jacobi迭代89次達到精度G-S迭代8次達到同樣精度。 線性方程組迭代解法4） Jacobi發(fā)散，Jacobi和G-S也許同時發(fā)散；【注】也也許同時收斂，但一

6、個快另一個慢；也許一個收斂而另一個發(fā)散。 G-S迭代10次達到精度第17頁第17頁. 線性方程組迭代解法4.2.3 逐次超松弛(SOR)迭代法SOR迭代法:G-S迭代法基礎上,用參數(shù)校正殘差加速. 一、逐次超松弛迭代公式G-S迭代公式中加、減 第18頁第18頁線性方程組迭代解法第i個方程殘差: 【注】（1）G-S：對舊值 ，經(jīng)殘差校正而得新近似值，校正量大小為（2）為加速收斂，將校正量乘加速因子 有 為松馳因子. 當 時為低松馳因子； 時為當G-S公式； 稱為超松馳因子.第19頁第19頁20二、逐次超松弛迭代法矩陣描述其中， 松弛迭代矩陣 整理得記作 寫成矩陣形式 第20頁第20頁線性方程組迭

7、代解法例4 用SOR解方程組，取解 方程組準確解為： 取初值 用G-S迭代得 第21頁第21頁線性方程組迭代解法利用SOR辦法 初值 迭代計算結(jié)果 第22頁第22頁線性方程組迭代解法【注】 SOR迭代5次，與G-S法迭代10次結(jié)果大體相同，SOR辦法松馳因子起到了加速收斂主要作用. 第23頁第23頁線性方程組迭代解法【注】 最佳松馳因子：使迭代收斂最快，記為（）特殊情形 若A為對稱正定三對角矩陣時 其中 為Jacobi迭代矩陣譜半徑 （）其它情形 采用試算辦法 例 方程組 取 精度為:為較佳松弛因子 顯然第24頁第24頁線性方程組迭代解法 4.3 迭代法收斂性研究： （1）收斂性與迭代矩陣關系

8、？ （2）迭代公式收斂充要條件？充足條件？ （3）迭代收斂速度？ 4. 3. 1迭代法收斂性判別（迭代法收斂充要條件）n 階線性方程組， ，A 為非奇異矩陣，且 等價形式為 一、迭代矩陣B準確解 滿足 線性迭代公式 第25頁第25頁線性方程組迭代解法【定理1】 設 ， ，收斂 （迭代法收斂充足條件） 由 假如，則 【定理2】 設，若，則 收斂, 且二、迭代矩陣范數(shù)【注】迭代矩陣范數(shù)小于1是收斂充足條件.第26頁第26頁線性方程組迭代解法（迭代法收斂基本定理） 【定義1】方陣A譜半徑： 其中 是An個特性值。 【定理3】和 證實（1）充足性：設由于 取迭代初值當時,收斂 （2）必要性：若迭代法收

9、斂，依據(jù)定理1 即 又由 因此三、迭代矩陣譜半徑（迭代法收斂基本定理） 第27頁第27頁線性方程組迭代解法例5證實:Jacobi收斂，G-S發(fā)散。 證實 1)2) Jacobi收斂。G-S發(fā)散【注】|BJ|=41. 利用迭代矩陣范數(shù)不能判別其收斂性。第28頁第28頁線性方程組迭代解法4.3.2 特殊方程組迭代法收斂性【定義2】行占優(yōu)： 列占優(yōu)： （對角占優(yōu)矩陣） 弱對角占優(yōu)矩陣： （或），且至少有一個不等式是嚴格成立?！径x3】（可約矩陣） 存在置換陣P使不存在置換陣P 使上式成立。（不可約矩陣） 【注】可約陣通過行列重排,求解化為求解 第29頁第29頁線性方程組迭代解法【定理4】(1)A為嚴

10、格對角占優(yōu)陣，Jacobi和G-S收斂。(2)A為弱對角占優(yōu)陣,且A不可約,則Jacobi和G-S收斂。只證實JacobiJacobi收斂例6 解 A嚴格對角占優(yōu) Jacobi和G-S收斂?！径ɡ?】A是對稱正定方陣，則解 G-S收斂。證實 第30頁第30頁線性方程組迭代解法例7 A對稱正定，則G-S收斂.（1）取 （2）Jacobi 發(fā)散。 G-S 收斂。 第31頁第31頁線性方程組迭代解法【定理6】SOR收斂 證實【定理7】A為實對稱正定矩陣,則 SOR收斂 【定理8】(1)A嚴格對角占優(yōu)陣(或弱對角占優(yōu)不可約陣)則解Ax=bSOR收斂。(2)第32頁第32頁線性方程組迭代解法4.3.3

11、迭代法收斂速度B為對稱矩陣 擬定使誤差縮小迭代次數(shù) 【注】k與成反比 【定義4】迭代法收斂速度 第33頁第33頁線性方程組迭代解法4.4 稀疏方程組及MATLAB實現(xiàn)4.4.1分塊迭代法為大型稀疏矩陣 其中 對x及b同樣分塊階非奇異矩陣，為 第34頁第34頁線性方程組迭代解法一、塊雅可比迭代法（BJ）其中【注】塊雅可比迭代法需要求解低階方程組 其中， 第35頁第35頁線性方程組迭代解法二、塊SOR迭代法（BSOR） 從共需要解q個低階方程組 【定理9】（1）假如A為對稱正定矩陣，（2）則解Ax=bBSOR迭代收斂。 4.4.2 MATLAB稀疏矩陣簡介例8 利用MATLAB生成稀疏矩陣及求解，

12、并與滿陣解法作時間上對比： 第36頁第36頁線性方程組迭代解法n=1000;e=ones(n,1);A=spdiags(e 4*e e, -1:1, n, n);%以對角帶生成A或用sparse語句生成b=e;tic;x=Ab;elapsed_time1=toc %輸出解稀疏矩陣方程組所用時間a=full(A);tic;x=ab;elapsed_time2=toc %輸出解滿陣方程組所用時間（與計算機速度相關）運營得到，解稀疏方程組所用時間為：elapsed_time1 = 0.解滿陣方程組所用時間為：elapsed_time2 = 0.4380.第37頁第37頁線性方程組迭代解法例9 首先編

13、寫數(shù)據(jù)文本文獻sp.dat. %sp.dat：輸入每個非零元素行數(shù)、列數(shù)及非零元素5 1 103 5 204 4 305 5 40在MATLAB命令窗口中輸入指令：load sp.dat A=spconvert(sp) %將數(shù)據(jù)文獻sp.dat轉(zhuǎn)換為稀疏矩陣A第38頁第38頁線性方程組迭代解法nn=nnz(A) %輸出矩陣A非零元素個數(shù)運營得到A= (5,1) 10 (4,4) 30 (3,5) 20 (5,5) 40 nn= 4【注】在MATLAB中利用sparse建立稀疏矩陣.比如，a=0 12 0;1 0 3;1 0 0;3 0 9;A=sparse(a) %將矩陣a轉(zhuǎn)換為稀疏矩陣形式 第39頁第39頁線性方程組迭代解法運營得到A = (2,1) 1 (3,1) 1 (4,1) 3 (1,2) 12 (2,3) 3 (4,3) 9第40頁第40頁41定義:設P 是一個 mn (0,1) 矩陣，如 mn且 PP=E，則稱 P為一個 mn置換矩陣。其中P是P轉(zhuǎn)置矩陣，E是m階單位