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

1、1第五章第五章線性方程組直接解法線性方程組直接解法 誤差估計(jì)誤差估計(jì)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 誤差估計(jì)誤差估計(jì)3向量范數(shù)向量范數(shù)設(shè)函數(shù)設(shè)函數(shù) f : Rn R，若，若 f 滿足滿足(1) f(x) 0， x Rn , 等號(hào)當(dāng)且僅當(dāng)?shù)忍?hào)當(dāng)且僅當(dāng) x = 0 時(shí)成立時(shí)成立(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 無(wú)窮范數(shù)（最大范數(shù)）無(wú)窮范數(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 上的任意一個(gè)范數(shù)，則上的任意一個(gè)范數(shù)，則 f f 關(guān)于關(guān)于 x x 的每個(gè)分量是連續(xù)的的每個(gè)分量是連續(xù)的(2) (2) 等價(jià)性等價(jià)性設(shè)設(shè) | |

3、|s s 和和 | | |t t 是是 R Rn n 上的任意上的任意兩個(gè)范數(shù)，則存在常數(shù)兩個(gè)范數(shù)，則存在常數(shù) c c1 1 和和 c c2 2 ，使得對(duì)，使得對(duì)任意的任意的 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 上的任意一個(gè)范數(shù)上的任意一個(gè)范數(shù)10supmaxnxx RxAxAAxx 9算子范數(shù)算子范數(shù)111maxnijj niAa n 常見的算子范數(shù)常見的算子范數(shù)2(

5、)TAA A 無(wú)窮范數(shù)（行范數(shù)）無(wú)窮范數(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容易計(jì)算容易計(jì)算計(jì)算較復(fù)雜計(jì)算較復(fù)雜對(duì)矩陣元素的對(duì)矩陣元素的變化比較敏感變化比較敏感不是從屬范數(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 的每個(gè)分量是連續(xù)的的每個(gè)分量是連續(xù)的(2) (2) 等價(jià)性：等價(jià)性：設(shè)設(shè) |s s 和

7、和 |t t 是是 R Rn n n n 上上的任意兩個(gè)矩陣范數(shù)，則存在常數(shù)的任意兩個(gè)矩陣范數(shù)，則存在常數(shù) c c1 1 和和 c c2 2 ，使，使得對(duì)任意的得對(duì)任意的 A A R Rn n n n 有有12stscAAcA14定理：定理：（相容性條件）相容性條件）設(shè)設(shè) | | 是是 Rn 上的任一向量上的任一向量范數(shù)，其對(duì)應(yīng)的算子范數(shù)也記為范數(shù)，其對(duì)應(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 的的微小微小變化變化會(huì)導(dǎo)致解的會(huì)導(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，此時(shí)的解為，此時(shí)的解為 x + x ，則，則1AbxbAx 病態(tài)矩陣病態(tài)矩陣響的擾動(dòng)對(duì)方程組解的影常數(shù)項(xiàng)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，此時(shí)的解為，此時(shí)的解為 x + x ，則，則111AxAAAAxAAA l 當(dāng)當(dāng) A 充分小時(shí)，不等式右端約為充分小時(shí)，不等式右端約為1AAAA 病態(tài)矩陣病態(tài)矩陣響的擾動(dòng)對(duì)方程組解的影系數(shù)矩陣A. 221q 分析表明，數(shù)分析表明，數(shù) 反映了方程組反映了方程組AXAX= =b b的解對(duì)的解對(duì)初始數(shù)據(jù)初始數(shù)據(jù)A A，b b擾動(dòng)的靈敏度，可用來(lái)刻畫方程組的擾動(dòng)的靈敏度，可用來(lái)刻畫方程組的病態(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)，常用的有無(wú)窮范數(shù)無(wú)窮范數(shù)和和2-范數(shù)范數(shù)l Cond(A)2 稱為稱為譜條件數(shù)譜條件數(shù)，當(dāng)，當(dāng) A 對(duì)稱時(shí)有對(duì)稱時(shí)有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í)數(shù)為

12、任意非零實(shí)數(shù)(3) 若若 R 是正交矩陣，則是正交矩陣，則 Cond(R)2=1(4) 若若 R 是正交矩陣，則對(duì)任意非奇異矩陣是正交矩陣，則對(duì)任意非奇異矩陣 A，有，有 Cond(AR)2=Cond(RA)2=Cond(A)224舉例舉例例：例：計(jì)算計(jì)算 Cond(Hk) 其中其中 H 為為 Hilbert 矩陣矩陣解：解：k=1 時(shí)，時(shí)， Cond(H1) =1k=2 時(shí)，時(shí)，Cond(H2) =2712211/ 246, 1/ 21/ 3612HH k=3 時(shí)，時(shí)，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運(yùn)行后得到如下結(jié)果運(yùn)行后得到如下結(jié)果:n cond3 524.0567784 15513.7387395 476607.2502426 14951058.6410057 475367356.37039387723649 4931539

14、86466.27094010 16025391750078.617000華長(zhǎng)生制作26,783.008.183.1200.0250.0333.0250.0333.0500.0333.0500.000.1332211xxxxxx簡(jiǎn)記為簡(jiǎn)記為 .)(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、長(zhǎng)生制作27%182. 0bb%.2 .51xx 這就是說這就是說 與與 相對(duì)誤差不超過相對(duì)誤差不超過 ，而引起解的相，而引起解的相對(duì)誤差超過對(duì)誤差超過 . . 3Hb%30%5028 利用定義判斷一個(gè)方程組是否病態(tài)，需要計(jì)算利用定義判斷一個(gè)方程組是否病態(tài)，需要計(jì)算矩陣的條件數(shù)，從而涉及計(jì)算逆矩陣，極不方便矩陣的條件數(shù)，從而涉及計(jì)算逆矩陣，極不方便。注注q 用選主元消去法消元中出現(xiàn)小主元；用選主元消去法消元中出現(xiàn)小主元；q系數(shù)行列式的絕對(duì)值相對(duì)地很小系數(shù)行列式的絕對(duì)值相對(duì)地很小q系數(shù)矩陣元素間數(shù)量級(jí)上相差很大且無(wú)一定規(guī)律；系數(shù)矩陣元素間數(shù)量級(jí)上相差很大且無(wú)一定規(guī)律；q出現(xiàn)了相對(duì)地很大的解。出現(xiàn)

16、了相對(duì)地很大的解。當(dāng)出現(xiàn)下列情況之一時(shí)，方程組很當(dāng)出現(xiàn)下列情況之一時(shí)，方程組很可能病態(tài)可能病態(tài)： 方程組的病態(tài)性質(zhì)，是方程組本身的特性。對(duì)于方程組的病態(tài)性質(zhì)，是方程組本身的特性。對(duì)于病態(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)驗(yàn)表明經(jīng)驗(yàn)表明：若若 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華長(zhǎng)生制作30向后誤差估計(jì)向后誤差估計(jì)(Backward error analysis)(Backward error analysis)設(shè)設(shè) 為方程組為方程組Ax=bAx=b的近似解，于是可計(jì)算的近似解，于是可計(jì)算 的剩余向的剩余向量量 ，