線性方程組的解法.ppt

線性方程組的解法 解線性方程組的迭代法IterativeMethodsforLinearSystemsJacobi迭代和Gauss Seidel迭代迭代法的矩陣表示MatrixformoftheIterativeMethods 線性方程組的解法在計算數(shù)學(xué)中占有極其重要的地位 線性方程組的解法大致分為迭代法與直接法兩大類 雅可比 Jacobi 迭代法 舉例說明雅可比迭代法的基本思路 例4 1 特點(diǎn) 系數(shù)矩陣主對角元均不為零 取迭代初值x1 0 0 x2 0 0 x3 0 0 將方程改寫成如下等價形式 據(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)確解一步迭代過程收斂 矩陣形式 以上這種迭代方法稱雅可比 Jacobi 迭代法 基本思想 將方程組的求解問題轉(zhuǎn)化為重復(fù)計算一組彼此獨(dú)立的線性表達(dá)式 i 1 2 n k 0 1 2 i 1 2 n 設(shè)有方程組 將第i個方程的第i個變量xi分離出來 據(jù)此建立分量形式的雅可比迭代公式 如果 用矩陣形式來表示雅可比迭代公式 設(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 迭代計算產(chǎn)生向量序列 若 則迭代過程收斂 x 是方程組Ax b的解 X 1 X 2 X k 迭代法適用于解大型稀疏方程組 萬階以上的方程組 系數(shù)矩陣中零元素占很大比例 而非零元按某種模式分布 背景 電路分析 邊值問題的數(shù)值解和數(shù)學(xué)物理方程 問題 1 如何構(gòu)造迭代格式 2 迭代格式是否收斂 3 收斂速度如何 4 如何進(jìn)行誤差估計 高斯塞德爾Gauss Seidel迭代法 Gauss Seidel迭代法是通過對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的全部分量計算出來的 那么在計算第i個分量xi k 1 時 已經(jīng)計算出x1 k 1 x2 k 1 xi 1 k 1 i 1 個分量 這些分量新值沒用在計算xi k 1 上 將這些 i 1 2 n i 1 2 n k 0 1 2 將這些分量利用起來 有可能得到一個收斂更快的迭代公式 具體作法 將分量形式的雅可比迭代公式右端前 i 1 個分量的上標(biāo)為k換成k 1 即 分量形式的高斯 塞德爾迭代公式 用矩陣形式來表示高斯 塞德爾迭代公式 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則 矩陣形式的高斯 塞德爾迭代公式 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 從計算結(jié)果可以明顯看出 Gauss Seidel迭代法比Jacobi迭代法效果好 一般而言 Gauss Seidel迭代法收斂速度比Jacobi迭代法快 但這兩種迭代法的收斂范圍并不完全重合 而只是部分相交 有的時候Jacobi迭代法可能比Gauss Seidel迭代法收斂速度更快 甚至可以舉出Jacobi迭代法收斂而Gauss Seidel迭代法發(fā)散的例子 Gauss Seidel迭代法和Jacobi迭代法的異同 Jacobi迭代法 公式簡單 每次只需做矩陣和向量的一次乘法 特別適合于并行計算 不足之處 需存放X k 和X k 1 兩個存儲空間 Gauss Seidel迭代法 只需一個向量存儲空間 一旦計算出了xj k 1 立即存入xj k 的位置 可節(jié)約一套存儲單元 有時起到加速收斂的作用 是一種典型的串行算法 每次迭代中必須依次計算解的各個分量 超松馳 SOR 迭代法 超松馳迭代法是迭代方法的一種加速方法 其計算公式簡單 但需要選擇合適的松馳因子 以保證迭代過程有較快的收斂速度 設(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因子 可期望獲得較快的收斂速度 如果在計算分量xi k 1 時 考慮利用已經(jīng)計算出來的分量x1 k 1 x2 k 1 xi 1 k 1 又可得到一個新的迭代公式特別當(dāng)aii 0時 將上面迭代公式應(yīng)用于方程組 i 1 2 n 由此得下列超松馳 SOR 迭代公式 i 1 2 n k 0 1 2 3 當(dāng)w 1時 稱超松馳法 當(dāng)w 1時 稱低松馳法 當(dāng)w 1時 就是Gauss Seidel迭代公式 所以超松馳 SOR 迭代法可以看成是Gauss Seidel迭代法的加速 而Gauss Seidel迭代法是超松馳方法的特例 定理4 8若A是對稱正定矩陣 則當(dāng)0 w 2時SOR迭代法解方程組Ax b是收斂的 定理4 9若A是嚴(yán)格對角占優(yōu)矩陣 則當(dāng)0 w 1時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 塊迭代法簡介設(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對角占優(yōu)矩陣diagonallydominantmatrix 原始方程 Ax b 迭代格式 x k 1 Bx k f 定理4 1 迭代法基本定理 迭代法x k 1 Bx k f收斂的充要條件是 B 1 迭代法有著算法簡單 程序設(shè)計容易以及可節(jié)省計算機(jī)存貯單元等優(yōu)點(diǎn) 但是迭代法也存在著收斂性和收斂速度等方面的問題 因此弄清楚迭代法在什么樣的條件下收斂是至關(guān)重要的 證對任何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 兩種迭代法之間沒有直接聯(lián)系對矩陣A1 求A1x b的Jacobi迭代法收斂 而Gauss Seidel迭代法發(fā)散 對矩陣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 則對任意初始向量x 0 和任意f 迭代公式收斂 k B k 0 B 1 定義4 1A aij n n 如果則稱A為嚴(yán)格對角占優(yōu)陣 例4 1 定理4 3若Ax b的系數(shù)矩陣A是嚴(yán)格對角占優(yōu)矩陣 則Jacobi迭代和Seidel迭代均收斂 證由于矩陣A嚴(yán)格對角占優(yōu) 由A矩陣構(gòu)造Jacobi迭代矩陣BJ D 1 D A 第i行絕對值求和 所以 例4 2試對下列方程組建立收斂的迭代公式 解通過觀察可發(fā)現(xiàn)這個方程組的系數(shù)矩陣不是對角占優(yōu)的 但經(jīng)行交換后可得下列等價形式 此等價形式的系數(shù)矩陣是嚴(yán)格對角占優(yōu)陣 據(jù)此建立的雅可比迭代公式和高斯 塞德爾迭代公式收斂 收斂速度 稱R B ln B 為迭代法的漸進(jìn)收斂速度簡稱收斂速度