4_YQJ_Ch2_4方组迭代Hh.ppt

1、2.4 解线性方程组的迭代法 ( Iterative Methods for Solving Linear Systems ),线性方程组Ax = b ，其中A为非奇异矩阵，对于工程技术中产生的大型稀疏矩阵方程组（A阶数很大，但零元素较多，例如 n104，由某些偏微分方程数值解所产生的线性方程组），利用迭代法求解比较合适，迭代法在计算机内存和运算两方面，通常可利用A中有大量零元素的特点。,解线性方程组的迭代法,思路:,将 改写为 等价形 ，进行迭代 。从初值 出发，得到序列 。,研究内容：, 如何建立迭代格式？ 收敛速度？ 向量序列的收敛条件？ 误差估计？,在用直接法解线性方程组时，要对系数矩

2、阵不断变换。如果方程组的阶数很高，则运算量将会很大并且大量占用计算机资源，因此对线性方程组 要求找寻更经济、适用的数值解法。,解线性方程组的迭代法,如果能将线性方程组(1)变换为,(2),显然，(1)式和(2)式同解，我们称(1)(2)等价。,对线性方程组(2)，采用以下步骤:,依此类推,这种方式就称为迭代法，以上过程称为迭代过程. 迭代法产生一个序列： 如果其极限存在，即 则称迭代法收敛，否则称为发散.,.(3),例 用迭代法求解方程组，误差不超过1e-4.,解 现将方程改写,或写为 x=BJ x+f 建立迭代公式：,任取初始值x(0)=(0,0,0)T，代入公式右边，,依此类推，得方程组满

3、足精度的解为x12：,x4 = 3.0241 1.9478 0.9205 d = 0.1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0006 0.9998 d = 0.0040 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004 x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004 x11 = 3.0000 2.0000

4、 1.0000 d = 1.7669e-004 x12= 3.0000 2.0000 1.0000 d = 3.0647e-005,精确解为,2.4.1 迭代法的一般形式及其收敛性,把矩阵 A 分裂为,则,方程组 (2.23) 与 原方程组 Ax = b 同解.,将（2.23）式写成迭代格式 上迭代过程称为迭代法，G 称为迭代矩阵。,给定初值x(0)，可得到向量序列,收敛定义：若存在常数向量 x* ,使 ， 则称迭代法收敛，否则,称其不收敛或发散。,问题：x* 是否为方程组 Ax = b 的解？,定理2.7* 任意给定初始向量 x（0），如果由逐次逼近法产生的向量序列收敛于向量 x*，那么，x

5、* 是方程组 x = Gx + d 的解.,证:,定理2.7 若有常数向量 x*，使对某种范数， 有 则必有,证 依据范数的等价定义，可设,即，有,故,定义 设方阵 A 的特征值是 , 称 为矩阵 A 的谱半径。,性质 谱半径的性质 （1）（特征值上界） 即A 的谱半径不超过A 的任何一种范数。 （2）如果A 为对称矩阵，则,迭代法收敛的条件,定理2.8 设线性方程组 x= Gx + d 有惟一解，那么，迭代法对任意初始向量 x收敛的充分必要条件是迭代矩阵 G 的谱半径 (G)1.,证:,因此,用若当标准形可证.,注:要检验一个矩阵的谱半径小于1，比较困难，所以，我们希望用别的办法判断收敛性.

6、,定理2.8* （迭代法收敛的充分条件） 若迭代法的迭代矩阵满足 | G | 1，那么， 迭代法收敛.,注:因为矩阵范数 都可以 直接用矩阵的元素计算，因此,用定理2.8*， 容易判别迭代法的收敛性。,定理2.9 (充分条件) 如果矩阵的某种范数|G| 1, 则迭代收敛，且有下列误差估计：,证明：(2),问题：如何判断可以终止迭代？（误差估计）,误差表达式及收敛速度。,停机准则。,(1),写成矩阵形式：,L,U,D,分裂 A = D+ L+U,拆分A为三个部分。,设线性方程组Ax = b的一般形式为,几种基本迭代法,令,2.4.2 Jacobi 迭代法 ( Jacobi Iterative M

7、ethods ),依此类推，线性方程组Ax = b可化为,对上式作迭代过程：,则转化为矩阵形式：,Jacobi 迭代矩阵,那么，原方程组与下面的迭代方程组同解：,D,L,U 的具体形式为,由定理2.8, 有 定理2.10 Jacobi 迭代法收敛的充要条件是(GJ) 1. 由定理2.9, 得到 定理2.11 若 | GJ | 1，则 Jacobi 迭代法收敛. (充分条件),Jacobi迭代法收敛的条件,注：为了得到更方便的收敛判别方法，先来讲一些预备知识。, 有关基本概念,严格对角占优矩阵与对角占优矩阵,定义1 设 A 是 n 阶方阵. 若 A 满足不等式,且至少有一个 i，使严格不等号成立

8、，则称 A 为（按行）对角占优矩阵.,若对所有的 i =1,2,n，都有严格不等号成立，称 A 为（按行）严格对角占优矩阵。,例：,A为按行按列严格对角占优阵；B为按行对角占优阵。,引理2.1 若 n 阶方阵 A 是主对角按行(或按列)严格占优 阵，则 A 非奇异。,证明 设 A 满足条件,因而，aii0, i =1,2,n，D = diag(aii) 非奇异。令 A = D + L + U = D I + D-1( L + U ) = D(I- G) 其中， G = - D -1( L + U ) ，由 A 满足的条件可知,依定理1.5，知 I- G 非奇异，故 A 也非奇异。,定理2.12

9、 若方程组 Ax=b 的系数阵 A 是主对角按行(或按列)严格占优阵，则用 Jacobi 迭代法求解必收敛。,证 若 A 是主对角按行(或按列)严格占优阵，则 D-1 = diag(aii-1) 存在。 假定 J-法不收敛，依定理2.8，迭代矩阵 GJ= - D-1( L + U ) 有一特征值 满足 |m|1，且有 det(m I - GJ) = 0 而 det(m I - GJ) = det(m I + D-1( L + U ) ) = detmD-1D+m-1 ( L + U ) = mn detD-1 det D+m-1 ( L + U ) (*) 由于 mn detD-1 0，又因

10、|m-1|1 ，所以， 当 A 是按行严格占优阵时，有,当 A 是按列严格占优阵时，有,即, 矩阵 D +m-1( L + U ) 是主对角按行(或按列)严格占优阵. 依引理2.1可知, det D +m-1( L + U ) 0, 于是 从 式 (*) 可知 det(m I - GJ) 0。 矛盾说明 J 法必收敛。,点击看式(*),det(m I -GJ) = det(m I + D-1( L + U ) ) = detmD-1D+m-1 ( L + U ) = mn detD-1 det D+m-1 ( L + U ) (*),例6 证明：用 Jacobi 迭代法求解下方程组必收敛, 并

11、求解, 要求 | xk- xk-1| 10-5.,解 迭代矩阵为,-(L+U),D-1,因 ,故 J-迭代法收敛.,矩阵形式迭代公式为,分量形式的迭代公式为,计算结果,见P38 表2-1.,计算式,例7 证明： 用 J-迭代法求解下方程组不收敛.,解 迭代矩阵为,其特征方程为,GJ 的特征值为因而, J-法不收敛.,例8 判别,下列方程组使用 J-迭代法求解是否收敛?,解 此方程组是严格按行对角占优的, 所以使用J-法收敛.,Algorithm: Jacobi Iterative Method Solve given an initial approximation . Input: the

12、number of equations and unknowns n; the matrix entries a ; the entries b ; the initial approximation X0 ; tolerance TOL; maximum number of iterations Mmax. Output: approximate solution X or a message of failure. Step 1 Set k = 1; Step 2 While ( k Mmax) do steps 3-6 Step 3 For i = 1, , n Set ; ( comp

13、ute xk ) Step 4 If then Output (X ); STOP; ( successful ) Step 5 For i = 1, , n Set X 0 = X ; ( update X0 ) Step 6 Set k +; Step 7 Output (Maximum number of iterations exceeded); STOP. ( unsuccessful ),What if aii = 0?,迭代过程中，A 的元素 不改变，故可以事先调整好 A 使得 aii 0，否则 A不可逆。,必须等x(k)完全计算 好了才能计算x(k+1)，因此 需要两组向量存储

14、。,A bit wasteful, isnt it?,分析Jacobi迭代法的迭代过程,将公式细化,2.2.3 Gauss - Seidel 迭代法, ,只存一组向量即可。,写成分量形式：,写成分量形式：,作 A 的另一个分裂：,G-S 迭代矩阵,Gauss - Seidel迭代的矩阵形式：,定理2.13 GS 迭代法收敛的充要条件是 (GG) 1. 定理2.14 若 | GG | 1，则 GS 迭代法收敛。 定理2.15 若方程组 Ax=b 的系数阵 A 是主对角按行(或列)严格占优阵，则用 GS 迭代法求解必收敛。 定理2.16 若方程组 Ax=b 的系数阵 A 是正定矩阵，则用 GS 迭

15、代法求解必收敛。,Gauss - Seidel迭代法收敛的条件,G-S迭代,Jacobi迭代、G-S迭代计算式：,例,用Gauss-Seidel迭代法求解补例.,从本例可以看出，Gauss-Seidel迭代法的 收敛速度比Jacobi迭代法要快。,通过迭代,至第7步得到满足精度的解x7 .,x1 =2.5000 2.0909 1.2273 d =3.4825 x2 =2.9773 2.0289 1.0041 d =0.5305 x3 =3.0098 1.9968 0.9959 d =0.0465 x4 =2.9998 1.9997 1.0002 d =0.0112 x5 =2.9998 2.0

16、001 1.0001 d =3.9735e-004 x6 =3.0000 2.0000 1.0000 d =1.9555e-004 x7 =3.0000 2.0000 1.0000 d =1.1576e-005,例 9:用 GS 和 Jacobi 迭代法求解例 6 中的方程组都收敛. 用GS法求解,说明这一结论. 要求 | xk- xk-1| 10-5.,解: GS 迭代矩阵为,迭代公式为,因为 , 所以 GS 法收敛.,因为 , 故方程组的近似解为,计算结果:,例 10:方程组用 Jacobi 迭代法求解例 7 不收敛,但用GS 法求解收敛. 验证此结论!,证 例7已经说明用J法不收敛.GS

17、 法的迭代矩阵为,Ggs的特征值为 0, -0.5, -0.5, r(Ggs)= 0.5 1 ,所以，GS 法收敛.,例 Jacobi 与 GS 迭代法求解都不收敛之例!,Jacobi 迭代法的迭代矩阵,GJ 的两个特征值是 -2.5, 2.5, 谱半径 2.5 大于1, J法不收敛. GS 法的迭代矩阵是,Ggs 的两个特征值是 0, 6.25, 谱半径 6.25 大于1, GS 法也不收敛.,GJ=- D-1(L+U),Ggs=-(D+L)-1U,(*),值得注意,若把式(*)中两个方程交换位置：,则它是主对角按行占优阵，用上两种迭代法求解它都将收敛 ！,注 随着方程组中方程或未知元的改变

18、，迭代方程的迭代矩阵的谱半径随之改变，因此，迭代法的收敛性也随之改变。从而可知，对于给定的方程组，若由其确定的迭代法不收敛，则可通过适当地改变方程组中方程或未知元的次序导出收敛的迭代格式。,例 方程组（1）用 GS迭代法求解不收敛， 方程组（2）用 GS迭代法求解收敛。,2.2.4 逐次超松驰迭代法 (SOR)迭代法 ( Successive Over Relaxation Method ),SOR是GS迭代法的一种加速方法，是解大型稀疏矩阵方程组的有效方法之一。它具有计算公式简单、程序设计容易、占用计算机内存较少等优点，但需要选择好的加速因子（最佳松驰因子）。 首先用GS法定义辅助量：,上式第一项看作校正量，x(k+1) 取x（k）与校正量的加权平均：,其中 (0)称为松驰因子。,SOR迭代的分量形式：,注：显然，当 =1，SOR方法即为GS迭代法。 SOR方法每迭代一次主要运算量是计算一次矩阵与向量的乘法。 当 1时，称为超松驰法；当1时，称为低松驰法。,SOR迭代的矩阵形式：,SOR 迭代矩阵,SOR迭代的矩阵形式：,SOR迭代法收敛的条件,定理2.17 SOR 迭代法收敛的充要条件是 (Gs) 1. 定理2.18 若 | Gs | 1，则 SOR 迭代法收敛。 定理2.19 SOR 迭代法收