解线性方程组的迭代法收敛性名师优质课赛课一等奖市公开课获奖课件.pptxVIP

迭代法收敛性邹昌文 第1页 迭代法矩阵写法A =-L-UD第2页 Jacobi 迭代阵第3页 Gauss-Seidel 迭代阵第4页 迭代法收敛性 / Convergence of Iterative methods /收敛条件充分条件: ||B|| 1必要条件:？定义设：AAkk=? ?lim是指ijkijkaa=? ?)(lim对全部 1? i, j ? n 成立。等价于对任何算子范数有第5页 定义定理第6页 对任意非零向量 成立定理设存在唯一解，则从任意 出发， 迭代收敛?0?kB证实：Bk ? 0|| Bk || ? 0“?”：对任意非零向量 有“?”：取则第 i 位对任意非零向量 成立从任意 出发， 记 ，则as k ? ?收敛 那什么条件可确保 Bk 收敛呢？第7页 定理 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) + ? 。第8页 定理第9页 第10页 注：第11页 定理 （充分条件）若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?关于Gauss-Seidel迭代证实与这类似第12页 §5 松弛法 / Relaxation Methods /换个角度看Gauss - Seidel 方法：其中ri(k+1) =/ residual /相当于在 基础上加个余项生成 。下面令 ，希望经过选取适当 ? 来加速收敛，这就是松弛法 / Relaxation Methods / 。iikikikiarxx)1()()1(+++=w0 ? 1低松弛法 / Under- Relaxation methods /? = 1Gauss - Seidel 法? 1(渐次)超松弛法 / Successive Over- Relaxation methods /第13页 写成矩阵形式：松弛迭代阵定理 设 A 可逆，且 aii ? 0，松弛法从任意 出发对某个 ? 收敛 ? ? ( L? ) 1。第14页 定理 （Kahan 必要条件）设 A 可逆，且 aii ? 0，松弛法 从任意 出发收敛