第三節(jié) 數(shù)值計(jì)算中需要注意的問題

1、數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 第三節(jié)第三節(jié) 設(shè)計(jì)算法時(shí)應(yīng)注意的原則設(shè)計(jì)算法時(shí)應(yīng)注意的原則 一、簡(jiǎn)化計(jì)算步驟一、簡(jiǎn)化計(jì)算步驟, 減少運(yùn)算次數(shù)減少運(yùn)算次數(shù) 計(jì)算多項(xiàng)式的值計(jì)算多項(xiàng)式的值: 0 ( ) n k nk k Pxa x 每項(xiàng)每項(xiàng) ak xk 有有k 次乘法運(yùn)算次乘法運(yùn)算, 因此計(jì)算因此計(jì)算 Pn (x) 共需共需 1 1 2 2 n n n 次乘法和次乘法和n 次加法運(yùn)算。次加法運(yùn)算。 如將如將 Pn (x) 寫成寫成: 1210nnnn Pxa xaxaxaxa 例例1 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 用遞推算法用遞推算法: 01 , , 1,2, . nkkn k uauuxakn 最終最

2、終 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ì)算。 1210nnnn Pxa xaxaxaxa 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 二、二、 注意避免兩個(gè)相近數(shù)的相減注意避免兩個(gè)相近數(shù)的相減 如用四位有效數(shù)字計(jì)算如用四位有效數(shù)字計(jì)算: 例例2 17013 13.04 13 0.04 結(jié)果只有一位有效數(shù)字；結(jié)果只有一位有效數(shù)字； 兩個(gè)相近的數(shù)相減兩個(gè)相近的數(shù)相減, 有效數(shù)字會(huì)大大損失。有效數(shù)字會(huì)大大損失。 170130.0384048 如改為：如改為： 11 1701

3、30.03840 13.041317013 有四位有效數(shù)字有四位有效數(shù)字, 新算法避免了兩個(gè)相近數(shù)的相減。新算法避免了兩個(gè)相近數(shù)的相減。 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 三、防止大數(shù)三、防止大數(shù) “吃掉吃掉” 小數(shù)小數(shù) 例例3 解解 用五位十進(jìn)制計(jì)算機(jī)進(jìn)行計(jì)算用五位十進(jìn)制計(jì)算機(jī)進(jìn)行計(jì)算: 0.1被大數(shù)被大數(shù)“吃掉吃掉”了了,從而從而 有有 1000 1 524920.152492 i 55 5 524920.10.52492 100.000001 10 0.52492 10 1000 1 524920.1 i 計(jì)算計(jì)算 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 如改為如改為 0.1 就沒有被吃掉。就沒有被吃掉。

4、 這也是構(gòu)造算法時(shí)要注意的問題這也是構(gòu)造算法時(shí)要注意的問題, 避免重要的參數(shù)避免重要的參數(shù) 被吃掉。被吃掉。 1000 1 0.15249210052492 i 55 5 0.01 100.52492 10 0.52502 1052505 1000 1 524920.1 i 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 四、避免除數(shù)的絕對(duì)值遠(yuǎn)小于被除數(shù)的絕對(duì)值四、避免除數(shù)的絕對(duì)值遠(yuǎn)小于被除數(shù)的絕對(duì)值 當(dāng)當(dāng)| x | y | 時(shí)時(shí), 舍入誤差會(huì)擴(kuò)大舍入誤差會(huì)擴(kuò)大 例例4 73 11 2 14 100.510 1 510 10 xx x x 很小的數(shù)作除數(shù)有時(shí)還會(huì)造成計(jì)算機(jī)的溢出而停機(jī)。很小的數(shù)作除數(shù)有時(shí)還會(huì)造成計(jì)

5、算機(jī)的溢出而停機(jī)。 3 0.510 的舍入誤差均為的舍入誤差均為 , 而而 的舍入誤差為的舍入誤差為:,則則 7 10 xy y x 2 )()()(yxyyxyx yx , 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 五、使用數(shù)值穩(wěn)定的算法五、使用數(shù)值穩(wěn)定的算法 用分部積分公式得遞推用分部積分公式得遞推 公式公式: 例例5 1 1 0 ,0,1,2, nx n Ix edxn In=1-nIn-1 , 在運(yùn)算過程中在運(yùn)算過程中,舍入誤差能控制在某個(gè)范圍內(nèi)的算法舍入誤差能控制在某個(gè)范圍內(nèi)的算法 稱為稱為數(shù)值穩(wěn)定的算法數(shù)值穩(wěn)定的算法,否則就稱為否則就稱為不穩(wěn)定的算法不穩(wěn)定的算法. 用四位有效數(shù)字計(jì)算用四位有效數(shù)

6、字計(jì)算: 近似值近似值 的遞推公式的遞推公式: n I ,1 1 nn nII 誤差誤差 的遞推公式的遞推公式:)( n Ie , )()( 1 nn IneIe 0 1 1 0 1 0 6321. 0 1 I edxeI x 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 算法算法 一一 代入得下表代入得下表 1 1 0 ,0,1,2, nx n Ix edxn 于是于是 與精確值已經(jīng)面目全非。與精確值已經(jīng)面目全非。 87 ,II 0 1 0 6321. 01IeI 5 6 7 8 9 n 0.1408 0.1120 0.2180 -0.7280 7.5520 0.14553 0.12680 0.11238 0

7、.10093 0.09161 0.6321 0.3678 0.2642 0.2074 0.1704 0.63212 0.36787 0.26424 0.20727 0.17089 0 1 2 3 4 近似值近似值 精確值精確值 In 近似值近似值精確值精確值 In n n I n I ,1 1 nn nII 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 4 0 105 . 0)( Ie 算法一算法一 )()( 1 nn IneIe 由于計(jì)算由于計(jì)算 有誤差有誤差 0 I 0 1 0 6321. 01IeI 不計(jì)中間再產(chǎn)生的舍入誤差不計(jì)中間再產(chǎn)生的舍入誤差 )(!)( 0 IenIe n 40320!8)( 8

8、Ie 到到 I8 時(shí)時(shí) 誤差擴(kuò)大了誤差擴(kuò)大了4萬倍萬倍, 因而該算法是不穩(wěn)定的。因而該算法是不穩(wěn)定的。 ,1 1 nn nII 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 可以估計(jì)出可以估計(jì)出 故故 1 1 0 11 n e I nn 1 1 0 ,0,1,2, nx n Ix edxn 算法二算法二 誤差誤差 nIeIe nn )()( 1 1111. 0409. 01250. 04046. 0 87 II nII nn )1( 1 則則 如果遞推式改為如果遞推式改為 In-1 =(1-In )/n 數(shù)學(xué)學(xué)院 信息與計(jì)算科學(xué)系 由由 列表如下列表如下,)1(,1000. 0 19 nIII nn 4 3 2 1 0 n 0.1709 0.2073 0.2642 0.3679 0.6321 0.17089 0.20272 0.26424 0.36787 0.63212 0.1000 0.1000 0.1125 0.1268 0.1455 0.09161 0.10093 0.11238 0.12680 0.14553 9 8 7 6 5 近似值近似值精確值精確值 In 近似值近