num_3.3迭代法的收敛定理

1、第三章第三章 线性方程组迭代解法线性方程组迭代解法 3.3 迭代法的收敛定理迭代法的收敛定理3.3 迭代法的收敛性迭代法的收敛性l基本数学问题描述基本数学问题描述l一、基本收敛定理一、基本收敛定理l定理定理3.2的证明的证明l实例求解实例求解l二、二、Jacobi 迭代法和迭代法和Gauss-Seidel迭代法的收敛速度迭代法的收敛速度基本数学问题描述基本数学问题描述迭代法的收敛性迭代法的收敛性，是指方程组bAX 从任意初始向量X(0)出发，由迭代算法fBXXkk )()1(算出向量序列,)1()()2()1( kkXXXX随着k的增加而趋向于解向量X *。 记各次误差向量)()1(1)0(0

2、kkXXXXXX 显然，迭代法的收敛性迭代法的收敛性与误差向量序列误差向量序列,10k 随着k的增加而趋向于零向量是等价的。 由于精确解X *自然满足fBXX 因此有 )()1(kkXXBXX 或kkB 1 再递推出0 kkB 所以，迭代法收敛性迭代法收敛性与迭代矩阵的幂迭代矩阵的幂B k，随着k的增加而趋向于零矩阵是等价等价的。返回节返回节(谱半径有界谱半径有界) 设设 ,则对任一种算子范数则对任一种算子范数 ,均有均有n nAR|A( ) |AA定理定理1设设 , 则则 的充分条件是的充分条件是B的的谱半径谱半径( )1B0()kBk n nBR定理定理2前一章的内容：前一章的内容：一、基

3、本收敛定理一、基本收敛定理由由 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 利用矩阵的标准形，可以证明(前一章中的结论)其中叫做 的谱半径。若 的特征值为 ，则(B) (0)(1) 1 3.1kkXBXfXXBXfB 迭迭代代法法收收敛敛的的充充要要条条件件设设有有线线性性方方程程组组，则则对对于于任任意意的的初初始始向

4、向量量，迭迭代代法法收收敛敛的的充充分分必必要要条条件件是是。定定理理性质有关。性质有关。的的代矩阵代矩阵的取值无关，而只与迭的取值无关，而只与迭和和与与法收敛与否法收敛与否表明，线性方程组迭代表明，线性方程组迭代定理定理 1 . 3 )0(BfX1. 定理定理3.1为判断迭代法的收敛性提供为判断迭代法的收敛性提供 了强有力的手段：了强有力的手段： 注意是充分必要条件！注意是充分必要条件！2. 定理定理3.1的条件往往不易验证：的条件往往不易验证： 矩阵的谱半径不易求出！矩阵的谱半径不易求出！注：注：3. 利用谱半径的有界性可以给出另外一利用谱半径的有界性可以给出另外一 个条件较弱的结果：个条

5、件较弱的结果： 即定理即定理3.2 0k 1B1 X 3 2X. kBXf 迭迭代代法法收收敛敛的的充充分分条条件件 如如果果，则则对对任任意意初初始始向向定定量量，迭迭代代法法必必理理收收敛敛，且且有有)1()()(*1 kkkXXBBXX(1)(1)A矩矩阵阵 的的谱谱半半径径不不超超过过矩矩阵阵的的任任何何一一种种算算子子范范数数! !( )(1)(0)*1kkBXXXXB进一步，我们可以推知进一步，我们可以推知： 式式(1)(1)说明，当说明，当|B|1 且不接近且不接近1并且相邻两次并且相邻两次迭代向量迭代向量X(k+1) 与与 X (k)很接近时，则很接近时，则X(k)与精确解与精

6、确解X *很接近。因此，在实际计算中，用很接近。因此，在实际计算中，用| X (k+1) - X (k) |作为迭代终止条件是合理的。作为迭代终止条件是合理的。 反复利用反复利用 | X (k+1) - X*|=|BX (k)- BX*|=|B( (X (k)- X*) )| B.XX (k)- X*,可以得到可以得到 |X (k)- X*|Bk XX(0)- X*，可见可见X X (0)越接近越接近X*，序列，序列 X (k)收敛越快，收敛速度收敛越快，收敛速度与初值与初值X (0)的选取有关。的选取有关。 另一方面，由于另一方面，由于(B) B1，B越小，越小，说明说明(B) 越小，序列越

7、小，序列 X (k)收敛越快。收敛越快。 收敛速度的概念收敛速度的概念下面我们给出收敛速度的概念：下面我们给出收敛速度的概念： 定义定义3.1 R(B)= -ln(B)，称为迭代法的渐进，称为迭代法的渐进收敛速度。收敛速度。证明: 显然显然)()()(*) 1(*) 1()(kkkkXXXXXX 根据范数性质根据范数性质(3)(三角不等式三角不等式) 可知可知YXYX YYXYYXX )(成立，也即成立，也即性质成立。性质成立。YXYX 因此因此成成立立)(*)1(*)(*)1(*)1()()()(kkkkkkXXXXXXXXXX )()()()1(*)1(*)1(*)(* kkkkXXBBX

8、BXfBXfBXXX显然显然根据范数性质根据范数性质(4)(乘积不等式乘积不等式) 可知可知BAAB成成立立) 1(*) 1(*)(*)( kkkXXBXXBXX)(*) 1(*1kkXXBXX 也即也即再将上两式联立，可以得出以下结果再将上两式联立，可以得出以下结果)1()()(*)1( kkkXXBBXX)(*kXX 再将此不等式两端同时减去再将此不等式两端同时减去 可得可得)(*)(*) 1(*)1 (kkkXXBBXXXX 由第由第2式可知式可知)(*)1(*)1()(kkkkXXXXXX 证明完毕。证明完毕。 将将定理定理3.1和和3.2用于用于Jacobi迭代法及迭代法及Seide

9、l迭代法，迭代法，则有则有 ; 1)( 1)( .1 GJBBSeidelJacobibAX 收收敛敛的的充充要要条条件件是是迭迭代代法法的的解解线线性性方方程程组组 。收收敛敛的的充充分分条条件件是是迭迭代代法法的的解解线线性性方方程程组组 1 1 .2 GJBBSeidelJacobibAX ULDBULDBGJ11, 其中其中在一般情况下，在一般情况下，计算矩阵的范数计算矩阵的范数比比计算谱半径计算谱半径省事，省事，所以通常是利用所以通常是利用定理定理3.2进行判断。进行判断。 但但定理定理3.2只是充分条件，所以即使判断失效，只是充分条件，所以即使判断失效，迭代法仍可能收敛，这时就应该

10、使用迭代法仍可能收敛，这时就应该使用定理定理3.1判断。判断。 设有线性方程组设有线性方程组 X=BX+f，其中，其中 218 . 03 . 00 . 09 . 0fB考察迭代法考察迭代法 X (k+1)=B X(k)+f 的收敛性。的收敛性。例如例如解解： 由于由于 均大于均大于1，故，故定理定理3.2在此无法在此无法判断；判断； 但因为但因为 1 =0.9, 2=0.8,即即(B) =0.91,由由定理定理3.1知知本题迭代法收敛。本题迭代法收敛。 54. 1, 1 . 1,02. 1, 2 . 121 FBBBB返回节返回节二、二、Jacobi 迭代法和迭代法和Gauss-Seidel迭

11、代法的收敛速度迭代法的收敛速度l引子引子l对角占优矩阵对角占优矩阵l实例实例l相关定理相关定理l定理定理3.3的证明的证明返回节返回节引子引子 虽然利用虽然利用定理定理3.1和和定理定理3.2可以判定可以判定Jacobi 迭代迭代法和法和G-S迭代法的收敛性，但其中只有迭代法的收敛性，但其中只有定理定理3.2对对Jacobi 迭代法使用比较方便，此外，对于大型方程迭代法使用比较方便，此外，对于大型方程组，要求出组，要求出G-S迭代矩阵迭代矩阵BG和和(BG)以及以及Jacobi 迭代迭代矩阵矩阵BJ和和(BJ)都不是容易的事。都不是容易的事。 这里介绍一些判定收敛的充分条件这里介绍一些判定收敛

12、的充分条件，它们是利它们是利用原方程组系数矩阵用原方程组系数矩阵A和迭代矩阵和迭代矩阵B的特殊性质建立的特殊性质建立的，很实用，用起来也很方便。这些判定定理也都的，很实用，用起来也很方便。这些判定定理也都是以定理是以定理3.1和定理和定理3.2为基础的。为基础的。 如果线性方程组如果线性方程组AX=b的系数矩阵的系数矩阵A具有某种特殊性质具有某种特殊性质（如对称正定、对角占优等），则可从（如对称正定、对角占优等），则可从A本身直接得出某本身直接得出某些迭代法收敛性结论。些迭代法收敛性结论。 定义定义3.1 如果矩阵如果矩阵A满足条件满足条件(1,2, )(2)iiijj iaain则称则称A是

13、严格对角占优阵是严格对角占优阵； 如果矩阵如果矩阵A满足条件满足条件(1,2, )(3)iiijj iaain且其中至少有一个不等式严格成立，则称且其中至少有一个不等式严格成立，则称A是弱对角占优阵是弱对角占优阵。例如例如 4121114238A 210011011B其中其中A 是严格对角占优阵；是严格对角占优阵；B 是弱对角占优阵。是弱对角占优阵。定理定理3.3 若若A为严格对角占优阵，则为严格对角占优阵，则Jacobi 迭代法迭代法和和G-S迭代法收敛。迭代法收敛。 定理定理3.43.4 若若A为对称正定阵，则为对称正定阵，则G-S迭代法收敛迭代法收敛。 在偏微分方程数值解中，有限差分往往

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

15、. 112. 005. 901.1058. 037.1269. 325. 1321321321xxxxxxxxx无法直接判断无法直接判断Jacobi 迭代法和迭代法和G-S迭代法的收敛性，但如果将迭代法的收敛性，但如果将方程组的次序修改为方程组的次序修改为 58. 037.1269. 325. 122. 367. 233. 422. 143. 112. 005. 901.10321321321xxxxxxxxx 由于系数矩阵由于系数矩阵A是严格对角占优阵，因此用是严格对角占优阵，因此用Jacobi 迭代迭代法和法和G-S迭代法求解该方程组均收敛迭代法求解该方程组均收敛。 定理定理3.3的证明的

16、证明证证 首先证明首先证明Jacobi 迭代的收敛性。由迭代的收敛性。由nnnJnnnnnnnnJabababfaaaaaaaaaaaaULDB22211121222222111111121,000)(易求易求ijnjiiijniJaaB,11max 由严格对角占优定义（由严格对角占优定义（定义定义3.1 ），得），得 BJ =det( ( ( (D-L)-)-U)=0)=0 我们通过我们通过A A的严格对角占优性质去证明的严格对角占优性质去证明det( ( ( (D-L)-)-U)=0)=0的根的根 有性质有性质 | |1。用反证法：假设。用反证法：假设| |1，且由于，且由于A的的严格对角

17、占优性质，有严格对角占优性质，有 11111 2, ,niniiijijijjj ijj iaaaain 这说明矩阵这说明矩阵 11111121221112()nnnnaaaaaaDLUaaa 是严格对角占优阵，所以它是非奇异的，即是严格对角占优阵，所以它是非奇异的，即det( (D-L)-U) 0与特征值与特征值 满足满足det( (D-L)-U) =0 矛盾。矛盾。故故 1 即即(BG) 1，G-S迭代法收敛。迭代法收敛。定理得证定理得证。 返回章返回章（2）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的收敛性没有必然的联系：收敛性没有必然的联系：即当即当Gauss-

18、Seidel法收敛时，法收敛时，Jacobi法可能不收敛；法可能不收敛；而而Jacobi法收敛时，法收敛时， Gauss-Seidel法也可能不收敛。法也可能不收敛。（1）Jacobi迭代法和迭代法和Gauss-Seidel迭代法的迭代法的迭代矩阵不同：迭代矩阵不同：BJ =D-1(L+U), B G-S = (D-L) -1U12312312321121xxxxxxxxx例如用用Jacobi迭代法求解不收敛，但用迭代法求解不收敛，但用 Gauss-Seidel法收敛。法收敛。1231231232212223xxxxxxxxx用用Jacobi迭代法求解收敛，迭代法求解收敛，但用但用 Gauss-Seidel法不收敛。法不收敛。022022101 ,023220002JG SBB BJ的特征值为0，0，0， 而BGS的特征值为 0，2，2l 迭代法程序简单，对于许多问题，收敛较快。迭代法程序简单，对于许多问题，收敛较快。因而，有时能够解决一些高阶问题。因而，