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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,迭代法收敛性,邹昌文,第1页,迭代法矩阵写法,A,=,-L,-U,D,第2页,Jacobi 迭代阵,第3页,Gauss-Seidel,迭代阵,第4页,迭代法收敛性,/Convergence of Iterative methods/,收敛条件,充分条件,:|,B,|,1,必要条件,:,？,定义,设,：,A,A,k,k,=,lim,是指,ij,k,ij,k,a,a,=,),(,lim,对全部 1,i,j,n,成立。,等价于对,任何算子范数有,第5页,定义,定理,第6页,对,任意非零向量 成立,定理,设,存在唯一解，则从任意 出发，,迭代,收敛,0,k,B,证实：,B,k,0,|,B,k,|,0,“”：对任意非零向量,有,“,”：取,则,第,i,位,对,任意非零向量 成立,从任意 出发，记 ，则,as,k,收敛,那什么条件可确保,B,k,收敛呢？,第7页,定理,B,k,0,(,B,)1,证实：,“,”若,是,B,eigenvalue,则,k,是,B,k,eigenvalue。,则,(,B,),k,=max|,|,k,=|,m,k,|,(,B,k,),|,B,k,|0,(,B,),0,存在算子范数,|,使得,|,A,|,(,A,)+,。,由,(,B,),1 可知存在算子范数,|使得,|,B,|1,。,|,B,k,|,B,|,k,0 as,k,B,k,0,迭代从任意向量出发收敛,B,k,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，且全部,a,ii,0。,证实：,若不然，即det(,A,)=0，则,A,是奇异阵。,存在非零向量 使得,记,显然,我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证实：任何一个,|,|,1,都,不可能,是对应迭代阵特征根，即,|,I B,|,0,。,Jacobi:,B,J,=,D,1,(,L,+,U,),a,ii,0,假如|,|,1 则,是SDD阵,|,I B,|,0,关于Gauss-Seidel迭代证实,与这类似,第12页,5,松弛法,/Relaxation Methods/,换个角度看Gauss-Seidel 方法：,其中,r,i,(,k,+1),=,/residual/,相当于在 基础上,加个余项,生成 。,下面令 ，希望经过选取适当,来加速收敛，这就是,松弛法,/Relaxation Methods/,。,ii,k,i,k,i,k,i,a,r,x,x,),1,(,),(,),1,(,+,+,+,=,w,0,1,(渐次)超松弛法,/Successive Over-Relaxation methods/,第13页,写成,矩阵形式,：,松弛迭代阵,定理,设,A,可逆，且,a,ii,0，,松弛法从任意 出发对某个,收敛,(,L,)1。,第14页,定理,（Kahan 必要条件）,设,A,可逆，且,a,ii,0，,松弛法 从任意 出发收敛,0,2,。,证实：,从 出发,利用,，而且收敛,|,i,|1 总成立,可知收敛,|,det(,H,),|1,|,det(,L,),|=|1,|,n,1 ,0,2,第15页,定理,（Ostrowski-Reich 充分条件）,若,A,对称正定，且有,0,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,-2/3,0,(,B,),=,max,|,1,+,|,|,1,+,3,|,当,取何值时,最小？,-2/3,-1/3,0,=,-,1/2,第17页,