3.4線性方程組的迭代法new

1、 Jacoai迭代和Seidel迭代由于收斂速度較慢，已經(jīng)越來越不適應當前信息時代人們對計算速度和精度的要求，所以在實際應用中使用得并不多。但是，他們體現(xiàn)了迭代法的最基本的思想，是學習其它迭代法的基礎。 直接法直接法是通過有限步運算后得到線性方程組的解是通過有限步運算后得到線性方程組的解, ,解解線性方程組還有另一種解法，稱為線性方程組還有另一種解法，稱為迭代法迭代法, ,它的基本思想它的基本思想是將線是將線性性方程組方程組 Ax=b Ax=b 化為化為 x=Bx+f x=Bx+f 再由此再由此構(gòu)造向量序列構(gòu)造向量序列 x x (k)(k): : x x(k+1)(k+1)=Bx =Bx (k

2、)(k)+f+f 若若 x x (k)(k) 收斂至某個向量收斂至某個向量x x * *, ,則可得向量則可得向量x x * *就是所求就是所求方程組方程組 AX=b AX=b 的準確解的準確解. . 線性方程組的迭代法主要有線性方程組的迭代法主要有JocobiJocobi迭代法、迭代法、SeidelSeidel迭代法和超松弛迭代法和超松弛( (Sor)Sor)迭代法迭代法. .迭代法的特點迭代法的特點 若在求解過程中 xkx*(k)，由 xk+1=(xk)產(chǎn)生的迭代 xk向x*的逼近 ，在數(shù)次迭代求解之后，由于機器跳動產(chǎn)生的xk值誤差或是有效數(shù)字產(chǎn)生的舍入誤差，都會在第k+1次迭代計算中自動

3、彌補過來或逐步糾正過來。因此，在 迭代求解過程中產(chǎn)生的各種誤差是可以忽略的，即迭代求解無累積誤差，實際上， xk只是解的一個近似，機器的舍入誤差并不改變它的此性質(zhì)。 a11 a12 a13 a1n a21 a22 a23 a2n A= =L+D+U an1 an3 an4 ann -4 2 1例例 矩陣矩陣 A= 1 -9 7 2 -6 10 如果如果 矩陣矩陣 A=(aA=(aij ij) )滿足滿足 n n |a |aii ii| | |a|aij ij| i=1,2,n,| i=1,2,n, j=1,j j=1,j i i 則稱方陣則稱方陣A A是是嚴格嚴格( (行行) )對角占優(yōu)的對角

4、占優(yōu)的. .L|一：一： 設有方程組設有方程組 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 . . . . . . . . . . . . . . . . . . . . . an1x1+an2x2+annxn=bn用矩陣表示：用矩陣表示： Ax =b （A A 為系數(shù)矩陣，非奇異；為系數(shù)矩陣，非奇異；b b為右端，為右端，x x為解向為解向量量) )假設假設 aii 0 令令 cij = -aij /aii (i j) gi= bi /aij , i=1,2,3,n 則 x1(k+1)= c12x2(k)+c13x3(k)+ +c1nxn(k)+g1

5、x2(k+1)=c21x1(k) +c23x3(k)+ +c2nxn(k)+g2 。 xn(k+1)=cn1x1(k) +cn2x2(k)+ +cn(n-1)xn-1(k) + gn Jacobi迭代格式迭代格式若令若令 0 c12 c13 c1n x1 c21 0 c23 c2n x2BJ= x= . cn1 cn3 cn4 0 xn a11 g1 a22 g= g2 易看出：易看出： BJ =D-1(D-A)=I - D -1A , D= . . ann gn ninijjiiikjiiijkiabxaax,2, 11)()1(gxBxJacobikJk)()1(迭代的矩陣格式Seidel

6、迭代法迭代法 為了加快收斂速度，同時為了節(jié)省計算機的內(nèi)存，我們作如下的改為了加快收斂速度，同時為了節(jié)省計算機的內(nèi)存，我們作如下的改進：每算出一個分量的近似值，立即用到下一個分量的計算中去，即用迭進：每算出一個分量的近似值，立即用到下一個分量的計算中去，即用迭代格式：代格式： 這樣所得的迭代法就稱為這樣所得的迭代法就稱為Gauss-SeidelGauss-Seidel迭代法，迭代法，也稱為也稱為“異步迭代異步迭代法法”，簡稱為，簡稱為GSGS迭代法迭代法利用利用Ax=b 及及A=L+D+U, ,其中其中D D為對角矩陣為對角矩陣, ,L,UL,U分別為嚴格下，上三角矩陣則有，分別為嚴格下，上三角

7、矩陣則有，GSGS迭代法的矩陣形式為迭代法的矩陣形式為: :iinijkjijijkjijikiaxaxabx1)1(11)()(bDUxDLxDxbDUxDLxDxkkk1)(1) 1(1) 1(111SeidelSeidel迭代法的具體形式迭代法的具體形式SeidelSeidel迭代格式迭代格式 x1(k+1)= c12x2(k)+c13x3(k)+ +c1nxn(k)+g1 x2(k+1)=c21x1(k+1) +c23x3(k)+ +c2nxn(k)+g2 。 xn(k+1)=cn1x1(k+1) +cn2x2(k+1)+ +cn(n-1)xn-1(k+1) + gn 假設假設 a a

8、ii ii 0 0 令令 cij = -aij /aii (i j) gi= bi /aij , i=1,2,3,n bLDgULDBJacobigxBxsssksk11)()1()(矩陣這里收斂性及誤差估計收斂性及誤差估計Jacobi迭代和迭代和GS迭代格式可表述為統(tǒng)一形式迭代格式可表述為統(tǒng)一形式: :對于其收斂性，我們有如下定理：對于其收斂性，我們有如下定理：定理：定理：對任意初始向量對任意初始向量x x(0)(0)及任意右及任意右端端向量向量 g g，由此產(chǎn)生的迭代向由此產(chǎn)生的迭代向量序列量序列 x x(k)(k) 收斂的充要條件是收斂的充要條件是證明：證明：必要性：必要性：設設x x(

9、k)(k)收斂，其極限為收斂，其極限為 x x* *，則則1BgBxxkk)()1(0*)0(*)0(*)1(*)(*limxxBxxBxxBxxgBxxkkkkk兩邊取極限 因上式對任意均成立，故因上式對任意均成立，故Bk 0(k ), (B)1 充分性：充分性：設設 (B)1, ,則則IB為非奇異陣為非奇異陣, ,且且 =0, =0,所以所以 有唯一解有唯一解, ,記為記為 則則 定理：若定理：若|B|1,B|1,則迭代法則迭代法 收斂收斂. .推論若推論若 滿足下列條件之一：滿足下列條件之一：（）（）)(limkkB;1max1njijihHnnijhH)(*)(limxxkk*)(*)

10、(*)0()0()0()()0()(xxBxxBxxBxxxxBxxkkkkkk由)0(xgBxx*xgBxx*gBxxkk )1()(2) (2) (3) (3) 則迭代法則迭代法 收斂。收斂。推論推論2 2：如果如果A為嚴格為嚴格對角占優(yōu)陣，則其對角占優(yōu)陣，則其 Jacobi迭代和迭代和Seidel迭代對迭代對任何初始向量任何初始向量x(0)都收斂。都收斂。推論推論3 3：如果如果A為對稱正定為對稱正定陣，則其陣，則其 Seidel迭代對任何初始向量迭代對任何初始向量x(0)都收斂都收斂。111maxniijjhH11,2njiijFhHgHxxkk)1()(下面給出迭代法的誤差估計下面給

11、出迭代法的誤差估計定理：若，則對迭代法定理：若，則對迭代法有有1H) 1() 1()(kgHxxkk*)0(*)(. 1xxHxxkk)()1(*)()1()(*)(1.31.2okkkkkxxHHxxxxHHxx)0()1(*)()0()1()()1()()1(*)()(*)()1()1()()(*)()(*)1()(*)(*)1()()1(*)0(*)1(*)(*)1(*)(*1,2|111)1(|)1(|)(, 1xxHHxxxxHxxxxHHxxHxxHxxxxHxxHxxHxxxxxxxxxxxxxxHxxHxxxxHxxgHxxxHkkkkkkkkkkkkkkkkkkkkkkkkk

12、kk有由結(jié)論另一方面由使有證明證明: :三例題及求解三例題及求解例：用迭代法解方程組例：用迭代法解方程組AX=b,AX=b,其中其中 已知該方程的解為已知該方程的解為 解：本題分別用簡單迭代法（解：本題分別用簡單迭代法（JacobiJacobi迭代法）和迭代法）和GSGS迭代法來解迭代法來解(1)(1)簡單迭代法簡單迭代法TbA15,11,25,6,8130110123111102110Tx1 , 1, 2 , 1*bDBxxxkkk1)1()1()(8151011112553081830101010151113111011105110101,0 ,0 ,0 ,0121)0(結(jié)果見表用四位小數(shù)

13、計算取簡單迭代法收斂TxB表K123456789100.60001.04730.93261.01520.98901.00320.99811.00060.99971.00012.27271.71592.05331.95372.01141.99222.00231.99872.00041.9998-1.1000 -0.8052 -1.0493 -0.9681 -1.0103 -0.9945 -1.0020 -0.9990 -1.0004 -0.99981.87500.88521.13090.97391.02140.99441.00360.99891.00060.9998)(2kx)(3kx)(4kx

14、0008.00002.00008.01*)10()9()10()9()10(*)10(xxxxxxBBxx而由定理，有)(1kx00001010001131110005110108151011112553,08183000101510001110000,)2(11)1()()(UbDLbDUxLxxGSkkk其中迭代法K123450.60001.03001.00651.00091.00012.32722.03702.00362.00032.0000-0.9873 -1.0140 -1.0025 -1.0003 -1.00000.87890.98440.99830.99991.0000)(1kx

15、)(2kx)(3kx)(4kx返回代法的一半而迭代次數(shù)只是簡單迭見表此時，用四位小數(shù)計算，結(jié)果仍取0003. 00001. 0 0 , 0 , 0 , 0)4()5()5(*)0(xxxxxT四四. . 相關程序設計相關程序設計原始數(shù)據(jù)（原始數(shù)據(jù)（A,b)A,b)可用一個二維數(shù)組存儲，也可將可用一個二維數(shù)組存儲，也可將A A用一個二維數(shù)組，用一個二維數(shù)組，b b用用一個一維數(shù)組分別存儲，存儲需要一個一維數(shù)組程序中應方便地一個一維數(shù)組分別存儲，存儲需要一個一維數(shù)組程序中應方便地對迭代方法和終止條件的選擇以及對初始向量和對迭代方法和終止條件的選擇以及對初始向量和 值的設置在迭代過程值的設置在迭代過

16、程中，為反映迭代情況，可設置一些中間數(shù)據(jù)的輸出，如迭帶次數(shù)，迭代中，為反映迭代情況，可設置一些中間數(shù)據(jù)的輸出，如迭帶次數(shù)，迭代向量，迭代殘向量向量，迭代殘向量等當然不需要每迭代一次都作輸出這可作為收斂等當然不需要每迭代一次都作輸出這可作為收斂情況或不收斂情況的分析作為不收斂的判定，可設置一個大的整數(shù)，情況或不收斂情況的分析作為不收斂的判定，可設置一個大的整數(shù)，當?shù)鼛Т螖?shù)超過該數(shù)時作為不收斂處理當?shù)鼛Т螖?shù)超過該數(shù)時作為不收斂處理GS GS 迭代法的計算公式為：迭代法的計算公式為：)(kxnikaxaxabxiiijnijkjijkjijiki2 , 1; 1111)1()()(五五. .方法優(yōu)缺

17、點討論方法優(yōu)缺點討論由以上例題的求解過程可明顯看出由以上例題的求解過程可明顯看出GSGS迭代法的收迭代法的收斂速度比簡單迭代法快，但對于任意給定的一個方程組斂速度比簡單迭代法快，但對于任意給定的一個方程組分別用簡單迭代法和分別用簡單迭代法和GSGS迭代法求解時，兩種迭代法可迭代法求解時，兩種迭代法可能都收斂，也可能都不收斂也有可能是能都收斂，也可能都不收斂也有可能是GSGS迭代法收迭代法收斂而斂而J J迭代法不收斂但亦有相反情況，即簡單迭代法迭代法不收斂但亦有相反情況，即簡單迭代法收斂而收斂而GSGS迭代法不收斂而且交換方程組中的方程和迭代法不收斂而且交換方程組中的方程和未知數(shù)的次序都會影響未

18、知數(shù)的次序都會影響GSGS迭代法的計算結(jié)果，但這種迭代法的計算結(jié)果，但這種交換對簡單迭代法是沒有影響的交換對簡單迭代法是沒有影響的SORSOR法介紹法介紹1)(k)()()1k()()()1(x)1 ()x(kkkkkxxxxxx利用利用Seidel Seidel 迭代法迭代法 ，考慮如下，考慮如下Sor Sor 迭代格式迭代格式Sor Sor 迭代格式也是線性迭代形式迭代格式也是線性迭代形式 例：設方程組為 3103220241225321321321xxxxxxxxx試分別寫出其 Jacobi迭代格式和 Seidel迭代格式以及相應的迭代矩陣。解：Jacobi迭代格式為 103)(2103

19、)(151)(2)(1101)1(3)(321)(141)(3)(141)1(2512)(351)(252)(3)(251)1(1)323(5220()212(kkkkkkkkkkkkkkkxxxxxxxxxxxxxxx故 Jacobi迭代矩陣為 BJ=0001035121415152103)1(2103)1(151)1(3)(321)1(141)1(2512)(351)(252)1(15kkkkkkkkkxxxxxxxxx1021)(381)(2201)1(3522)(32011)(2101)1(2512)(351)(252)1(1.kkkkkkkkkxxxxxxxxx從例中可以看出Jacobi迭代矩陣Bj的主對角線為零，而Seidel迭代矩陣Bs的第1列都是零，這對一般情況也是成立的。8120120111015152s000B舉例檢驗舉例檢驗JacoaiJacoai迭代的收斂性迭代的收斂性已知三階線性方程組：已知三階線性方程組： 8x1 -3x2 +2x3 =204x1 +11x2 -x3 =336x1 +3x2 +12x3 =36首先將原方程組寫為迭代形式的方程組，即