线性代数方程组的迭代法省公开课一等奖全国示范课微课金奖PPT课件.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章,线性方程组,迭代法,第1页,1,迭代法基础,问 题,在实际应用中碰到系数矩阵多为大型稀疏矩阵，如用求解线性方程组直接法求解，在计算机上会花费大量时间和存放单元。在许多应用问题中使用迭代法。,第2页,思绪,将 改写为 等价形式 ，建立迭代,从初值 出发，得到序列 。,研究内容：,怎样建立迭代格式？,收敛速度？,向量序列收敛条件？,误差预计？,第3页,普通迭代法,定义1,对方程组 ，化为等价方程组 ，设 为任取,初值，,将上式写为,迭代过程,这种迭代过程称为,逐次迫近法,，,B,称为,迭代矩阵,。若,称逐次迫近法,收敛，,不然，称逐次迫近法,不收敛或发散,。,第4页,问题：,按上述思想,迭代产生向量序列 在什,么条件下,收敛于方程组Ax=b解？,引进误差向量,：，其中 为方程组解，即有,所以，要使 收敛到 ，则需研究 在,什么条件下有 。,第5页,迭代法收敛条件与误差预计,引理,当k,时，,B,k,0,(,B,)1,定理1,设有线性方程组 ，那么逐次迫近,法对任意初始向量 收敛充分必要条件,是迭代矩阵B谱半径,(,B,),1。,注：,要检验一个矩阵谱半径小于1比较困难，所以我们希望用别方法判断收敛性。,第6页,注,:,1.因为矩阵范数 都能够直接用矩阵元素,计算，所以用定理2，很轻易判别逐次迫近法收敛性。,2.定理2是充分条件，当找不到矩阵某一范数小于1时，,并不能判断,迭代法不收敛。,定理2,设线性方程组 有惟一解 ，,若存,在一个矩阵范数使得|,B,|1,则,迭代收敛,且有以下误差预计：,第7页,（7,.1,）,1雅克比（Jacobi）迭代法,设有,n,阶方程组,2,几个惯用迭代法,第8页,若系数矩阵非奇异，且,(,i,=1,2,n,)，,将方程组,（7.1）,改写成,第9页,然后写成迭代格式,（7.2）,（7.2）,式也能够简单地写为,（7.3）,第10页,记 ,其中,则雅克比迭代法矩阵形式为：,(7.4),称 为雅克比迭代矩阵。,第11页,第12页,写成矩阵形式：,2高斯赛得尔(Gauss-Seidel)迭代法,(7.5),(7.6),其中 称为,高斯赛得尔,迭代矩阵。,第13页,定理4,n阶矩阵A是严格对角占优矩阵充分必要条件是,Jacobi迭代法迭代矩阵满足 B,J,1。,3,Jacobi迭代法和Gauss-Seidel迭代法收敛性,定理5,假如A是严格对角占优矩阵，那么Jacobi和GS,迭代法都收敛。,定理6,若A是n阶正定矩阵，那么G-S迭代法收敛。,定理3,n阶矩阵A是严格对角占优矩阵，则A非奇异，且,全部对角元 。,第14页,注意问题,（1）Jacobi迭代法和Gauss-Seidel迭代法迭代矩阵不一样：,B,J,=D,-1,(L+U),B,G-S,=(D-L),-1,U,（2）Jacobi迭代法和Gauss-Seidel迭代法收敛性没有必定,联络。,即当Gauss-Seidel法收敛时，Jacobi法可能不收,敛；而Jacobi法收敛时，Gauss-Seidel法也可能不收敛,（3）Jacobi迭代和Gauss-Seidel迭代特征方程：,第15页,Jacobi迭代：,Gauss-Seidel迭代：,第16页,用Jacobi迭代法求解收敛，,但用 Gauss-Seidel法不收敛。,B,J,特征值为0，0，0，,B,GS,特征值为0，2，2,（4）举例,：,用Jacobi迭代法求解不收敛，,但用 Gauss-Seidel法收敛。,第17页,系数矩阵A是正定矩阵，所以用 Gauss-Seidel法收敛。,线性方程组系数矩阵为,是严格对角占优，所以Jacobi和Gauss-Seidel迭代格式,均收敛。,第18页,（1）迭代,（2）加速,（7.7）,即,3,超松驰,迭代法（SOR法）,（Sequential Over-Relaxation),矩阵形式：,第19页,注：,1.称 为,超松弛,迭代矩阵。,2.称 为,松弛因子。,3.当 时，就是G-S,迭代法；当 时，称为低,松弛,迭代法；当 时，称为,超松弛,迭代法。,4.SOR法也称为,G-S,迭代法一个加速方法。,5.研究SOR法就是需要找到最正确,松弛因子，使得,迭代,过程收敛速度最快，即 。,6.在找最正确,松弛因子之前，先要处理 在什么范围内,取值，才能确保SOR法,收敛。,第20页,定理7,对Ax=b,设 ，SOR方,法收敛必要条件是,松驰因子 。,定理8,给定线性方程组Ax=b,假如A是对称正定矩,阵，且 ，则SOR方法收敛。,第21页,