JA4-2-線性方程組迭代要點

1、3.2線性方程組的迭代解2.1 j acobi迭代法對線性方程組a11x1 +a12x2 +a1nxn =b1a21x1 +a22x2 + +a2nxn =bnan1x1 - an2x2- annxn =6可仿照f(x) =0的求根方法建立迭代格 式.當(dāng)aii #0(i =1,2,，n)時，(4.9)可以改寫為xi =1/ai(bi-a12 x2 - a13 x3 -a n,n j.xn _1 a a1nxn )x2 =1/a22(b2-a21x1- 223x3 j-an,nxn_ a2n xn )(2)xn =1 / a nn(bn-an1x1 - an2x2 - an3x3一an,nxn建

2、立迭代格式=1/ a11(bi-ai2x2k)(k 1)x2=1/a22(b2 - a21x1 )-a13x3k)-a23x3k)x(k) a x(k) 1,nxn一 a1nxn )(k)(k)2,nxn- a2nxn )(k 1)xn =1通(k)(k)(k)(bn -an1x1- an2x2- an3x3(k) 一an,nxn將(4.9)改用矩陣形式表示為ax=b,設(shè)a. #0(i =1,2,，n),記/ 000-00 %0一 a12-a a21000000- a a31 a320.00f =1a-ab-9000jan1 an 2 an3-一an,n0001323e 二11d =diag(

3、a11,a22,ann),d=diag(a1111、,a22 , a nn ),一 a1n一 a 2n-anj,n0上面，e為嚴(yán)格下三角陣(4)下為嚴(yán)格上三角陣，口為對角陣，則迭代格式(3)可以寫為 x(k 1)=d(e f)x(k)d】b, (k=1,2,)進一令m =d、(e +f), g =d,b,則迭代格式為x(k 1)=mx(k) g, (k =1,2,)稱為jacobi迭代的矩陣形式，m稱為jacobi迭代矩陣.算法:(6)(8)(8)，顯然這是由于迭代矩陣m輸入 方程組ax =b中的a,b.初始向量x0,誤差容限tol;最大迭代次數(shù)m輸出 近似解x或迭代次數(shù)超過m的信息.step

4、 1 4:寸 k =1,，m做step 2 - 4.step 2 ki=1，nnxi : (bi aijx0j)/aj 二j 1step 3 若 | x x0 |tol,則輸出(x1，xn);停機.step 4 i =1,，nx0i xi.step 5 輸出(maxim un number of iterations exceeded);停機.在step3中的迭代終目準(zhǔn)則，可用| x。x0 |0 tol.|x|所用的向量范數(shù)可以是 任何一種簡便的范數(shù)，最常用的是10c范數(shù).2.2 迭代的收斂條件ex.用迭代法求方程組3xi -20x2 =26 =2.5x1 +x2 =4的解解若將(6)改寫為x

5、1 =20/3 x2 +26/30,x=0.11(2)對任意的實數(shù) 九,|0x|a=(xt a拉戶=|?j(xtax戶 0,x#0.(3)因a正定，因此總存在非奇異下三 角陣l,使得a = llt于是 11|x|a=(xtlltx)2 =(ltx)t(ltx)2 =|ltx|l從而，.對任意的x, y w rn,恒有l(wèi)lx y|a=|lt(x - y)|2=|ltx lty)|b|ltx|2 |lty|2n|x|a |y|arn中的向量范數(shù)具有下列性質(zhì)(1)110 11=0.(2)w,y wrn,恒有l(wèi)lxll-llyll -llx -y|.按不同公式規(guī)定的向量范數(shù)，其大小一般不相等.然而，有

6、范數(shù)等性：(3) rn中的一切向量范數(shù)都是等價的，即對任意兩種范數(shù)|岡匕,|丫|口(不限于1p范數(shù))總存在兩個與 比關(guān)的正常數(shù)c1,c2 wr,使得對vxwrn,有c1|x|-.|x|.0, 存在5 = 3(b) 0,使得當(dāng)|y -x|p5時，恒有l(wèi)lyll： tlxll：.：二；.證 根據(jù)范數(shù)性質(zhì)(2) &,we havelly|：.-|x|;. iq|x-y|.0,取6=8/“.當(dāng)|x-y|pbf,便有l(wèi)ly|：.-|x|-.；.rn空間中的lp(p =1,2,8)范數(shù)滿足下面關(guān)系式：l|x|x|1n|x|:?l|x|:：|x|20, varn,?, ao;(2) | xaih x|a|,

7、va - k然，及 vie r；(3)|a+b|%a|+|b|,va,ber僅,(4) 11ab 伯|a| .|b|a,ber叫則稱| a |為矩陣a的一種范數(shù)，并說r%是賦以范數(shù)| a|的賦范線性空間.假定在rh陽中規(guī)定了一種矩陣范數(shù)|，|值在rn中規(guī)定了一種向量范數(shù)心若對r刈中 的任何一個矩陣a和r”中任何一個向量x,恒有不等式l|ax|ao,因此，11ahm注|心|.0.|x| .土(2)對v九w r,據(jù)| a |的定義及向量范數(shù)條件2,有ha|=maxj| ax|=|， max111ax|-.=| |a|.|x|-.m-|兇3-(3)據(jù)向量范數(shù)條件3,有|a b|二maxj|(a b)

8、x|.max |ax|. - max |bx |. = | a | - |b|.|x| -4- |x| -4- |x| . 4-.，一 . .1 一 .(4)對xx非奪xwr，由于x =1,因此|x|a11ax|：.二 |x|.al 1 j|x|。jx|一 a 1 x-|x|：.二|x|：. a |a|x|.對xza, bwrn河,|ab| = max|a(bx)|-.0,從而有i la|.由此我們得到一個重要的關(guān)系式：(a) 3|a|.定理4.4對于迭彳t格式(5)，即x(k*)=mx(k) +g,若m的某一種范數(shù)11mh1,則對任意 初始向量x(0)和g,迭代序列k)斂，且有誤差估計式i|

9、x(k)-x| restart; with(linalg):warning, the protected names norm and trace have been redefined and unprotected jacobi:=proc(a,b,x0,m) local n,x,x0,a1,a2,k,i,j; n:=vectdim(col(a,1); x0:=x0; x:=vector(0,0,0,0); for k from 1 to m do for i from 1 to n do a1:=0;a2:=0; for j by 1 from 1 to i-1 do a1:=a1+ai

10、,j*x0j; end do; for j by 1 from i+1 to n do a2:=a2+ai,j*x0j; end do; xi:=(bi-a1-a2)/ai,i; end do; x0:=x; print(map(evalf,x); end do; end: a:=matrix(4,4,5,-1,-1,-1,-1,10,-1,-1,-1,-1,5,-1,-1,-1,-1,10): b:=vector(-4,12,8,34): x0:=vector(0,0,0,0): jacobi(a,b,x0,6);.4400000000, 1.744000000,2.716800000, 3

11、.890080000.8701760000, 1.947705600,2.941592320, 3.975947392.9730490624, 1.989058877,2.987611066, 3.994971901 .9943283689, 1.997691134,2.997398281, 3.998941778.9988062385, 1.999514630,2.999452529, 3.999777340精確結(jié)果為(1, 2, 34)。2.3 gauss-seidel在jacobi迭代法中,迭代法有一個明顯的特點，就是每次迭代右端的變量的值全部用前一次迭代 值來代換，所以jacobi迭代

12、，又稱為同步迭代法.沖)馬上算出來可以設(shè)想，如果迭代序列收斂，則將迭代格式(3)中第一個方程計算出來的如果jacobi迭代法中迭代序列收斂，將其迭彳t格式(3)中第一個方程計算出來的x1代入到第二個方程使用，把前兩個方程計算出來的x1(k* ,x1(k*)馬上代入到第三個方程x3),；按這樣建立的迭代方程 稱為gauss-seidel迭代法迭代格式如下：x1(k 1)k 1)a111 / (k 1)(a21 x1(k)(k)(k)(k)、1.-a12x2a13x3-a1,nxn-a1nxn ) b1w)a 221an-a23x3k) -a2,nxn? a2nxnk)，b2a11/ (k 1)(

13、k 1)(a31 x1- a32x2 -a3,nxnk1a3nxnk)a221 b3a33(6)/ (k 1)(k 1)(an1x1-an2x2，b ann(k 1)1xn二一a11(6)由(4)式，式(6)可以寫成矩陣形式 (k 1)1 (k 1)1(k)x = d ex d fx g.進一下可將(6)改寫為x(k 1) = mx(k) g.其中m =(d e) f,g =(d e) b,則.稱(7)為guass seidel迭代的矩陣形式(丫(6)= dx(k* =ex(k*)+fx(k) +b(丫 g = d,b)= (d -e)x(k+) =fx(k) +而(口 e)存在.)關(guān)于gau

14、ss-seidel代法的收斂結(jié)論，除了用定理4.4與4.5外，還可由方程組ax =b的系數(shù)矩陣的某些特征來判斷迭代是不收斂：(1)若a為嚴(yán)格對角占優(yōu)矩陣(各行非對角元絕對值之和小于對角元絕對值的矩陣)，則| a|#0 ,且jacobi迭代法與gauss-seidel迭代法都收斂.(2)對a為對稱正定陣，則| a|#0且gauss-seidel迭代法收斂.(jacobi?)需進一步說明，某些方程對于jacobi迭代收斂，而對gauss-seidel迭代不收斂，而某些對于gauss-seidel收斂，但用jacobi迭代卻不收斂，但，對待實際問題可用上述兩個結(jié)論加以判斷， 或交換方程的次序使迭代法

15、收斂.ex.2 xex.1,用gauss-seidel迭代法解方程組ax = b.(a,b及初始解向量x0在程序中) restart; with(linalg): gaussseidel:=proc(a,b,x0,m) local n,x,x0,a1,a2,k,i,j; n:=vectdim(col(a,1); x0:=x0; x:=vector(0,0,0,0); for k from 1 to m do for i from 1 to n do a1:=0;a2:=0; for j by 1 from 1 to i-1 do a1:=a1+ai,j*xj; end do; for j by

16、 1 from i+1 to n do a2:=a2+ai,j*x0j; end do; xi:=(bi-a1-a2)/ai,i; end do; x0:=x; print(k);print(map(evalf,x); end do; end:a:=matrix(4,4,5,-1,-1,-1,-1,10,-1,-1,-1,-1,5,-1,-1,-1,-1,10): b:=vector(-4,12,8,34): x0:=vector(0,0,0,0): gaussseidel(a,b,x0,6);-.8000000000, 1.120000000, 1.664000000, 3.59840000

17、0.4764800000, 1.773888000,2.769753600, 3.902012160.8891307520, 1.956089651,2.949446513, 3.979466692 .9951406946, 1.998025279,2.997773268, 3.999093924.9989784943, 1.999584569,2.999531397, 3.999809446精確結(jié)果為(1, 2, 3, 4)。2.4逐次超超松弛迭代法逐次超松馳迭代法是gauss-seidel迭代法的一種加速方法，是解大型稀疏矩陣方程組的有占用計算機內(nèi)存比較少之優(yōu)點，但需要效方法之一，它具有計

18、算公式簡單，程序設(shè)計容易, 選擇好的加速因子(即最佳松弛因子)現(xiàn)將迭代法(5)改寫成(k 1)(k)x1=x1+1/a11n(b1 - %a1 j xj )j 3x2k 哨=x2k) +1 / a22(k：；1)(b2 - a21x1n，a2jx(k)j占(8)xnk *=xnk) +1/anni,(k 1)ri= bi -aij xj 土i xnxi(k *=x(k)+1/aii(biaijx(jk+)-zaijx(k)jj 王n a (k -1)(k)、(bn - anjx j - ann xn ) j a若記n(k 1)-(k)j - aij xj ,(i=12, n)則當(dāng)?shù)諗繒r，r

19、jk由t 0(kt叼;因此,gaussseide迭代法的第k +1步是相當(dāng)于在第 造的基礎(chǔ)上每一個分量增 加一個修正量 工ri(k+);為獲得更快的收斂效果，在修正量前乘以一 aii個參數(shù)。即(8)為i 1nx(k+ =xi(k) +(bi -z aijx尸-z aijx(k), (i=1,2； ,n)(9)aiij wj 適當(dāng)選取6彳t,可使迭代收斂速度加快，這咱方法稱為逐步超松 馳迭代法，匕o稱為松3因子，當(dāng)8=1日1 (9)為gaussseide迭代法.現(xiàn)將(9)式寫成等價形式i 1nx(k +=(1)xi(k) +3 (b -z aij x(k+)-z aijx(k), (i =1,2

20、,，n)aiij 土j 1則上式寫成矩陣形式為x(k 1) =(1 _ .)x.d(b ex(k 1) fx(k)(*)或x(k 1) =x(k).(10)其中疝=(d e)(1 )d f , =(d 一，e)，( .b).(丫 (*) = dx(k+ =(1 f)dx(k) +(cb +oex(k+) +c；ifx(k)二(d - e)x(k 1) =(1 一 .)d.fx(k)b)關(guān)于逐步超松馳迭代法我們有下面的結(jié)論.定理4.6逐次超松馳迭代法收斂的充要條件是p(m ) restart; with(linalg):warning, the protected names norm and trace have been redefined and unprotected sor:=proc(a,b,x0,m) local w,n,x,x0,a1,a2,k,i,j; w:=1.2; n:=vectdim(col(a,1); x0:=x0