第三讲 线性方程组基本迭代解法

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 不可约对角占优矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-133.2.3 对称正定矩阵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6、 3-153.2.4 相容次序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-173.3 正则分裂 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-203.3.1 正则分裂, 弱正则分裂和非负分裂 . . . . . . . .

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 外推技术 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-373.5.2 Chebyshev 加速 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-3

11、8注: 本讲义仅供课堂教学使用. 2016.09· 3-2 ·常用的定常迭代主要包括:• Jacobi 迭代• Gauss-Seidel (GS) 迭代• 超松弛 (SOR, Successive Over-Relaxation) 迭代• 对称超松弛 (SSOR, Symmetric SOR) 迭代• 加速超松弛 (AOR, Accelerated Over-Relaxation) 迭代• 交替方向 (ADI) 迭代

12、和对称与斜对称 (HSS) 迭代迭代算法的基本思想: 给定一个迭代初始值 x(0), 通过一定的迭代格式生成一个迭代序列 {x(k)}∞ k=0, 使得lim k→∞ x(k) = x∗ � A−1b.一般来说, 迭代法可表示为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 就称为迭代函数. 若 φk 都是线性的, 则称为线性迭代法, 否则称为非线性迭代法.• 如果存在正整数 ℓ, 使得当 k ≥ ℓ 时, φk 的表达式与 k 无关, 则上述迭代格式就构成一个 定常迭代法 (stationary iteration), 否则就是非定常的 (nonstationary).• 如果是定常迭代, 则有 φℓ = φℓ+1 = · · · � φ, 此时 x(k+1)

14、 只与 x(k), x(k−1), . . . , x(k−ℓ+1)有关. 若 x(k+1) 只与 x(k) 有关, 则称为单步迭代, 否则就称为多步迭代.� 本讲主要介绍基于矩阵分裂的单步线性迭代方法.3.1.1 矩阵分裂与迭代法首先给出 矩阵分裂 的定义.定义 3.1 (矩阵分裂 Matrix Splitting) 设 A ∈ Rn×n 非奇异, 称A = M − N (3.1)为 A 的一个矩阵分裂, 其中 M 非奇异.