解线性方程组的迭代法收敛性省公共课一等奖全国赛课获奖课件.pptx

迭代法收敛性迭代法收敛性邹昌文邹昌文 第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页对对任意非零向量任意非零向量 成立成立定理定理设设存在唯一解，则从任意存在唯一解，则从任意 出发，出发，迭代迭代收敛收敛0kB证实：证实：Bk 0|Bk|0“”：对任意非零向量：对任意非零向量 有有“”：取：取则则第第 i 位位对对任意非零向量任意非零向量 成立成立从任意从任意 出发，出发，记记 ，则则as k 收敛收敛 那什么条件可确保那什么条件可确保 Bk 收敛呢？收敛呢？第7页定理定理 Bk 0 0 (B)1 1证实：证实：“”若若 是是 B eigenvalue,则则 k 是是 Bk eigenvalue。则则 (B)k=max|k=|mk|(Bk)|Bk|0 (B)0,存在算子范数存在算子范数|使得使得|A|(A)+)+。由由 (B)1 可知存在算子范数可知存在算子范数|使得使得|B|1。|Bk|B|k 0 as k Bk 0迭代从任意向量出发收敛迭代从任意向量出发收敛Bk 0 0 (B)1)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(+=0 1(渐次渐次)超松弛法超松弛法/Successive Over-Relaxation methods/第13页写成写成矩阵形式矩阵形式：松弛迭代阵松弛迭代阵定理定理 设设 A 可逆，且可逆，且 aii 0，松弛法从任意松弛法从任意 出发对出发对某个某个 收敛收敛 (L )1)1。第14页定理定理 （Kahan 必要条件）必要条件）设设 A 可逆，且可逆，且 aii 0，松弛法松弛法 从任意从任意 出发收敛出发收敛 0 0 2 2 。证实：证实：从从 出发出发利用利用，而且收敛，而且收敛|i|1|1 总成立总成立可知收敛可知收敛|det(H)|1|1|det(L)|=|1|=|1|n 1 1 0 0 2 2 第15页定理定理 （Ostrowski-Reich 充分条件）充分条件）若若A 对称正定，且对称正定，且有有 0 0 2 2，则，则松弛法从任意松弛法从任意 出发收敛出发收敛。Q:What factor determines the speed of convergence?考查迭代考查迭代：设：设 B 有特征根有特征根 1、n 对对应应 n 个线性无关特征向量个线性无关特征向量 。则从任意。则从任意 出发，出发，可表为可表为 线性组合，即线性组合，即A:The smaller (B)is,the faster the iterations will converge.对于对于SOR法，希望找法，希望找 使得使得 (L )最小最小。第16页定理定理 若若 A 为为对称正定三对角阵对称正定三对角阵，则，则且且SOR最正确松弛因子最正确松弛因子/optimal choice of for SOR method/为为 ，此时，此时 。例：例：，考虑迭代格式，考虑迭代格式问：问：取何值可使迭代收敛？取何值可使迭代收敛？取何值时迭代收敛最快？取何值时迭代收敛最快？解：解：考查考查 B=I+A 特征根特征根 1=1+,2=1+3 收敛要求收敛要求 (B)1 )1 2/3 2/3 0 (B)=max|1+|,|1+3|当当 取何值时取何值时最小？最小？2/32/31/31/30 0 =1/2第17页