《数值分析新课件教学专用NA04c》由会员分享,可在线阅读,更多相关《数值分析新课件教学专用NA04c(13页珍藏版)》请在金锄头文库上搜索。
1、4 迭代法的收敛性 /* Convergence of Iterative methods */,的收敛条件,充分条件: |B| 1,必要条件:,?,等价于对 任何算子范数有,4 Convergence of Iterative methods,证明:,“”:对任意非零向量 有,But hey, you dont seriously expect me to compute Bk whenever I want to check the convergence, do you?,4 Convergence of Iterative methods,证明:,“” 若 是 B 的eigenvalu
2、e, 则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, ( B ) 1,4 Convergence of Iterative methods,证明:,4 Convergence of Iterative methods,证明:首先需要一个引
3、理 /* Lemma */,若A 为SDD阵,则det(A) 0,且所有的 aii 0。,证明:若不然,即det(A) = 0,则 A 是奇异阵。,存在非零向量 使得,显然,我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证明:任何一个| | 1 都不可能是对应迭代阵的特征根,即 | I B | 0 。,Jacobi: BJ = D1( L + U ),aii 0,如果 | | 1 则,是SDD阵,HW: p.135 #7,关于Gauss-Seidel迭代的证明 与此类似。,5 松弛法 /* Relaxation Methods */,换个角度看Gauss - Seidel
4、方法:,其中ri(k+1) =,/* residual */,相当于在 的基础上加个余项生成 。,5 Relaxation Methods,写成矩阵形式:,松弛迭代阵,Oooooh come on! Its way too complicated to compute H , and you cant expect me to get its spectral radius right! Theres gotta be a short cut ,5 Relaxation Methods,证明:从 出发, | det(H) | = | 1 |n 1 0 2,5 Relaxation Method
5、s,Q: What factor determines the speed of convergence?,A: The smaller ( B ) is, the faster the iterations will converge.,对于SOR法,希望找 使得 ( H ) 最小。,5 Relaxation Methods,解:考察 B = I + A 的特征根, (B) = max | 1+ |, | 1+ 3 | 当 取何值时最小?, = - 1/2,HW: p.136 #11,5 Relaxation Methods,5 Relaxation Methods,注意:检查每个aii时,先向下 找最大元,若非0则交换到对角线上; 否则向上找最大元,若非0则 将该行加到第 i 行上。,5 Relaxation Methods,