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

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

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

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

一、真值與誤差

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

E=x–x^*

稱為誤差。

二、誤差分類

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

e=｜x-x^*｜

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

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

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

三、有效數(shù)字

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

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

在計算機上進(jìn)行數(shù)值計算時，帶有誤差的數(shù)據(jù)會將所含的誤差在以后計算中進(jìn)行轉(zhuǎn)移、擴散和發(fā)展等，謂之誤差傳播。在四則運算、函數(shù)計算等各類算法中誤差傳播具有如下的一些公式：
四則運算中的誤差傳播公式
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ù)值計算中應(yīng)注意幾個問題

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

六、誤差分析

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

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

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

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

和方差

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

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

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

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

這時取初值

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

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

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