電子科大 數(shù)值分析課件第四章 線性方程組的迭代解法

1、第四章 線性方程組的迭代解法,迭代法的基本思想 Jacobi迭代和GaussSeidel迭代 迭代法的收斂性 超松弛迭代 分塊迭代法,第四章 線性方程組的迭代解法,4.1 迭代法的基本思想：,例：求解方程組,其精確解是x*=(3,2,1)T。,現(xiàn)將原方程組改寫為,簡寫為x=B0 x+f，其中,任取初始值，如取x(0)=(0,0,0)T，代入x=B0 x+f右邊，若等式成立則求得方程組的解，否則，得新值x(1)=(x1(1),x2(1),x3(1)T=(2.5,3,3)T，再將x(1)代入，反復計算，得一向量序列x(k)和一般的計算公式（迭代公式）：,簡寫為x(k+1)=B0 x(k)+f k=

2、0,1,2,x(10)=(3.000032,1.999838,0.999813)T,迭代到第10次時有,|(10)| =|x(10)x*|=0.000187,定義：,（1）對于給定方程組x=Bx+f，用迭代公式x(k+1)=Bx(k)+f (k=0,1,2,)逐步代入求近似解的方法稱迭代法；,（2）若k時lim x(k)存在（記為x*），稱此迭代法收斂，顯然x*就是方程組的解，否則稱迭代法發(fā)散；,（3）B稱為迭代矩陣。,問題：, 如何建立迭代格式？ 收斂速度？ 向量序列的收斂條件？ 誤差估計？,設(shè)Ax=b，A非奇異，且對角元不為零，將原方程組改寫為,4.2 Jacobi迭代與GaussSeid

3、el迭代,4.2.1 Jacobi迭代法,又代入，反復繼續(xù)，得迭代格式：,稱Jacobi 迭代法。,選取初始向量,代入上面方程組右端得,Jacobi迭代法的矩陣表示：,計算公式為：,(i=1,2,n)，(k=0,1,2,表迭代次數(shù)),矩陣表示：,則BJ=I- D-1 A = D-1(L+U)， fJ=D-1b， 稱BJ為Jacobi迭代矩陣。,（aii0）,將方程組Axb的系數(shù)矩陣A分解為：A=D-L-U,例1:,用Jacobi迭代法求解方程組，誤差不超過10-4。,解:,依此類推,得方程組滿足精度的解為x12,迭代次數(shù)：12次,x4 = 3.0241 1.9478 0.9205 d = 0.

4、1573 x5 = 3.0003 1.9840 1.0010 d = 0.0914 x6 = 2.9938 2.0000 1.0038 d = 0.0175 x7 = 2.9990 2.0026 1.0031 d = 0.0059 x8 = 3.0002 2.0006 0.9998 d = 0.0040 x9 = 3.0003 1.9999 0.9997 d = 7.3612e-004 x10 = 3.0000 1.9999 0.9999 d = 2.8918e-004 x11 = 3.0000 2.0000 1.0000 d = 1.7669e-004 x12 = 3.0000 2.0000

5、 1.0000 d = 3.0647e-005,若在迭代時盡量利用最新信息，則可將迭代格式變?yōu)?4.2.2 GaussSeidel迭代法,稱GaussSeidel迭代法.,計算公式：,（i=2,3,n-1）,(i = 1,2,n),即,其中 BG-S=(D-L)-1 U 稱GaussSeidel迭代矩陣。,(D L)x(k+1) = b Ux (k),故,GaussSeidel迭代格式：,1. 矩陣的范數(shù)（三種算子范數(shù)、譜半徑、譜范數(shù)、F-范數(shù)）,前一次課內(nèi)容回顧,3. 迭代法求解線性方程組（Jacobi迭代、Gauss-Seidel迭代及其矩陣表示）,2. 線性方程組求解的誤差分析 （病態(tài)方

6、程組、良態(tài)方程組、擾動分析、事后誤差估計）,例2.,用Gauss-Seidel迭代法求解例1方程組,要求誤差仍然不超過10-4。,解:,Gauss-Seidel迭代格式為,x1 =2.5000 2.0909 1.2273 d =3.4825 x2=2.9773 2.0289 1.0041 d =0.5305 x3 =3.0098 1.9968 0.9959 d =0.0465 x4 =2.9998 1.9997 1.0002 d =0.0112 x5 =2.9998 2.0001 1.0001 d =3.9735e-004 x6 =3.0000 2.0000 1.0000 d =1.9555e

7、-004 x7 =3.0000 2.0000 1.0000 d =1.1576e-005,取初值x(0)=(0,0,0)T通過迭代，至第7步得到滿足精度的解x7：,從例1和例2可以看出，Gauss-Seidel迭代法的收斂速度比Jacobi迭代法要快。,Jacobi迭代法和Gauss-Seidel迭代法統(tǒng)稱為簡單迭代法。,4.3 迭代法的收斂性,設(shè)求解線性方程組的迭代格式為,將上面兩式相減,得,而方程組的精確解為x*，則,則,因此迭代法收斂的充要條件,可轉(zhuǎn)變?yōu)?引理：迭代格式,收斂的充要條件為,定理：迭代格式,收斂的充要條件為,迭代矩陣的譜半徑(B)1。,證: 對任何 n 階矩陣B，都存在非奇

8、矩陣P，使 B = P 1 J P 其中， J 為B的 Jordan 標準型。,其中, Ji 為Jordan塊,其中i 是矩陣B的特征值， 由 B = P 1 J P,B k = (P 1 J P) (P 1 J P) (P 1 J P)= P 1 J k P,迭代法 x(k+1) = B x(k) + f 收斂 ,(i = 1, 2, r),(i = 1, 2, r),譜半徑 (B) 1,定理：設(shè)x*為方程組 Ax=b 的解，若|B|1,則 對迭代格式 x(k+1) = B x(k) + f ， 有,（1）,（2）,推論 若|B|1，則迭代法x(k+1) = B x(k) + f 收斂。,（

9、因為(B) |B| ）,證 由|B|1，故用其特征值判斷。,所以Gauss-Seidel迭代法發(fā)散。,注：在例1和例2中，Gauss-Seidel迭代法收斂速度比Jacobi迭代法要高，但例3卻說明Gauss-Seidel迭代法發(fā)散時而Jacobi迭代法卻收斂，因此，不能說Gauss-Seidel迭代法比Jacobi迭代法更好。,可得,故,定義 設(shè)A=(aij )nn Rnn ，若 (i=1,2,n)，則稱A為對角占優(yōu)矩陣，若不等式嚴格成立，則稱A為嚴格對角占優(yōu)矩陣。,迭代法收斂的其他結(jié)論：,定理 若Ax=b中A為嚴格對角占優(yōu)矩陣，則Jacobi迭代和GaussSeidel迭代均收斂。,證明：

10、,因為系數(shù)矩陣A嚴格對角占優(yōu)，所以,故Jacobi迭代法收斂,(1)對于Jacobi迭代法，其迭代矩陣為,即,從而,因此,(2)對于GS迭代法，其迭代矩陣為,BG的特征值滿足,分析：要證GS迭代法收斂，即證其迭代矩陣的譜半徑(B)1，只要證明其特征值 1即可.,由于,可得,矛盾,由前述定理知，,GS迭代法收斂。,定理 若A為對稱正定陣，則GaussSeidel迭代收斂。,考慮解線性方程組的Gauss-Seidel迭代法,4.4 超松弛迭代法（SOR）迭代法的加速,令,因此,上式稱為逐次超松弛法(SOR迭代法),由GS迭代法的矩陣形式,上式為逐次超松弛法(SOR迭代法)的矩陣形式,令,當1時，S

11、OR法化為,GS迭代法,GS法為SOR法的特例, SOR法為G-S法的加速。,例1.,用GS法和SOR法求下列方程組的解:,要求精度1e-6,解:,(1)G-S迭代法,x1 x2 x3 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431 . 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944

12、 1.9999946 k = 71,x= 0.999995 0.999994 1.999995,滿足精度的解,迭代次數(shù)為71次,(2)SOR迭代法,x1 x2 x3 1 1 1 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932 . 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 k = 24,x= 1.000000 1.000000 2.000000,滿足精度的解,迭代次數(shù)為24次,選取適當?shù)?，SOR法的收斂速度比G-S法要快得多。,SOR迭代收斂條件： SOR迭代收斂(B)1； SOR迭代收斂的必要條件是02； 若A對稱正定，則當02時，SOR收斂。 若A為嚴格對角占優(yōu)矩陣，則當01 時，SOR收斂。,另外，松弛因子的選取是很困難的，一般采用試算進行。,設(shè) ARnn，xRn， bRn， 將方程組Ax = b中系數(shù)矩陣A分塊,其中，