數(shù)值分析(10) 誤差分析和解的精度改進(jìn)

1、數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 第四節(jié)第四節(jié) 誤差分析和解的精度改進(jìn)誤差分析和解的精度改進(jìn)一、解的誤差分析基本問題一、解的誤差分析基本問題解的穩(wěn)定性解的穩(wěn)定性二二、方方程程組組的的狀狀態(tài)態(tài)和和條條件件數(shù)數(shù)三三、數(shù)數(shù)值值穩(wěn)穩(wěn)定定性性及及解解的的精精度度改改進(jìn)進(jìn)四四、病病態(tài)態(tài)方方程程組組的的處處理理數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析一、解的誤差分析基本問題一、解的誤差分析基本問題解的穩(wěn)定性解的穩(wěn)定性,Axb 用用直直接接法法求求解解，得得到到的的是是帶帶有有誤誤差差的的計(jì)計(jì)算算解解（數(shù)數(shù)值值解解）誤誤差差產(chǎn)產(chǎn)生生的的原原因因主主要要有有兩兩個(gè)個(gè)：1,()(),A bAbAA xxbbAb（ ）一一

2、般般原原始始數(shù)數(shù)據(jù)據(jù)都都帶帶有有誤誤差差，因因此此實(shí)實(shí)際際解解的的方方程程組組是是近近似似方方程程組組將將對對解解的的精精度度產(chǎn)產(chǎn)生生影影響響。2（ ）計(jì)計(jì)算算過過程程中中，舍舍入入誤誤差差的的傳傳播播和和積積累累將將影影響響解解的的精精度度。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析12解解的的穩(wěn)穩(wěn)定定性性：“小小的的誤誤差差會會不不會會引引起起解解的的很很大大變變化化”有有兩兩種種解解的的穩(wěn)穩(wěn)定定性性概概念念：（）數(shù)數(shù)值值方方法法的的穩(wěn)穩(wěn)定定性性：與與數(shù)數(shù)值值方方法法有有關(guān)關(guān)。（）數(shù)數(shù)學(xué)學(xué)穩(wěn)穩(wěn)定定性性：是是由由數(shù)數(shù)學(xué)學(xué)問問題題本本身身故故有有屬屬性性所所決決定定的的，與與數(shù)數(shù)值值方方法法無無關(guān)關(guān)。即

3、即通通常常所所說說的的“病病態(tài)態(tài)問問題題”和和“良良態(tài)態(tài)問問題題”。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 數(shù)學(xué)穩(wěn)定性數(shù)學(xué)穩(wěn)定性: :對數(shù)學(xué)問題而言，如果輸入數(shù)據(jù)有對數(shù)學(xué)問題而言，如果輸入數(shù)據(jù)有微小擾動，引起輸出數(shù)據(jù)（即數(shù)學(xué)問題的解）有很微小擾動，引起輸出數(shù)據(jù)（即數(shù)學(xué)問題的解）有很大擾動，則稱數(shù)學(xué)問題是大擾動，則稱數(shù)學(xué)問題是病態(tài)問題病態(tài)問題，否則稱為，否則稱為良態(tài)良態(tài)問題問題。 數(shù)值方法的穩(wěn)定性數(shù)值方法的穩(wěn)定性: :一個(gè)算法如果輸入數(shù)據(jù)有擾一個(gè)算法如果輸入數(shù)據(jù)有擾動（即有誤差），而計(jì)算過程中舍入誤差不增長，動（即有誤差），而計(jì)算過程中舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則稱此算法為不穩(wěn)定則稱此

4、算法是數(shù)值穩(wěn)定的，否則稱此算法為不穩(wěn)定的。的。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析151210.31032105(1)(0,0.333) ,(1.0,1.667)(2)(0.0333,0.333) ,(1.0,2. )10TTTTxxxAxxAx 順順序序消消元元列列主主元元消消元元例例151210.3102.999210.0014.999(3)(0.0333,0.334) ,(1.0,2.0)TTxxxAx 列列主主元元消消元元數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析120.7800.5630.2170.9130.6590.254(1)(1.0, 1.0)(0.217,0.254)(2)(1.0, 1.

5、0)(0.217,0.254)2TTTTxxxAxxAx 順順序序消消元元列列主主元元消消元元例例120.78010.56290.2170.91300.65910.254(3)(0.2528,0.0352)(0.217,0.254)(4)(0.341, 0.08)(0.217,0.254)TTTTxxxAxxAx 列列主主元元消消元元列列主主元元消消元元數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析120.7800.5630.21720.9130.6590.2541(5)(176.500, 105.60)(0.2171,0.2547)TTxxxAx 列列主主元元消消元元120.7800.5630.2170.

6、9130.6590.254(1)(1.0, 1.0)(0.217,0.254)(2)(1.0, 1.0)(0.217,0.254)2TTTTxxxAxxAx 順順序序消消元元列列主主元元消消元元例例數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析|1.|xxxxxxrbAxbbx 解解的的相相對對誤誤差差不不知知道道是是否否可可改改用用相相對對剩剩余余量量來來估估計(jì)計(jì)誤誤差差兩兩種種誤誤差差估估用用計(jì)計(jì)即即代代替替二二、方方程程組組的的狀狀態(tài)態(tài)和和條條件件數(shù)數(shù)由由前前面面例例子子說說明明是是不不可可以以的的。為為什什么么？下下面面我我們們來來證證明明事事后后誤誤差差估估計(jì)計(jì)。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1

7、1*rArAebAbxA 將將上上兩兩式式合合并并就就推推出出*,()exxrbAxAxAxA xxAe 事事后后誤誤差差估估記記計(jì)計(jì)1rbAxAeeA r 由由和和可可得得到到,1rAeAr *1*1,bAxb xA bxAbA 由由得得，數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1*erA Abx 得得到到事事后后誤誤差差估估計(jì)計(jì)1,.A A 當(dāng)當(dāng)很很大大時(shí)時(shí) 不不能能用用相相對對剩剩余余量量來來估估計(jì)計(jì)解解的的相相對對誤誤差差數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 | | |bAx 又又1,0bbA 先先驗(yàn)驗(yàn)誤誤差差估估計(jì)計(jì)：（ ）只只有有 有有擾擾動動bAxbxAbbxxAbAx 1)( 相相減減得得

8、|1bAx 11| | |AbxbAAbxbA 解解的的相相對對誤誤差差估估計(jì)計(jì)式式數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析111| | 1| |1 |,|20AAbAAAAAxAxAA 當(dāng)當(dāng)時(shí)時(shí)，解解的的相相對對誤誤差差（ ）只只有有擾擾動動估估計(jì)計(jì)式式為為有有1| | 130,0AAAb 當(dāng)當(dāng)時(shí)時(shí)，解解的的相相對對（ ）誤誤差差估估計(jì)計(jì)式式為為1*1()1AbA AxAbxAA 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析.,1, 1max0是非奇異的是非奇異的時(shí)時(shí)當(dāng)當(dāng)因此因此與所設(shè)矛盾與所設(shè)矛盾由范數(shù)定義由范數(shù)定義AIAxAxAx 1,1,11()11n nARAIAIAAA 若若則則是是非非奇奇異異陣陣

9、且且有有引引理理000(1),()0,0:,.IAIA xxAxx 假假設(shè)設(shè)是是奇奇異異陣陣 則則有有非非零零解解 即即證證明明 用用反反法法存存在在證證使使100 xAx于是于是數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析AAI 11)(1即即)()()()(1,)()()2(111AIAIAIAIIAIAII 有有兩邊取范數(shù)兩邊取范數(shù)又由又由1)(11 AIA得得到到1111()()()()IAIIAAIAIIAA 再再利利用用有有證畢證畢數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1*1()1AbA AxAbxAA 下下面面證證明明相相對對誤誤差差估估計(jì)計(jì)式式*, ()()(): AxbAAxxbbAAxbAx

10、 兩兩式式相相減減得得證證明明111,().AAIAA 設(shè)設(shè)由由引引理理知知非非奇奇異異11111)()(,)( AAAIAAAAIAAA 有有也也非非奇奇異異于于是是111*()()xIAAAbAx 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析111*1*1()()()1由引理的估計(jì)式得到xIAAAbAxAbxAxAA bAxxAb *1, 即即由由AAbbAAAAxx 11*1)( 得得到到數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析:(),.Acond AAAxb 若若線線性性代代數(shù)數(shù)方方程程組組的的系系數(shù)數(shù)矩矩陣陣 的的條條件件數(shù)數(shù)相相對對很很大大 稱稱 對對求求解解線線性性代代數(shù)數(shù)方方程程組組是是病病態(tài)態(tài)的

11、的矩矩陣陣 方方程程組組稱稱為為病病態(tài)態(tài)方方程程組組反反之之則則定定稱稱其其為為良良態(tài)態(tài)的的義義11:2,).(nAA AAcond AA A 對對非非奇奇異異 階階方方陣陣稱稱量量為為矩矩陣陣 的的條條件件數(shù)數(shù)記記為為矩矩陣陣的的條條件件數(shù)數(shù)定定義義11:.,.,.A AA A 大大致致是是實(shí)實(shí)際際誤誤差差對對原原始始誤誤差差的的放放大大倍倍數(shù)數(shù)于于是是這這個(gè)個(gè)數(shù)數(shù)學(xué)學(xué)量量定定量量的的刻刻畫畫了了方方程程組組對對原原始始誤誤差差的的敏敏感感程程度度即即 病病態(tài)態(tài) 程程度度由由此此 定定義義矩矩由由先先驗(yàn)驗(yàn)估估計(jì)計(jì)式式說說明明陣陣的的條條件件數(shù)數(shù)數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1.( )1,2

12、.( ),Cond AAAxbCond AAAxb 當(dāng)當(dāng)是是病病態(tài)態(tài)矩矩陣陣是是病病態(tài)態(tài)方方程程幾幾點(diǎn)點(diǎn)注注意意：組組。當(dāng)當(dāng)較較小小時(shí)時(shí)是是良良態(tài)態(tài)矩矩陣陣是是良良態(tài)態(tài)方方程程組組。3.( )4.( )Cond AACond A與與矩矩陣陣 本本身身的的結(jié)結(jié)構(gòu)構(gòu)有有關(guān)關(guān)，與與其其他他任任何何外外部部因因素素?zé)o無關(guān)關(guān)。條條件件數(shù)數(shù)的的大大小小沒沒有有絕絕對對的的標(biāo)標(biāo)準(zhǔn)準(zhǔn)，與與方方陣陣的的階階數(shù)數(shù)有有關(guān)關(guān)。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析11111( )( )cond AAAcond AAA 通常使用的條件數(shù)有通常使用的條件數(shù)有1max1222min()( )()TTnA Acond AAAA A

13、 譜條件數(shù)譜條件數(shù)22maxmin,( )( )( ):.TAA AAcond AAA 當(dāng)當(dāng) 為為非非奇奇異異的的實(shí)實(shí)對對稱稱陣陣時(shí)時(shí) 因因注注意意 譜譜條條件件數(shù)數(shù)在在理理論論上上有有重重要要意意義義111maxmax2minmin()()111()()TTTTnAAAAAAAA A證：證：數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析111( )1,1Acond AIAAIAAA A 對對任任何何條條件件數(shù)數(shù)的的性性質(zhì)質(zhì)非非奇奇異異陣陣 都都有有222maxmax22,.,()()()()()TTTAQcond QAcond AQcond AQAA Q QAA AA 對對非非奇奇異異陣陣 作作正正交交變

14、變換換后后 譜譜條條件件數(shù)數(shù)不不變變即即若若正正交交陣陣 則則為為 11,0,()( )ppppkcond kAkAkAAAcond A 矩矩陣陣乘乘非非零零的的常常數(shù)數(shù)后后條條件件數(shù)數(shù)不不變變1,( )1,1,2,pIcond Ip 單單位位陣陣 的的條條件件數(shù)數(shù)為為數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1,2以以上上說說明明，正正交交變變換換在在數(shù)數(shù)值值計(jì)計(jì)算算中中有有很很好好的的數(shù)數(shù)值值穩(wěn)穩(wěn)定定性性。（ ）對對矩矩陣陣的的正正交交變變換換不不改改變變矩矩陣陣的的譜譜條條件件數(shù)數(shù) 正正交交矩矩陣陣的的條條件件數(shù)數(shù)達(dá)達(dá)到到最最小小。（ ）對對有有誤誤差差的的向向量量（矩矩陣陣），正正交交變變化化后

15、后按按譜譜范范數(shù)數(shù)不不會會增增加加誤誤差差。1)()()()()(minmaxminmax2 IIQQQQQcondTT 21.,()1.Qcond Q 正正交交陣陣的的譜譜條條件件數(shù)數(shù)等等于于即即若若 是是正正交交陣陣 則則數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析22|n nARAAAQA QA Q AQ AA 同同樣樣，對對有有，則則，且且正正交交變變換換后后，誤誤差差也也沒沒有有增增加加。22,|()()() () |TTTQ xQxQ xx Q Qxxxx 其其中中是是的的誤誤差差 且且即即正正交交變變換換后后，沒沒有有增增加加誤誤差差。在正交變換下，誤差不增長在正交變換下，誤差不增長,nn

16、nxRxxxxQRQxQxQ x 對對有有誤誤差差，用用正正交交陣陣作作變變換換，數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2.(1)(2)(3)Axb 解解的的精精度度改改進(jìn)進(jìn)雙雙在在良良態(tài)態(tài)下下，用用穩(wěn)穩(wěn)定定的的數(shù)數(shù)值值方方法法求求解解，也也總總是是會會有有誤誤差差的的，可可用用以以下下方方法法改改進(jìn)進(jìn)計(jì)計(jì)算算解解的的精精度度。用用雙雙精精度度計(jì)計(jì)算算，有有效效數(shù)數(shù)字字增增加加了了，舍舍入入誤誤差差自自然然會會減減少少。精精度度改改善善：（行行）比比例例增增減減改改善善迭迭代代改改善善三三、數(shù)數(shù)值值穩(wěn)穩(wěn)定定性性及及解解的的精精度度改改進(jìn)進(jìn)1.Axb 結(jié)結(jié)論論：直直接接法法解解，用用順順序序消消元元是

17、是不不穩(wěn)穩(wěn)定定，而而用用選選主主元元（列列主主元元）是是數(shù)數(shù)值值穩(wěn)穩(wěn)定定性性穩(wěn)穩(wěn)定定的的。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 前面介紹的列主元法解決了前面介紹的列主元法解決了GaussGauss消元法由于小主元的出消元法由于小主元的出現(xiàn)所導(dǎo)致的舍入誤差的積累，從而出現(xiàn)的失真的問題。但列主現(xiàn)所導(dǎo)致的舍入誤差的積累，從而出現(xiàn)的失真的問題。但列主元法也有缺點(diǎn)，當(dāng)方程中出現(xiàn)比例因子時(shí)，列主元法就無能為元法也有缺點(diǎn)，當(dāng)方程中出現(xiàn)比例因子時(shí)，列主元法就無能為力了。力了。41212121011,02xxGaussxxxx 法法求求解解，失失真真列主元法求解列主元法求解x1 1= =x2 2=1=1377121

18、2121010101,02xxxxxx 列列主主元元法法求求解解，失失真真 按行比例按行比例消元法消元法 : :將每個(gè)方程乘上一個(gè)適當(dāng)?shù)谋壤蜃?，使將每個(gè)方程乘上一個(gè)適當(dāng)?shù)谋壤蜃?，使方程組的最大系數(shù)的絕對值不超過方程組的最大系數(shù)的絕對值不超過1 1，然后再做列主元消元。，然后再做列主元消元。（2）（行）比例增減改善）（行）比例增減改善數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析例例4 4 應(yīng)用按比例消元法求解應(yīng)用按比例消元法求解 方程組方程組 3321221132110410234332ExxxExxExxx2,51,43,21, 110, 4, 2331221111321 rsasasaksss對對解

19、解：2 2、在第、在第k k步消元前，選最小的步消元前，選最小的r r，使，使iiknikrrksasa max3 3、對換、對換 E Ek k E Er r , s, sk k s sr r 4 4、消元、消元 具體步驟如下：具體步驟如下：1 1、在第一步消元前，計(jì)算、在第一步消元前，計(jì)算niasijnji,2,1max1 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析得得：2323332222, 315113022,3123/22ssEErsasak 10211141178432234322321084322434312333232121333222321121 xxxExExxExxsExxsExxs

20、Exx解解得得：消消元元，得得12121211221231232123323312334334322323210410224834,2,10EEssxxExxExxxExxExxxExxEsss 對對換換，得得：消消元元，得得數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析算法算法 按行比例列主元高斯消元法解線性方程組按行比例列主元高斯消元法解線性方程組 Ax = bAx = b停停機(jī)機(jī)。信信息息輸輸出出失失敗敗則則認(rèn)認(rèn)為為如如果果使使確確定定、選選列列主主元元步步。循循環(huán)環(huán)執(zhí)執(zhí)行行到到第第對對、, , 0det , 0 ,max 2 51, 2 , 1 , 1,max, 1det 1 1 kikiiikni

21、kikikijnjikkkkaaSaSainkniaS kkkikikjikjkSSbbnkkjaaki detdet , ), 1,( , 4 , 3否否則則交交換換行行步步轉(zhuǎn)轉(zhuǎn)出出執(zhí)執(zhí)行行第第、如如果果數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析。、輸輸出出解解向向量量、否否則則停停機(jī)機(jī)。輸輸出出失失敗敗信信息息則則認(rèn)認(rèn)為為如如果果、回回代代求求解解、FTnnniinijjijiinnnnnnnnkkAAbbbxanniababbabbaaadet, ,),( 8detdet7)1 , 2 , 2, 1( / )( / , 0,6detdet 5211 (3) ), 1( (2) /(1) , 2,

22、14kikiikjikijijkkikikikbabbnkjaaaaaamankki 、消消元元計(jì)計(jì)算算數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析,(3)Axbxxxxxxxx 求求解解，迭迭代代改改善善計(jì)計(jì)算算解解 有有誤誤差差則則精精確確解解,()()xAxbAxA xxbA xbA xbA xxbAx 以以上上未未知知，但但由由可可得得到到A xbbAxrxxxx 解方程組解出解方程組解出就得到改進(jìn)解就得到改進(jìn)解這個(gè)過程可以用迭代方法重復(fù)進(jìn)行，這就是這個(gè)過程可以用迭代方法重復(fù)進(jìn)行，這就是計(jì)算解的迭代改善法（余量校正法）。計(jì)算解的迭代改善法（余量校正法）。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析rbAxA

23、xrxxx 迭迭代代改改善善法法：迭代改善的計(jì)算格式：迭代改善的計(jì)算格式：(1)()()()(1)()()0Pr(1, 2,.)kkkkkkxbAxLYUxYxxxk ( (k k) )取取r r(1)1x 問問題題： 可可否否取取數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析det( ),1.1AA如如數(shù)數(shù)量量級級差差別別大大，分分布布零零亂亂，特特病病態(tài)態(tài)問問題題的的識識別別：有有以以下下幾幾種種方方法法（）由由 的的直直觀觀信信息息，判判斷斷病病態(tài)態(tài)的的可可能能征征值值分分布布分分散散，的的大大小小 但但都都只只是是性性?？煽赡苣苄孕?。 12(,)det( ),( ),( ),.,( ),1,2,.,

24、m nn nniARARAr AAcond Air 這這是是關(guān)關(guān)于于數(shù)數(shù)學(xué)學(xué)穩(wěn)穩(wěn)定定性性的的問問題題刻刻畫畫矩矩陣陣固固有有屬屬性性的的量量有有：奇奇異異值值這這些些量量從從不不同同角角四四、病病態(tài)態(tài)方方程程組組度度考考察察矩矩的的處處理理陣陣的的好好壞壞。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析10 10111011001det( )1( )5120ARACond A 如：如：100 10010012121det( )( )12ARACond A 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(2)( )Cond A 有有一一些些近近似似方方法法，帶帶有有經(jīng)經(jīng)驗(yàn)驗(yàn)性性，但但不不增增估估計(jì)計(jì)加加計(jì)計(jì)算算量量。(3)

25、()AxbAA xbxx 比比較較所所得得結(jié)結(jié)果果， 與與 相相差差大大，試試算算和和則則病病態(tài)態(tài)。111111,()| | | |AxbAAAAxbAxbxA bA AxAAA xxAAxxxAAxxxAAx 對對有有小小擾擾動動由由1| |( )|,( ),|xxAAACond AAxxxACond AAx 得得到到若若大大 則則大大 因因?yàn)闉樾⌒?。?shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析病態(tài)嚴(yán)重：病態(tài)嚴(yán)重：1:1:正交分解正交分解2:2:A A的奇異值分解。的奇異值分解。輕度病態(tài)：輕度病態(tài)：1:1:雙精度改善雙精度改善2:2:比例增減改善比例增減改善3:3:迭代改善。迭代改善。2.解的精度改進(jìn)解的精度改進(jìn)數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析證明證明：病態(tài)的程度。病態(tài)的程度。接近奇異接近奇異的大小可作為度量矩陣的大小可作為度量矩陣最小的奇異值最小的奇異值分解分解的的nnTTnAAAAAconddiagVUASVDA 1minmax221)()()(),.,(,)