數(shù)值分析——誤差估計

1、1第五章第五章線性方程組直接解法線性方程組直接解法 誤差估計誤差估計2本講內(nèi)容本講內(nèi)容n 向量范數(shù)向量范數(shù)n 矩陣范數(shù)矩陣范數(shù)l 向量范數(shù)的定義向量范數(shù)的定義l 常見的向量范數(shù)常見的向量范數(shù)l 向量范數(shù)的性質(zhì)向量范數(shù)的性質(zhì)l 矩陣范數(shù)的定義矩陣范數(shù)的定義l F-范數(shù)與算子范數(shù)范數(shù)與算子范數(shù)l 矩陣范數(shù)的性質(zhì)、算子范數(shù)的性質(zhì)矩陣范數(shù)的性質(zhì)、算子范數(shù)的性質(zhì)n 誤差估計誤差估計3向量范數(shù)向量范數(shù)設(shè)函數(shù)設(shè)函數(shù) f : Rn R，若，若 f 滿足滿足(1) f(x) 0， x Rn , 等號當(dāng)且僅當(dāng)?shù)忍柈?dāng)且僅當(dāng) x = 0 時成立時成立(2) f( x) = | | f(x) ， x Rn , R (3

2、) f(x+y) f(x) + f(y) 則稱則稱 f 為為 Rn 上的（向量）范數(shù)，通常記為上的（向量）范數(shù)，通常記為 | | q 4向量范數(shù)向量范數(shù)11niixx n 常見的向量范數(shù)常見的向量范數(shù)12221niixx 1maxii nxx 無窮范數(shù)（最大范數(shù)）無窮范數(shù)（最大范數(shù)） 2-范數(shù)范數(shù) EuclidEuclid范數(shù)。范數(shù)。 1-范數(shù)范數(shù)5范數(shù)性質(zhì)范數(shù)性質(zhì)n 范數(shù)的性質(zhì)范數(shù)的性質(zhì)(1) (1) 連續(xù)性連續(xù)性設(shè)設(shè) f f 是是 R Rn n 上的任意一個范數(shù)，則上的任意一個范數(shù)，則 f f 關(guān)于關(guān)于 x x 的每個分量是連續(xù)的的每個分量是連續(xù)的(2) (2) 等價性等價性設(shè)設(shè) | |

3、|s s 和和 | | |t t 是是 R Rn n 上的任意上的任意兩個范數(shù)，則存在常數(shù)兩個范數(shù)，則存在常數(shù) c c1 1 和和 c c2 2 ，使得對，使得對任意的任意的 x x R Rn n 有有12stscxxcx6范數(shù)性質(zhì)范數(shù)性質(zhì)(3) Cauchy-Schwarz 不等式不等式(4) 向量序列的收斂性向量序列的收斂性( )lim*kkxx 22( , )x yxy( )lim*0kkxx7矩陣范數(shù)矩陣范數(shù)設(shè)函數(shù)設(shè)函數(shù) f : Rn n R，若，若 f 滿足滿足(1) f(A) 0， A Rn n , 且且 f(A) = 0 A = 0(2) f( A) = | | f(A) ， A

4、 Rn , R (3) f(A+B) f(A) + f(B)(4) f(AB) f(A)f(B)則稱則稱 f 為為 Rn n 上的（矩陣）范數(shù)，通常記為上的（矩陣）范數(shù)，通常記為 | | n 矩陣范數(shù)矩陣范數(shù)8矩陣范數(shù)矩陣范數(shù)n 常見的矩陣范數(shù)常見的矩陣范數(shù)(1) F-范數(shù)范數(shù) (Frobenious 范數(shù)范數(shù))12211nnijFijAa (2) 算子范數(shù)算子范數(shù) (從屬范數(shù)、誘導(dǎo)范數(shù)從屬范數(shù)、誘導(dǎo)范數(shù))其中其中 | | 是是 Rn 上的任意一個范數(shù)上的任意一個范數(shù)10supmaxnxx RxAxAAxx 9算子范數(shù)算子范數(shù)111maxnijj niAa n 常見的算子范數(shù)常見的算子范數(shù)2(

5、)TAA A 無窮范數(shù)（行范數(shù)）無窮范數(shù)（行范數(shù)） 2-范數(shù)（譜范數(shù)）范數(shù)（譜范數(shù)） 1-范數(shù)（列范數(shù)）范數(shù)（列范數(shù)）11maxniji njAa ,max)()(21nAAA的譜半徑，即為10算子范數(shù)算子范數(shù)例例求矩陣求矩陣A A的各種常用范數(shù)的各種常用范數(shù)110121021A解解:1Aniijnja11max25234252 ,5 ,2max1njAnjijnia11max42 ,4 ,3max1ni2A)(maxAAT由于由于11的特征值因此先求AATAAT110121021110122011211190102特征方程為特征方程為)det(AAIT2111901020的特征值為可得AAT

6、9361. 0,9211. 2,1428. 9321121428. 9)(maxAAT2A)(maxAAT0237. 3FA)(AAtrT2926056. 31AA2AFA容易計算容易計算計算較復(fù)雜計算較復(fù)雜對矩陣元素的對矩陣元素的變化比較敏感變化比較敏感不是從屬范數(shù)不是從屬范數(shù)較少使用較少使用性質(zhì)較好性質(zhì)較好13矩陣范數(shù)性質(zhì)矩陣范數(shù)性質(zhì)n 矩陣范數(shù)的性質(zhì)矩陣范數(shù)的性質(zhì)(1) (1) 連續(xù)性：連續(xù)性：設(shè)設(shè) f f 是是 R Rn n n n 上的任一矩陣范數(shù)，則上的任一矩陣范數(shù)，則 f f 關(guān)于關(guān)于 A A 的每個分量是連續(xù)的的每個分量是連續(xù)的(2) (2) 等價性：等價性：設(shè)設(shè) |s s 和

7、和 |t t 是是 R Rn n n n 上上的任意兩個矩陣范數(shù)，則存在常數(shù)的任意兩個矩陣范數(shù)，則存在常數(shù) c c1 1 和和 c c2 2 ，使，使得對任意的得對任意的 A A R Rn n n n 有有12stscAAcA14定理：定理：（相容性條件）相容性條件）設(shè)設(shè) | | 是是 Rn 上的任一向量上的任一向量范數(shù)，其對應(yīng)的算子范數(shù)也記為范數(shù)，其對應(yīng)的算子范數(shù)也記為 | | ，則有，則有算子范數(shù)性質(zhì)算子范數(shù)性質(zhì)AxAxn 算子范數(shù)的性質(zhì)算子范數(shù)的性質(zhì)定理：定理：設(shè)設(shè) | | 是任一算子范數(shù)，則是任一算子范數(shù)，則( )AA 15算子范數(shù)性質(zhì)算子范數(shù)性質(zhì)定理：定理：設(shè)設(shè) | | 是任一算子范

8、數(shù)，若是任一算子范數(shù)，若 |B| 1 ，則，則 IB 非奇異，且非奇異，且 111IBB 定理：定理： (特征值上界特征值上界) ) 設(shè)設(shè)則則即即 A A 的譜半徑不超過的譜半徑不超過 A A 的任何一種算子范數(shù)的任何一種算子范數(shù). . nnRAAA )(16 定理：定理：設(shè)設(shè) , , 則則 的充要條件的充要條件是是B B的譜半徑的譜半徑( )1B0()kBk n nBR17病態(tài)矩陣病態(tài)矩陣考慮線性方程組考慮線性方程組 AxAx= =b b，如果，如果 A A 或或 b b 的的微小微小變化變化會導(dǎo)致解的會導(dǎo)致解的巨大巨大變化，則稱此線性方程組是變化，則稱此線性方程組是病態(tài)病態(tài)的，的，并稱矩陣

9、并稱矩陣 A A 是是病態(tài)病態(tài)的，反之則是的，反之則是良態(tài)良態(tài)的。的。n 病態(tài)矩陣病態(tài)矩陣?yán)豪?211211.00012xx 1220 xx 122.00011211.0 010 1xx 1211xx 18定理：定理：考慮線性方程組考慮線性方程組 Ax=b，設(shè)，設(shè) A 是精確的，是精確的，b 有有微小微小的變化的變化 b，此時的解為，此時的解為 x + x ，則，則1AbxbAx 病態(tài)矩陣病態(tài)矩陣響的擾動對方程組解的影常數(shù)項b. 119設(shè)方程組設(shè)方程組 AXAX= =b b+ +b b 的解為的解為即即 ()A XXbb- -得得 A Xb即即 1XAb于是有于是有1XAb另一方面，由另一

10、方面，由得得 bA X且且0X 故故 1AXbXXX1XbAAXb由由與與有有 20定理：定理：考慮線性方程組考慮線性方程組 Ax=b，設(shè)，設(shè) b 是精確的，是精確的，A 有有微小微小的變化的變化 A，此時的解為，此時的解為 x + x ，則，則111AxAAAAxAAA l 當(dāng)當(dāng) A 充分小時，不等式右端約為充分小時，不等式右端約為1AAAA 病態(tài)矩陣病態(tài)矩陣響的擾動對方程組解的影系數(shù)矩陣A. 221q 分析表明，數(shù)分析表明，數(shù) 反映了方程組反映了方程組AXAX= =b b的解對的解對初始數(shù)據(jù)初始數(shù)據(jù)A A，b b擾動的靈敏度，可用來刻畫方程組的擾動的靈敏度，可用來刻畫方程組的病態(tài)程度病態(tài)程

11、度。 1AAn 矩陣的矩陣的條件數(shù)條件數(shù)定義：設(shè)定義：設(shè) A 非奇異，則稱非奇異，則稱為為 A 的的條件數(shù)條件數(shù)。1Cond( )AAA 矩陣條件數(shù)矩陣條件數(shù)22n 條件數(shù)與范數(shù)有關(guān)，常用的有條件數(shù)與范數(shù)有關(guān)，常用的有無窮范數(shù)無窮范數(shù)和和2-范數(shù)范數(shù)l Cond(A)2 稱為稱為譜條件數(shù)譜條件數(shù)，當(dāng)，當(dāng) A 對稱時有對稱時有1Cond( )AAA 1222Cond( )AAA 121maxCond( )minii nii nA 矩陣條件數(shù)矩陣條件數(shù)23條件數(shù)性質(zhì)條件數(shù)性質(zhì)n 條件數(shù)的性質(zhì)條件數(shù)的性質(zhì)(1) Cond(A) 1(2) Cond( A)=Cond(A), 其中其中 為任意非零實數(shù)為

12、任意非零實數(shù)(3) 若若 R 是正交矩陣，則是正交矩陣，則 Cond(R)2=1(4) 若若 R 是正交矩陣，則對任意非奇異矩陣是正交矩陣，則對任意非奇異矩陣 A，有，有 Cond(AR)2=Cond(RA)2=Cond(A)224舉例舉例例：例：計算計算 Cond(Hk) 其中其中 H 為為 Hilbert 矩陣矩陣解：解：k=1 時，時， Cond(H1) =1k=2 時，時，Cond(H2) =2712211/ 246, 1/ 21/ 3612HH k=3 時，時，Cond(H3) =74813211/ 21/ 3936301/ 21/ 31/ 4 , 361921801/ 31/ 41

13、/ 530180180HH Cond(H4) =28375Cond(H10) =3.5 101325for i=3:10 h=hilb(i); condA(i)=cond(h,2); %cond(h,inf)enddisp(n cond);for i=3:10 s=sprintf(%d %f,i,condA(i); disp(s);end運行后得到如下結(jié)果運行后得到如下結(jié)果:n cond3 524.0567784 15513.7387395 476607.2502426 14951058.6410057 475367356.37039387723649 4931539

14、86466.27094010 16025391750078.617000華長生制作26,783.008.183.1200.0250.0333.0250.0333.0500.0333.0500.000.1332211xxxxxx簡記為簡記為 .)(33bbxxHHbxHT3)60/47,12/13, 6/11( 方程組方程組 與與(6.8)(6.8)的精確解分別為的精確解分別為bxH3%,02.01018.0333HHT)4910. 0,5120. 0,0895. 0(x.)491002798. 1,487967062. 0,089512538. 1 (T xx,) , 1, 1, 1 (Tx華

15、長生制作27%182. 0bb%.2 .51xx 這就是說這就是說 與與 相對誤差不超過相對誤差不超過 ，而引起解的相，而引起解的相對誤差超過對誤差超過 . . 3Hb%30%5028 利用定義判斷一個方程組是否病態(tài)，需要計算利用定義判斷一個方程組是否病態(tài)，需要計算矩陣的條件數(shù)，從而涉及計算逆矩陣，極不方便矩陣的條件數(shù)，從而涉及計算逆矩陣，極不方便。注注q 用選主元消去法消元中出現(xiàn)小主元；用選主元消去法消元中出現(xiàn)小主元；q系數(shù)行列式的絕對值相對地很小系數(shù)行列式的絕對值相對地很小q系數(shù)矩陣元素間數(shù)量級上相差很大且無一定規(guī)律；系數(shù)矩陣元素間數(shù)量級上相差很大且無一定規(guī)律；q出現(xiàn)了相對地很大的解。出現(xiàn)

16、了相對地很大的解。當(dāng)出現(xiàn)下列情況之一時，方程組很當(dāng)出現(xiàn)下列情況之一時，方程組很可能病態(tài)可能病態(tài)： 方程組的病態(tài)性質(zhì)，是方程組本身的特性。對于方程組的病態(tài)性質(zhì)，是方程組本身的特性。對于病態(tài)方程組，用一般的求解方法不易求得較精確的解，而病態(tài)方程組，用一般的求解方法不易求得較精確的解，而且病態(tài)越嚴(yán)重，求解越困難。且病態(tài)越嚴(yán)重，求解越困難。29迭代迭代 改善改善(Iterative refinement)：設(shè)設(shè)Ax=b Ax=b ，其中，其中A A為非奇異矩陣，且為病態(tài)方程組為非奇異矩陣，且為病態(tài)方程組( (但不但不過分病態(tài)過分病態(tài)) ). Step 1:近似解近似解 bxA;1xStep 2:;11

17、xAbr Step 3:;111drdA Step 4:;112dxx If is exact solution，thenOtherwise go to step 2Otherwise go to step 21dbAxAbAxx11112)( 2x經(jīng)驗表明經(jīng)驗表明：若若 A 不是非常病態(tài)（例如：不是非常病態(tài)（例如： ），），則如此迭代可達(dá)到機(jī)器精度；但若則如此迭代可達(dá)到機(jī)器精度；但若 A 病態(tài)，則此算法也病態(tài)，則此算法也不能改進(jìn)。不能改進(jìn)。1)( Acond Approximate solution by Guassian elimination華長生制作30向后誤差估計向后誤差估計(Backward error analysis)(Backward error analysis)設(shè)設(shè) 為方程組為方程組Ax=bAx=b的近似解，于是可計算的近似解，于是可計算 的剩余向的剩余向量量 ，