線性方程組的解法.ppt
《線性方程組的解法.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《線性方程組的解法.ppt(39頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
線性方程組的解法 解線性方程組的迭代法IterativeMethodsforLinearSystemsJacobi迭代和Gauss Seidel迭代迭代法的矩陣表示MatrixformoftheIterativeMethods 線性方程組的解法在計(jì)算數(shù)學(xué)中占有極其重要的地位 線性方程組的解法大致分為迭代法與直接法兩大類 雅可比 Jacobi 迭代法 舉例說(shuō)明雅可比迭代法的基本思路 例4 1 特點(diǎn) 系數(shù)矩陣主對(duì)角元均不為零 取迭代初值x1 0 0 x2 0 0 x3 0 0 將方程改寫成如下等價(jià)形式 據(jù)此建立迭代公式 x 0 000 x 1 0 77780 80000 8667 x 2 0 96300 96440 9778 x 3 0 99290 99350 9952 x 4 0 99870 99880 9991 x1 1 0000 x2 1 0000 x3 1 0000 準(zhǔn)確解 可以看出 迭代每前進(jìn)一步 結(jié)果就逼近準(zhǔn)確解一步迭代過(guò)程收斂 矩陣形式 以上這種迭代方法稱雅可比 Jacobi 迭代法 基本思想 將方程組的求解問(wèn)題轉(zhuǎn)化為重復(fù)計(jì)算一組彼此獨(dú)立的線性表達(dá)式 i 1 2 n k 0 1 2 i 1 2 n 設(shè)有方程組 將第i個(gè)方程的第i個(gè)變量xi分離出來(lái) 據(jù)此建立分量形式的雅可比迭代公式 如果 用矩陣形式來(lái)表示雅可比迭代公式 設(shè)有方程組 AX b其中A aij n為非奇異矩陣 X x1 x2 xn T b b1 b2 bn T 唯一解為X x1 x2 xn T將A分解為 A U D L其中 于是 U D L X b得X D U L X D b據(jù)此得矩陣形式的雅可比迭代公式X k 1 D U L X k D b記B D U L f D b有B 迭代矩陣 任取X 0 迭代計(jì)算產(chǎn)生向量序列 若 則迭代過(guò)程收斂 x 是方程組Ax b的解 X 1 X 2 X k 迭代法適用于解大型稀疏方程組 萬(wàn)階以上的方程組 系數(shù)矩陣中零元素占很大比例 而非零元按某種模式分布 背景 電路分析 邊值問(wèn)題的數(shù)值解和數(shù)學(xué)物理方程 問(wèn)題 1 如何構(gòu)造迭代格式 2 迭代格式是否收斂 3 收斂速度如何 4 如何進(jìn)行誤差估計(jì) 高斯塞德?tīng)朑auss Seidel迭代法 Gauss Seidel迭代法是通過(guò)對(duì)Jacobi迭代法稍加改進(jìn)得到的 Jacobi迭代法的每一步迭代新值x k 1 x1 k 1 x2 k 1 xn k 1 T都是用前一步的舊值x k x1 k x2 k xn k T的全部分量計(jì)算出來(lái)的 那么在計(jì)算第i個(gè)分量xi k 1 時(shí) 已經(jīng)計(jì)算出x1 k 1 x2 k 1 xi 1 k 1 i 1 個(gè)分量 這些分量新值沒(méi)用在計(jì)算xi k 1 上 將這些 i 1 2 n i 1 2 n k 0 1 2 將這些分量利用起來(lái) 有可能得到一個(gè)收斂更快的迭代公式 具體作法 將分量形式的雅可比迭代公式右端前 i 1 個(gè)分量的上標(biāo)為k換成k 1 即 分量形式的高斯 塞德?tīng)柕?用矩陣形式來(lái)表示高斯 塞德?tīng)柕?DX k 1 b LX k 1 UX k 即 D L X k 1 UX k b如果 D L 存在 則X k 1 D L UX k D L b記B D L f D L b則 矩陣形式的高斯 塞德?tīng)柕?B 迭代矩陣 例 例 Jacobi迭代算法 A 9 1 1 110 1 1 115 b 7 8 13 x 0 0 0 er 1 k 0 whileer 0 00005er 0 k k 1 fori 1 3s 0 t x i x i 0 forj 1 3s s A i j x j endx i t y i b i s A i i er max abs x i y i er endx y x end 0 77780 80000 86670 96300 96440 97190 99290 99350 99520 99870 99880 99910 99980 99980 99981 00001 00001 00001 00001 00001 0000 Gauss Seidel迭代算法 A 9 1 1 110 1 1 115 b 7 8 13 x 0 0 0 er 1 k 0 whileer 0 00005er 0 k k 1 fori 1 3s 0 t x i x i 0 forj 1 3s s A i j x j endx i b i s A i i er max abs x i t er endx end 0 77780 87780 97700 98390 99610 99870 99940 99980 99991 00001 00001 00001 00001 00001 0000 從計(jì)算結(jié)果可以明顯看出 Gauss Seidel迭代法比Jacobi迭代法效果好 一般而言 Gauss Seidel迭代法收斂速度比Jacobi迭代法快 但這兩種迭代法的收斂范圍并不完全重合 而只是部分相交 有的時(shí)候Jacobi迭代法可能比Gauss Seidel迭代法收斂速度更快 甚至可以舉出Jacobi迭代法收斂而Gauss Seidel迭代法發(fā)散的例子 Gauss Seidel迭代法和Jacobi迭代法的異同 Jacobi迭代法 公式簡(jiǎn)單 每次只需做矩陣和向量的一次乘法 特別適合于并行計(jì)算 不足之處 需存放X k 和X k 1 兩個(gè)存儲(chǔ)空間 Gauss Seidel迭代法 只需一個(gè)向量存儲(chǔ)空間 一旦計(jì)算出了xj k 1 立即存入xj k 的位置 可節(jié)約一套存儲(chǔ)單元 有時(shí)起到加速收斂的作用 是一種典型的串行算法 每次迭代中必須依次計(jì)算解的各個(gè)分量 超松馳 SOR 迭代法 超松馳迭代法是迭代方法的一種加速方法 其計(jì)算公式簡(jiǎn)單 但需要選擇合適的松馳因子 以保證迭代過(guò)程有較快的收斂速度 設(shè)有方程組AX b其中A aij n為非奇異矩陣 X x1 x2 xn T b b1 b2 bn T 記X k 為第k步迭代近似值 則r k b AX k 表示近似解X k 的殘余誤差 引進(jìn)如下形式的加速迭代公式 X k 1 X k w b AX w稱作松馳因子 其分量形式為選擇適當(dāng)?shù)乃神Y因子 可期望獲得較快的收斂速度 如果在計(jì)算分量xi k 1 時(shí) 考慮利用已經(jīng)計(jì)算出來(lái)的分量x1 k 1 x2 k 1 xi 1 k 1 又可得到一個(gè)新的迭代公式特別當(dāng)aii 0時(shí) 將上面迭代公式應(yīng)用于方程組 i 1 2 n 由此得下列超松馳 SOR 迭代公式 i 1 2 n k 0 1 2 3 當(dāng)w 1時(shí) 稱超松馳法 當(dāng)w 1時(shí) 稱低松馳法 當(dāng)w 1時(shí) 就是Gauss Seidel迭代公式 所以超松馳 SOR 迭代法可以看成是Gauss Seidel迭代法的加速 而Gauss Seidel迭代法是超松馳方法的特例 定理4 8若A是對(duì)稱正定矩陣 則當(dāng)0 w 2時(shí)SOR迭代法解方程組Ax b是收斂的 定理4 9若A是嚴(yán)格對(duì)角占優(yōu)矩陣 則當(dāng)0 w 1時(shí)SOR迭代法解方程組Ax b是收斂的 例4 3用SOR方法解方程組 w 1 4 w input input w A 2 10 12 1 0 12 b 1 0 1 8 x 1 1 1 er 1 k 0 whileer 0 0005er 0 k k 1 fori 1 3s 0 t x i x i 0 forj 1 3s s A i j x j endx i 1 w t w b i s A i i er max abs x i t er endendk k 10 x 1 19991 39991 5999 1 2 只需k 6 塊迭代法簡(jiǎn)介設(shè)A Rn n x Rn b Rn將方程組Ax b中系數(shù)矩陣A分塊 其中 Aii Rni ni Aij Rni nj xi Rni bi Rni 將A分解 A DB LB UB Jacobi塊迭代DBx k 1 LB UB x k b i 1 2 r 2 Gauss Seidel塊迭代DBx k 1 LBx k 1 UBx k b i 1 2 r 迭代法的收斂性Convergenceofiterativemethod迭代矩陣譜半徑Spectralradius對(duì)角占優(yōu)矩陣diagonallydominantmatrix 原始方程 Ax b 迭代格式 x k 1 Bx k f 定理4 1 迭代法基本定理 迭代法x k 1 Bx k f收斂的充要條件是 B 1 迭代法有著算法簡(jiǎn)單 程序設(shè)計(jì)容易以及可節(jié)省計(jì)算機(jī)存貯單元等優(yōu)點(diǎn) 但是迭代法也存在著收斂性和收斂速度等方面的問(wèn)題 因此弄清楚迭代法在什么樣的條件下收斂是至關(guān)重要的 證對(duì)任何n階矩陣B都存在非奇矩陣P使B P 1JP其中 J為B的Jordan標(biāo)準(zhǔn)型 其中 Ji為Jordan塊 其中 i是矩陣B的特征值 由B P 1JP Bk P 1JP P 1JP P 1JP P 1JkP 迭代法x k 1 Bx k f收斂 i 1 2 r 例線性方程組Ax b 分別取系數(shù)矩陣為 試分析Jacobi迭代法和Seidel迭代法的斂散性 1 2 A2 2 1 1 1 1 1 1 1 2 兩種迭代法之間沒(méi)有直接聯(lián)系對(duì)矩陣A1 求A1x b的Jacobi迭代法收斂 而Gauss Seidel迭代法發(fā)散 對(duì)矩陣A2 求A2x b的Jacobi迭代法發(fā)散 而Gauss Seidel迭代法收斂 證由 k B k 1 得 k B k 1 k 1 2 3 所以 定理4 2 迭代收斂的充分條件 設(shè)有迭代公式x k 1 Bx k f 如果 B 1 則對(duì)任意初始向量x 0 和任意f 迭代公式收斂 k B k 0 B 1 定義4 1A aij n n 如果則稱A為嚴(yán)格對(duì)角占優(yōu)陣 例4 1 定理4 3若Ax b的系數(shù)矩陣A是嚴(yán)格對(duì)角占優(yōu)矩陣 則Jacobi迭代和Seidel迭代均收斂 證由于矩陣A嚴(yán)格對(duì)角占優(yōu) 由A矩陣構(gòu)造Jacobi迭代矩陣BJ D 1 D A 第i行絕對(duì)值求和 所以 例4 2試對(duì)下列方程組建立收斂的迭代公式 解通過(guò)觀察可發(fā)現(xiàn)這個(gè)方程組的系數(shù)矩陣不是對(duì)角占優(yōu)的 但經(jīng)行交換后可得下列等價(jià)形式 此等價(jià)形式的系數(shù)矩陣是嚴(yán)格對(duì)角占優(yōu)陣 據(jù)此建立的雅可比迭代公式和高斯 塞德?tīng)柕绞諗?收斂速度 稱R B ln B 為迭代法的漸進(jìn)收斂速度簡(jiǎn)稱收斂速度- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 線性方程組 解法
鏈接地址:http://ioszen.com/p-8519394.html