数值分析第6章 解线性方程组迭代法

1、1 1 引言引言第第6 6章章 解线性代数方程组的迭代法解线性代数方程组的迭代法考虑线性方程组也就是 AX=b. (1.1)nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111 低阶稠密的线性方程组用直接法(如高斯消去法和三角分解法)。大型稀疏非带状的线性方程组(n很大,且零元素很多.如偏微方程数值解产生的线性方程组,n104)的求解问题？零元素多，适合用迭代法。我们将介绍迭代法的一般理论及雅可比迭代法、高斯塞德尔迭代法、超松弛迭代法，研究它们的收敛性。例例1 1 求解线性方程组(1.2) .361236,33114,2023832132132

2、1xxxxxxxxx记为Ax=b,即 .36332012361114238321 xxx 精确解x*=(3,2,1)T.改写(1.2)为(1.3) ).3636( ),334( ),2023(21121331111232811xxxxxxxxx或写为x=B0 x+f,即 .000123611338203211231261111148283321 xxx xxx任取初值,如x(0)=(0,0,0)T,代入(1.3)得到x(1)=(2.5,3,3)T.反复迭代(1.4) .12/)3636(,11/)334( ,8/)2023()(2)(1)1(3)(3)(1)1(2)(3)(2)1(1kkkkk

3、kkkkxxxxxxxxx即 x(k+1)=B0 x(k)+f， (k=0,1,2,)解。逐步逼近此方程的精确序列代法产生的向量从此例可以看出，由迭其中)()10()10()10()10(x.*,000187.0 ,)9998813.0 ,999838.1 ,000032.3(kTxxx. fBxxbAx 变形得到等价的一般地，由(1.5) * *,fBxxx则设有唯一解(1.6) ,)()1()0(fBxxxkk则可构造迭代序列又设任取初值.)6 . 1 (1) 1) )迭迭代代法法( (定定义义一阶定常迭代法近似解的方法称为逐步代入求，用公式对于方程组fBxx.,*,*)(lim)2()(

4、否则迭代法发散是解显然，则称此记为存在若xxx迭迭代代法法收收敛敛kk . )5 . 1 ()6 . 1 (*,)0()()1()()(BBxxkkkkk得则由引进误差向量 .lim0lim )(0 0kkkkB收敛： . ) )0 0( (kkBB满足什么条件下要研究 .)(的收敛性有以上讨论，需研究kx.lim), 2 , 1( lim ,),(,),( )()()(21)()(2)(1)()(xxxxnixxRxxxxRxxxxRxkkkikiknTnnTknkkknk，记为收敛于则称向量序列使若存在，设向量序列定定义义2 2.lim), 2 , 1,( lim )(,)( )()(AA

5、AAAAkkkijkijknnijnnkijknjiaaRaRa，记为收敛于则称，若设矩阵序列定定义义3 3.1|0,02,01 1222，考查其极限且，设矩阵序列kkkkkAAA例例2 2. 01limlimlim1kkkkkkkkk为任意一种向量范数。其中显然，|0,|x-|limlim )()(kkkkxxx.|0limlim 的任一算子范数为矩阵，其中。用矩阵算子范数来描述矩阵序列极限概念可以AAAAkkkk定定理理1 1. 0lim,0lim xAxAkknkkR定定理理2 2，证毕。时就证明了列元素极限均为零，当的第表示则，个坐标向量为第立，取反之，若定理的右边成立。所以就有定理的

6、右边成有，故对一切则若属范数有证明：对任一种矩阵从0lim, 2 , 1, 0lim. 0|lim,0|lim , 0lim . |x| |x|kkkjkkjkknkkkkkkAnjjAeAejxxARxAAAA. 1|B| )3(. 1)( )2(; 0lim ) 1 (: ,)( . )()()1(，使阵范数至少存在一种从属的矩的谱半径则下列三个条件等价设矩阵，其中矩阵的幂构成，即的收敛性，这种序列由有关的矩阵序列下面讨论一种与迭代法BBBBkknnkijnnkkkRbRBBfBxx定定理理3 3. 1)(), 1( 10lim0limBriJBikkkk).(|lim | , 1Bkkk

7、nnBRB则为任意一种矩阵范数，设定理4定理4的各种迭代法。就得到解阵，选取为迭代法的迭代矩阵，称其中代法从而可构造一阶定常迭也就是分裂矩阵。于是为的某种近似，称容易求解，一般选择为且使，为可选择的非奇异矩阵其中分裂为将的迭代法。立它为非奇异矩阵，下面建其中设有方程组bAxMAMIBbMfAMIAMMNMBbMNxMxbAxMAdMxMNMAAAbAxkk11111)()1(11.,)( , , fBxxfBxx迭代法及其收敛性. 1)()8 . 1 (1.8) (1.7) )0()()1(BxfBxxfBxx收敛迭代法则对任意初始向量及一阶定常迭代法设有方程组一个充分必要条件。下面给出迭代法

8、收敛的kk定理5定理5例3，P184例4，P185，则的某种算子范数如果有定常迭代法及一阶设有方程组迭代法收敛的充分条件充分条件。代法收敛的一个，下面利用范数判别迭由于1 ).8 . 1 ()7 . 1 ( |)( qBBBB) )定定理理6 6( (；，且，意）迭代法收敛，即对任（fBxxxxx*lim 1)()0(kk；）（)0()(* 2xxxxkkq；）（) 1()()(1* 3kkkqqxxxx.1* 4)0() 1 ()(xxxxqqkk）（ 定理6只给出迭代法收敛的一个充分条件，即使条件|B|1超松驰,1低松驰; 4)控制迭代终止的条件:例例3 3 用上述迭代法解线性代数方程组)

9、()()()1(1)()1(maxkkkikinikkxx Axbrxx或初值x(0)=0，写出计算格式。1111 43214111141111411114xxxxP195. 1)()5 . 3(3.5) (3.4) )0()() 1(BxfBxxfBxx收敛迭代法则对任意初始向量及一阶定常迭代法设有方程组kk定定理理4 41) Jacobi: BJ=D-1(L+U)，fJ=D-1b;2) Gauss-Seidel: BG=(D-L)-1U，fG= =(D-L)-1b;3) SOR: BSOR=(D-wL)-1(1-w)D+wU，fSOR= w(D-wL)-1b.迭代的统一格式：x(k+1)=

10、Bx(k)+f.)1()(1)(;)(, 1)();(1)(, 111UDLDLLULDGGULDJJDULDAAbAx，其中迭代法收敛其中塞德尔迭代法收敛高斯，其中雅可比迭代法收敛则非奇异非奇异设SORRnn推论推论例例5 5 考察用雅可比迭代法求解线性方程组(1.2) .361236,33114,20238321321321xxxxxxxxx.53,52 1221xxxx和. ;, ),2( 11221211否则为不可约矩阵为可约矩阵则称为方阵，使得如果存在置换阵设矩阵AAAAAAPPPA0 0定义4定义4TnnnR定义定义3 3 （1）按行严格对角占优：nijiiijjniaa1), 2

11、 , 1( |,|（2）按行弱对角占优：nijiiijjniaa1), 2 , 1( |,|上式至少有一个不等号严格成立。二、某些特殊方程组的迭代收敛性二、某些特殊方程组的迭代收敛性21212212110)(ddyyAAAbPxPAPPTTT.210123321310210321301212201 ),( ,4110140110410114 , 11122211DCBA，都不为零考察矩阵iiinnnnncbabacbacbacb例7例7，则有有精确解非奇异其中仍考虑*,xAbAxnnR定理定理6(6(对角占优定理)若矩阵A A按行(或列)严格对角占优，或按行(或列)弱对角占优且不可约；则矩阵A

12、 A非奇异。定理定理7 7 若矩阵A A按行(或列)严格对角占优,或按行(或列)弱对角占优不可约；则Jacobi迭代、Gauss-Seidel迭代都收敛。证明证明 若矩阵A按行严格对角占优，或按行(或列)弱对角占优不可约，则GS迭代收敛。假若不然，(BG)1，即迭代矩阵BG的某一特征值使得|1，并且. |)( |)( |)( | |0 ULDLDULDIBIG11.|)( | ,|)( | 001ULDLD又事实上矛盾从而非奇异可约或按行弱对角占优且不按行严格对角占优但是 . ., ,)( ,ULD. | )(nijijijijnijijijijiiaaaaa111111. )( ,nnnnn

13、nnnnnnnnnnnaaaaaaaaaaaaaaaaULD1211112111121222211111211类似地，若矩阵A按行严格对角占优，或按行(或列)弱对角占优不可约，则Jacobi迭代收敛。假若不然，(BJ)1，即迭代矩阵BJ的某一特征值使得|1，并且. | | )( | |0 ULDDULDIBIJ11.| | ,| 001ULDD又事实上矛盾从而非奇异可约或按行弱对角占优且不按行严格对角占优但是 . ., , ,ULD. | )(nijijijijnijijijijiiaaaaa111111. ,nnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaULD1211112

14、111121222211111211. 20 ,SOR 则松弛因子迭代收敛若定定理理8 8. |)1 ( | )det()1 ()det(| | )1det()det(| |)1()det(| )det(|)( , ,SOR 1112121nnnnnDDUDLDUDLDLLL于是特征值为迭代矩阵为设证证明明2.0 , 1)(|1 | SOR即迭代收敛，所以因为L定理定理9 9 对于线性方程组AxAx=b b，若A A为对称正定矩阵，则当02时，SOR迭代收敛. 证明证明 只需证明1（其中为L的任一特征值）.)()1( ,)1()( , ,1yLDyUDyyUDLDyyyL或于是的特征向量为相应于设,)()()1 ( ),(),(),(),)(1 ( ).(),(),(),(),( ),(),(iiiiTyLyyDyyUyyDyyLyLyyyyLyUyyLyyDy于是，则，记. 1)()1 (| 2222222. 0)2)(2()()1 (,2)(022yy,ULD定理定理10 10 对于线性代数方程组Ax=b， 若A按行(或列)严格对角占优，或按行(或