3.3迭代法的收敛定理.ppt

《3.3迭代法的收敛定理.ppt》由会员分享，可在线阅读，更多相关《3.3迭代法的收敛定理.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第三章第三章 线性方程组迭代解法线性方程组迭代解法 Iterative techniques for Iterative techniques for solving linear systemsolving linear system 3.3 3.3 迭代法的收敛定理迭代法的收敛定理 The convergence theorem of iterative methodThe convergence theorem of iterative method3.3 3.3 迭代法的收敛性迭代法的收敛性l基本数学问题描述基本数学问题描述 The problemThe problem l一、基本收敛

2、定理一、基本收敛定理The convergence theorem of iterative methodThe convergence theorem of iterative methodThe Fundamental convergence theoremThe Fundamental convergence theoremThe Fundamental convergence theoremThe Fundamental convergence theorem 二、二、JacobiJacobi 迭代法和迭代法和Gauss-SeidelGauss-Seidel迭代法的收敛条件迭代法的收敛

3、条件 The condition for convergence ofThe condition for convergence of Jacobi Jacobi and and GuassGuass-Seidel method-Seidel method一、基本收敛定理一、基本收敛定理 The Fundamental convergence theoremThe Fundamental convergence theoremThe Fundamental convergence theoremThe Fundamental convergence theoremTheorem:for any

4、 initial value ,Theorem:for any initial value ,the fundamental iterative method definedthe fundamental iterative method definedby by x x(k k+1)+1)=BxBx(k k)+f+f (k=0,1,2,)converges converges to the unique solution of x=to the unique solution of x=BxBx+f+f if only if only ifif 收敛速度的概念收敛速度的概念下面我们给出收敛速

5、度的概念下面我们给出收敛速度的概念：定义定义3.1 3.1 R R(B B)=-)=-lnln(B B)，称为迭代法的渐称为迭代法的渐进收敛速度。进收敛速度。The rate of convergence Definition 3.1Definition 3.1 R R(B B)=-)=-lnln(B B)is called)is called by the rate of convergence.by the rate of convergence.将将定理定理3.13.1和和3.23.2用于用于JacobiJacobi迭代法及迭代法及SeidelSeidel迭代迭代法，则有法，则有Appl

6、ication to Jacobi and Guass-Seidel method:Necessary and sufficient conditionsSufficient conditions 在一般情况下，在一般情况下，计算矩阵的范数计算矩阵的范数比比计算谱半径计算谱半径省事，省事，所以通常是利用所以通常是利用定理定理3.23.2进行判断。进行判断。但但定理定理3.23.2只是充分条件，所以即使判断失效，只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用迭代法仍可能收敛，这时就应该使用定理定理3.13.1判断。判断。设有线性方程组设有线性方程组 X X=BXBX+f f，其

7、中其中 考察迭代法考察迭代法 X X(k k+1)+1)=B XB X(k k)+f f 的收敛性。的收敛性。Example:Example:解解：由于由于 均大于均大于1 1，故，故定理定理3.23.2在此无法判断；在此无法判断；但因为但因为 1 1=0.9,=0.9,2 2=0.8,=0.8,即即(B B)=0.91,)=0.91,由由定理定理3.13.1知本题迭代法收敛。知本题迭代法收敛。返回节返回节二、二、JacobiJacobi 迭代法和迭代法和Gauss-SeidelGauss-Seidel迭迭代法的收敛条件代法的收敛条件l引子引子l对角占优矩阵对角占优矩阵l实例实例l相关定理相关

8、定理l定理定理3.33.3的证明的证明返回节返回节Some convergence theorem of Some convergence theorem of Jacobi Jacobi and and GuassGuass-Seidel method for linear system-Seidel method for linear systemWith special matrix A With special matrix A 引子引子 虽然利用虽然利用定理定理3.13.1和和定理定理3.23.2可以判定可以判定JacobiJacobi 迭迭代法和代法和G-SG-S迭代法的收敛性，但

9、其中只有迭代法的收敛性，但其中只有定理定理3.23.2对对JacobiJacobi 迭代法使用比较方便，此外，对于大型方程迭代法使用比较方便，此外，对于大型方程组，要求出组，要求出G-SG-S迭代矩阵迭代矩阵B BG G和和(B BG G)以及以及JacobiJacobi 迭代迭代矩阵矩阵B BJ J和和(B BJ J)都不是容易的事。都不是容易的事。这里介绍一些判定收敛的充分条件，它们是利这里介绍一些判定收敛的充分条件，它们是利用原方程组系数矩阵用原方程组系数矩阵A A和迭代矩阵和迭代矩阵B B的特殊性质建立的特殊性质建立的，很实用，用起来也很方便。这些判定定理也都的，很实用，用起来也很方便

10、。这些判定定理也都是以定理是以定理3.13.1和定理和定理3.23.2为基础的。为基础的。对角占优矩阵对角占优矩阵diagonally dominant matrixdiagonally dominant matrix 如果线性方程组如果线性方程组AXAX=b b的系数矩阵的系数矩阵A A具有某种特殊性质具有某种特殊性质（如对称正定、对角占优等），则可从（如对称正定、对角占优等），则可从A A本身直接得出某些本身直接得出某些迭代法收敛性结论。迭代法收敛性结论。定义定义3.13.1 如果矩阵如果矩阵A A满足条件满足条件则称则称A A是是严格对角占优阵严格对角占优阵(strictly diago

11、nally dominant strictly diagonally dominant matrix)matrix)；如果矩阵如果矩阵A A满足条件满足条件且其中至少有一个不等式严格成立，则称且其中至少有一个不等式严格成立，则称A A是是弱对角占优阵弱对角占优阵weak diagonally dominant matrixweak diagonally dominant matrix。实例(Example)例如例如其中A A 是严格对角占优阵；是严格对角占优阵；B B 是弱对角占优阵。是弱对角占优阵。定理定理3.3 3.3 若若A A为为严格对角占优阵严格对角占优阵，则，则JacobiJaco

12、bi 迭迭代法和代法和G-SG-S迭代法收敛。迭代法收敛。定理定理3.43.4 若若A A为为对称正定阵对称正定阵，则，则G-SG-S迭代法收敛迭代法收敛。相关定理Theorem 3.3 If A is strictly diagonally dominant matrix,thenFor any choices of x0,both the Jacobi and Guass-Seidel methods converge to the unique solution 0f Ax=bTheorem 3.4 If A is symmetry and positive definitive mat

13、rix,then for any choices of x0,Guass-Seidel methods converge to the unique solution 0f Ax=b 在偏微分方程数值解中，有限差分往往导出对角占优的在偏微分方程数值解中，有限差分往往导出对角占优的线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，因此这两个判断定理是很实用的。因此这两个判断定理是很实用的。对于给定的线性方程组，借助于对于给定的线性方程组，借助于定理定理3.33.3和定理和定理3.43.4可以可以直接判断直接判断JacobiJacobi 迭

14、代法和迭代法和G-SG-S迭代法的收敛性。迭代法的收敛性。但同时应当注意，迭代法收敛与否与方程组中方程排列但同时应当注意，迭代法收敛与否与方程组中方程排列顺序有关，如线性方程组顺序有关，如线性方程组 无法直接判断无法直接判断JacobiJacobi 迭代法和迭代法和G-SG-S迭代法的收敛性，但如果迭代法的收敛性，但如果将方程组的次序修改为将方程组的次序修改为 由于系数矩阵由于系数矩阵A A是严格对角占优阵，因此用是严格对角占优阵，因此用JacobiJacobi 迭代迭代法和法和G-SG-S迭代法求解该方程组均收敛。迭代法求解该方程组均收敛。定理定理3.33.3的证明的证明证 首先证明首先证明

15、JacobiJacobi 迭代的收敛性。由迭代的收敛性。由易求 由严格对角占优定义（由严格对角占优定义（定义定义3.13.1 ），得），得 B BJ J 1,=detdet(D-LD-L)-)-U U)=0)=0 The proof of convergence for G-S method Considering the eigenvalues of iterative matrix B BG G=(D-L)-1U In order to prove the eignevalues of BG satisfying that|1We can use a method by Contradic

16、tions.Suppose|1,then|1,then返回章返回章 我们通过我们通过A A的严格对角占优性质去证明的严格对角占优性质去证明detdet(D-D-L L)-)-U U)=0)=0的根的根 有性质有性质|1|1。用反证法：假设用反证法：假设|1|1，且由于且由于A A的严格对角占优性质，有的严格对角占优性质，有 thereforeis strictly diagonally dominant and (D-L)-U is nonsingular.Then|1 holds.是严格对角占优阵，所以它是非奇异的，即是严格对角占优阵，所以它是非奇异的，即detdet(D-L)-U)(D-L

17、)-U)0 0与特征值与特征值 满足满足detdet(D-L)-(D-L)-U)U)=0=0 矛盾。矛盾。故故|1|1即即(B BG G)1)1，G-SG-S迭代法收敛。迭代法收敛。定理得证定理得证。l对于对称正定矩阵对于对称正定矩阵A A，Jacobi Jacobi迭代法不一定收迭代法不一定收敛。敛。l一般来说，可能一般来说，可能JacobiJacobi迭代法和迭代法和GuassGuass-Seidel-Seidel迭代法都收敛，也可能都是都不收敛，或一个迭代法都收敛，也可能都是都不收敛，或一个收敛，一个不收敛，在两者都收敛的情况下，收敛，一个不收敛，在两者都收敛的情况下，收敛速度也不一定。

18、收敛速度也不一定。p76p76例例3.23.2For a symmetry and positive definite A,Jacobi method mayNot be convergent necessarily.l 迭代法程序简单，对于许多问题，收敛迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。较快。因而，有时能够解决一些高阶问题。但应注意，对于某些问题，迭代法可能发但应注意，对于某些问题，迭代法可能发散或收敛很慢，以致失去使用价值。这种散或收敛很慢，以致失去使用价值。这种情况下，仍以采用直接法为宜。情况下，仍以采用直接法为宜。l只要断定系数矩阵满足收敛条件，尽管多只要断定系数矩阵满足收敛条件，尽管多次迭代计算工作量大一些，却能达到预定次迭代计算工作量大一些，却能达到预定精度。精度。返回节返回节