第三講 線性方程組基本迭代解法

1、第三講 線性方程組基本迭代解法3.1 定常迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13.1.1 矩陣分裂與迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-23.1.2 Jacobi 迭代 . . . . . . . . . . .

2、. . . . . . . . . . . . . . . . . . . . . . . 3-33.1.3 Gauss-Seidel 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-43.1.4 SOR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

3、-43.1.5 SSOR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-53.1.6 AOR 與 SAOR 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-63.1.7 Richardson 迭代 . . . . . . . . . . . . . . . .

4、. . . . . . . . . . . . . . . . 3-73.1.8 塊迭代方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-83.2 收斂性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-83.2.1 迭代法的收斂性

5、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-83.2.2 不可約對(duì)角占優(yōu)矩陣 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-133.2.3 對(duì)稱正定矩陣 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6、 3-153.2.4 相容次序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-173.3 正則分裂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-203.3.1 正則分裂, 弱正則分裂和非負(fù)分裂 . . . . . . . .

7、. . . . . . . . . . . . . 3-203.3.2 正則分裂與迭代收斂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-273.3.3 P-正則分裂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-293.4 交替方向迭代法 . . . . . . . .

8、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-313.4.1 多步迭代法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-313.4.2 交替方向法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9、 . . 3-313.4.3 HSS 迭代 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-323.4.4 HSS 迭代的推廣 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-343.5 加速技巧 . . . . . . . . . . . . . . . . .

10、 . . . . . . . . . . . . . . . . . . . . . . 3-373.5.1 外推技術(shù) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-373.5.2 Chebyshev 加速 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3

11、8注: 本講義僅供課堂教學(xué)使用. 2016.09· 3-2 ·常用的定常迭代主要包括:? Jacobi 迭代? Gauss-Seidel (GS) 迭代? 超松弛 (SOR, Successive Over-Relaxation) 迭代? 對(duì)稱超松弛 (SSOR, Symmetric SOR) 迭代? 加速超松弛 (AOR, Accelerated Over-Relaxation) 迭代? 交替方向 (ADI) 迭代

12、和對(duì)稱與斜對(duì)稱 (HSS) 迭代迭代算法的基本思想: 給定一個(gè)迭代初始值 x(0), 通過(guò)一定的迭代格式生成一個(gè)迭代序列 {x(k)}∞ k=0, 使得lim k→∞ x(k) = x? ? A?1b.一般來(lái)說(shuō), 迭代法可表示為x(k+1) = φk(x(k), x(k?1), . . . , x(1), x(0), A, b), k = 0, 1, 2, . . . ,其中 x(0) = φ0(A, b), 或者 x(0) 直接給出.

13、? 這里 φk 就稱為迭代函數(shù). 若 φk 都是線性的, 則稱為線性迭代法, 否則稱為非線性迭代法.? 如果存在正整數(shù) ?, 使得當(dāng) k ≥ ? 時(shí), φk 的表達(dá)式與 k 無(wú)關(guān), 則上述迭代格式就構(gòu)成一個(gè) 定常迭代法 (stationary iteration), 否則就是非定常的 (nonstationary).? 如果是定常迭代, 則有 φ? = φ?+1 = · · · ? φ, 此時(shí) x(k+1)

14、 只與 x(k), x(k?1), . . . , x(k??+1)有關(guān). 若 x(k+1) 只與 x(k) 有關(guān), 則稱為單步迭代, 否則就稱為多步迭代.? 本講主要介紹基于矩陣分裂的單步線性迭代方法.3.1.1 矩陣分裂與迭代法首先給出 矩陣分裂 的定義.定義 3.1 (矩陣分裂 Matrix Splitting) 設(shè) A ∈ Rn×n 非奇異, 稱A = M ? N (3.1)為 A 的一個(gè)矩陣分裂, 其中 M 非奇異.