高斯赛得尔迭代法.ppt

《高斯赛得尔迭代法.ppt》由会员分享，可在线阅读，更多相关《高斯赛得尔迭代法.ppt（32页珍藏版）》请在第壹文秘上搜索。

1、1解线性方程组的迭代法解线性方程组的迭代法3.3 高斯高斯-赛得尔迭代法赛得尔迭代法迭代公式迭代公式(3-10,即即Jacobi迭代迭代)用方程组表示为用方程组表示为)123(1)knx(1)2kx(1)1kx()()()()12213 311111kkkknnnnb xb xbxb xg()()()()21 123 321122kkkknnnnb xb xbxb xg()()()()1 1223 311kkkknnnnnnnb xb xb xbxg,ijijiiaba(,1,2,),ij i jniiiibga(1,2,).in其中其中2解线性方程组的迭代法解线性方程组的迭代法因此，在因此，

2、在Jacobi迭代法的计算过程中，迭代法的计算过程中，要同时保留要同时保留两个近似解向量两个近似解向量()kx和和(1).kx)133(1)2kx(1)knx()()()()12213311111kkkknnnnb xb xbxb xg(1)()()()21 123321122kkkknnnnb xb xbxb xg(1)1kx(1)(1)(1)(1)1 1223311kkkknnnnnnnb xb xb xbxg在迭代收敛时在迭代收敛时,因因比老值比老值更准确些更准确些,求出新值求出新值(1)kix()kix(1)kix后用后用(1)kix代替前一次的代替前一次的()kix继续进行计算继续进

3、行计算,这种充分利用新值这种充分利用新值建立起来的迭代公式建立起来的迭代公式p43解线性方程组的迭代法解线性方程组的迭代法即每算出新近似解的一个分量即每算出新近似解的一个分量(1),kix再算下一个再算下一个分量分量(1)1kix时时，用新分量用新分量(1)kix代替老分量代替老分量)(kix进行计算进行计算。这样，在整个计算过程中这样，在整个计算过程中，只需用只需用n个个单元存储近似解分量单元存储近似解分量。选初始向量选初始向量,)0(x用迭代公式用迭代公式（3-13）产生近产生近似解序列似解序列,)(kx这种方法叫这种方法叫Gauss-Seidel迭代法迭代法，式式（3-13）为为 Gau

4、ss-Seidel迭代法的计算公式迭代法的计算公式。4解线性方程组的迭代法解线性方程组的迭代法公式公式(3-13)用矩阵表示为用矩阵表示为)1(kxgxUxLkk)()1()143(其中其中21313212310000nnnnnbLbbbbbb05解线性方程组的迭代法解线性方程组的迭代法0000122311312nnnnbbbbbbU0移项可得移项可得(1)()kIL xgxUk)()1(kxgxUxLkk)()1()143(6解线性方程组的迭代法解线性方程组的迭代法因为因为,1 LI故故1)(LI存在存在,上式可改写成上式可改写成1()1()(),kILUxILg)1(kx如果用矩阵如果用矩

5、阵A来表示来表示,记记000001321323121nnnnnaaaaaaaL0(1)()kIL xgxUk)(3-15)7解线性方程组的迭代法解线性方程组的迭代法000122311312nnnnaaaaaaU0则则,1LDLUDU1于是于是)(1LDDLDDD11LI)163(8解线性方程组的迭代法解线性方程组的迭代法将式将式(3-16)代入式代入式(3-15)得得(1)kx1()1()()kDLUxDLb)173(这是这是Gauss-Seidel迭代公式的矩阵表示迭代公式的矩阵表示,式中矩阵式中矩阵1()MDLU为迭代矩阵为迭代矩阵。gLIxULIk1)(1)()()1(kx)(1LDDL

6、DDD11LI(3-15)(3-16),1LDLUDU19解线性方程组的迭代法解线性方程组的迭代法算法算法3.23.21.输入输入(0)(0)(0)1(,)nxxx),(1nbbb(),ijAa维数维数n,最大容许迭代次数最大容许迭代次数N。2.置置 k=11x112)0(11/)(axabnjjj 3.计算计算:ix1(0)11()/iniijjijjiijj iba xa xa)1,3,2(ninxnnnjjnjnaxab/)(1110解线性方程组的迭代法解线性方程组的迭代法4.若若(0),xx输出输出),(1nxxx停机停机;否则转否则转5 5。5.若若kN,置置)0(iixx,1kk(

7、1,2,),in转转3;否则输出失败信息否则输出失败信息,停机停机。定理定理 若方程组若方程组Axb的系数矩阵的系数矩阵A是对称正定矩阵是对称正定矩阵,则则 Gauss-Seidel迭代法收敛迭代法收敛.11解线性方程组的迭代法解线性方程组的迭代法例例 用用Gauss-Seidel迭代法求线性方程组迭代法求线性方程组解解 由由Jacobi迭代法的计算公式迭代法的计算公式),103(b有有123542,xxx12310283,xxx12310272,xxx(1)3kx(1)2kx(1)1kx()()230.10.27.2kkxx()()130.10.28.3kkxx()()120.20.28.4

8、kkxx1230.10.27.2xxx2130.10.28.3xxx3120.20.28.4xxx12解线性方程组的迭代法解线性方程组的迭代法用用Gauss-Seidel迭代法解例迭代法解例1。仍取仍取,)0,0,0()0(Tx按式按式(3-13)计算得计算得0200.7)1(1x(0)(0)231(272)10 xx72101)1(2x)830200.7(101(1)(0)131(283)10 xx0020.9(1)3kx(1)2kx(1)1kx()()230.10.27.2kkxx(1)()130.10.28.3kkxx(1)(1)120.20.28.4kkxx(1)3kx(1)2kx(1

9、)1kx()()230.10.27.2kkxx()()130.10.28.3kkxx()()120.20.28.4kkxxJacobi迭代法迭代法13解线性方程组的迭代法解线性方程组的迭代法)420020.90200.7(51(1)(1)121(42)5xx)1(3x0644.11如此计算下去如此计算下去,计算结果见表计算结果见表3-23-2。14解线性方程组的迭代法解线性方程组的迭代法表表 3-2k01234560.000 07.200 010.430 810.931 310.991 310.998 910.999 90.000 09.020 011.671 911.957 211.994

10、711.999 311.999 90.000 011.644 012.820 512.977 812.997 212.999 613.000 0()1kx)(3kx)(2kx15解线性方程组的迭代法解线性方程组的迭代法计算结果表明计算结果表明,用用Gauss-Seidel迭代法求解例迭代法求解例1中中的方程组比的方程组比Jacobi迭代法效果好迭代法效果好,迭代迭代5次次所得到的结果与例所得到的结果与例1中迭代中迭代9次所得到的结果相仿。次所得到的结果相仿。事实上事实上,对有些问题对有些问题Gauss-Seidel迭代法确实比迭代法确实比Jacobi迭代法收敛得快迭代法收敛得快,但也有但也有G

11、auss-Seidel迭迭代比代比Jacobi迭代收敛得慢迭代收敛得慢,甚至还有甚至还有Jacobi迭代迭代收敛收敛,Gauss-Seidel迭代发散的情形。迭代发散的情形。16解线性方程组的迭代法解线性方程组的迭代法3.4 松弛法松弛法为了加速迭代过程的收敛为了加速迭代过程的收敛,我们通过引入参数我们通过引入参数,在在Gauss-Seidel迭代的基上得到一种新的迭代法迭代的基上得到一种新的迭代法.记记Tnxxxx),(21)()1(kkxx其中其中)1(kx由式由式(3-13)(即高斯即高斯-赛德尔迭代公式赛德尔迭代公式)算出算出。于是有于是有111)()()1(ijnijkiikjijk

12、jijxgxbxbix1(1)()()111()inkkkiijjijjijj iiiba xa xxa ix17解线性方程组的迭代法解线性方程组的迭代法1(1)()()111()inkkkiijjijjijj iiiba xa xxa 若将若将x看作修正项看作修正项,则则Gauss-Seidel迭代的第迭代的第k次次近似解近似解)(kx以此项修正后得到新的近似解以此项修正后得到新的近似解)1(kx().kxx 松弛法松弛法是将是将x乘上一个参数因子乘上一个参数因子作为修正项而得到新的近似解作为修正项而得到新的近似解,(3 18)(1,2,)inix18解线性方程组的迭代法解线性方程组的迭代法

13、其具体公式为其具体公式为)1(kxxxk)(1)()kkiiixxx 1()(1)()11(1)()inkkkiiijjijjjj iiixba xa xa(1,2,)(3 19)in即即1()(1)()()111()inkkkkiiijjijjijj iiixba xa xxa 按式按式(3-19)计算方程组计算方程组(3-1)的近似解序列的方法称为的近似解序列的方法称为松弛法松弛法,称为称为松弛因子松弛因子。19解线性方程组的迭代法解线性方程组的迭代法11算法算法3.33.31.输入输入),(ijaA),(21nbbbb),()0()0(1)0(nxxx参数参数,误差限误差限,最大容许迭代

14、次数最大容许迭代次数N.1.k 2.2.置置3.3.计算计算当当时称为时称为低松弛低松弛,1时是时是Gauss-Seidel迭代迭代,时称为时称为超松弛超松弛,简称简称SOR法法(Successive Over-Relaxation).20解线性方程组的迭代法解线性方程组的迭代法(0)(0)111112(1)()/njjjxbaxa。否则转停机输出若5,),(,.41)0(nxxxxx(0)5.,1,(1,2,),3iikNkk xxin 若置转；1(0)(0)11(1)()/iniiijjijjiijjixba xa xa 1(0)1(1)()/nnnnjjnnjxba xa(2,1)in1

15、x ix nx否则输出失败信息，停机。21解线性方程组的迭代法解线性方程组的迭代法(0)1.4,(1,1,1),Tx2321.8xx12320 xxx1221xx(1)1kx(1)3kx(1)2kx()10.4kx()20.4kx()30.4kx例例2 2 取取用超松弛法求解方程组用超松弛法求解方程组解解:由迭代公式由迭代公式(3-19),(3-19),有有1(1)()(1)()11(1)()inkkkkiiiijjijjjj iiixxba xa xa(3 19)(1,2,)in()20.7(1)kx(1)()130.7()kkxx(1)20.7(1.8)kx22解线性方程组的迭代法解线性方

16、程组的迭代法(0)(1,1,1)Tx如此继续下去，计算结果如表如此继续下去，计算结果如表3-33-3：0.40.7(1 1)(1)3x0.40.7(1 1)(1)1x1(1)2x11.560.40.7(1.81)(1)1kx(1)3kx(1)2kx()()120.40.7(1)kkxx()(1)()2130.40.7()kkkxxx()(1)320.40.7(1.8)kkxx将将代入上式得代入上式得23解线性方程组的迭代法解线性方程组的迭代法k01234567891.000 01.000 01.000 01.274 41.218 01.202 31.193 21.205 11.199 91.200 01.000 01.000 01.392 01.468 21.413 61.391 61.403 41.402 71.400 01.399 61.000 01.560 01.618 41.640 41.593 41.606 81.600 71.601 61.599 41.600 1)(1kx)(2kx)(3kx24解线性方程组的迭代法解线性方程组的迭代法所以，方程组有解所以，方程组有解,20