新版線性方程組的迭代解法市公開(kāi)課獲獎(jiǎng)?wù)n件

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

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

3、i.m解例1.線性方程組迭代解法計(jì)算得到輸入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頁(yè)第9頁(yè)4.2.2 高斯塞德?tīng)?G-S)迭代法線性方程組迭代解法例2 解下面方程組（與例1相同，準(zhǔn)確解 ）解 1） 等價(jià)方程組 第10頁(yè)第10頁(yè)2） 高斯-賽德?tīng)柕?線性方程組迭代解法3） 取初始向量 第11頁(yè)第11頁(yè)線性方程組迭代解法迭代計(jì)算，得 【注】高斯-賽德?tīng)柕ū妊趴杀鹊ㄊ諗靠臁?第12頁(yè)第12

4、頁(yè)線性方程組迭代解法二、n階方程組高斯塞德?tīng)柕ǖ趇個(gè)方程 等價(jià)方程組 任取初始解向量 計(jì)算得迭代序列 高斯-賽德?tīng)?G-S)迭代公式對(duì)于 終止條件 第13頁(yè)第13頁(yè)G-S迭代矩陣形式 線性方程組迭代解法【注】（1）迭代法分量形式:用于計(jì)算編程；矩陣形式:用于研究迭代序列是否收斂等理論分析。（2）Jacobi適合并行計(jì)算. 不足:需存儲(chǔ)兩個(gè)向量。（3）G-S迭代法只需一個(gè)向量存儲(chǔ)空間。三、高斯塞德?tīng)柕ň仃嚸枋鼍仃嚤硎?第14頁(yè)第14頁(yè)調(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迭代法加速收斂，但它是一個(gè)典型串行算法。 第15頁(yè)第15頁(yè)例3 分別用雅可比和高斯-賽德?tīng)柕ń夥匠探M，均取相同初值1） Jacobi迭代4次達(dá)到精度G-S發(fā)散。 線性方程組迭代解法2） Jacobi發(fā)散， G-S發(fā)散。 第16頁(yè)第16頁(yè)3） Jacobi迭代89次達(dá)到精度G-S迭代8次達(dá)到同樣精度。 線性方程組迭代解法4） Jacobi發(fā)散，Jacobi和G-S也許同時(shí)發(fā)散；【注】也也許同時(shí)收斂，但一

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

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

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

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

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

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

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

13、寫(xiě)數(shù)據(jù)文本文獻(xiàn)sp.dat. %sp.dat：輸入每個(gè)非零元素行數(shù)、列數(shù)及非零元素5 1 103 5 204 4 305 5 40在MATLAB命令窗口中輸入指令：load sp.dat A=spconvert(sp) %將數(shù)據(jù)文獻(xiàn)sp.dat轉(zhuǎn)換為稀疏矩陣A第38頁(yè)第38頁(yè)線性方程組迭代解法nn=nnz(A) %輸出矩陣A非零元素個(gè)數(shù)運(yùn)營(yíng)得到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頁(yè)第39頁(yè)線性方程組迭代解法運(yùn)營(yíng)得到A = (2,1) 1 (3,1) 1 (4,1) 3 (1,2) 12 (2,3) 3 (4,3) 9第40頁(yè)第40頁(yè)41定義:設(shè)P 是一個(gè) mn (0,1) 矩陣，如 mn且 PP=E，則稱(chēng) P為一個(gè) mn置換矩陣。其中P是P轉(zhuǎn)置矩陣，E是m階單位