对于线性方程利用组迭代法数学解法

1、（五）（五） 迭代法的收敛条件迭代法的收敛条件（一）（一） 迭代法的一般形式迭代法的一般形式主要内容：主要内容：（二）（二） 雅可比（雅可比（JacobiJacobi）迭代法）迭代法（三）（三） 高斯高斯- -赛德尔赛德尔(Gsuss-Seidel)(Gsuss-Seidel)迭代法迭代法 （四）（四） 松弛法松弛法线性方程组的迭代解法 第三章（一）一般迭代形式（一）一般迭代形式 x=Mx+g x=Mx+g （3-2）TnnnijbbbaA),(,1代入迭代公式x x（k+1k+1）=Mx=Mx(k)(k)+g+g (k=0,1,2,-) (k=0,1,2,-) （3-3）1、对线性方程组 A

2、x=b （3-1）构造同解方程组产生向量序列 ，当k充分大时，以 作为方程组（3-1）的近似解-一般迭代法。 kxkx主要解决的问题：(1).在多种方法中，构造那种迭代格式的好？(2).他们的收敛性如何？(3).在收敛的条件下，最佳计算运行格式？ 计算近似值的迭代次数.(4).多种迭代格式误差的类比。2、向量序列、矩阵序列的收敛性、向量序列、矩阵序列的收敛性,如果定义定义3、1 设 为 中向量序列，( )kxnRnxR( )lim0kkxx(3-4)其中 为范数，则称 收敛于x，记为 ( )kx( )limkkxx( )lim0kkAA其中 为矩阵范数，则称 收敛于A，记为 ( )kA()li

3、mkkAA(3-5)定义定义3、2 设 为n阶方阵序列，A为n阶方阵, 如果 () kA）（因1322112222212111212111nnnnnnnnnnbxaxaxabxaxaxabxaxaxa系数矩阵A是非奇异的，不妨设将方程组（3-1）变为), 2 , 1( , 0niaiibi)迭代法二、雅可比(Jaco）（23112211223231212112121nnnnnnnnnnngxbxbxbxgxbxbxbxgxbxbx)., 2 , 1( ,), 2 , 1,( ,niabgnjijiaabiiiiiiijij其中gBxxggggbbbbbbBnnnnn,0002121221112

4、记：)0(x取初始向量 代入（3-2）右边有新向量。 ) 0 (x 如此下去，产生一个序列 ，满足为中向量序列 （3-33-3）上述过程给出的迭代法称雅可比迭代法（简单迭代法）。 ), 2 , 1 , 0( ,)()1(kgBxxkk kxnR), 2 , 1 , 0(),()(1)(1)()1(kbDxADIgBxxkkk其矩阵表示为),(),(1111111nnnnaadiagDaadiagD其中（3-4）例例2 2. .用雅可比迭代法求解方程组4258321072210321321321xxxxxxxxx10111 102 ,115A 解解：100001000010D1111100001

5、000010D1231231238322041133631236xxxxxxxxx3,2,1Tx 例：用Jacobi迭代法求解方程组，精确解为(1)( )( )123(1)( )( )213(1)( )( )3121(3220)81( 433)111( 6336)12kkkkkkkkkxxxxxxxxx(0)0,0,0Tx(10)3.0000321.9998380.999813x解：按迭代过程取初始向量，迭代10次得实际计算结果表明Jacobi迭代法收敛与精确解。迭代法Seidel)-(Gauss赛德尔-三、高斯要准确.因此,设想一旦当新分量已求出,马上)1( kx仔细研究Jacobi迭代法就

6、会发现在逐个求) 1( kix的分量时,当计算到 时,分都已求出,但没有被利用.直观上看,最新算出的分量可能) 1(1kx) 1(1) 1(2, kikxx量 比旧的分量迭代格式如下：SeidelGauss ) 43 (), 2 , 1, 0(,)(1)(1)(1) 1(11) 1(22) 1(11) 1(2)(2)(323) 1(12122) 1(21)(1)(313)(21211) 1(1niabxaxaxaaxbxaxaxaaxbxaxaxaaxiinknnnknknnnknknnkkkknnkkk就用它来代替,也就是在Jacobi迭代法中求,)(2)(1)1(1)1(2)1(1)1(k

7、kkikkkixxxxxx代替时用 迭代法。这就是SeidelGaussxki,)(1公式（3-4）表示为 ),2, 1 ,0( ,)()1()1(kgxUxLxkkk000,00011122121nnnnnbbbUbbbL其中)(,11111LDDLDDDLIUDULDL若从而得迭代式), 2 , 1 , 0( ,)()(1)(1)1(kbLDUxLDxkk上式中矩阵 为Gauss-Seidel迭代矩阵。ULDM1)(例例4 4 用用Gauss-SeidelGauss-Seidel迭代法求解方程组迭代法求解方程组4258321072210321321321xxxxxxxxx取初值 代入迭代式

8、有 Tx) 0 , 0 , 0 () 0 (6440.11)(510200. 9)2(1012000. 772101)2(1013) 1 (2) 1 (1) 1 (32)0(3) 1 (1) 1 (21)0(3)0(2) 1 (1bxxxbxxxbxxx解解：(6)(5)xBxb易知，方程组的精确解为 Tx)13,12,11(迭代结果（当迭代次数为迭代结果（当迭代次数为6 6次时）就赶上雅可比迭次时）就赶上雅可比迭代代9 9次的结果。（其它情况以后再讨论）次的结果。（其它情况以后再讨论）如此下去，(10.9999,11.9999,13.000)T123123123832204113363123

9、6xxxxxxxxx3,2,1Tx 例：用Gauss-Seidel迭代法求解方程组，精确解为。(1)( )( )123(1)(1)( )213(1)(1)(1)3121(3220)81( 433)111( 6336)12kkkkkkkkkxxxxxxxxx(0)0,0,0Tx(5)2.9998432.0000721.000061x解：其迭代过程取初始向量，迭代5次得与Jacobi迭代10次的精度相同。例例5. 用超松弛法求解方程组8 . 1202123232121xxxxxxxTx)1 , 1 , 1(,4.1)0(其中有迭代公式（3-5）有)8 . 1 (7 . 04 . 0), 2 , 1

10、 , 0(),(7 . 04 . 0)1 (7 . 04 . 0)1(2)(3)1(3)(3)1(1)(2)1(2)(3)(1)1(1kkkkkkkkkkxxxkxxxxxxx代入上式将Tx)1 ,1 ,1()0(解：解：56.1)18 .1 (7 .04 .01)11 (7 .04 .01)11 (7 .04 .0)1(3)1(2)1(1xxx继续下去，方程组有解 6001.1,3996.1,2000.1)9(3)9(2)9(1xxx与精确解 6 . 1, 4 . 1, 2 . 1321xxx比较，误差为 3)9(10210004.0 xx1.41231231234202422233xxxx

11、xxxxx 例：分别用Gauss-Seidel迭代法和SOR迭代法()求解方程组(0)1,1,1Tx取初始向量 当(1)( )71,2,3max10kkiiixx 时，停止迭代结论：1。Gauss-Seidel迭代法要迭代72次得2SOR迭代法( )，只须迭代25次得1.4(72)0.9999520.9999451.999995x1.4(25)0.9999940.9999982.000000 x适当选择，SOR迭代法具有明显的加速收敛效果。3GaussSeidel、迭代法2Jacobi、迭代法小结 4.松弛迭代法松弛迭代法(SOR)1、迭代法的一般形式 五五. .迭代法的收敛条件迭代法的收敛条

12、件 5 51 1 矩阵的谱半径矩阵的谱半径 称的特征值为阶矩阵设), 2 , 1(nininnRA 定义定义6（谱半径（谱半径)ini1max）（A的为矩阵A谱半径谱半径。之间的关系。下面讨论谱半径与范数值，则由，的特征的为对应于的任意特征值，为设AXAAXX 再由相容性条件有可得,AXX 0limkkA定理定理1 1 ： 设A为n阶方阵，则的充要条件为 1)(A0limkkA0limkkA由定义kkkAAA)()(0而由极限存在准则，有 0)(limkkA1)(A所以5 5、2 2迭代法的收敛条件迭代法的收敛条件证明：证明：若若必要性必要性, 定理定理2 2 对任意初始向量 和右边g，由迭代

13、 格式 产生向量序列 收敛条件是)0(x), 2 , 1 , 0(,)()1(kgMxxkk1)(M)(kx设存在n维向量x*，使得*)(limxxkk则x*满足 gMxx*由迭代公式 (0)*()kMxx证明：证明：()*kxx(1)*kM xgM xg(1)*()kM xx2(2)*()kMxx0)(lim)(lim*)(*)0(xxxxMkkkk于是因x0为任意n维向量，上式成立必须0limkkM。由定理知1)(M)(kx推论推论1 1、在定理、在定理2 2条件下，若条件下，若 ，则，则 收敛。收敛。推论推论2 2、松弛法收敛的必要条件为、松弛法收敛的必要条件为 。1M20 解方程组32

14、22122321321321xxxxxxxxx讨论雅可比迭代法与Gauss-Seidel迭代法的收敛性。 （1）由定理2知迭代法是收敛等价迭代矩阵 的谱半径1)(M,100010001,122111221DA例例5。2、 解解 ：00 01 0 0 ,22 0L 1JacobiBID A特征方程为.02211223BI1)(JB因此雅可比迭代法收敛。 022001 ,000U022101220 （2）由Gauss-Seidel迭代法， 111221DL1()GAUSSMDLU11()11021DL 100022110010210 022232Gauss-Seidel迭代法发散。12)(GAUS

15、SM1230,2,22023002IM特征方程为2(2)0. 为非严格对角占优阵，但为对称正定矩阵，210121012A4 .1例中例中系数矩阵松弛法收敛。试讨论用三种迭代法求解的收敛性。例、设有方程组，其中15 .05 .05 .015 .05 .05 .01A因为对称正定矩阵（各阶主子式大于零），由判别条件知Gauss-Seidel迭代法收敛， 松弛法收敛。但不是弱对角占优阵，则不能用判别条件断定迭代法收敛性。只能通过计算迭代矩阵为 2005 . 05 . 05 . 005 . 05 . 05 . 001ADIB解解：1,213211)(JB由定理知雅可比迭代法不收敛。. 0) 1()2(

16、)4/3(42222222113111111BI特征方程为、误差估计、误差估计 收敛于收敛于，则有误差估计，则有误差估计gMxxkk)()1()63(1)0()1(*)(xxMMxxkk定理定理、设有迭代格式、设有迭代格式)(, 1kxM 若注注由误差估计式（由误差估计式（3 36 6），据给定的），据给定的精度精度，可估计出迭代次数可估计出迭代次数： ）（73ln)1(ln)0()1(MxxMEk事实上事实上，1IM*(),IM xg*1()(*1)xIMg( )*(1)*()()kkxxMxgMxg( )*1(0)(1)()kkxxMIMxx( )*(0)(1)1(*3)1kkxxMxxM, 1xMxg(0)(1)()(*2)fxx定理、公式定理、公式( )*(0)(1)11kkxxMxxM(1)(0)(1)lnlnMxxkM(1)( )kkxMxg如在例中，若要求各分量的误差绝对值不超过，则由 4 .83 .82 .7.000,02 .02 .02 .001 .02 .01 .00)1()0(xxM4.8,4.0)0()1(xxM有代入（3-7）得932.124 . 0ln4 . 8)4 . 01 (10ln4k所需迭代1次才能保证各分量的误差绝对值不超过。 采用采用事后误差估计事后误差估计方法方法-用用相邻两次迭代值之差相邻两次迭代值之差作