1.3 選用算法時應遵循的原則

《1.3 選用算法時應遵循的原則》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、§3選用算法時應遵循的原則誤差是用來衡量數(shù)值方法好與壞的重要標志為此對每一個算法都要進行誤差分析。(1)兩個相近的數(shù)相減，會嚴重損失有效數(shù)字例如x=1958.75，y=1958.32都具有五位有效數(shù)字，但x-y=0.43只有兩位有效數(shù)字通常采用的方法是改變計算公式,例如當與很接近時,由于計算方法計算方法用右端代替左端公式計算,有效數(shù)字就不會損失。計算方法當x很大時可作相應的變換則用右端來代替左端。計算方法（2）防止大數(shù)“吃掉”小數(shù)例求二次方程x2-105x+1=0的根解：按二次方程求根公式x1=(105+(1010-4)1/2)/2x2=(105-(1010-4

2、)1/2)/2在8位浮點數(shù)計算得x1=(105+105)/2=105(正確）,x2=(105-105)/2=0(錯誤）計算方法產(chǎn)生錯誤的原因①出現(xiàn)大數(shù)吃掉小數(shù)4的情況②分子部分出現(xiàn)兩個相近數(shù)相減而喪失有效數(shù)位常稱為災難性的抵消計算方法（3）絕對值太小的數(shù)不宜做除數(shù)當分母為兩個相近數(shù)相減時,會喪失有效數(shù)字這里分子的誤差被擴大104倍,再如若將分母變?yōu)?.0011,即分母只有0.0001的變化時,計算結(jié)果卻有了很大變化計算方法解:分子分母分別計算后相除(取9位小數(shù))A=0.0005×0.0143×0.0012=0.00000715×0.0012=0.00000000

3、9(有舍入)B=0.0003×0.0125×0.0135=0.00000375×0.0135=0.000000051(有舍入)D=A/B=0.17647真值為0.16948148…，所以D只準確到小數(shù)后一位例：計算計算方法算法2。分成三組因子。每組只取六位小數(shù)計算a=0.0005/0.0003=1.666667(有舍入)b=0.0143/0.0125=1.144000c=0.0012/0.0135=0.088889(有舍入)D=a×b×c=1.666667×1.144000×0.088889=0.169482，準確到小數(shù)后5位。bca計算方法（4）簡化計算步驟，

4、減少運算次數(shù)x255=xx2x4x8x16x32x64x128原先要做254次乘法現(xiàn)只需14次即可又如計算多項式p(x)=anxn?an-1xn-1?…?a1x?a0的值若直接計算akxk,再逐項相加，一共要做n+(n-1)+…+2+1=n(n+1)/2次乘法和n次加法計算方法如果將前n項提出x，則有p(x)=（anxn-1?an-1xn-2?…?a1）x?a0=((anxn-2?an-1xn-3?…?a2)x?a1）x?a0=(…(anx?an-1)x?…?a2)x?a1)x?a0寫成遞推公式計算方法于是,這種多項式求值的算法稱為秦九韶算法,只做n次乘法和n次

5、加法,程序?qū)崿F(xiàn)簡單計算方法（5）選用數(shù)值穩(wěn)定性好的公式，以控制舍入誤差的傳播對于一個數(shù)學問題的求解往往有多種數(shù)值方法在選擇數(shù)值方法時，要注意所用的數(shù)值方法不應將計算過程中難以避免的誤差放大的較快，造成計算結(jié)果完全失真。計算方法例13計算積分并估計誤差。解容易得到遞推公式計算方法即為計算方法則準確的理論遞推式實際運算的遞推式兩式相減有計算方法這就是說,若與的誤差為=-,即，則誤差的遞推規(guī)律為于是計算方法計算時的誤差被擴大了倍,顯然算法是數(shù)值不穩(wěn)定的。如果將遞推公式變換一種形式計算方法準確的理論遞推式實際運算的遞推式從而有即計算方法于是有則這個算法的誤差傳遞規(guī)律為即

6、每計算一步的誤差的絕對值是上一步的十分之一，誤差的傳播逐步縮小，得到很好的控制，這個算法是數(shù)值穩(wěn)定的。