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

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

2、終 Pn (x)=un 共需共需n 次乘法和次乘法和n 次加法運算。次加法運算。 一般地要注意一般地要注意: 能在循環(huán)外計算能在循環(huán)外計算, 就不要放在循環(huán)就不要放在循環(huán) 內(nèi)計算。內(nèi)計算。 1210nnnn Pxa xaxaxaxa 數(shù)學學院 信息與計算科學系 二、二、 注意避免兩個相近數(shù)的相減注意避免兩個相近數(shù)的相減 如用四位有效數(shù)字計算如用四位有效數(shù)字計算: 例例2 17013 13.04 13 0.04 結(jié)果只有一位有效數(shù)字；結(jié)果只有一位有效數(shù)字； 兩個相近的數(shù)相減兩個相近的數(shù)相減, 有效數(shù)字會大大損失。有效數(shù)字會大大損失。 170130.0384048 如改為：如改為： 11 1701

3、30.03840 13.041317013 有四位有效數(shù)字有四位有效數(shù)字, 新算法避免了兩個相近數(shù)的相減。新算法避免了兩個相近數(shù)的相減。 數(shù)學學院 信息與計算科學系 三、防止大數(shù)三、防止大數(shù) “吃掉吃掉” 小數(shù)小數(shù) 例例3 解解 用五位十進制計算機進行計算用五位十進制計算機進行計算: 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 計算計算 數(shù)學學院 信息與計算科學系 如改為如改為 0.1 就沒有被吃掉。就沒有被吃掉。

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

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

6、字計算: 近似值近似值 的遞推公式的遞推公式: n I ,1 1 nn nII 誤差誤差 的遞推公式的遞推公式:)( n Ie , )()( 1 nn IneIe 0 1 1 0 1 0 6321. 0 1 I edxeI x 數(shù)學學院 信息與計算科學系 算法算法 一一 代入得下表代入得下表 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ù)學學院 信息與計算科學系 4 0 105 . 0)( Ie 算法一算法一 )()( 1 nn IneIe 由于計算由于計算 有誤差有誤差 0 I 0 1 0 6321. 01IeI 不計中間再產(chǎn)生的舍入誤差不計中間再產(chǎn)生的舍入誤差 )(!)( 0 IenIe n 40320!8)( 8

8、Ie 到到 I8 時時 誤差擴大了誤差擴大了4萬倍萬倍, 因而該算法是不穩(wěn)定的。因而該算法是不穩(wěn)定的。 ,1 1 nn nII 數(shù)學學院 信息與計算科學系 可以估計出可以估計出 故故 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ù)學學院 信息與計算科學系 由由 列表如下列表如下,)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 近似值近