NA04c数值分析课件.ppt

* §4 迭代法的收敛性 /* Convergence of Iterative methods */ 的收敛条件 充分条件: ||B|| 1 必要条件: ？ 定义 设： A A k k =  ? ? lim 是指 ij k ij k a a =  ? ? ) ( lim 对所有 1? i, j ? n 成立。 等价于对 任何算子范数有 对任意非零向量 成立 §4 Convergence of Iterative methods 定理 设 存在唯一解，则从任意 出发， 迭代 收敛 ? 0 ? k B 证明： Bk ? 0 || Bk || ? 0 “?”：对任意非零向量 有 “?”：取 则 第 i 位 对任意非零向量 成立 从任意 出发， 记 ，则 as k ? ? 收敛 But hey, you don’t seriously expect me to compute Bk whenever I want to check the convergence, do you? §4 Convergence of Iterative methods 定理 Bk ? 0 ? ? ( B ) 1 证明： “?” 若 ? 是 B 的eigenvalue, 则?k 是 Bk 的eigenvalue 。 则 [? (B)]k = [ max | ? | ]k = | ?mk | ? ? ( Bk ) ? || Bk || ? 0 ? ? (B) 1 ? “?” 首先需要一个引理 /* Lemma */ 对任意 ? 0, 存在算子范数 || · || 使得 || A || ? ? (A) + ? 。 由 ? (B) 1 可知存在算子范数|| · || 使得 || B || 1。 || Bk || ? || B ||k ? 0 as k ? ? Bk ? 0 迭代从任意向量出发收敛 Bk ? 0 ? ( B ) 1 证明：对 A 做 Jordan 分解，有 ，其中 ， ， ?i 为 A 的 eigen value。 令 ，则有 易证： 是由 导出的算子范数。 所以只要取 ? ? ，就有|| A ||? ? (A) + ? 。 §4 Convergence of Iterative methods 定理 （充分条件）若存在一个矩阵范数使得 || B || = q 1, 则迭代收敛，且有下列误差估计： ① ② 证明： ① ? ② §4 Convergence of Iterative methods 定理 （充分条件）若A 为严格对角占优阵 /* strictly diagonally dominant matrix */ 则解 的Jacobi 和 Gauss - Seidel 迭代均收敛。 证明：首先需要一个引理 /* Lemma */ 若A 为SDD阵，则det(A) ? 0，且所有的 aii ? 0。 证明：若不然，即det(A) = 0，则 A 是奇异阵。 存在非零向量 使得 记 显然 我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证明：任何一个| ? | ? 1 都不可能是对应迭代阵的特征根，即 | ?I ? B | ? 0 。 Jacobi: BJ = ?D?1( L + U ) aii ? 0 如果 | ? | ? 1 则 是SDD阵 | ?I ? B | ? 0 ? HW: p.76 #1 关于Gauss-Seidel迭代的证明 与此类似 (p.73)。 另一种证明引理的方法利用 Ger?gorin Disc Theorem (p.72)。 §5 松弛法 /* Relaxation Methods */ 换个角度看Gauss - Seidel 方法： 其中ri(k+1) = /* residual