第一節(jié)誤差的基本概念

1、數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系第一節(jié)第一節(jié) 誤誤 差差定義：定義：數(shù)值計(jì)算方法是計(jì)算數(shù)學(xué)的一個(gè)分支數(shù)值計(jì)算方法是計(jì)算數(shù)學(xué)的一個(gè)分支, 又稱又稱數(shù)值分析或計(jì)算方法數(shù)值分析或計(jì)算方法, 它是研究用數(shù)字計(jì)算機(jī)求解它是研究用數(shù)字計(jì)算機(jī)求解各種數(shù)學(xué)問題的數(shù)值方法及其理論的一門學(xué)科各種數(shù)學(xué)問題的數(shù)值方法及其理論的一門學(xué)科, 是是程序設(shè)計(jì)和對數(shù)值結(jié)果進(jìn)行分析的依據(jù)和基礎(chǔ)。程序設(shè)計(jì)和對數(shù)值結(jié)果進(jìn)行分析的依據(jù)和基礎(chǔ)。應(yīng)用計(jì)算機(jī)解決科學(xué)技術(shù)和工程問題的步驟：應(yīng)用計(jì)算機(jī)解決科學(xué)技術(shù)和工程問題的步驟： (1) 提出實(shí)際問題提出實(shí)際問題 (2) 建立數(shù)學(xué)模型建立數(shù)學(xué)模型 (3) 選用數(shù)值計(jì)算方法選用數(shù)值計(jì)算方法 (4) 編

2、程上機(jī)計(jì)算得出數(shù)據(jù)結(jié)果。編程上機(jī)計(jì)算得出數(shù)據(jù)結(jié)果。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系一、誤差的來源一、誤差的來源1. 模型誤差模型誤差:在建立數(shù)學(xué)模型過程中在建立數(shù)學(xué)模型過程中, 不可能將所有因素均考不可能將所有因素均考慮慮, 必然要進(jìn)行必要的簡化必然要進(jìn)行必要的簡化, 這就帶來了與實(shí)際這就帶來了與實(shí)際問題的誤差。問題的誤差。2. 觀測誤差觀測誤差: 測量已知參數(shù)時(shí)測量已知參數(shù)時(shí),數(shù)據(jù)帶來的誤差。數(shù)據(jù)帶來的誤差。3. 截?cái)嗾`差截?cái)嗾`差: 在設(shè)計(jì)算法時(shí)在設(shè)計(jì)算法時(shí),近似處理帶來的誤差。近似處理帶來的誤差。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系函數(shù)函數(shù) 用泰勒多項(xiàng)式用泰勒多項(xiàng)式)(xf)1()0(!1)0(! 21)

3、0()0()()(2nnnxfnxfxffxP 近似代替時(shí)，有誤差近似代替時(shí)，有誤差)2()()!1(1)()()(1)1( nnnnxfnxPxfxR 其中其中 在在 與與 之間。這種誤差就是截?cái)嗾`之間。這種誤差就是截?cái)嗾`差。差。 0 x例如：例如：數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系4. 舍入誤差舍入誤差: 計(jì)算機(jī)的字長是有限的計(jì)算機(jī)的字長是有限的, 每一步運(yùn)算每一步運(yùn)算 均需四舍五入均需四舍五入, 由此產(chǎn)出的誤差。由此產(chǎn)出的誤差。例如：例如：用用3.14159近似代替近似代替 , 產(chǎn)生的誤差產(chǎn)生的誤差 0000026. 014159. 3 R就是舍入誤差。就是舍入誤差。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系二

4、、浮點(diǎn)數(shù)二、浮點(diǎn)數(shù)任何一個(gè)浮點(diǎn)數(shù)均可表示為任何一個(gè)浮點(diǎn)數(shù)均可表示為UpLraaarwxptp,. 021其中，其中，r叫做這個(gè)數(shù)的基，叫做這個(gè)數(shù)的基，p是階，是一個(gè)整數(shù)，是階，是一個(gè)整數(shù)，取正數(shù)取正數(shù),負(fù)數(shù)或零。負(fù)數(shù)或零。w是尾數(shù)，由是尾數(shù)，由t位小數(shù)構(gòu)成，位小數(shù)構(gòu)成， 若若 ，則該浮點(diǎn)，則該浮點(diǎn)數(shù)為規(guī)格化浮點(diǎn)數(shù)。數(shù)為規(guī)格化浮點(diǎn)數(shù)。tirai, 2, 11001a 對于一個(gè)特定的機(jī)器，尾數(shù)的位數(shù)對于一個(gè)特定的機(jī)器，尾數(shù)的位數(shù)t是固定的，是固定的，也稱其精度有也稱其精度有t個(gè)個(gè)r進(jìn)位數(shù)字。進(jìn)位數(shù)字。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系二、誤差的基本概念二、誤差的基本概念 1. 1. 誤差和誤差限誤差和誤差

5、限 設(shè)設(shè) 是準(zhǔn)確值是準(zhǔn)確值x 的一個(gè)近似值的一個(gè)近似值, ,稱稱 為近似值為近似值 的絕對誤差的絕對誤差, , 簡稱簡稱誤差誤差. . 又簡記又簡記 . . xxxxe )( x)( xe e誤差是無法計(jì)算的誤差是無法計(jì)算的 ( (因?yàn)闇?zhǔn)確值因?yàn)闇?zhǔn)確值 x 不知道不知道), ), 但可但可以估計(jì)出它的一個(gè)上界。即以估計(jì)出它的一個(gè)上界。即 , ,稱稱 是近似值是近似值 的的絕對誤差限絕對誤差限, , 簡稱誤差限簡稱誤差限. .)( xxx )( x x誤差是有量綱的，可正可負(fù)。誤差是有量綱的，可正可負(fù)。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系2. 相對誤差和相對誤差限相對誤差和相對誤差限實(shí)際計(jì)算中實(shí)際計(jì)算中,

6、 , 由于準(zhǔn)確值由于準(zhǔn)確值 x 總是未知的總是未知的, , 且由于且由于稱稱()()re xxxexxx ()()e xe xxx ()()e xxxxx 2( ()()e xx xe x 2()1()rrexex 為近似值為近似值 的的相對誤差相對誤差。簡記為。簡記為 。 x re數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系()()re xxxexxx 相對誤差是無量綱的相對誤差是無量綱的, , 也可正可負(fù)也可正可負(fù), , 它的絕對值的它的絕對值的上界稱為該近似值的上界稱為該近似值的相對誤差限相對誤差限, , 記作記作)( xr ()()()rrxexxx 簡記為簡記為 r 即即是是 的平方項(xiàng)級的平方項(xiàng)級,

7、故當(dāng)故當(dāng) 較小時(shí)較小時(shí), 常取常取)( xer)( xer數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系三、有效數(shù)字三、有效數(shù)字005.0002.0 xx00005.0000008.0 xx 如果近似值如果近似值 的誤差限是某一位的半個(gè)單的誤差限是某一位的半個(gè)單位位, ,該位到該位到 的第一位非零數(shù)字共有的第一位非零數(shù)字共有n 位位, ,我們稱我們稱 有有n 位位有效數(shù)字有效數(shù)字。 x x x = 3.1415926535, 取取 = 3.14 時(shí)，時(shí)，x所以所以 = 3.14 作為作為的近似值的近似值, ,有有3 位有效數(shù)字；位有效數(shù)字； x而取而取 =3.1416 時(shí)時(shí), x所以所以 = 3.1416 作為作

8、為的近似值有的近似值有5 位有效數(shù)字位有效數(shù)字。 x定義：定義：例例數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系mnaaax10. 021 下面給出有效數(shù)字的另一等價(jià)定義下面給出有效數(shù)字的另一等價(jià)定義 用用 表示表示x 的近似值，并將的近似值，并將 表示成表示成 x x若其誤差限若其誤差限nmxx 1021,則稱則稱 具有具有 n 位位有效有效數(shù)字?jǐn)?shù)字, , 這里這里 m 是整數(shù)是整數(shù), a1, a2 , an 為為 09 中的一個(gè)數(shù)中的一個(gè)數(shù)字字, 且且a1 0. x定義：定義：數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系例例 = 3.1415926535 , 取取 = 3.14時(shí)，時(shí)， x 21021005.0002.0 x

9、x即即 m- n = - 2, m=1, n = 3, 所以所以 = 3.14 作為作為 近似值近似值時(shí)時(shí), , 就有就有3 位有效數(shù)字。位有效數(shù)字。 x 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系四四 誤差限與有效數(shù)字的關(guān)系誤差限與有效數(shù)字的關(guān)系證明證明mnaaax10. 021 故故111110)1(|10 mmaxa此定理說明，相對誤差是由有效數(shù)字決定的。此定理說明，相對誤差是由有效數(shù)字決定的。定理定理1 1111021)( nraxe有有n 位有效數(shù)字，位有效數(shù)字，。則其相對誤差限為則其相對誤差限為mnaaax10.021 01 a設(shè)近似值設(shè)近似值1111102110105 . 0)( nmnmraa

10、xxxxe數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 已知已知nm 1021定理定理211111(1)10102(1)mnaa 設(shè)近似值設(shè)近似值mnaaax10. 021 的相對誤差的相對誤差 ,10)1(2111*nraxe則它至少有則它至少有n 位有效數(shù)字。位有效數(shù)字。111102(1)na )( xer)( xexxxr故故 至少有至少有n 位有效數(shù)字。位有效數(shù)字。 x證明證明數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系例例解解由于由于,5204 所以所以,41 a由定理有由定理有,%1 . 0102111 na即即,81104 n得得4 n要使要使 的近似值的相對誤差限小于的近似值的相對誤差限小于0.1% ,要取幾位有

11、效數(shù)字。要取幾位有效數(shù)字。20故只要對故只要對 的近似數(shù)取的近似數(shù)取4 位有效數(shù)字位有效數(shù)字,20472. 420 因此因此,可取可取其相對誤差就可小于其相對誤差就可小于0.1%,數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 一、算術(shù)運(yùn)算的誤差一、算術(shù)運(yùn)算的誤差( *)()( *)( *)e xyd xydxdye xe y可見可見, 和、差的誤差是誤差之和、差和、差的誤差是誤差之和、差, 但是因?yàn)榈且驗(yàn)? *)( *)( *)xyxy所以和或差的誤差限是誤差限之和，以上的結(jié)論適用所以和或差的誤差限是誤差限之和，以上的結(jié)論適用于任意多個(gè)近似數(shù)的和或差。于任意多個(gè)近似數(shù)的和或差。第二節(jié)第二節(jié) 數(shù)值運(yùn)算中誤差的傳

12、播數(shù)值運(yùn)算中誤差的傳播1. 由于由于 x* 的誤差的誤差 e(x*) = x*- x 可看作是可看作是 x 的微分的微分, 即即dx = x* - x ,則：則：( *)( *)( *)e xye xe y數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系同理可得：乘、除運(yùn)算的誤差同理可得：乘、除運(yùn)算的誤差,以兩數(shù)為例寫出以兩數(shù)為例寫出112212222| | ()| | ()|,0()xxe xxe xexxx 112212222|() |(),0()xxxxxxxx 121221()()()e x xxe xxe x 121221()()()x xxxxx 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系2. x* 的相對誤差是的相對

13、誤差是*( *)lnrxxdxexdxxx 它是對數(shù)函數(shù)的微分。它是對數(shù)函數(shù)的微分。設(shè)設(shè) u = xy , 則則 lnu=lnx+lny , 因而因而dlnu = dlnx + dlny 這就是說這就是說, 乘積的相對誤差是各乘數(shù)的相對誤差之和乘積的相對誤差是各乘數(shù)的相對誤差之和,相對誤差限是各乘數(shù)的相對誤差限之和。相對誤差限是各乘數(shù)的相對誤差限之和。 r (u* ) = r (x* ) + r (y* ) 即即 er (u* ) = er (x* ) + er (y* )數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系即商的相對誤差是被除數(shù)與除數(shù)的相對誤差之差即商的相對誤差是被除數(shù)與除數(shù)的相對誤差之差, 但但相對

14、誤差限是各乘數(shù)的相對誤差限之和相對誤差限是各乘數(shù)的相對誤差限之和. 由此可得由此可得:任意多次連乘、連除所得結(jié)果的相對誤差限等于各任意多次連乘、連除所得結(jié)果的相對誤差限等于各乘數(shù)和除數(shù)的相對誤差限之和。乘數(shù)和除數(shù)的相對誤差限之和。 r (u* ) = r (x* ) + r (y* ) 同樣同樣, 若若 u = x/y, 則則 lnu = lnx lny, 因此因此dlnu = dlnx dlny 即即 er (u* ) = er (x* ) - - er (y* ) 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系例例1xyuz 解因解因 lnlnlnlnln zyxu所以所以 lnlnlnlnlndzdydxd

15、ud 從而得到從而得到 lnlnlnlnlndzdydxdxd 設(shè)設(shè) u 的相對誤差限等于乘數(shù)的相對誤差限等于乘數(shù)x、y和除數(shù)和除數(shù)z、的相對誤差的相對誤差限之和。限之和。求求u的相對誤差限。的相對誤差限。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 ()( )( )( *) ( *)e f xdf xfx dxfxe x 取絕對值得取絕對值得| ( *)| |( )| | ( *)|( )|( *)|( *)|( *)e f xfxe xfxxfxx 其中其中 為近似數(shù)為近似數(shù) x* 的誤差限。的誤差限。二、函數(shù)運(yùn)算誤差二、函數(shù)運(yùn)算誤差設(shè)設(shè) f (x)在在(a,b)內(nèi)連續(xù)可微內(nèi)連續(xù)可微, x 的近似值為的近似

16、值為 x*, f (x)的近的近似值為似值為 f (x*), 其誤差為其誤差為e f(x*),誤差限為誤差限為 ()f x ()x 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系*)(*)(*)(| )(|*)(xxfxxfxf *)(*)(*)(*)()()(*)(xxfxfxxfxfxfr 對多元函數(shù)對多元函數(shù)),(21nxxxfy 自變量的近似值為自變量的近似值為yxxxn*,*,*,21的近似值為的近似值為12*(*,*,*),nyf xxx 函數(shù)值函數(shù)值 y*的運(yùn)算誤差為的運(yùn)算誤差為可得出一元函數(shù)運(yùn)算的誤差限和相對誤差限分別為：可得出一元函數(shù)運(yùn)算的誤差限和相對誤差限分別為：1212121211( *)

17、(*,*,*)(,)(,)(*,*,*)(*)(*)nnnnnniiiiiie ye f xxxdf x xxf x xxf xxxe xe xxx數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系1212121211( *) (*,*,*)(,)(,)(*,*,*)(*)(*)nnnnnniiiiiie ye f xxxdf x xxf x xxf xxxe xe xxx,*),*,*,(21 iinxfxxxxf記記則上式簡記為則上式簡記為*)(*)(*)(11iniiiniixexfxexfye 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系相對誤差限相對誤差限11*( *)*nniiiiffyxx|*|*)(*|*)(*)(11

18、yxxfyxxfyniiniir 于是誤差限于是誤差限*)(*)(*)(11iniiiniixexfxexfye 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系例例1 計(jì)算多項(xiàng)式的值計(jì)算多項(xiàng)式的值: 每項(xiàng)每項(xiàng) ak xk 有有k 次乘法運(yùn)算次乘法運(yùn)算, 因此計(jì)算因此計(jì)算 Pn (x) 共需共需 1122n nn 次乘法和次乘法和n次加法運(yùn)算。次加法運(yùn)算。 1210nnnnPxa xaxaxaxa如將如將 Pn (x) 寫成寫成: 一、簡化計(jì)算步驟一、簡化計(jì)算步驟, 減少運(yùn)算次數(shù)減少運(yùn)算次數(shù)第三節(jié)第三節(jié) 設(shè)計(jì)算法時(shí)應(yīng)注意的原則設(shè)計(jì)算法時(shí)應(yīng)注意的原則0( )nknkkPxa x 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系用遞推算法用

19、遞推算法: 01, , 1,2, .nkkn kuauuxakn最終最終 Pn (x)=un 共需共需n 次乘法和次乘法和n次加法運(yùn)算。次加法運(yùn)算。 一般地要注意一般地要注意:能在循環(huán)外計(jì)算能在循環(huán)外計(jì)算, 就不要放在循環(huán)就不要放在循環(huán)內(nèi)計(jì)算。內(nèi)計(jì)算。 1210nnnnPxa xaxaxaxa數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系如用四位有效數(shù)字計(jì)算如用四位有效數(shù)字計(jì)算: 例例21701313.04 130.04結(jié)果只有一位有效數(shù)字；結(jié)果只有一位有效數(shù)字；兩個(gè)相近的數(shù)相減兩個(gè)相近的數(shù)相減,有效數(shù)字會(huì)大大損失。有效數(shù)字會(huì)大大損失。二、二、 注意避免兩個(gè)相近數(shù)的相減注意避免兩個(gè)相近數(shù)的相減170130.038

20、4048如改為：如改為：11170130.0384013.041317013 有四位有效數(shù)字有四位有效數(shù)字, 新算法避免了兩個(gè)相近數(shù)的相減。新算法避免了兩個(gè)相近數(shù)的相減。數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系例例3 計(jì)算計(jì)算 解解 用五位十進(jìn)制計(jì)算機(jī)進(jìn)行計(jì)算用五位十進(jìn)制計(jì)算機(jī)進(jìn)行計(jì)算:0.1被大數(shù)被大數(shù)“吃掉吃掉”了了,從而從而有有三、防止大數(shù)三、防止大數(shù) “吃掉吃掉” 小數(shù)小數(shù) 10001524920.152492i 555524920.10.52492 100.000001 100.52492 1010001524920.1i 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系如改為如改為 0.1 就沒有被吃掉。就沒有被吃掉

21、。 這也是構(gòu)造算法時(shí)要注意的問題這也是構(gòu)造算法時(shí)要注意的問題, 避免重要的參數(shù)避免重要的參數(shù)被吃掉。被吃掉。100010.15249210052492i 5550.01 100.52492 100.52502 105250510001524920.1i 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系當(dāng)當(dāng)| x | y | 時(shí)時(shí), 舍入誤差會(huì)擴(kuò)大舍入誤差會(huì)擴(kuò)大2( *)( *)*()*xyyxxyy 四、避免除數(shù)的絕對值遠(yuǎn)小于被除數(shù)的絕對值。四、避免除數(shù)的絕對值遠(yuǎn)小于被除數(shù)的絕對值。 例例430.5 10 的舍入誤差均為的舍入誤差均為, 而而的舍入誤差為的舍入誤差為:,則則 7311214100.5 1015 10

22、10 xxxx 很小的數(shù)作除數(shù)有時(shí)還會(huì)造成計(jì)算機(jī)的溢出而停機(jī)。很小的數(shù)作除數(shù)有時(shí)還會(huì)造成計(jì)算機(jī)的溢出而停機(jī)。710 xy*yx*, yx|yx 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系五、使用數(shù)值穩(wěn)定的算法五、使用數(shù)值穩(wěn)定的算法用分部積分公式得遞推用分部積分公式得遞推公式公式:近似值近似值 In* 的遞推公式的遞推公式: In* =1-nIn-1* 例例5110,0,1,2,nxnIx edxn 1110001*0.6321xIedxeI In=1-nIn-1 在運(yùn)算過程中在運(yùn)算過程中,舍入誤差能控制在某個(gè)范圍內(nèi)的算法舍入誤差能控制在某個(gè)范圍內(nèi)的算法稱為數(shù)值穩(wěn)定的算法稱為數(shù)值穩(wěn)定的算法,否則就稱為不穩(wěn)定的算

23、法否則就稱為不穩(wěn)定的算法. e(In* ) = - n e( In-1* ), 用四位有效數(shù)字計(jì)算用四位有效數(shù)字計(jì)算:誤差誤差e( In* )的遞推公式的遞推公式:數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系于是于是I7* , I8* 與精確值已經(jīng)面目全非。與精確值已經(jīng)面目全非。n精確值精確值 In 近似值近似值In*n精確值精確值 In 近似值近似值In*012340.632120.367870.264240.207270.170890.63210.36780.26420.20740.1704567890.145530.126800.112380.100930.091610.14080.11200.2180-

24、0.72807.5520算法一算法一 In =1-nIn-1 ,100*10.6321IeI 代入得下表代入得下表 110,0,1,2,nxnIx edxn 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系由于計(jì)算由于計(jì)算I0有誤差有誤差 不計(jì)中間再產(chǎn)生的舍入誤差不計(jì)中間再產(chǎn)生的舍入誤差 |e(In* )|= n! |e(I0* ) | 到到 I8 時(shí)時(shí) |e(I8* )|= 8! = 40320 誤差擴(kuò)大了誤差擴(kuò)大了4萬倍萬倍, 因而該算法是不穩(wěn)定的。因而該算法是不穩(wěn)定的。 40105 . 0)*( Ie e(In* ) = - n e( In-1* ) 100*10.6321IeI 分析：分析： In=1-nIn-1 , 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系可以估計(jì)出可以估計(jì)出 故故 70.04600.1250I80.04090.1111I11011neInn 110