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

§1.引言迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。§1.引言迭代法的基本思想是构造一串收敛到解的1第六章-迭代法数值分析课件2第六章-迭代法数值分析课件3引入误差向量则可得由问题是在什么条件下所以等价于也即引入误差向量则可得由问题是在什么条件下所以等价于也即4§2.基本迭代法设有其中A为非奇异矩阵将A分解成其中M是可选择的非奇异矩阵,且使Mx=d容易求解由此,原问题就可转化为等价方程得:可构造迭代法§2.基本迭代法设有其中A为非奇异矩阵将A分解成其中M是可选5Jacobi迭代法Jacobi迭代法6第六章-迭代法数值分析课件7

Jacobid迭代的矩阵形式

8收敛与解故如果序列收敛,则收敛到解.B称迭代矩阵.收敛与解故如果序列收敛,则收敛到解.B称迭代矩阵.9第六章-迭代法数值分析课件10第六章-迭代法数值分析课件11高斯—塞德尔（Gauss-Seidel)迭代法高斯—塞德尔（Gauss-Seidel)迭代法12第六章-迭代法数值分析课件13第六章-迭代法数值分析课件14用矩阵可表示为:移项得又所以可逆用矩阵可表示为:移项得又所以可逆15也即选取M为A的下三角部分，即M=D－L，Ａ＝Ｍ－N，则Ａx=b可等价为（M－N)x=b联系上面已经得到的矩阵迭代形式,为统一起见,记:A=D－L－U也即选取M为A的下三角部分，即M=D－L，Ａ＝Ｍ－N16等价为其中或其中Ｇ即为G-S迭代法的迭代矩阵等价为其中或其中Ｇ即为G-S迭代法的迭代矩阵17第六章-迭代法数值分析课件18第六章-迭代法数值分析课件19Gauss-Seidel迭代法的计算过程如下：Gauss-Seidel迭代法的计算过程如下：20松弛(SOR)法松弛(SOR)法21第六章-迭代法数值分析课件22SOR迭代法也可以看作是G-S迭代法的一种修正.假设已知:及首先利用G-S迭代计算预测值加权平均可得:即得再由和的前i-1个分量SOR迭代法也可以看作是G-S迭代法的一种修正.及首先利23第六章-迭代法数值分析课件24返回返回25松弛法计算过程如下：松弛法计算过程如下：26引入误差向量则可得由等价于问题是在什么条件下所以等价于也即§3.迭代法的收敛性作:引入误差向量则可得由27第六章-迭代法数值分析课件28

注:其中为矩阵的任一种算子范数(p244定理1)

注:29注注30迭代法基本定理迭代法基本定理31第六章-迭代法数值分析课件32矩阵的谱半径定理2矩阵的谱半径定理233由此得P248的定理5(迭代法收敛的充分条件)定理5设有方程组和其定常迭代法如果B的某种算子范数则:1.迭代法收敛．即对任取的有２．３．４．证明由此得P248的定理5(迭代法收敛的充分条件)定理534(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迭代法也收敛.如142第六章-迭代法数值分析课件43第六章-迭代法数值分析课件44特别特别45第六章-迭代法数值分析课件46误差估计误差估计47第六章-迭代法数值分析课件48第六章-迭代法数值分析课件49第六章-迭代法数值分析课件50证明：2.3.1.返回证明：2.3.1.返回51注:返回注:返回52证明:只证关于简单迭代法的两个，其余两个的证明类似.(1)设A具有严格对角优势，以下证ρ(BJ)<1反证法，设BJ有特征值μ,|μ|≥1.3.20证明:只证关于简单迭代法的两个，其余两个的证明类似.反证53所以μD+L+U也具有严格对角优势，所以|μD+L+U|≠0，所以|μ|≥1不可能成立，所以|μ|<1，即ρ(BJ)<1。3.21与矛盾所以μD+L+U也具有严格对角优势，所以|μD+L+U|≠54(2)A不可约且具有对角优势，证ρ(BJ)<1，由定理有A非奇异，又（否则A必有一行元素全为零，与A非奇矛盾）用反证法，设BJ有特征值μ,|μ|≥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，即ρ(BJ)<1.所以μD+L+U有对角线优势，56§1.引言迭代法的基本思想是构造一串收敛到解的序列，即建立一种从已有近似解计算新的近似解的规则。由不同的计算规则得到不同的迭代法，本章介绍单步定常线性迭代法。§1.引言迭代法的基本思想是构造一串收敛到解的57第六章-迭代法数值分析课件58第六章-迭代法数值分析课件59引入误差向量则可得由问题是在什么条件下所以等价于也即引入误差向量则可得由问题是在什么条件下所以等价于也即60§2.基本迭代法设有其中A为非奇异矩阵将A分解成其中M是可选择的非奇异矩阵,且使Mx=d容易求解由此,原问题就可转化为等价方程得:可构造迭代法§2.基本迭代法设有其中A为非奇异矩阵将A分解成其中M是可选61Jacobi迭代法Jacobi迭代法62第六章-迭代法数值分析课件63

Jacobid迭代的矩阵形式

64收敛与解故如果序列收敛,则收敛到解.B称迭代矩阵.收敛与解故如果序列收敛,则收敛到解.B称迭代矩阵.65第六章-迭代法数值分析课件66第六章-迭代法数值分析课件67高斯—塞德尔（Gauss-Seidel)迭代法高斯—塞德尔（Gauss-Seidel)迭代法68第六章-迭代法数值分析课件69第六章-迭代法数值分析课件70用矩阵可表示为:移项得又所以可逆用矩阵可表示为:移项得又所以可逆71也即选取M为A的下三角部分，即M=D－L，Ａ＝Ｍ－N，则Ａx=b可等价为（M－N)x=b联系上面已经得到的矩阵迭代形式,为统一起见,记:A=D－L－U也即选取M为A的下三角部分，即M=D－L，Ａ＝Ｍ－N72等价为其中或其中Ｇ即为G-S迭代法的迭代矩阵等价为其中或其中Ｇ即为G-S迭代法的迭代矩阵73第六章-迭代法数值分析课件74第六章-迭代法数值分析课件75Gauss-Seidel迭代法的计算过程如下：Gauss-Seidel迭代法的计算过程如下：76松弛(SOR)法松弛(SOR)法77第六章-迭代法数值分析课件78SOR迭代法也可以看作是G-S迭代法的一种修正.假设已知:及首先利用G-S迭代计算预测值加权平均可得:即得再由和的前i-1个分量SOR迭代法也可以看作是G-S迭代法的一种修正.及首先利79第六章-迭代法数值分析课件80返回返回81松弛法计算过程如下：松弛法计算过程如下：82引入误差向量则可得由等价于问题是在什么条件下所以等价于也即§3.迭代法的收敛性作:引入误差向量则可得由83第六章-迭代法数值分析课件84

注:其中为矩阵的任一种算子范数(p244定理1)

注:85注注86迭代法基本定理迭代法基本定理87第六章-迭代法数值分析课件88矩阵的谱半径定理2矩阵的谱半径定理289由此得P248的定理5(迭代法收敛的充分条件)定理5设有方程组和其定常迭代法如果B的某种算子范数则:1.迭代法收敛．即对任取的有２．３．４．证明由此得P248的定理5(迭代法收敛的充分条件)定理590(P252定理8)(P252定理8)91第六章-迭代法数值分析课件92第六章-迭代法数值分析课件93第六章-迭代法数值分析课件94(特殊方程组迭代法的收敛性P249)(特殊方程组迭代法的收敛性P249)95第六章-迭代法数值分析课件96定理6:(对角占优定理P250)如果矩阵A为严格对角占矩阵或为不可约弱对角占优矩阵,则A为非奇异矩阵.定理6:(对角占优定理P250)如果矩阵A为97(P251定理7,9,10)<例同时G-S迭代法也收敛.如1．条件的矩阵，证明(P251定理7,9,10)<例同时G-S迭代法也收敛.如198第六章-迭代法数值分析课件99第六章-迭代法数值分析课件100特别特别101第六章-迭代法数值分析课件102误差估计误差估计103第六章-迭代法数值分析课件104第六章-迭代法数值分析课件105第六章-迭代法数值分析课件106证明：2.3.1.返回证明：2.3.1.返回107注:返回注:返回10