e基本的矩陣迭代法ppt課件.ppt

1 第三章線性方程組的迭代解法 基本的矩陣分裂迭代法 2 本講內(nèi)容 Jacobi迭代算法Gauss Seidel迭代算法SOR迭代算法收斂性分析 矩陣分裂迭代法的典型代表 3 Jacobi迭代 考慮線性方程組 Ax b 其中A aij n n非奇異 且對角線元素全不為0 將A分裂成A D L U 其中 4 Jacobi迭代 k 0 1 2 令M D N L U 可得雅可比 Jacobi 迭代方法 Jacobi迭代 迭代矩陣記為 5 6 Gauss Seidel迭代 在計算時 如果用代替 則可能會得到更好的收斂效果 7 Gauss Seidel迭代 寫成矩陣形式 此迭代方法稱為高斯 塞德爾 Gauss Seidel 迭代法 k 0 1 2 可得 迭代矩陣記為 8 SOR迭代 為了得到更好的收斂效果 可在修正項前乘以一個松弛因子 于是可得迭代格式 在G S迭代中 9 SOR迭代 寫成矩陣形式 可得 SOR SuccessiveOver Relaxation 迭代方法 迭代矩陣記為 SOR的優(yōu)點 通過選取合適的 可獲得更快的收斂速度SOR的缺點 最優(yōu)參數(shù) 的選取比較困難 10 Jacobi G S SOR Jacobi迭代 SOR迭代 G S迭代 11 舉例 例 分別用Jacobi G S SOR迭代解線性方程組 取初始向量x 0 0 0 0 迭代過程中小數(shù)點后保留4位 12 舉例 G S迭代 x 1 0 5000 2 8333 1 0833 T x 9 2 0000 3 0000 1 0000 T 迭代可得 13 舉例 SOR迭代 取 1 1 迭代可得 x 1 0 5500 3 1350 1 0257 T x 7 2 0000 3 0000 1 0000 T 如何確定SOR迭代中的最優(yōu)松弛因子是一件很困難的事 14 15 收斂性分析 定理 對任意初始向量x 0 上述迭代格式收斂的充要條件是 16 Jacobi迭代收斂的充要條件 J 1G S迭代收斂的充要條件 G 1SOR迭代收斂的充要條件 L 1 收斂性 收斂性定理 Jacobi迭代收斂的充分條件 J 1G S迭代收斂的充分條件 G 1SOR迭代收斂的充分條件 L 1 譜半徑 17 18 收斂性分析 B M 1N 定理 若存在算子范數(shù) 使得 B q 1 則 證明 P112 迭代法收斂 19 系數(shù)矩陣法 對角占優(yōu)矩陣 且至少有一個不等式嚴(yán)格成立 則稱A為弱對角占優(yōu) 若所有不等式都嚴(yán)格成立 則稱A為嚴(yán)格對角占優(yōu) i 1 2 n 定義 設(shè)A Rn n 若 20 Jacobi G S收斂性 引理3 2 若A嚴(yán)格對角占優(yōu) 則A非奇異 21 SOR收斂性 定理 若SOR迭代收斂 則0 2 SOR收斂的必要條件 22 舉例 例 設(shè) 給出Jacobi和G S收斂的充要條件 23 舉例 解法二 Jacobi的迭代矩陣為 設(shè) 是J的特征值 則由det I J 0可得 a 2 2a 0 Jacobi收斂的充要條件是 J 1 1 即 0