第六章迭代法数值分析优秀课件.ppt

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