章 線性方程組的迭代解法

1、第14章 線性方程組的迭代解法Jocobi迭代法 Jacobi迭代算法1. 輸入變量個(gè)數(shù)n、初值向量x（0）、迭代精度eps、系數(shù)矩陣A、常數(shù)項(xiàng)b 和迭代最大次數(shù)nmax2 For i=1,2,n如果|aii|eps1,則輸出“迭代失敗”提示并終止3. Bj E-D-1A4. gj D-1b5. For k=1,2,nmaxx Bj.x0+ gj 如果|x-x0|eps ,輸出迭代失敗，終止。 Jacobi 迭代法程序Cleara,b,x;nmax=500;n=Input“線性方程組階數(shù)n=”;a=Input系數(shù)矩陣A=；b=Input常數(shù)項(xiàng)b=；x0=Input輸入迭代初值向量x0；eps1

2、=0.000001;eps=Input輸入精度控制eps=；DoIfAbsai,ieps1,t1=1;Return,t1=0,i,1,n;Ift1=1,PrintJacobi迭代法失效, d=DiagonalMatrixTableai,i,i,1,n; d1=Inversed; bj=IdentityMatrixn-d1.a; gj=d1.b; Dox=bj.x0+gj; err=MaxAbsx-x0; Printx=,x/N, i=,i, err=,err/N; IfNerr=eps,Print迭代失敗 說(shuō)明：本程序用于求線性方程組Ax=b的解。程序執(zhí)行后，先通過(guò)鍵盤輸入線性方程組階數(shù)n、系

3、數(shù)矩陣A、常數(shù)項(xiàng)b、迭代初值向量x0和輸入精度控制eps，程序即可給出每次迭代的次數(shù)和對(duì)應(yīng)的迭代向量序列x(K),其中最后輸出的結(jié)果即為所求的根。如果迭代超出500次還沒(méi)有求出滿足精度的根則輸出迭代失敗提示，如果出現(xiàn)主對(duì)角線元素aii=0給出Jacobi迭代法失效提示。程序中變量說(shuō)明：x0：存放初始向量和迭代過(guò)程中的向量x（k）x: 存放迭代過(guò)程中的向量x（k+1）nmax:存放迭代允許的最大次數(shù)err：存放誤差|x-x0|t1：臨時(shí)變量注：迭代最大次數(shù)可以修改為其他數(shù)字。例題與實(shí)驗(yàn)例1 用Jacobi 迭代法解如下線性方程組 5x1+2x2+3x3= -12 -x1+4x2+2x3= 20

4、2x1-3x2+10x3= 3要求誤差|x(k+1)-x(k)|10-4，并用取不同初值的方法實(shí)驗(yàn)觀察迭代收斂的情況。解：執(zhí)行Jacobi迭代法程序后在輸入的4個(gè)窗口中按提示分別輸入3，5, 2, 1, -1, 4, 2, 2, -3, 10，-12, 20, 3，0, 0, 0，0.0001每次輸入后用鼠標(biāo)點(diǎn)擊窗口的“OK”按扭，得如下輸出結(jié)果。 x=-2.4, 5., 0.3 i=1 err=5.x=-4.46, 4.25, 2.28 i=2 err=2.06x=-4.556, 2.745, 2.467 i=3 err=1.505x=-3.9914, 2.6275, 2.0347 i=4

5、err=0.5646x=-3.85794, 2.9848, 1.88653 i=5 err=0.3573x=-3.97123, 3.09225, 1.96703 i=6 err=0.113286x=-4.03031, 3.02368, 2.02192 i=7 err=0.0685705x=-4.01386, 2.98146, 2.01316 i=8 err=0.042216x=-3.99522, 2.98995, 1.99721 i=9 err=0.0186374x=-3.99542, 3.00259, 1.99603 i=10 err=0.0126367x=-4.00024, 3.00313

6、, 1.99986 i=11 err=0.0048186x=-4.00122, 3.00001, 2.00099 i=12 err=0.00312067x=-4.0002, 2.9992, 2.00025 i=13 err=0.00102319x=-3.99973, 2.99983, 1.9998 i=14 err=0.000625697x=-3.99989, 3.00017, 1.99989 i=15 err=0.00034136x=-4.00005, 3.00008, 2.00003 i=16 err=0.000155236x=-4.00004, 2.99997, 2.00003 i=17

7、 err=0.000106099x=-4., 2.99997, 2. i=18 err=0.0000414468此結(jié)果說(shuō)明迭代18次，求得誤差為err=0.0000414468的近似解，最后顯示的近似解向量為x=-4., 2.99997, 2.，它表示所求解為x1=-4，x2=2.99997，x3=2。本題的準(zhǔn)確解為 x1=-4，x2=3，x3=2 。如果將如上輸入的初值改為21, -18, 30，執(zhí)行Jacobi迭代法程序后得如下輸出結(jié)果。 x=-1.2, -4.75, -9.3 i=1 err=39.3x=1.36, 9.35, -0.885 i=2 err=14.1x=-5.963, 5

8、.7825, 2.833 i=3 err=7.323x=-5.2796, 2.09275, 3.22735 i=4 err=3.68975x=-3.88257, 2.06642, 1.98375 i=5 err=1.39703x=-3.62332, 3.03749, 1.69644 i=6 err=0.97106x=-3.95428, 3.24595, 1.93591 i=7 err=0.330963x=-4.08556, 3.04347, 2.06464 i=8 err=0.202475x=-4.03032, 2.94629, 2.03015 i=9 err=0.0971858x=-3.98

9、455, 2.97734, 1.98995 i=10 err=0.0457716x=-3.98893, 3.00889, 1.99011 i=11 err=0.0315451x=-4.00158, 3.00771, 2.00045 i=12 err=0.0126504x=-4.00318, 2.99938, 2.00263 i=13 err=0.00833246x=-4.00028, 2.99789, 2.00045 i=14 err=0.00289753x=-3.99925, 2.99971, 1.99942 i=15 err=0.0018145x=-3.99977, 3.00048, 1.

10、99976 i=16 err=0.000770763x=-4.00014, 3.00018, 2.0001 i=17 err=0.000375926x=-4.00009, 2.99992, 2.00008 i=18 err=0.000261658x=-3.99998, 2.99994, 1.99999 i=19 err=0.000107579x=-3.99997, 3.00001, 1.99998 i=20 err=0.0000714045從計(jì)算結(jié)果可以看到雖然所取的初值不同，但迭代總是收斂相同的結(jié)果?？疾毂绢}系數(shù)矩陣可以發(fā)現(xiàn)它是嚴(yán)格對(duì)角占優(yōu)矩陣，由收斂判別法，Jacobi迭代對(duì)任意初值都是收

11、斂的，我們通過(guò)實(shí)際計(jì)算驗(yàn)證了這個(gè)結(jié)果。例2 通過(guò)Jacobi 迭代序列觀察用Jacobi 迭代法解如下線性方程組 x1+2x2+2x3= -12 -x1+4x2+x3= 20 2x1-3x2+x3= 3的收斂性。解：執(zhí)行Jacobi迭代法程序后在輸入的4個(gè)窗口中按提示分別輸入3，1, 2, 2, -1, 4, 1, 2, -3, 1，-12, 20, 3，0, 0, 0，0.0001每次輸入后用鼠標(biāo)點(diǎn)擊窗口的“OK”按扭，得如下輸出結(jié)果。 x=-12., 5., 3. i=1 err=12.x=-28., 1.25, 42. i=2 err=39.x=-98.5, -12.5, 62.75 i

12、=3 err=70.5x=-112.5, -35.3125, 162.5 i=4 err=99.75.246.719, -120.176, 696.719 i=8 err=763.5x=-1165.09, -107.5, -850.965 i=9 err=1547.68x=1904.93, -73.5303, 2010.67 i=10 err=3070.02x=-3886.28, -21.4355, -4027.45 i=11 err=6038.12x=8085.77, 40.2917, 7711.26 i=12 err=11972.1x=-15515.1, 98.6279, -16047.7

13、 i=13 err=23758.9x=31886.1, 138.141, 31329.1 i=14 err=47401.2x=-62946.5, 144.247, -63354.7 i=15 err=94832.5x=126409., 107.068, 126329. i=16 err=189683.x=-252883., 25.0775, -252494. i=17 err=379292.x=504925., -92.4305, 505845. i=18 err=758339.通過(guò)觀察迭代過(guò)程中的誤差是不斷變大的特點(diǎn)可以知道本題的Jacobi 迭代序列是不收斂的，因此，本題線性方程組不能用J

14、acobi 迭代法求解。這個(gè)實(shí)驗(yàn)說(shuō)明并不是每個(gè)線性方程組都能用Jacobi 迭代法求解。Seidel迭代 Seidel迭代算法1.輸入變量個(gè)數(shù)n、初值向量x（0）、迭代精度eps、系數(shù)矩陣A、常數(shù)項(xiàng)b 和迭代最大次數(shù)nmax2. For i=1,2,n 如果|aii|eps1,則輸出“迭代失敗”提示并終止3.For i=1,2,nmax For i=1,2,n 如果|x(k+1)-x(k)|eps ,輸出解向量x ，終止；否則x（k） x(k+1)4. 如果|x-x0|eps ,輸出迭代失敗，終止。 Seidel 迭代法程序Cleara,b,x;nmax=500;n=Input“線性方程組階數(shù)

15、n=”;a=Input系數(shù)矩陣A=；b=Input常數(shù)項(xiàng)b=；x0=Input輸入迭代初值向量x0；eps1=0.000001;eps=Input輸入精度控制eps=； x=x0; DoIfAbsai,ieps1,t1=1;Return,t1=0,i,1,n; Ift1=1,PrintSeidel迭代法失效, Do Dou1=Sumai,j*xj,j,1,i-1; u2=Sumai,j*x0j,j,i+1,n; xi=(bi-u1-u2)/ai,i, i,1,n; err=MaxAbsx-x0; Printx=,x/N, k=,k, err=,err/N; IfNerr=eps,Print迭代

16、失敗 說(shuō)明：本程序用于求線性方程組Ax=b的解。程序執(zhí)行后，先通過(guò)鍵盤輸入線性方程組階數(shù)n、系數(shù)矩陣A、常數(shù)項(xiàng)b、迭代初值向量x0和輸入精度控制eps，程序即可給出每次迭代的次數(shù)和對(duì)應(yīng)的迭代向量序列x(K),其中最后輸出的結(jié)果即為所求的根。如果迭代超出500次還沒(méi)有求出滿足精度的根則輸出迭代失敗提示，如果出現(xiàn)主對(duì)角線元素aii=0給出Jacobi迭代法失效提示。程序中變量說(shuō)明：x0：存放初始向量和迭代過(guò)程中的向量x（k）x: 存放迭代過(guò)程中的向量x（k+1）nmax：存放迭代允許的最大次數(shù)err：存放誤差|x-x0|t1,u1,u2：臨時(shí)變量注：迭代最大次數(shù)可以修改為其他數(shù)字例題與實(shí)驗(yàn)例3 用

17、Seidel 迭代法解如下線性方程組 5x1+2x2+3x3= -12 -x1+4x2+2x3= 20 2x1-3x2+10x3= 3要求誤差|x(k+1)-x(k)|10-4。解：執(zhí)行Seidel迭代法程序后在輸入的4個(gè)窗口中按提示分別輸入3，5, 2, 1, -1, 4, 2, 2, -3, 10，-12, 20, 3，0, 0, 0，0.0001每次輸入后用鼠標(biāo)點(diǎn)擊窗口的“OK”按扭，得如下輸出結(jié)果。x=-2.4, 4.4, 2.1 k=1 err=4.4x=-4.58, 2.805, 2.0575 k=2 err=2.18x=-3.9335, 2.98787, 1.98306 k=3

18、err=0.6465x=-3.99176, 3.01053, 2.00151 k=4 err=0.0582625x=-4.00451, 2.99812, 2.00034 k=5 err=0.0127509x=-3.99931, 3., 1.99986 k=6 err=0.00519946x=-3.99997, 3.00007, 2.00002 k=7 err=0.000659841x=-4.00003, 2.99998, 2. k=8 err=0.0000916628 此結(jié)果說(shuō)明迭代8次，求得誤差為err=0.0000916628的近似解，最后顯示的近似解向量為x=-4.00003, 2.99

19、998, 2.，與本題的準(zhǔn)確解為 x1=-4.，x2=3.，x3=2. 誤差很小。注意到本題在同樣迭代誤差和初值前提下，用Jacobi 迭代需要18次迭代才獲得具有同樣精度的解，這說(shuō)明，在都收斂的前提下，Seidel 迭代比Jacobi 迭代收斂快。例4 設(shè)線性方程組為 x1+2x2-2x3= 1 x1+x2+x3= 1 2x1+2x2+x3= 1考察用Jacobi迭代法和Seidel 迭代法求解該線性方程組的收斂情況。如果收斂，給出誤差滿足|x(k+1)-x(k)|10-4的解。解：執(zhí)行Seidel迭代法程序后在輸入的4個(gè)窗口中按提示分別輸入3，1, 2, -2, 1,1,1, 2,2,1，1,1,1，0, 0, 0，0.0001每次輸入后用鼠標(biāo)點(diǎn)擊窗口的“OK”按扭，得如下輸出部分結(jié)果。.x=-5123., 5379., -511. k=9 err=3072.x=-11779., 12291., -1023. k=10 err=6912.x=-26627., 27651., -2047. k=11 err=1