資源描述:
《選用算法時(shí)應(yīng)遵循的原則》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、§3選用算法時(shí)應(yīng)遵循的原則誤差是用來衡量數(shù)值方法好與壞的重要標(biāo)志為此對(duì)每一個(gè)算法都要進(jìn)行誤差分析。(1)兩個(gè)相近的數(shù)相減,會(huì)嚴(yán)重?fù)p失有效數(shù)字例如x=1958.75,y=1958.32都具有五位有效數(shù)字,但x-y=0.43只有兩位有效數(shù)字通常采用的方法是改變計(jì)算公式,例如當(dāng)與很接近時(shí),由于計(jì)算方法計(jì)算方法用右端代替左端公式計(jì)算,有效數(shù)字就不會(huì)損失。計(jì)算方法當(dāng)x很大時(shí)可作相應(yīng)的變換則用右端來代替左端。計(jì)算方法(2)防止大數(shù)“吃掉”小數(shù)例求二次方程x2-105x+1=0的根解:按二次方程求根公式x1=(105+(
2、1010-4)1/2)/2x2=(105-(1010-4)1/2)/2在8位浮點(diǎn)數(shù)計(jì)算得x1=(105+105)/2=105(正確),x2=(105-105)/2=0(錯(cuò)誤)計(jì)算方法產(chǎn)生錯(cuò)誤的原因①出現(xiàn)大數(shù)吃掉小數(shù)4的情況②分子部分出現(xiàn)兩個(gè)相近數(shù)相減而喪失有效數(shù)位常稱為災(zāi)難性的抵消計(jì)算方法(3)絕對(duì)值太小的數(shù)不宜做除數(shù)當(dāng)分母為兩個(gè)相近數(shù)相減時(shí),會(huì)喪失有效數(shù)字這里分子的誤差被擴(kuò)大104倍,再如若將分母變?yōu)?.0011,即分母只有0.0001的變化時(shí),計(jì)算結(jié)果卻有了很大變化計(jì)算方法解:分子分母分別計(jì)算后相除(取
3、9位小數(shù))A=0.0005×0.0143×0.0012=0.00000715×0.0012=0.000000009(有舍入)B=0.0003×0.0125×0.0135=0.00000375×0.0135=0.000000051(有舍入)D=A/B=0.17647真值為0.16948148…,所以D只準(zhǔn)確到小數(shù)后一位例:計(jì)算計(jì)算方法算法2。分成三組因子。每組只取六位小數(shù)計(jì)算a=0.0005/0.0003=1.666667(有舍入)b=0.0143/0.0125=1.144000c=0.0012/0.0135
4、=0.088889(有舍入)D=a×b×c=1.666667×1.144000×0.088889=0.169482,準(zhǔn)確到小數(shù)后5位。bca計(jì)算方法(4)簡化計(jì)算步驟,減少運(yùn)算次數(shù)x255=xx2x4x8x16x32x64x128原先要做254次乘法現(xiàn)只需14次即可又如計(jì)算多項(xiàng)式p(x)=anxn?an-1xn-1?…?a1x?a0的值若直接計(jì)算akxk,再逐項(xiàng)相加,一共要做n+(n-1)+…+2+1=n(n+1)/2次乘法和n次加法計(jì)算方法如果將前n項(xiàng)提出x,則有p(x)=(anxn-1?an-1xn-2
5、?…?a1)x?a0=((anxn-2?an-1xn-3?…?a2)x?a1)x?a0=(…(anx?an-1)x?…?a2)x?a1)x?a0寫成遞推公式計(jì)算方法于是,這種多項(xiàng)式求值的算法稱為秦九韶算法,只做n次乘法和n次加法,程序?qū)崿F(xiàn)簡單計(jì)算方法(5)選用數(shù)值穩(wěn)定性好的公式,以控制舍入誤差的傳播對(duì)于一個(gè)數(shù)學(xué)問題的求解往往有多種數(shù)值方法在選擇數(shù)值方法時(shí),要注意所用的數(shù)值方法不應(yīng)將計(jì)算過程中難以避免的誤差放大的較快,造成計(jì)算結(jié)果完全失真。計(jì)算方法例13計(jì)算積分并估計(jì)誤差。解容易得到遞推公式計(jì)算方法即為計(jì)算方
6、法則準(zhǔn)確的理論遞推式實(shí)際運(yùn)算的遞推式兩式相減有計(jì)算方法這就是說,若與的誤差為=-,即,則誤差的遞推規(guī)律為于是計(jì)算方法計(jì)算時(shí)的誤差被擴(kuò)大了倍,顯然算法是數(shù)值不穩(wěn)定的。如果將遞推公式變換一種形式計(jì)算方法準(zhǔn)確的理論遞推式實(shí)際運(yùn)算的遞推式從而有即計(jì)算方法于是有則這個(gè)算法的誤差傳遞規(guī)律為即每計(jì)算一步的誤差的絕對(duì)值是上一步的十分之一,誤差的傳播逐步縮小,得到很好的控制,這個(gè)算法是數(shù)值穩(wěn)定的。