1、6.3 迭代法的構(gòu)造與基本迭代法,6.3.1線性方程組一般迭代公式的構(gòu)造,為非奇異矩陣，。,nn,設(shè)方程組 Axb，其中 A aij ,T,12n,b (b ,b ,b ),將 A分裂為 AMN，則方程 Ax b 等價于 Mx Nx b 若 M 是非奇異陣，則得 x M1Nx M1b ，從而得迭代公式 x(k1) M 1Nx( k ) M 1b ,(k 0,1,) 記 M1N B 、M1b f，于是得到一般迭代公式,xk 1Bxk f k 0,1, 2,6.3.2Jacobi迭代法,對方程組 Ax b，設(shè) det(A) 0,aii 0(i 1,2,n)，將A改寫成：,11,21,22,31,3

2、2,0,2n,n1,n2,a,n,n1,0,a, ,a0,A,aa0,a, , ,n , ,0a12a13a1n 0aa,23 , DLU,an1,n ,aaa0,若取 M =D，則 NMALU ，從而 Ax b 化為,Dx (LU)x b,x D1(L U)x D1b,J,x(k 1)Bx(k ),f,記,、,，于是,，從而得迭代公式,1,f Db,J,1,B D (LU),J,x B x f,其中,稱為Jacobi迭代矩陣。,J,這就是Jacobi迭代公式，這種迭代方法稱為Jacobi迭代法， 1,B D (LU),0,00 ,0,T,x1,x2,xn,取初值 x,則Jacobi迭代的分量

3、形式為,，,1,T,k ,k ,k k ,，記 x,x,x2,xn,n,k,k,i,i,ijj,i,ijj,ijj,axk ,xk 1,j i +1,j 1 j i,1 b,1 b,aii , ,aii ,ax,i1 j 1,n ax, i 1, 2, n ; k 0,1, 2,亦即為,1,1,122,133,2,2,211,213,1nn,2nn,n,n,n11,n 22,x( k ),x( k ),x( k ) ),a11,x,x( k ),x( k ),x( k ) ),a22,x( k ),x( k ),x( k ) ),ann,( k 1),nn1n1,x( k 1),1(b(a,a

4、, ,1(b -(a,a, ,x( k 1),1(b(a,a,a,a,a,a11 x1 a12 x2 ,a21 x1 a22 x2 ,an1 x1 an 2 x2,a1n xnb1 a2n xnb2 ,ann xnbn,11,122,11,1,1331nn,221 12132nn,nn,a,x1(b (a,x,1(b -(a,2 ,xaxax ),xaxax ),a22 ,xn a(bn (an1 x1 an2 x2 ann1 xn1 ),Jacobi迭代分量形式,例6.3.1,用Jacobi迭代法求下面線性方程組，,其精確解是 x* (1, 2, 1,1)T 。,2,6,10 x1 x2 2

5、x3,x1 11x2 x3 x4 25,2x1 x2 10 x3 x4 11 ,3xx3 8x4 15,解將 ,12,3,2,134,4,23,10,11 1 10,x1 (6 x2 x ),x,1 (25 x x3x ),轉(zhuǎn)化為等價方程組 , x 3,(11 2 x1 x2 x4 ), ,1 (15 3xx ),x 8,1,2,134,3,124,4,23,1 10,11,10,8,x,(k1),(6 x (k) 2x (k) ) 23, ,x(k1),1 (25 x(k) x(k) 3x(k) ), 得Jacobi迭代公式,x(k1),1 (112x(k) x(k) x(k) ),x(k1

6、),1 (15 3x(k) x(k) ),取初始向量,x(0) (0,0,0,0)T,經(jīng)10次迭代得近似解為 x(10) (1.0001,1.9998,0.9998,0.9998)T,誤差為：,x* x(10),0.0002,6.3.3Gauss-Seidel迭代法,若取 M =D-L，則 N MAU，從而 Ax b化為 (D L)x Ux bx (D L)1Ux (D L)1b,G,x(k 1),Bx(k ),f,記,、,，從而得迭代公式,f (D L)b,G,11,B(DL)U,G,，于是 x Bx f,迭代法，其中,稱為Gauss-Seidel迭代矩陣。,G,這就是Gauss-Seide

7、l迭代公式，這種迭代方法稱為Gauss-Seidel 1,B(DL)U,0,00 ,0,T,x1,x2,xn,取初值 x,則Jacobi迭代的分量形式為,，,1,T,k ,k k ,k ,，記 x,x,x2,xn,亦即為,i,b,n,k,j i1,k1,xi,1 ,aii ,aij x j ，（i 1,2,n;k 0,1,2,）,k1,i1 ijj j1,ax,Gauss-Seidel迭代分量形式,1,11221331nn,22112132nn,n,nn11n22,a11,x(k ) ),a22,ann,x(k1),x(k1),x(k1) ),nn1n1, ,2 ,x(k1),1(b(ax(k

8、1) a,1(b(ax(k ) ax(k ) ax(k ) ),1(b -(ax(k1) ax(k ) a,x(k1) a,將Gauss-Seidel迭代法， 簡記為：G-S迭代法。,當(dāng)計算出,就沖掉舊的分量,。,G-S迭代法與Jacobi迭代法一樣每迭代一次只需計算 一次矩陣與向量的乘法，但G-S迭代法比Jacobi迭代法有一個 明顯的優(yōu)點，那就是僅需一組工作單元來保存向量 x(k )（或,向量 x(k1）),j,x,(k1),(k ) j,x,以看作是Jacobi迭代法的一個修正。,由G-S迭代公式可看出在x(k) x(k1) 的一步迭代中，計算分量x(k 1) 時,i 1) 。因此，G-

9、S迭代法可,利用了已計算出來的新分量 xj,(k1),( j 1, 2,i ,例6.3.2,用G-S迭代法求例6.3.1相同的線性方程組。,2,6,10 x1 x2 2x3,x1 11x2 x3 x4 25,2x1 x2 10 x3 x4 11 ,3xx3 8x4 15,解將 ,12,3,2,134,3,124,10,11,10,1,x1 (6 x2 x ),x,1 (25 x x3x ),轉(zhuǎn)化為等價方程組 ,x,1 (11 2 x xx ),x4,(15 3x2 x3 ) 8,1,34,21,3124,3,42,1 10,11,10,8,x,(k1),(6 x (k) 2x (k) ) 23

10、,x(k1) 1 (25x(k1) x(k) 3x(k) ), 得G-S迭代公式,x(k1) 1 (112x(k1) x(k2) x(k) ),x(k1) 1 (153x(k1) x(k2) ),取初始向量 x(0) (0,0,0,0)T, 經(jīng)5次迭代得近似解為,誤差為： x* x(5),0.0001,x51.0001,2.0000,1.0000,1.0000T,從此例可見， G-S迭代法比Jacobi迭代法收斂快， 但這個結(jié)論對Ax=b的矩陣滿足某些條件才是對的，例如,123,2,3,x1 2x2 2x3 1,線性方程組 xxx1 ,1,用Jacobi迭代法收斂 而G-S迭代法卻發(fā)散。,事實

11、上，,G,1,1,202,102 ,2 10002 1,B DLU1 1,001 1 0,0001 0 0,23 0,1 210,00,00,2 ,210,(BG ) 2 1,1,J,1,2x2xx1 0,1 ,22 022 0 0,B DLU ,1,1 1,1,0 ,0 ,122,22,特征方程: 3 0,J,(B ) 0 1,2 特征方程:(2)2 0,6.3.4Jacobi迭代與G-S迭代法的收斂性,根據(jù)線性方程組迭代法收斂的基本定理，Jacobi迭代與 G-S迭代法的收斂性定理。 定理6.3.1 解方程組Ax=b 的Jacobi迭代與G-S迭代法收斂的 充分必要條 件分別是 (BJ )

12、 1與 BG( ) 1，BJ 與 BG 是Jacobi迭代 矩陣與G-S矩陣。,定義6.3.1 （對角占優(yōu)矩陣）設(shè),即 A 的每一行對角元素絕對值嚴(yán)格大,于同行其他元素絕對值之和，則稱 A 為嚴(yán)格對角占優(yōu)矩陣。,A (aij )nn,n,j 1 j i,0(i 1 n，),若 aiiaij,n,0(i 1 n) 且至少有一個不等式嚴(yán)格成立，,若 aiiaij,j 1 j i 則稱 A 為弱對角占優(yōu)矩陣。 定義6.3.2（可約與不可約矩陣）設(shè)A (aij )nn 當(dāng) n 2 時，如果存在 n 階排列矩陣 P 使,PT,A1 1A1 2 AP ,0,A22 ,11,成立。其中 A,為 r 階子矩陣

13、， A22 為 n-r 階,子矩陣(1r n)，則稱矩陣 A 為可約的。若不存在排列矩陣 P 使上式成立，則稱 A 為不可約矩陣。 當(dāng)A 為可約矩陣，則 Ax=b 可經(jīng)過若干行列重排化為兩個 低階方程組求解。,定理6.3.2（對角占優(yōu)定理）若 A (aij )nn 為嚴(yán)格對角占 優(yōu)矩陣或為不可約弱對角占優(yōu)矩陣，則 A 是非奇異陣。,其中為 r 維向量。于是，方程 Ax=b 化為：,y ,d ,事實上，由 Ax=b 化為：PT AP(PT x) PTb，設(shè) y PT x ,1T , P b ,1 ,y2 d2 ,y1 , d1,A11 y1 A12 y2 d1 A22 y2 d2 定理6.3.3

14、 若 A Rnn 為嚴(yán)格對角占優(yōu)矩陣或為不可約對角占優(yōu) 矩陣，則對任意的初始向量 x(0) 方程組 Ax=b 的Jacobi迭代法和 G-S迭代法均收斂。且G-S迭代法比Jacobi迭代法收斂速度快。,線性方程組迭代法的收斂與否與方程組中方程的排列 順序有關(guān)，如線性方程組,123,1.25x1-3.69x2 12.37x3 0.58,-10.01x1 9.05x2 0.12x3 1.43 ,1.22x -4.33x2.67x3.22,無法直接判斷Jacobi迭代法和G-S迭代法的收斂性，但如果將,方程組中方程的次序調(diào)換為 -10.01x1 9.05x2 0.12x3 1.43 1.22x1-4.33x2 2.67x3 3.22,1.25x1-3.69x2 12.37x3 0.58,則方程組的系數(shù)矩陣 A 是嚴(yán)格對角占優(yōu)矩陣，因此用Jacobi迭 代法和G-S迭代法求解該方程組均收斂。,？,如何對G-S迭代法進行改進使其收斂速度更快？,6.3 迭代法的構(gòu)造與