91欧美在线免费观看,漂亮的人妻中文字幕,国产精品免费在线观看视频,男女一起插插插视频,四虎国产精品久久久久,人妻精品有码一区二区三区,亚洲 欧美 你懂的,亚洲制服一区二区三区在线,高中女厕偷拍一区二区三区

數(shù)學(xué)技術(shù)之算法概論篇（2）

③ 誤差及其計(jì)算傳播
用計(jì)算機(jī)求解一個實(shí)際問題，從實(shí)際問題提出到上機(jī)求解、給出計(jì)算結(jié)果，以數(shù)值計(jì)算為例，通常須經(jīng)歷以下過程：

經(jīng)上述過程給出的計(jì)算結(jié)果，多數(shù)情況下只是實(shí)際問題相應(yīng)未知真值的一個近似值，存在誤差。計(jì)算前、計(jì)算中和計(jì)算結(jié)果處理，不可避免的會出現(xiàn)各種各樣的、大大小小的誤差。因此，誤差成了算法中經(jīng)常遇到和需要深入研究的一個問題。
算法中的誤差論，研究計(jì)算機(jī)上算法中的誤差來源、性質(zhì)和分類，誤差的傳播規(guī)律，誤差影響，誤差分析方法和估算誤差影響的理論等，為算法研究的基礎(chǔ)理論之一。
對輸入到計(jì)算機(jī)中數(shù)據(jù)的初始誤差、引進(jìn)數(shù)學(xué)模型中形成的誤差、計(jì)算過程中出現(xiàn)的各種誤差和結(jié)果誤差進(jìn)行分類，對各類誤差及其關(guān)系進(jìn)行研究和分析，對計(jì)算過程中誤差的傳播和對計(jì)算結(jié)果的影響進(jìn)行探討，從而對所用數(shù)值方法的誤差上限給出可用的估計(jì)，以得到這一算法是否可行、計(jì)算結(jié)果是否可用或?qū)ζ涓倪M(jìn)的可能等進(jìn)行深入研討，發(fā)現(xiàn)其規(guī)律性，探索進(jìn)一步可采用的新方法和研發(fā)的新途徑等，這許多方面的研究及其成果就構(gòu)成了我們所說的算法中的誤差論。
常用的誤差分析方法有一般誤差分析、特殊誤差分析、誤差定性分析、誤差定量分析、向前誤差分析、向后誤差分析、隨機(jī)誤差分析、區(qū)間誤差分析等。一般誤差分析只分析誤差的通用規(guī)律性，如誤差的數(shù)字特征、分布特征及其性態(tài)，誤差傳播的一般規(guī)律性，給出最后誤差的上限等；特殊誤差分析法分析一類數(shù)據(jù)或算法的誤差特性，給出最后誤差的上限，如計(jì)算機(jī)浮點(diǎn)數(shù)算術(shù)運(yùn)算的舍入誤差分析、線代數(shù)方程組迭代解法的誤差分析等。

一、真值與誤差

真值：所謂“真值”即真實(shí)值，是在一定條件下的實(shí)際值，通常是未知量，有理論真值、規(guī)定真值和相對真值之分。
理論真值：理論真值又稱絕對真值，如平面三角形三內(nèi)角之和恒為180 。
規(guī)定真值：國際上公認(rèn)的某些基準(zhǔn)量值，如1982年國際計(jì)量局召開的米定義咨詢委員會提出米的定義為“米等于光在真空中1／299792458秒時(shí)間間隔內(nèi)所經(jīng)路徑的長度”。這個米基準(zhǔn)就當(dāng)作計(jì)量長度的規(guī)定真值。規(guī)定真值也稱約定真值。
相對真值：計(jì)量器具按精度不同分為若干等級，上一等級的指示值即為下一等級的真值，此真值稱為相對真值。如在力值的傳遞標(biāo)準(zhǔn)中，用二等標(biāo)準(zhǔn)測力計(jì)校準(zhǔn)三等標(biāo)準(zhǔn)測力計(jì)，此時(shí)二等標(biāo)準(zhǔn)測力計(jì)的指示值即為三等標(biāo)準(zhǔn)測力計(jì)的相對真值。
誤差：數(shù)值結(jié)果x與其相應(yīng)真值x^*之差

E=x–x^*

稱為誤差。

二、誤差分類

計(jì)算機(jī)計(jì)算中出現(xiàn)的誤差種類繁多，常見的有初始誤差，即輸人計(jì)算機(jī)內(nèi)的近似值和其相應(yīng)真值之差；輸入誤差，即計(jì)算機(jī)上輸入數(shù)據(jù)中出現(xiàn)的誤差（如用有限小數(shù)表示1/3、用有限位二進(jìn)制數(shù)表示1/10等產(chǎn)生的誤差）；舍入誤差，因應(yīng)用需要和計(jì)算機(jī)字長的限制，把位數(shù)較多的數(shù)用位數(shù)較少的數(shù)代替原數(shù)而產(chǎn)生的誤差；數(shù)據(jù)誤差，數(shù)學(xué)模型中所含參數(shù)的誤差，這些參數(shù)可能是觀測得到的，含觀測誤差，也可能是計(jì)算得到的，含計(jì)算誤差等；由于數(shù)學(xué)模型的局限與近似等原因產(chǎn)生的模型誤差，經(jīng)離散化處理后出現(xiàn)的離散化誤差，經(jīng)逼近處理后出現(xiàn)的逼近誤差，為簡化計(jì)算、用近似表達(dá)式代替精確表達(dá)式出現(xiàn)的截?cái)嗾`差等等。
由觀測工具不準(zhǔn)確和隨機(jī)干擾等諸多因素引起的觀測誤差，含系統(tǒng)、隨機(jī)和疏失等誤差項(xiàng)：觀測誤差中的系統(tǒng)誤差是由于儀器本身不精確、或?qū)嶒?yàn)方法粗略、或?qū)嶒?yàn)原理不完善而產(chǎn)生的誤差；偶然誤差是由各種偶然因素對實(shí)驗(yàn)者、測量儀器、被測物理量的影響而產(chǎn)生的；過失誤差會明顯地歪曲試驗(yàn)結(jié)果，如測錯、讀錯、記錯、傳錯或計(jì)算錯等。含有過失誤差的測量數(shù)據(jù)是不能采用的，必須利用一定的準(zhǔn)則從測得的數(shù)據(jù)中剔除或修正。因此，在進(jìn)行誤差分析時(shí)，只考慮系統(tǒng)誤差與隨機(jī)誤差。
在應(yīng)用中，按誤差的性質(zhì)，可分為絕對誤差和相對誤差兩種。
絕對誤差與誤差限：設(shè)x^*是精確值，x是它的一個近似值，稱

e=｜x-x^*｜

為近似值x的絕對誤差，簡稱誤差。誤差e的上界 ，即 x-x^* ≤ ，稱為近似值x的誤差限。
相對誤差與相對誤差限：誤差e與精確值的比值

e/x^*= x-x^* /|x|

稱為近似值x的相對誤差(顯然，此時(shí)要求x^*不為零)。相對誤差不僅表示測量的絕對誤差，而且能反映出測量時(shí)所達(dá)到的精度。

三、有效數(shù)字

如果近似值x的誤差限 是它某一個數(shù)位的半個單位，x準(zhǔn)確到該位。從這一位起到前面第一個非0數(shù)字位置的所有數(shù)字稱為x的有效數(shù)字。如有x= a₁a₂a₃…a_n時(shí)，其中a₁、a₂、a₃、…、a_n是0-9之中的自然數(shù)，且a₁≠0，稱其有n位精度。

四、數(shù)值計(jì)算時(shí)的誤差傳播

在計(jì)算機(jī)上進(jìn)行數(shù)值計(jì)算時(shí)，帶有誤差的數(shù)據(jù)會將所含的誤差在以后計(jì)算中進(jìn)行轉(zhuǎn)移、擴(kuò)散和發(fā)展等，謂之誤差傳播。在四則運(yùn)算、函數(shù)計(jì)算等各類算法中誤差傳播具有如下的一些公式：
四則運(yùn)算中的誤差傳播公式
e（x₁+x₂）=e（x₁）+e（x₂）；
e（x₁*x₂）=|x₁|e（x₁）+|x₂|e（x₂）；
e（x₁/x₂）=[|x₁|e（x₁）+|x₂|e（x₂）|]/|x₂|²。
函數(shù)f(x)的誤差限：|e（f（x））|≤ f′(x) e（x）。

五、數(shù)值計(jì)算中應(yīng)注意幾個問題

在計(jì)算機(jī)上進(jìn)行數(shù)值計(jì)算時(shí)，必須考慮參與計(jì)算的數(shù)受計(jì)算機(jī)字長有限和數(shù)值計(jì)算中的誤差及其傳播和累積等許多方面的問題。特別是以下幾點(diǎn)，應(yīng)給予更多的關(guān)照：
1.使用數(shù)值穩(wěn)定的算法，即在運(yùn)算過程中四舍五入誤差不增加或增加比較慢的算法；
2.防止兩個相近數(shù)的相減，降低有效數(shù)字的損失；
3.簡化計(jì)算步驟，降低運(yùn)算次數(shù)；
4.避免除數(shù)的絕對值遠(yuǎn)小于被除數(shù)的絕對值；
5.防止大數(shù)“吃掉”小數(shù)。如大小相差很大的兩個數(shù)間進(jìn)行加法運(yùn)算，因計(jì)算機(jī)上采用高階對位，很小的數(shù)和很大的數(shù)相比進(jìn)行高階對位時(shí)變?yōu)?，俗稱“大數(shù)‘吃掉’小數(shù)”。

六、誤差分析

在計(jì)算機(jī)進(jìn)行計(jì)算時(shí)，為保證計(jì)算的有效性和可用性，要對計(jì)算中出現(xiàn)的各種誤差進(jìn)行分析，其中包括一般誤差分析（分析誤差的通用規(guī)律性，如誤差的數(shù)字特征，分布特征及其性態(tài)，誤差傳播的一般規(guī)律性，給出最后誤差的上限等）和特殊誤差分析（分析一類數(shù)據(jù)或算法的誤差特性，給出最后誤差的上限，如計(jì)算機(jī)浮點(diǎn)數(shù)算術(shù)運(yùn)算的舍入誤差分析，線代數(shù)方程組迭代解法的誤差分析等），誤差定性分析（對一類算法計(jì)算中的誤差進(jìn)行“質(zhì)”方面的分析，揭示誤差傳播的內(nèi)在規(guī)律，給出該算法是否可用的定性描述）和誤差定量分析（建立數(shù)學(xué)模型，依據(jù)統(tǒng)計(jì)數(shù)據(jù)，計(jì)算出分析對象的各項(xiàng)誤差指標(biāo)及其數(shù)值大小，給出該算法是否可用的定量描述）。誤差分析方法也很多，常見的有向前誤差分析和向后誤差分析，區(qū)間誤差分析和概率誤差分析等。
④ 公式及其數(shù)值運(yùn)算
數(shù)學(xué)上的公式運(yùn)算和計(jì)算機(jī)上數(shù)學(xué)公式的具體數(shù)值計(jì)算有許多不同，主要表現(xiàn)有：
1．在計(jì)算機(jī)上，可以通過算法設(shè)計(jì)，用不同的算法實(shí)現(xiàn)數(shù)學(xué)上同一計(jì)算公式的數(shù)值計(jì)算；不同的算法，計(jì)算速度和計(jì)算結(jié)果精度有時(shí)會有顯著的不同。
2．?dāng)?shù)學(xué)公式中的加、減、乘、除運(yùn)算，不考慮實(shí)施具體數(shù)值計(jì)算時(shí)，和數(shù)的排序無關(guān)，和數(shù)列的長度無關(guān)；在計(jì)算機(jī)上實(shí)施實(shí)際數(shù)值運(yùn)算時(shí)，由于字長有限和舍入誤差的影響，既和數(shù)的排序有關(guān)，又和數(shù)列的長度有關(guān)。
3．在數(shù)學(xué)上，不涉及真正的實(shí)際計(jì)算時(shí)，不考慮加、減、乘、除運(yùn)算的速度；計(jì)算機(jī)上的數(shù)值運(yùn)算，特別是核心運(yùn)算部分，涉及到算法的時(shí)間復(fù)雜度，要考慮加、減、乘、除的運(yùn)算速度，如加、減的運(yùn)算速度相近，乘法速度次之，除法最慢。因此，在程序設(shè)計(jì)中，常用a+a代替2*a，用0.5*（a+b）代替（a+b）/2.0等，以降低時(shí)間復(fù)雜度。
4．在計(jì)算機(jī)上，為提高加、減、乘、除運(yùn)算的穩(wěn)定性，想方設(shè)法減少有效數(shù)字的損失，如極力避免兩相近數(shù)的減法運(yùn)算、兩相差很大數(shù)的加法運(yùn)算、特大數(shù)作乘法和特小數(shù)作除法的運(yùn)算等。
在算法執(zhí)行過程中會出現(xiàn)舍入誤差的積累。對同一個計(jì)算問題，在不同的算法中舍入誤差對計(jì)算結(jié)果產(chǎn)生的影響也各不相同。舍入誤差對計(jì)算結(jié)果的精確性影響小的算法，具有較好的數(shù)值穩(wěn)定性；反之，算法的數(shù)值穩(wěn)定性差。例如，若干個正數(shù)相加時(shí)，按從大到小的次序進(jìn)行就不如按從小到大的次序進(jìn)行的數(shù)值穩(wěn)定性好。
再以二次方程 x²+bx+ =0求根為例，說明如何利用不同的算法避免兩相近數(shù)的減法運(yùn)算。對二次方程 x²+bx+ =0求根，有如下公式：

若b>0，且b²>>4| |，則由于b和√b²-4ac很接近，用公式(1)計(jì)算x1遇到兩個相近的數(shù)相減，就會使有效數(shù)字嚴(yán)重?fù)p失。但這時(shí)可先用公式(2)計(jì)算x₂，然后根據(jù)關(guān)系x₁x₂= / 計(jì)算x₁，會得到比較好的結(jié)果。在用消去法解線性代數(shù)方程組時(shí)，選主元的算法比不選主元的算法的數(shù)值穩(wěn)定性好，同樣說明計(jì)算機(jī)上數(shù)值計(jì)算順序選擇的重要性。
下面再通過統(tǒng)計(jì)計(jì)算中的一個簡單實(shí)例，計(jì)算一組觀察數(shù)據(jù)的均值和方差，說明數(shù)學(xué)中的公式計(jì)算和計(jì)算機(jī)上的數(shù)的實(shí)際計(jì)算的不同。
給出n個數(shù)據(jù)

？？？？？？？？？？？？？？？ x₁，x₂，…，x_{n？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？} （3）

經(jīng)常需要計(jì)算它們的均值

和方差

在數(shù)學(xué)上，顯然有

（5）、（6）兩式恒等，同時(shí)成立?，F(xiàn)在要問，對一組給出的數(shù)據(jù)（3），在計(jì)算機(jī)上用（5）和（6）二式分別進(jìn)行計(jì)算方差時(shí)，結(jié)果是否還完全相同？和（4）、（5）、（6）相比，能否給出均值和方差計(jì)算結(jié)果誤差更小、計(jì)算所用計(jì)算機(jī)機(jī)時(shí)更省的公式或算法？
對均值和方差，通常有下面三個不同的算法可用：
1.直接算法

和上面的（4）、（6）相同，只需對數(shù)據(jù)（3）進(jìn)行一輪循環(huán)處理，即可得到結(jié)果。
2.二次均值算法

從數(shù)學(xué)上看，（10）是一道多余的計(jì)算，因此，（9）、（11）和（7）、（8）在理論上是一樣的；但在計(jì)算機(jī)上對實(shí)際數(shù)據(jù)進(jìn)行處理時(shí)，它們可不一樣，經(jīng)常給出有一定差異的計(jì)算結(jié)果；和（7）、（8）相比，（9）、（10）、（11）要對數(shù)據(jù)（3）進(jìn)行三輪循環(huán)處理，才能得到結(jié)果，計(jì)算工作量增大，但可避免“大”吃“小”，舍入誤差的影響會更小一些，結(jié)果會更為可靠。
3.遞推算法
記

這時(shí)取初值

對i=2，3，…，n，用

進(jìn)行遞推計(jì)算，最后得

利用遞推算法（12）–（16），只需對數(shù)據(jù)（3）進(jìn)行一輪循環(huán)處理，即可得到計(jì)算結(jié)果。
計(jì)算結(jié)果的精度受多種因素的影響，如數(shù)組取值的大小、排序的不同等，計(jì)算結(jié)果的精度都會有所不同，三種算法的優(yōu)劣一時(shí)還很難定論；但綜合考慮計(jì)算量和結(jié)果精度并通過實(shí)例進(jìn)行計(jì)算的結(jié)果表明，遞推算法更好一些。