迭代法的收敛定理

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 method 二、二、jacobijacobi 迭代法和迭代法和gauss-seidelgauss-seidel迭代法的收敛条件迭代法的收敛条件 the condition for convergence of jacobi and the condition for convergence of jacobi and guassguass-seidel method-seidel method基本数学问题描述基本数

3、学问题描述迭代法的收敛性迭代法的收敛性，是指方程组是指方程组bax 从任意初始向量从任意初始向量x x(0)(0)出发，由迭代算法出发，由迭代算法fbxxkk )()1(算出向量序列算出向量序列,)1()()2()1( kkxxxx随着随着k k的增加而趋向于解向量的增加而趋向于解向量x x * *。 记各次记各次误差向量误差向量)()1(1)0(0kkxxxxxx the error vector 显然，迭代法的收敛性与误差向量序列显然，迭代法的收敛性与误差向量序列,10k 随着随着k k的增加而趋向于零向量是等价的。的增加而趋向于零向量是等价的。 由于精确解由于精确解x x * *自然满足

4、自然满足fbxx 因此有因此有 )()1(kkxxbxx 或或kkb 1 再递推出0 kkb the convergence of x x( (k k) ) b bk k 0 0 ( (k k ) ) 由由 x(k+1)=bx(k)+f 及及 x *=b x *+f可见可见 x(k) x* b k 0 ( (k k ) ) k+1 = x (k+1) - x *= b（x (k) - x *） = = b k+1（x(0) -x *） = b k+1 0 可推知可推知 11 01,maxknii njordanbbbbbb 利用矩阵的标准形，可以证明(第二章中的结论)其中叫做 的谱半径。若 的

5、特征值为 ，则(b)一、基本收敛定理一、基本收敛定理 theorem :for any initial value , theorem :for any initial value , the fundamental iterative method definedthe fundamental iterative method definedby by x x( (k k+1)+1)=bx=bx( (k k) )+f+f (k=0,1,2,) converges converges to the unique solution of x=bxto the unique solution of

6、 x=bx+f +f if only if only ifif nrx)0( )1b性质有关。性质有关。的的代矩阵代矩阵的取值无关，而只与迭的取值无关，而只与迭和和与与法收敛与否法收敛与否表明，线性方程组迭代表明，线性方程组迭代定理定理 1 . 3 )0(bfx 0k 1b1 x 3 .2 xkbxf迭代法收敛的充分条件 如果，则对任意初始向定量，迭代法必理收敛，且有)1()()(*1 kkkxxbbxx(1)(1)theorem 3.2: if |b|1 for any initial vector theorem 3.2: if |b|1 for any initial vector th

7、e sequence the sequence x x( (k k) ) converges and the estimate converges and the estimate (1) holds. (1) holds. theorem 3.2theorem 3.2( )(1)(0)*1kkbxxxxb进一步，我们可以推知进一步，我们可以推知： 式式(1)(1)说明，当说明，当|b|1 |b|1 且不接近且不接近1 1并且相邻两并且相邻两次迭代向量次迭代向量x x(k+1)(k+1) 与与 x x (k) (k)很接近时，则很接近时，则x x(k)(k)与精确解与精确解x x * *很接近

8、。因此，在实际计算中，用很接近。因此，在实际计算中，用| | x x (k+1) (k+1) - - x x (k)(k) | |作为迭代终止条件是合理的。作为迭代终止条件是合理的。 so possible stopping criteria is to iterate until so possible stopping criteria is to iterate until | | x x( (k+1k+1) ) - - x x( (k k) )| is smaller than given tolerance | is smaller than given tolerance . .反

9、复利用反复利用 | | x x (k+1) (k+1) - - x x* *|=|=|bxbx (k) (k)- - bxbx* *|=|=|b b( (x x (k) (k)- x- x* *)|)| b b.x.x (k) (k)- x- x* *,可以得到可以得到 | |x|x (k) (k)- x- x* *|b bk k xx(0)(0)- x- x* *，可见可见x x (0) (0)越接近越接近x x* *，序列，序列 x x (k) (k) 收敛越快，收敛速度收敛越快，收敛速度与初值与初值x x (0) (0)的选取有关。的选取有关。 另一方面，由于另一方面，由于( (b b)

10、 ) b b11，b b越小，说越小，说明明( (b b) ) 越小，序列越小，序列 x x (k) (k) 收敛越快。收敛越快。 the relationship of the rate of convergence tothe relationship of the rate of convergence tothe spectral radius of the iterative matrix b can the spectral radius of the iterative matrix b can be seen from theorem 3.2.be seen from theo

11、rem 3.2.收敛速度的概念收敛速度的概念下面我们给出收敛速度的概念下面我们给出收敛速度的概念： 定义定义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.证明证明: 显然显然)()()(*) 1(*

12、) 1()(kkkkxxxxxx 根据范数性质根据范数性质(3)(3)(三角不等式三角不等式) ) 可知可知yxyx yyxyyxx )(成立，也即成立，也即性质成立。性质成立。yxyx 因此因此成成立立)(*)1(*)(*)1(*)1()()()(kkkkkkxxxxxxxxxx -（2）the proof of theorem 3.2)1()()(*1 kkkxxbbxx)()()() 1(*) 1(*) 1(*)(* kkkkxxbbxbxfbxfbxxx显然显然根据范数性质根据范数性质(4)(4)(乘积不等式乘积不等式) ) 可知可知baab成成立立) 1(*) 1(*)(*)( kk

13、kxxbxxbxx)(*) 1(*1kkxxbxx 也即也即再将上两式联立，可以得出以下结果再将上两式联立，可以得出以下结果)1()()(*)1( kkkxxbbxx)(*kxx 再将此不等式两端同时减去再将此不等式两端同时减去 可得可得)(*)(*) 1(*)1 (kkkxxbbxxxx 由第由第2 2式可知式可知)(*)1(*)1()(kkkkxxxxxx 证明完毕证明完毕。 将定理将定理3.13.1和和3.23.2用于用于jacobijacobi迭代法及迭代法及seidelseidel迭代迭代法，则有法，则有1.() 1 ()1 ;jgaxbjacobi seidelbb解解线线性性方方

14、程程组组的的迭迭代代法法收收敛敛的的充充要要条条件件是是2. 1 1 jgaxbjacobi seidelbb解解线线性性方方程程组组的的迭迭代代法法收收敛敛的的充充分分条条件件是是。 uldbuldbgj11, 其中其中application to jacobi and guass-seidel method:necessary and sufficient conditionssufficient conditions 在一般情况下，计算矩阵的范数比计算谱半径省事，在一般情况下，计算矩阵的范数比计算谱半径省事，所以通常是利用定理所以通常是利用定理3.23.2进行判断。进行判断。 但定理但定

15、理3.23.2只是充分条件，所以即使判断失效，只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该使用定理迭代法仍可能收敛，这时就应该使用定理3.13.1判断。判断。 设有线性方程组设有线性方程组 x x= =bxbx+ +f f，其中，其中 218 . 03 . 00 . 09 . 0fb考察迭代法考察迭代法 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,

16、2 2=0.8,=0.8,即即( (b b) =0.91,) =0.91,由定由定理理3.13.1知本题迭代法收敛。知本题迭代法收敛。 54. 1, 1 . 1,02. 1, 2 . 121 fbbbb返回节返回节二、二、jacobijacobi 迭代法和迭代法和gauss-seidelgauss-seidel迭代法的收敛条件迭代法的收敛条件l引子引子l对角占优矩阵对角占优矩阵l实例实例l相关定理相关定理l定理定理3.33.3的证明的证明返回节返回节some convergence theorem of jacobi some convergence theorem of jacobi and

17、 guassand guass-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迭代法的收敛性，但其中只有定理迭代法的收敛性，但其中只有定理3.23.2对对jacobijacobi 迭代法使用比较方便，此外，对于大型方程迭代法使用比较方便，此外，对于大型方程组，要求出组，要求出g-sg-s迭代

18、矩阵迭代矩阵b bg g和和( (b bg g) )以及以及jacobijacobi 迭代迭代矩阵矩阵b bj j和和( (b bj j) )都不是容易的事。都不是容易的事。 这里介绍一些判定收敛的充分条件，它们是利这里介绍一些判定收敛的充分条件，它们是利用原方程组系数矩阵用原方程组系数矩阵a a和迭代矩阵和迭代矩阵b b的特殊性质建立的特殊性质建立的，很实用，用起来也很方便。这些判定定理也都的，很实用，用起来也很方便。这些判定定理也都是以定理是以定理3.13.1和定理和定理3.23.2为基础的。为基础的。 如果线性方程组如果线性方程组axax= =b b的系数矩阵的系数矩阵a a具有某种特殊

19、性质具有某种特殊性质（如对称正定、对角占优等），则可从（如对称正定、对角占优等），则可从a a本身直接得出某些本身直接得出某些迭代法收敛性结论。迭代法收敛性结论。 定义定义3.13.1 如果矩阵如果矩阵a a满足条件满足条件(1,2, )(2)iiijj iaain则称则称a a是是严格对角占优阵严格对角占优阵( (strictly diagonally dominant strictly diagonally dominant matrix)matrix)； 如果矩阵如果矩阵a a满足条件满足条件(1,2, )(3)iiijj iaain且其中至少有一个不等式严格成立，则称且其中至少有一个不

20、等式严格成立，则称a a是是弱对角占优阵弱对角占优阵weak diagonally dominant matrixweak diagonally dominant matrix 。例如例如 4121114238a 210011011b其中a a 是严格对角占优阵；是严格对角占优阵；b b 是弱对角占优阵。是弱对角占优阵。定理定理3.3 3.3 若若a a为为严格对角占优阵严格对角占优阵，则，则jacobijacobi 迭迭代法和代法和g-sg-s迭代法收敛。迭代法收敛。 定理定理3.43.4 若若a a为为对称正定阵对称正定阵，则，则g-sg-s迭代法收敛迭代法收敛。 theorem 3.3

21、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 matrix, then for any choices of x0, guass-seidel methods converge to the unique solution 0f ax=

22、b 在偏微分方程数值解中，有限差分往往导出对角占优的在偏微分方程数值解中，有限差分往往导出对角占优的线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，线性代数方程组，有限元法中的刚性矩阵往往是对称正定阵，因此这两个判断定理是很实用的。因此这两个判断定理是很实用的。 对于给定的线性方程组，借助于定理对于给定的线性方程组，借助于定理3.33.3和定理和定理3.43.4可以可以直接判断直接判断jacobijacobi 迭代法和迭代法和g-sg-s迭代法的收敛性。迭代法的收敛性。 但同时应当注意，迭代法收敛与否与方程组中方程排列但同时应当注意，迭代法收敛与否与方程组中方程排列顺序有关，如线性方程组

23、顺序有关，如线性方程组 22. 367. 233. 422. 143. 112. 005. 901.1058. 037.1269. 325. 1321321321xxxxxxxxx无法直接判断无法直接判断jacobijacobi 迭代法和迭代法和g-sg-s迭代法的收敛性，但如果迭代法的收敛性，但如果将方程组的次序修改为将方程组的次序修改为 58. 037.1269. 325. 122. 367. 233. 422. 143. 112. 005. 901.10321321321xxxxxxxxx 由于系数矩阵由于系数矩阵a a是严格对角占优阵，因此用是严格对角占优阵，因此用jacobijaco

24、bi 迭代迭代法和法和g-sg-s迭代法求解该方程组均收敛。迭代法求解该方程组均收敛。 定理定理3.33.3的证明的证明证 首先证明首先证明jacobijacobi 迭代的收敛性。由迭代的收敛性。由nnnjnnnnnnnnjabababfaaaaaaaaaaaauldb22211121222222111111121,000)(易求ijnjiiijnijaab,11max 由严格对角占优定义（由严格对角占优定义（定义定义3.13.1 ），得），得 b bj j 1, = detdet( ( ( (d-ld-l)-)-u u)=0 )=0 the proof of convergence for

25、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 contradictions. suppose | | |1,then |1,thenniaaaanijijijijnijjijii, 2 , 1,111, 1nnnnaaaaaaaaauld21112221111111)(返回章返回章 我们通过我们通过a a的严格对角占优性质去证明的严格对角占优性质去证明detdet( ( ( (d-d-l l)-)-u u)=0)=0的根的根 有性质有性质 | | |1 |1。用反证法：假设。用反证法：假设| | |1 |1，且由于，且由于a a的严格对角占优性质，有的严