擾動誤差分析_第1頁
擾動誤差分析_第2頁
擾動誤差分析_第3頁
擾動誤差分析_第4頁
擾動誤差分析_第5頁
已閱讀5頁,還剩9頁未讀 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

1、第2章線性代數(shù)方程組數(shù)值解法I:直接法考慮方程組Ax = b (A e Rnxn非奇異,b e Rn且b。0 ) (2.6.1)設A有誤差5A,b有誤差8b,則因此引起解x有誤差,即有擾動方程組(A + 5A)( x + 5x) = b + 5b現(xiàn)在來研究如何通過5A和5b對5 x的影響作出估計。定理2.6.1設 方程組(2.6.1)中A,b分別有擾動5A ,5b,因而解向量有誤差5x ;又5A足夠小,使得A-i|A|v 1,則有誤差估計式:指號+埠)證明由 A5x + (5A)x + (5A)(5x) =5b5x = A-i5b 一 A-i (5A) x 一 A-i (5A)(5x)兩邊取范

2、數(shù)有I5x| | |A-1|啊| + |A-i|5A|x| +|A-1|網(wǎng)5圳得到|5x|-|A-i|5A|5x| |A-i|網(wǎng) +|A-i|5A|x(i-|A-|陋|)|聞 |A-i|(|5b| + 網(wǎng)得到|px| (| 5b|+|5A|x|)又注意到Ax = b有|A|x|習|b|從而得到. i故上述不等式左邊乘以席,右 x邊圓括號第一項乘以第二項乘以IA,bll并從括號中提出|A|,則得(2.6.3)定理的結果實際包含兩種特殊情形:(1)A 精確,艮口 5A = 0,b 有擾動 5b,從而 A(x + 5x) = b + 5b A-i |A| A有擾動M , b精確,即5b = 0,這時

3、(A + 5A)(x + &) = b網(wǎng) 1cond (A) = cond (A-i)cond (a A) = cond (A)(2)根據(jù)定義|A| =勺(ATA),可得2- maxcond (A) = A -i若U為正交陣,即UUT = /,則cond (U = 1又 A 非奇異,則 cond(A) = cond(AU) = cond(UA)設X1與X n為A按模最大和最小的特征值,則IX I cond (A) * 人n特別地,若A = AT (即A對稱),則cond(A)=用 冗n力右A對稱正定,則cond(A)2 =十n證明略 定理2.6.2 (事后誤差估計)設方程組Ax = b, A非

4、奇異,b。0, x是精確解,x是近似解,剩余向量r = b - AX,則有估計式1 kllcond (A)同- COnd (A證明:因 Ax = b得 r = b 一 Ax = Ax 一 Ax = A(x 一 x),從而 x 一 x = A-ir,于是又由1 JA,于是得估計式右端x bA -i rA = cond (A) M(A類似地,由上述r = A(x 一 x),得|r| A,由 x = A-ib 得|x| | |A-i|b,綜合兩式得估計式兩端1 IM101-1-1-211103-131002 _1002一01-1-1一010200260013于是有 x二(2,2,3)t。(2)Gau

5、ss-Jordan消去法算法的核心部分為: 對k=1,2,,n,做a J-ki- (j=k, k+1,n, n+1) kj a kk對 k=1,2,nAik,做a, j a -a, a (j=k+1,n,n+1)輸出解 xa. H (i=1,2, /)(4)從上述做法可引發(fā)如下思考:Gauss-Jordan消去過程自然也可考慮 加上選主元和換行的技巧;就計算量而言,Gauss-Jordan消去過程顯然要大(可推導其乘除運算次數(shù)為生級,而順序Gauss消去過 2程乘除運算次數(shù)為擔級)。因此,用Gauss-Jordan消去法解方程組 3并不經(jīng)濟。但它有什么用途呢?這又引出一個新的思考。例題2.4設

6、Le R n*n為非奇異下三角陣,試(1)寫出求解方程組Lx= f的計算公式;統(tǒng)計上述求解過程的乘除法次數(shù);給出求L-1的計算公式。解(1)這是解下三角方程組的遞推公式:TfiEi X = (f 一文lx )/1 (i = 2,3, A , n)2 i ij j iilj=1(2)乘除法運算,第一式有1次,第二次i =2時有2次,i = n時有n次, 故上述公式的乘除運算次數(shù)有1 + 2+ + n = n(n +1) /2 (次)(3)因L非奇異,L-i存在,且由矩陣知識知L-i也為下三角陣,記L-i = (v ), ij由 LL-i = I,艮口LL-i =111121M122M01 Mv2

7、2M011011L ni1n2A1 nnn1vn2Avnn1考慮I的對角線元素,顯然有l(wèi) 九=i(i = i,2,A , n),于是得v = i/1 (i = i,2,A ,n)。禮vk=1考慮I對角線以下的元素,即對i = 2,3,A ,n; j = i,2,A ,i -1,則有 =1 v = i v +1 vik kj ik kj ij ijk=1于是得 v = (- 1 v )/1 (i - 2,3,A ,n; j = 1,2,A ,i -1)ijik kj ii例題2.5設A= (aij) g Rn*n對稱,其順序主子式尹0(i=1,2,n),試證明分解A=LDLT存在唯一,其中L為單

8、位下三角陣,D為對角陣;寫出利用此分解求解方程組Ax=b的步驟(這稱為改進的平方根法);用改進的平方跟法解方程組101630 xix29 17解(1)由A的順序主子式不為零,故存在唯一分解式A=LU, L為單位下三角 陣,U為上三角陣。改寫A=LU=LDU0,D為對角陣,U0為單位上三角陣。由 A對稱,有A=At=(LDU0)t= Ut(DLt),又由分解的唯一性即得Ut =L或 U0=Lt,于是代入可得A=LU=LDU0=LDLt存在唯一。(2)將 A=LDLt代入 Ax=b 得 LDLTx=b,令 DLTx=y (即 LTx=D-1y), 則Ly=b,改進平方根法如下:1)將A直接分解為A

9、=LDLt,即求出L,D;2)求解下三角方程組Ly=b,得y;3)求解上三角方程組LTx=D-1y(3)令 A=LDLt335 一35959171l21l311l132d1d2d3得x。1 l1 21311l32L1 _,由矩陣乘法并對比等式兩邊得d1 1121l 31315/3d 32d3=2/3解Ly=b即115/3y1y 2y 3101630115/3尤112尤_21尤3解 LTx=D-iy 即1/3得 x= ( 1, -1, 2)TA=以丫1 HYPERLINK l bookmark25 o Current Document P以2O可見改進平方根法比原始平方根法避免了開方運算;另一方

10、面,改進平方根法對 滿足LU分解條件的對稱矩陣(不一定要正定)都適用。例題2.6已知方程組Ax=b的系數(shù)矩陣形如:P2y*2OOMPayn-1n-1n-1A P a其中A的n-l階、主子距陣,*為其實數(shù),。試設計一個求解上述方程組基于追趕 的解決方案 解把A記為B v r 1 A= -i L J ut a n其中Bn-1為A的n-1階(對三角型)主子距陣,V, UER.對B 用追趕法可n-1作三角分解OLY11 HYPERLINK l bookmark22 o Current Document Pa22B =0n-1d y1 1d y22o opn-2OLn-2份l 一1Yn-2an-1Yn-

11、2dn-2 -再對A作三角分解,Bn-1Vp0QzUTa10dA=nnPQWtQ其中ZeR(N-由下三角方程組Pz二V求出,WeR(N-l)由方程組w tQ=ut(即下三角方程組QtW=U)求出,d由Wr + d =a算出。由此,求解上述方程組的解決方 nn n案如下:對& 用追趕法求出P, Q;n-1解下三角方程組Pz=v,求出z;解下三角方程組QtW=U求出W;計算d =a -Wtz;n n一 P Q 前推解下三角方程組y=b求出y;Wt 1 J Q Z回代解上三角方程組:,x=y求出x;0 a例題2.7設三對角方程組Ax=b,其中A=a b11 ca22c30b2a301b0cabn -

12、 1n - 1n - 1c a _nnx=X1X2X3MXn-1Xnd1d2d=d3Mdn-1dn 試建立A的順序主子式氣(k=1,2,.,n)的逆推公式。(2)試設計求解上述三對角方程組的另一種有別于一般追趕法(基于LU分解)的 新算法。解補充記氣=1,則顯然有A = a A = a a - b c = a A - b c A1121 21 22 11 2 Q一般地,猜想A = a A- b c A(k=3,4,.,n)k k k-1k -1 k k - 2用歸納法證明:當k=2時,上式成立。現(xiàn)假設有Ak -1-bk - 2,則由ab11cab222000k-2cak-2bk-2=akA k

13、-1 - bk-1ckA k - 2ck-1ak-1bk-1可知上述猜想成立。綜上所述,可得遞推公式:A = 1A = aA = a A b c A (k = 2,3,.,n)k k k-1k-1 k k - 2(2)由Ax=d的第一個方程可得即得x由x表示的關系式。將它代入第二個方程c x + ax + bx = d,又可得122 11 22 32x2由x3表示的關系式如此繼續(xù)代入,直到第n -1個方程,于是有如下形式的關系式=fkxk+1+g(k=2,3,., n-1)k-1其中fk和gk待定?,F(xiàn)將形式如(2沖孫._關系式代入Ax=d的第k(k=2,3,., n -1)個方程cx 1k k

14、 k+1k則有cJk-1 xk +c整理可得ckfbkk-1+axk+1+ dk fg-1 cJk -1 + ak(k=2,3,., n-1) (3)與關系式(2)比較得bk+ akgkk_I cJk -1 + ak(k=2,3,., n-1) (4)注意到方程組中的記號,令Cb=0。由(4)中取k=1,可得匕=-t1g1代入(1)得x = fx + g,可見(2)式對k=1也成立;又由(4)中取k=n,則可得f = 0,1121n1,而由于方程組Ax=d的第n個方程c x + a x = d可以寫成 a f + ann-1n n nc x + a x + b x = d,其中b = 0,x

15、。0,從而上述的代入可直至第nn n-1n n n n+1nnn+1個方程,也就是說(2)和(3)式對k = n也成立,于是有x廣gn。綜上所述,可得解三對角方程組的新算法如下:ckf-f _bf = i,g1 a 1 a-,g = kkk-1 (k = 2,3,., n -1)k c f + ak k - 1k。七為1a f +a= f x + g (k = n 一 1, n 一 2,.,2,1)k k+1kb kk-1+ag例題2.8證明下列兩個命題(其中|均為算子范數(shù)):(1)設 B e Rn*n 且 |Bl1,則I土B非奇異;(2)設A e Rn*n非奇異,B e Rn*n奇異,則k - B| 1。這與假設x, 0X|B|1矛盾,可知I + B非奇異。關于(2),由陽 土 B)一11 = W 土 B)一1(I 土 B H B) = |i H 0 土 B)-1 Bl |I| + 陽 土 B)|B|移項整理|G 土 B)-|B|) |I|由假設ibii1及注意到hl=mi =|/|2 =1,于是可得阪 土 B )-111 -I BII(2)對需要證明的不等式,自然與上述提及的3個基本定理聯(lián)系起來??梢試L試一下,但會發(fā)現(xiàn)難以聯(lián)系得起來

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論