第六章-迭代法数值分析课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1.,引言,迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。,1.引言 迭代法的基本思想是构造一串收敛到解的,1,第六章-迭代法数值分析课件,2,第六章-迭代法数值分析课件,3,引入误差向量,则可得,由,问题是在什么条件下,所以,等价于,也即,引入误差向量则可得由问题是在什么条件下所以等价于也即,4,2.基本迭代法,设有,其中A为非奇异矩阵,将A分解成,其中M是可选择的非奇异矩阵,且使Mx=d容易求解,由此,原问题就可转化为等价方程,得:,可构造迭代法,2.基本迭代法设有其中A为非奇异矩阵将A分解成其中M是可选,5,Jacobi,迭代法,Jacobi 迭代法,6,第六章-迭代法数值分析课件,7,Jacobid迭代的矩阵形式,8,收敛与解,故如果序列收敛,则收敛到解.B 称迭代矩阵.,收敛与解故如果序列收敛,则收敛到解.B 称迭代矩阵.,9,第六章-迭代法数值分析课件,10,第六章-迭代法数值分析课件,11,高斯,塞德尔（,Gauss-Seidel),迭代法,高斯塞德尔（Gauss-Seidel)迭代法,12,第六章-迭代法数值分析课件,13,第六章-迭代法数值分析课件,14,用矩阵可表示为,:,移项得,又,所以,可逆,用矩阵可表示为:移项得又所以可逆,15,也即选取 M 为A的下三角部分，即 M=DL，N，,则 x=b可等价为（MN)x=b,联系上面已经得到的矩阵迭代形式,为统一起见,记:A=DLU,也即选取 M 为A的下三角部分，即 M=DL，N,16,等价为,其中,或,其中即为G-S迭代法的迭代矩阵,等价为其中或其中即为G-S迭代法的迭代矩阵,17,第六章-迭代法数值分析课件,18,第六章-迭代法数值分析课件,19,Gauss-Seidel,迭代法的计算过程如下：,Gauss-Seidel迭代法的计算过程如下：,20,松弛,(SOR),法,松弛(SOR)法,21,第六章-迭代法数值分析课件,22,SOR迭代法也可以看作是G-S迭代法的一种修正.,假设已知:,及,首先利用G-S迭代计算预测值,加权平均可得:,即得,再由,和,的前 i-1个分量,SOR迭代法也可以看作是G-S迭代法的一种修正.及首先利,23,第六章-迭代法数值分析课件,24,返回,返回,25,松弛法,计算过程如下,：,松弛法计算过程如下：,26,引入误差向量,则可得,由 等价于,问题是在什么条件下,所以,等价于,也即,3.迭代法的收敛性,作:,引入误差向量则可得由,27,第六章-迭代法数值分析课件,28,注:,其中 为矩阵的任一种算子范数 (p244,定理1,),注:,29,注,注,30,迭代法基本定理,迭代法基本定理,31,第六章-迭代法数值分析课件,32,矩阵的谱半径,定理2,矩阵的谱半径定理2,33,由此得,P248,的定理,5(,迭代法收敛的充分条件,),定理5 设有方程组 和其定常迭代法,如果B的某种算子范数,则:1.迭代法收敛即对任取的有,证明,由此得P248的定理5(迭代法收敛的充分条件)定理5,34,(P252定理8),(P252定理8),35,第六章-迭代法数值分析课件,36,第六章-迭代法数值分析课件,37,第六章-迭代法数值分析课件,38,(特殊方程组迭代法的收敛性P249),(特殊方程组迭代法的收敛性P249),39,第六章-迭代法数值分析课件,40,定理6:(对角占优定理 P250),如果矩阵A为严格对角占矩阵或为不可约弱对角占优矩阵,则A为非奇异矩阵,.,定理6:(对角占优定理 P250)如果矩阵A为,41,(P251定理7,9,10),例,同时G-S迭代法也收敛.,如1条件的矩阵，,证明,(P251定理7,9,10)例同时G-S迭代法也收敛.如1,42,第六章-迭代法数值分析课件,43,第六章-迭代法数值分析课件,44,特别,特别,45,第六章-迭代法数值分析课件,46,误差估计,误差估计,47,第六章-迭代法数值分析课件,48,第六章-迭代法数值分析课件,49,第六章-迭代法数值分析课件,50,证明：,2.,3.,1.,返回,证明：2.3.1.返回,51,注:,返回,注:返回,52,证明,:只证关于简单迭代法的两个，其余两个的证明类似.,(1)设,A,具有严格对角优势，以下证,(,B,J,)1,反证法，设,B,J,有特征值,|,|,1.,3.20,证明:只证关于简单迭代法的两个，其余两个的证明类似.反证,53,所以,D+L+U,也具有严格对角优势，所以|,D+L+U,|,0，,所以|,|,1不可能成立，所以|,|1，即,(,B,J,)1。,3.21,与 矛盾,所以D+L+U也具有严格对角优势，所以|D+L+U|,54,(2),A,不可约且具有对角优势，证,(,B,J,)1，,由定理有,A,非奇异，,又,（否则,A,必有一行元素全为零，与,A,非奇矛盾）,用反证法，设,B,J,有特征值,|,|,1.,同（1）有(3.20),(3.21)。,注意,D+L+U,中非零元素的位置与,A,中非零元素的位置完全,相同，而,A,不可约.所以必有,D+L+U,不可约.,返回,(2)A 不可约且具有对角优势，证(BJ),55,所以,D+L+U,有对角线优势，,所以|,D+L+U,|,0，,与（3.20）矛盾。,|,|,1不可能成立，,所以|,|1，即,(,B,J,)1.,所以 D+L+U有对角线优势，,56,