數(shù)值分析課件

1、第 3 章 線性方程組的解法本章探討大型線性方程組計算機求解 的常用數(shù)值方法的構(gòu)造和原理， 主要介紹在 計算機上有效快速地求解線性方程組的有 關(guān)知識和方法 .重點論述Jacobi迭代法、Seidel迭代法、 Guass 消元法 及 LU 分解法 的原理、構(gòu)造、 收斂性等內(nèi)容。3.1 實際案例3.2 問題的描述與根本概念 解線性方程組問題在線性代數(shù)中已有 很優(yōu)美的行列式解法， 但對大型的線性方程 組階數(shù)n>40的求解問題使用價值并不大， 因為其計算量太大。 實際問題中經(jīng)常遇到自 變量個數(shù) n 都很大的線性方程組求解問題， 這些線性方程組要借助計算機的幫助才能 求出解。n個變元Xi,X2,

2、,Xn的線性方程組的一般 形式為a11x1a12x2La1nxnb1a21x1a22x2La2nxnb2M3.3am1x1am2x2Lamnxnbm式中， aij 稱為系數(shù)， bi 稱為右端項，它們都 是的常數(shù)。 如果有 x1 x1* , x2 x2*,L ,xn x*n 使方程組 3.3成立，那么稱值* * *x1* ,x2*,L ,xn*為線性方程組的 3.3的一組解。主要討本章在不作特別說明的情況下，論 m=n 的線性方程組a11x1a12x2La1nxnb1a21x1a22x2La2nxnb2Man1x1an2x2Lannxnbn的求解問題，且假設(shè)它有唯一解。線性方程組的矩陣表示Ax

3、b式中 A 稱為系數(shù)矩陣， b 稱為右端項數(shù)值分析中， 線性方程組的數(shù)值解法主 要分為 直接法 和 迭代法 兩大類。直接法是用有限次計算就能求出線性 方程組“準(zhǔn)確解 的方法不考慮舍入誤差 ； 迭代法是由線性方程組構(gòu)造出迭代計算公 式，然后以一個猜想的向量作為迭代計算的 初始向量逐步迭代計算， 來獲得滿足精度要 求的近似解。迭代法是一種逐次逼近的方法。3.3 線性方程組的迭代解法線性方程組迭代解法有 Jocobi 迭代法、 Seidel 迭代法及 Sor 法等根本思想 與簡單迭代法類比 將線性方程組 Ax b 等價變形為x Bx g以構(gòu)造向量迭代格式k1xBx kg用算出的向量迭代序列1 x2,

4、x 2 ,L 去逼近解 。1.構(gòu)造原理1 Jacobi迭代法1將線性方程組3.4 的第i個變元X用其他n-1個變元表出，可得1亠x(b1a11X2丄a21 X1a221八Xn(bnan1 X1anna13X3La1n Xn )a23X3La2n Xn )an2X2Lann 1Xn 1 )(3.5)稱3.5 為不動點方程組(2)將(3.5 )式寫成迭代格式x1k1)丄 Q ai2x2k) 43x3k)(k) y nQaiix2k 1) (b2a>ixjk)a23x3k)(k)-a2 nXn )a22(3.6)xnk 1) (bna1ix(k)an2x2k)-ann ix!k!)annJac

5、obi迭代格式(3)取定初始向量x00 0 , 0 T xi ,X2, L ,Xn,代入，可逐次算出向量序列 這里 x k Xik ,X2k 丄，xnk 。12k .X ,x ,L ,x L ,(k 1)Xi(b1a111 (b2 a221 Qann(k 1)an1 X1an2X2k 1)0 lXnki1)2) Seidel迭代法(k)(k)(k)、62X2，ax；丿-a1nxn;)(k 1)(k)(k)、a21X1a23X3-a2nXn )Seidel迭代格式Seidel迭代并不能取代Jacobi迭代3) Sor 法用Seidel迭代算出的 X 1與xk相減得到 差向量x Wo 1 xk采用

6、加速技術(shù)做下一步迭代：k 1kx x x得Sor法的迭代格式kx aiii 1nk 1k z iajXjajXj,i 1,2丄,nj 1j i 1式中參數(shù)稱為松弛因子，可以任意選取，當(dāng) =1時，Sor法就是Seidel迭代法(例如對線性方程組10x1x22X37.2x110 x22X38.3x1x25X34.2先將其寫成不動點方程組1x1(7.21 10x22x3)1x2(8.3x1X3)1X35(4.2X1X2)Jacobi迭代x1k1)110(7.2x2k)2x3k)x2k 1)1(8.3 x(k)x3k)10x3k 1)1(4.2 x!k)x2k)5Seidel迭代扣2 x2k)2x3k

7、)101 (8.3 x1k1) x3k)10 11(4.2 x1k1) x2k1)5Sor迭代1)1kX1(7.210x2k) 2x3k)x2k1)1kX2 (8.310(k 1)X1x3k)xT1)1kX1(4.25(k 1) x()x2k 1)2.迭代分析及向量收斂1) 三種迭代法的向量迭格式 對 Ax=b ，將系數(shù)矩陣 A 作如下分解ADLUa11a22Oann0a12 La1na21 M0L0MOMa2n Man1an2 L 0那么Ax=b可以寫成D L U x b。假設(shè)d 1存 在，得Ax=b的等價方程組x D 1 L U x D 1b由此可得到Jacobi迭代的向量迭代格式|xk1

8、 D 1 L U xk D 1bk 1kxBjXgjBj D 1 L U ,gj D 1b，Bj 稱為 Jacobi 迭代 矩陣。Seidel向量迭代格式k 1kxBsXgs式中矩陣Bs稱為Seidel迭代矩陣,1 1Bs D L U,gs DLb。Sor法的向量迭代格式k 1kx B x g式中矩陣B稱為超松弛迭代矩陣，1 1B D L 1 DU , g DLb。三種迭代格式可用一個迭代格式Xk 1 Bxk g2) 向量收斂定義定義31設(shè)向量序列Xkx/k丄，Xnk及量為向 limx1* , x*2 ,L ,x*n 都是 Rn 中的向量，如果有*Xi,i 1,2丄，n成立，,那么稱x(k)收

9、斂于x 。k*簡記為 lkim x x3) 范數(shù)定義與科學(xué)計算中的常用范數(shù)定義3.2 設(shè)L是數(shù)域K上的一個線性空 間，如果定義在L上的實值函數(shù)p(x)滿足1) 任取 x L，有 P(x) 0,且 P(x) 0 x 0 ；2) 任取 x L, K，有 p( x) | | p x ；3) 任取 x,y L ,有 P(x y) P x P y ,那么稱P()是L上的一個范數(shù)，稱P(x)為x的 一個范數(shù)。范數(shù)的定義很象絕對值函數(shù),故常用II IIp或 II表示范數(shù)，而范數(shù)px常記為IIx P或I x。這 樣，上面范數(shù)定義中的 3個條件常寫為1任取 x L，有 |x| 0,且 |x|0 x 0 ；2任取

10、 x L, K，有 | | H ；3任取 x,y L，有 |x y| |x| |y|將其與絕對值比擬，是否很象？實際上，很多有關(guān)絕對值的運算和結(jié)論可以 平行引進到有關(guān)范數(shù)的運算和證明問題中。數(shù)值分析中常用的線性空間有n維向量空間連續(xù)函數(shù)空C a,b f x | f x 在a,b上連續(xù)函數(shù)空間C a,b是由閉區(qū)間 a,b上所有 連續(xù)函數(shù)組成的集合，其線性運算定義為 加法 f g: f g x f x g x 數(shù)乘 f ： f x f x， 為數(shù)在這些空間上，數(shù)值分析中常用的范數(shù)有(1)Rn的向量范數(shù)n1) Ilxll1lxk ,k 1，3制mkax|x<|式中向量x Xi，X2丄,xn 。

11、(2) Rn n的矩陣范數(shù)矩陣范數(shù)要滿足如下四條1任取 ARnn，有IA0,且IA0A 0；2任取 ARnn,K ,有 | Al丨 IIIAI ;3任取 A,B Rnn，有 |A B J A |B|4 任取 A,B Rnn，有 | AB IA | B| 相容性與向量范數(shù)做比照由于線性方程組求解問題中，系數(shù)矩陣總 是與向量聯(lián)系在一起的，為描述這種聯(lián)系， 引入如下的算子范數(shù)概念。定義3.3設(shè)矩陣A Rnn，稱Apmaxx Rnx 0Ax|p為矩陣A的算子范數(shù)容易證明，矩陣A的算子范數(shù)也是矩陣范數(shù)，且滿足不等式關(guān)系IIAxip blip Mp.常用的矩陣范數(shù)有如下 4種n1) 列范數(shù):IIAIi m

12、axx I aJ i 1n2) 行范數(shù):iia maxx怙i3) F 范數(shù)：af g4) 2 范數(shù)：, max 是 A A 最大 特征值以上4個矩陣范數(shù)中，|A|i，|A|2，|A|是算子 范數(shù)，I A| F不是算子范數(shù)。3范數(shù)等價與向量極限定義3.4設(shè)llpJllq是線性空間L上的 兩個范數(shù)，假設(shè)存在正常數(shù)m和M，成立叫x|p |x|q M|x|p, X L那么稱范數(shù)I定理3.1定理3.2|q是等價范數(shù)。Rn上的所有范數(shù)都是等價的I 0。XX m NkXX Im != k式中II II是Rn上任何一種范數(shù)4譜半徑及其與范數(shù)的關(guān)系定義 3.5 設(shè) A Rn n , k,k 1,2,L ,n 是

13、 A 的 n個特征值，那么稱實數(shù)A mk剛 ki為矩陣A的譜半徑。注意k如果是復(fù)數(shù)，| k 表示復(fù)數(shù)模。kI A kIkAx|ax丨kxAxk kxk因為|xk| 0，上式同除|xk|，得I J IAI由k的任意性可得 A A。k定理3.3設(shè)A Rn n，那么有 A A , A|為 矩陣A的任意算子范數(shù)。證明 設(shè)k是A的任意一個特征值，xk為 對應(yīng)的特征向量，那么有取范數(shù)，得3.迭代法的收斂條件與誤差估計1收斂條件定理：線性迭代格式kk 1 Bxk g對任意初 始向量x0都收斂的充要條件是迭代矩陣譜 半徑B 1。引理3.4設(shè)A Rn n，貝Ulim Ak0 A 1證明必要性設(shè) kim xk x

14、*，在 xk 1 B xk g 中令 k , 得x Bx g，兩式相減并把k+1記為k, 得xk x* B xk 1 x* B2 xk 2 x* L Bk x0 x由kimxk X*及x0 ,x*的任意性，有kim Bk 0 由引理，可得 (B) 1。充分性因為 (B) 1，那么有 I B 非奇異(這里 I 為單位矩陣)，從而線性方程組I B x g有唯一解X*，即有I B x* g，展開有 x* B x* g 。類似必要性處理，有k * k 0 *x x B x x由引理， 由 (B) 1有 lkim Bk 0 ，上式取極限， 得 lkim x k x* 。譜半徑 (B) 一般不易計算， 因

15、此充要定理 通常只用在理論上。但由充要定理，可以得到如下易于計算的 判別迭代收斂條件 ，但要注意它們都是 充分 條件！判別條件I假設(shè)IB 1，那么迭代格式xk 1 Bxk g對任 意初始向量X0都收斂于線性方程組x B x g的唯一解。IIB是矩陣B的某種算子范數(shù)。定義3.6設(shè)A Rn n,1如果A的主對角元素滿足nakk|aj ,k 0,1 丄，nj k那么稱矩陣A是嚴(yán)格行對角占優(yōu)陣；2)如果A的主對角元素滿足n(3 18)akk|陽| ,k 0,1,L ,ni 1i k那么稱矩陣A是嚴(yán)格列對角占優(yōu)。嚴(yán)格行對角占優(yōu)陣和嚴(yán)格列對角占優(yōu) 陣統(tǒng)稱為嚴(yán)格對角占優(yōu)陣。定理嚴(yán)格對角占優(yōu)陣是非奇異矩陣。證

16、明不妨設(shè)矩陣A aj nn是嚴(yán)格行對 角占優(yōu)陣。用反正法。假設(shè)A是奇異的，那么由矩陣?yán)碚摽芍?，齊 次線性方程組Ax 0有非零解x*，即存在* T*xXi，X2，L ,xn0，滿足 Ax 0。記 |x；| |x| ，有 xm 0x； |x：|,k 1,2,L ,n。n將Ax 0的第m個等式amkxk 0寫為k 1ammXmamkXkk 1k m等式兩邊取絕對值有ammXm*a xmm八mn*amk Xkk 1k mn*amk Xkk 1k mn*amk Xkk 1k m因為|x；| 0，上式同除|x；|，有nnammk 1amk*Xk/*Xmk 1amkk mk m此與A是嚴(yán)格行對角占優(yōu)陣矛盾。

17、故假設(shè) A 是非奇異的。設(shè)矩陣 A 是嚴(yán)格對角占優(yōu)陣，那么線性方 程組 Ax b 的 Jacobi 迭代和 Seidel 迭代對任 意初始向量 x0 都收斂。判別條件 III設(shè) A 是對稱正定矩陣，那么 Ax b 的Seidel 迭代對任意初始向量 x 都收斂判別條件II的證明證明只對A是行對角占優(yōu)情況證之設(shè)矩陣A是嚴(yán)格行對角占優(yōu)陣，那么有nakkakj ，k O,1丄，n，將不等式兩邊同除j 17j k1 nakk，成立|akjjlakj1，k 0,1，L，nj kJacobi迭代矩陣BjI D 1A，故有nakj1 nmaxmax .akj1 k nj 1akk1 k n bkkl j 1

18、BJj kj k1由判別條件I,可得 Jacobi迭代的收斂性。對Seidel迭代，其迭代矩陣Bs d l 1u , 設(shè)k是矩陣Bs的任一特征值，那么有特征方程1det kI Bs det D L det k D L U 0因det D L 1 0，故矩陣Bs的特征方程變?yōu)閐et k D L U 0寫出這個行列式方程對應(yīng)的矩陣kai1a12La1nbsk D L Uka21ka22La2nMMOMk an1kan2Lkann如果丨k 1,利用矩陣A的行對角占優(yōu)的不等 式，可以得出如下不等式kakkklakknkakjk 1kakjnakj,k 0,1丄,nj 1j 1j k 1j k這說明矩陣

19、%也是行嚴(yán)格對角占優(yōu)陣，由定 理，有detBS 0。矛盾，故應(yīng)有丨訃1成立。由k的任意性有譜半徑Bs 1，于是可得Seidel迭代的收斂性。定理 3.7 Sor 法收斂的必要條件是松弛因 子 滿足 0< <2。證明 因為 Sor 法的迭代矩陣為1BDL1 D U有detBdet D1L 1 det 1 D UdetD1 det 1D 1 n設(shè) k ,k1,2,L,n 是 B的 n 個特征值，那么有detB1 2Ln1，假設(shè) Sor 收斂，必有B1，注意到 12L n B ，得n1nBn1。解之得 0 2 。2誤差估計定理3.8設(shè)矩陣B的某種矩陣范數(shù)| B1,那么由式xk 1 B x

20、k g算出的序列x k與線性方程組*x B x g的準(zhǔn)確解x有如下的誤差估計xk*xBillxkxk1|1IlBllII1事后估計式B1 l|B|2事先估計式證明可以參照非線性方程求根定理的證明，注意將那里的絕對值換成這里的范數(shù)，那里的函數(shù)換成這 里的矩陣，并注意范數(shù)關(guān)系的使用即可。要求誤差I(lǐng)解此題的才1)2.4O.4x2k)O.6x3k)x2k 1)50.25x；k)O.5x3k)x3k 1)0.30.2x1k)0.3x2k)10 4XJacobi迭代格式為例3.1用Jacobi迭代法解線性方程組5xi+2x2+3x3= -12xi+4x2+2x3= 202xi-3x2+10X3= 3k 1

21、0.40.6它的Jacobi迭代矩陣為bj0.250o.50.2 0.30因為|Bj|f 0.981071<1,故此題的 Jacobi迭代 格式對任意初值x0都收斂。取初值X00,0,0 T進行迭代計算如下X12.4,5,0.3 T ,1 0XX0.5 10 42TX24.46,4.25,2.28,X2X12.06104Mx184.,2.99997,2. T ,X18x170.41L104 10故所求近似解為X14,X22.9997,X32。準(zhǔn)確解為人4,X23, X32)1 22x1例3.2方程組111y22 21z31) 寫出Jacobi和Seidel迭代格式;2) 判別兩種迭代格式的收斂性。 解1)Jacobi迭代格式為x(k1)2y(k) 3z(k) 1y(k1)x(k) z(k) 2z(k1)2x(k) 2y(k) 3Seidel迭代格式為(k x1)2y(k)3z(