統(tǒng)計計算 課件 第1章第1節(jié) 數(shù)值計算的誤差

1第一章優(yōu)化算法

1.1數(shù)值計算的誤差

1.2

方程求根和優(yōu)化算法

2

統(tǒng)計計算的定義：

統(tǒng)計計算的主要內(nèi)容：

本課程主要內(nèi)容包括優(yōu)化算法、非線性方程求根、隨機數(shù)的產(chǎn)生、隨機模擬、MCMC方法、EM算法、自助法等內(nèi)容

統(tǒng)計計算主要研究用計算機求解各種統(tǒng)計問題的數(shù)值計算方法及其理論與軟件實現(xiàn).

統(tǒng)計計算研究對象與特點3統(tǒng)計學的真正廣泛應用得益于計算機信息技術的發(fā)展。統(tǒng)計計算就是統(tǒng)計方法和實際計算的結(jié)合。統(tǒng)計計算包括兩個方面：統(tǒng)計方法的實現(xiàn)算法，把統(tǒng)計方法變成可靠、高效的算法，并編程實現(xiàn)，屬于經(jīng)典的統(tǒng)計計算（statisticalcomputing。借助于現(xiàn)代計算機的強大處理能力，發(fā)展新的統(tǒng)計方法,稱為計算統(tǒng)計computationalstatistics。本課程集中于經(jīng)典統(tǒng)計計算，但是包括隨機模擬，隨機模擬是很多計算統(tǒng)計方法的基礎。統(tǒng)計計算的范疇4誤差分析最優(yōu)化與方程求根（極值問題、求根問題、優(yōu)化問題（牛頓法、梯度下降法））隨機數(shù)生成隨機模擬MCMC算法EM算法近似計算，包括函數(shù)逼近(連分式)、數(shù)值積分（梯形法則、辛普森法則）自助法本課程的內(nèi)容5誤差分析近似計算，包括函數(shù)逼近、插值、數(shù)值積分、數(shù)值微分矩陣計算隨機數(shù)生成，隨機模擬最優(yōu)化與方程求根統(tǒng)計計算的內(nèi)容6隨機模擬：在計算機上模擬生成一個統(tǒng)計問題的數(shù)據(jù)并進行大量的重復，這樣相當于獲得了此問題的海量的樣本。最常用的一種是MCMC?；陔S機模擬的方法，如貝葉斯推斷，Bootstrap和Jacknife,permutation檢驗，等等數(shù)據(jù)挖掘、機器學習、統(tǒng)計學習、深度學習等方面的算法計算統(tǒng)計的內(nèi)容7為什么需要MCMCMCMC方法是用來在概率空間，通過隨機采樣估算興趣參數(shù)的后驗分布。動機一假如你需要對一維隨機變量X進行采樣，

X

的樣本空間是

{1,2,3}

，且概率分別是

{1/2,1/4,1/4}

。首先根據(jù)各離散取值的概率大小對

[0,1]

區(qū)間進行等比例劃分，如劃分為

[0,0.5],[0,5,0.75],[0.75,1]

這三個區(qū)間，再通過計算機產(chǎn)生

[0,1]

之間的偽隨機數(shù)，根據(jù)偽隨機數(shù)的落點即可完成一次采樣。

X

是連續(xù)分布，概率密度是

f(x)

，那該如何進行采樣呢？要想到累積分布函數(shù)，即在

[0,1]

間隨機生成一個數(shù)

a

，然后求使得使

P(X<t)=a

成立的

t

，

t

即可以視作從中得到的一個采樣結(jié)果。這里有兩個前提：一是概率密度函數(shù)可積；第二個是累積分布函數(shù)有反函數(shù)。假如條件不成立怎么辦呢？MCMC就登場了。8計算統(tǒng)計的內(nèi)容動機二假如對于高維隨機變量，比如

R50

，若每一維取100個點，則總共要取

10100

，而已知宇宙的基本粒子大約有

1087

個，對連續(xù)的也同樣如此。因此MCMC可以解決“維數(shù)災難”問題。

9一維空間中，把一個單位空間（退化為區(qū)間）以每個點距離不超過0.01采樣，需要102個平均分布的采樣點，而在10維度空間中，需要1020個點才行。frommatplotlibimportpyplotaspltimportnumpyasnpmax_dimensionality=10ax=plt.axes(xlim=(0,max_dimensionality),ylim=(0,1/(0.01**max_dimensionality)))x=np.linspace(0,max_dimensionality,1000)y=1/(0.01**x)plt.plot(x,y,lw=2)plt.show()10Bootstrap方法Bootstrap的定義是利用有限的樣本經(jīng)由多次重復抽樣，建立起充足的樣本，在機器學習中解決了樣本不足的問題。

Bootstrap是非參數(shù)統(tǒng)計方法，是一種有放回的抽樣方法，其實質(zhì)是對觀測信息進行再抽樣，進而對總體的分布特性進行統(tǒng)計推斷。步驟：采用重抽樣技術從原始樣本中抽取一定數(shù)量（自己給定）的樣本，此過程允許重復抽樣。根據(jù)抽出的樣本計算給定的統(tǒng)計量T。重復上述N次（一般大于1000），得到N個統(tǒng)計量T。計算上述N個統(tǒng)計量T的樣本方差，得到統(tǒng)計量的方差。11Bootstrap方法數(shù)據(jù)集較小時是不錯的選擇。自助法在數(shù)據(jù)集較小、難以有效劃分訓練集和測試集時很有用，將多次隨機抽樣得到的樣本作為訓練集，將初始數(shù)據(jù)作為測試集。對集成學習方法有幫助。自助法能從初始數(shù)據(jù)集中產(chǎn)生多個不同的訓練集，這對集成學習等方法有很大的好處。穩(wěn)健性和效率高。該方法充分利用了給定的觀測信息，不需要模型其他的假設和增加新的觀測，并且具有穩(wěn)健性和效率高的特點但會引入估計偏差。自助法產(chǎn)生的數(shù)據(jù)集改變了初始數(shù)據(jù)集的分布，這會引入估計偏差。因此，在初始數(shù)據(jù)量足夠時，留出法和交叉驗證法更常用一些。12交叉驗證交叉驗證(

CrossValidation)，就是進行多次train_test_split劃分；每次劃分時，在不同的數(shù)據(jù)集上進行訓練、測試評估，從而得出一個評價結(jié)果；如果是5折交叉驗證，意思就是在原始數(shù)據(jù)集上，進行5次劃分，每次劃分進行一次訓練、評估，最后得到5次劃分后的評估結(jié)果，一般在這幾次評估結(jié)果上取平均得到最后的評分。k-foldcross-validation，其中，k一般取5或10。13許多算法已有現(xiàn)成軟件，尤其是R軟件、python、Matlab，SPSS等。學習這些基礎算法有什么意義？

沒有現(xiàn)成的方法可以套用時，需要自己解決；

即使有現(xiàn)成的統(tǒng)計軟件可用，我們也需要理解這些軟件的工作原理以避免錯誤使用；在遇到新問題時，需要能夠修改原有代碼或編寫新代碼，把計算工具結(jié)合在一起解決自己的數(shù)據(jù)分析問題，而不是修改自己的問題以適應現(xiàn)成的軟件。學習統(tǒng)計計算意義141.1.1誤差來源與分類

用計算機解決科學計算問題的過程如下：

首先要建立數(shù)學模型，它是對被描述的實際問題進行抽象、簡化而得到的，因而是近似的.

數(shù)學模型與實際問題之間出現(xiàn)的誤差稱為模型誤差.實際問題數(shù)學模型1.1誤差來源與分類15一、模型誤差統(tǒng)計計算的算法通常是用來求解某種統(tǒng)計模型。任何用來解決實際問題的數(shù)學模型都或多或少地簡化了實際問題，忽略掉一些細節(jié)，從而模型誤差不可避免。

如果模型不合適，其它誤差控制得再完美，問題也不能得到解決；更糟的是，良好的計算結(jié)果會給使用者以錯誤的信心。比如，我們使用的回歸模型要求觀測是獨立的，而實際數(shù)據(jù)觀測有不可忽略的序列相關性，盡管我們用軟件算出了很完美的結(jié)果，這個結(jié)果也是錯誤的。我們應當仔細選擇模型，盡可能減少模型誤差?，F(xiàn)代的統(tǒng)計學習理論和方法對控制模型誤差有一系列的研究和實用做法，比如，區(qū)分訓練集和測試集，交叉驗證。16實際問題數(shù)學模型

在數(shù)學模型中往往還有一些根據(jù)觀測得到的物理量，如溫度、長度、電壓等等，這些參量顯然也包含誤差.

這種由觀測產(chǎn)生的誤差稱為觀測誤差.二、觀測誤差17建立統(tǒng)計模型所需的數(shù)據(jù)來自實驗、觀測、抽樣調(diào)查等過程，在這樣的過程中會出現(xiàn)實驗誤差，包括隨機誤差、系統(tǒng)誤差、過失誤差。隨機誤差是試驗過程中由一系列隨機因素引起的不易控制的誤差，可以通過多次重復試驗或改進模型設計來減小隨機誤差。系統(tǒng)誤差是多次測量持續(xù)偏高或偏低的誤差，多次重復測量不能消除或減少系統(tǒng)誤差。在記錄實驗數(shù)據(jù)時由于人的過失可以導致誤差發(fā)生,這樣的誤差稱為過失誤差。18在用雷達測量飛機的方位和速度時，可能受到地磁、氣溫、地形的影響。由于測量儀器精度的限制也會產(chǎn)生隨機誤差，比如用最小刻度是1度的溫度計測量溫度，只能把不足1度的值四舍五入或者估計小數(shù)點后一位數(shù)字。隨機誤差也可能來自特定條件下才發(fā)生的程序錯誤。隨機誤差19用不銹鋼直尺測量家具高度，直尺本身在溫度不同時長度有細微變化。系統(tǒng)誤差也可能來自儀器使用不當，比如用天平測量質(zhì)量時天平?jīng)]有配準。當發(fā)現(xiàn)有系統(tǒng)誤差時，必須找出引起誤差的原因并消除。系統(tǒng)誤差20用在記錄儀表（如水表、電表）的讀數(shù)時看錯數(shù)字在記錄數(shù)值時寫錯小數(shù)點位置在上傳數(shù)據(jù)時報告了過時的或錯誤的數(shù)據(jù)統(tǒng)計數(shù)據(jù)分析必須甄別并改正這樣的過失誤差，否則會對分析結(jié)果產(chǎn)生嚴重影響。過失誤差21

近似解與精確解之間的誤差稱為截斷誤差.實際問題數(shù)學模型上機計算求出結(jié)果統(tǒng)計計算方法三、截斷誤差22

例如，用泰勒(Taylor)多項式近似代替可微函數(shù)，則數(shù)值方法的截斷誤差是23例1如果只取前四項，則就是截斷誤差24產(chǎn)生的誤差用近似代替，就是舍入誤差.例如，

有了計算公式后，在用計算機做數(shù)值計算時，還要受計算機字長的限制，原始數(shù)據(jù)在計算機上表示會產(chǎn)生誤差，計算過程又可能產(chǎn)生新的誤差，這種誤差稱為舍入誤差.

四、舍入誤差25

若能根據(jù)測量工具或計算情況估計出誤差絕對值的一個上界，即1.1.2誤差與有效數(shù)字

設為準確值，為的一個近似值，

通常準確值是未知的，因此誤差也是未知的.為近似值的絕對誤差，定義1稱簡稱誤差.

則叫做近似值的誤差限，它總是正數(shù).26

例如，用毫米刻度的米尺測量一長度，讀出和該長度接近的刻度，是的近似值，它的誤差限是，于是如讀出的長度為，則有.

雖然從這個不等式不能知道準確的是多少，但可知結(jié)果說明在區(qū)間內(nèi).27

對于一般情形，即也可以表示為

需要注意的是誤差限的大小并不能完全表示近似值的好壞.28

實際計算中，由于真值總是未知的，

把近似值的誤差與準確值的比值稱為近似值的相對誤差，記作.作為的相對誤差，條件是較小，通常取此時利用知29

相對誤差也可正可負，它的絕對值上界叫做相對誤差限，是的平方項級，記作，故可忽略不計.即30

當準確值位數(shù)比較多時，常常按四舍五入的原則得到的前幾位近似值，

取3位

取5位它們的誤差都不超過末位數(shù)字的半個單位，例如即31

若近似值的誤差限是某一位的半個單位，該位到的第一位非零數(shù)字共有位，就說有位有效數(shù)字.

表示為（1）其中是0到9中的一個數(shù)字，為整數(shù)，（2）定義2且32如取作為的近似值，取，按這個定義，就有3位有效數(shù)字，就有5位有效數(shù)字.33

按定義，187.93,0.037856,8.0000,2.7183.的5位有效數(shù)字近似數(shù)是8.0000，而不是8，

例2按四舍五入原則寫出下列各數(shù)具有5位有效數(shù)字的近似數(shù)：187.9325,0.03785551,8.000033,2.7182818.上述各數(shù)具有5位有效數(shù)字的近似數(shù)分別是因為8只有1位有效數(shù)字.注意：34如果以m/s2為單位，

重力常數(shù)g，若以km/s2為單位，，它們都具有3位有效數(shù)字，按(1)的表示方法，這里

它們雖然寫法不同，但都具有3位有效數(shù)字.例3因為按第一種寫法按第二種寫法35

至于絕對誤差限，由于單位不同所以結(jié)果也不同但相對誤差都是

例3說明有效位數(shù)與小數(shù)點后有多少位數(shù)無關.36

從(2)可得到具有位有效數(shù)字的近似數(shù)，其絕對誤差限為在相同的情況下，越大則越小，故有效位數(shù)越多，絕對誤差限越小.（2）371.1.3數(shù)值運算的誤差估計

兩個近似數(shù)與，其誤差限分別為及，它們進行加、減、乘、除運算得到的誤差限分別為38

設是一元函數(shù)，的近似值為，以近似，其誤差界記作，

一般情況下，當自變量有誤差時函數(shù)值也產(chǎn)生誤差，取絕對值得其誤差限可利用函數(shù)的泰勒展開式進行估計.利用泰勒展開39

假定與的比值不太大，可忽略的高階項，于是可得計算函數(shù)的誤差限40

當為多元函數(shù)，如計算時.

的近似值為，則的近似值為于是由泰勒展開，函數(shù)值的誤差為如果41于是誤差限而的相對誤差限為42

已測得某場地長的值為，寬的值為，已知.試求面積的絕對誤差限與相對誤差限.

因知例4解由43其中而于是絕對誤差限相對誤差限441.1.4誤差穩(wěn)定性分析

一個工程或科學計算問題往往要運算千萬次，由于每步運算都有誤差，如果每步都做誤差分析是不可能的，也不科學.

因為誤差積累有正有負，絕對值有大有小，都按最壞情況估計誤差限得到的結(jié)果比實際誤差大得多，這種保守的誤差估計不反映實際誤差積累.45

用一個算法進行計算，如果初始數(shù)據(jù)誤差在計算中傳播使計算結(jié)果的誤差增長很快，這個算法就是數(shù)值不穩(wěn)定的.

計算并估計誤差.

由分部積分可得計算的遞推公式若計算出，代入（3），可逐次求出的值.（3）例546

而要算出就要先計算.并取，則得，

若用泰勒多項式展開部分和用4位小數(shù)計算，截斷誤差47

當初值取為時，用（3）遞推計算結(jié)果見表1-1的列.

用近似產(chǎn)生的誤差就是初值誤差，它對后面計算結(jié)果是有影響的.（3）計算公式為48

從表中看到出現(xiàn)負值，這與一切相矛盾.因此，當較大時，用近似顯然是不正確的.（4）實際上，由積分估值得49

計算公式與每步計算都是正確的，計算結(jié)果錯誤的原因主要就是初值有誤差，由此引起以后各步計算的誤差滿足關系

容易推得這說明有誤差，則就是的倍誤差.50

例如，，若，這就說明完全不能近似了.

若換一種計算方案.由（4）取，取則

它表明計算公式（A）是數(shù)值不穩(wěn)定的.則（4）51將公式(3)倒過來算，即由算出，公式為計算結(jié)果見表1-1的列.（3）52

反之，當用方案（A）計算時，盡管初值相當準確，

此例說明，數(shù)值不穩(wěn)定的算法是不能使用的.

記，則，比縮小了倍，因此，盡管較大，但由于誤差逐步縮小，故可用近似.由于誤差傳播是逐步擴大的，因而計算結(jié)果不可靠.

可以看出與的誤差不超過.53

一個算法如果輸入數(shù)據(jù)有誤差，而在計算過程中舍入誤差不增長，則稱此算法是數(shù)值穩(wěn)定的，否則稱此算法為不穩(wěn)定的.

在例5中算法（B）是數(shù)值穩(wěn)定的，而算法（A）是不穩(wěn)定的.定義32024/5/9不同的算法可能導致不同的計算誤差，應該盡可能選用計算精度高的數(shù)學公式，另外在設計算法時需要注意避免一些損失精度的做法。例如，計算直接累加計算會造成很大的累積誤差只要把公式變換成就只要計算一個除法和一個減法2024/5/9練習56

算法設計的好壞不但影響計算結(jié)果的精度，還可以大量節(jié)省計算時間.

一個計算問題如果能減少運算次數(shù)，不但可以及減少計算量還可以減少誤差，這是算法設計中一個重要原則.多項式求值的秦九韶算法

以多項式求值為例，設給定次多項式求處的值.57可表示為（5）

若直接計算再相加，共需做次乘法和次加法.

若采用則即為所求.這就是秦九韶算法.

用它計算次多項式的值只用次乘法和次加法58

秦九韶算法的另一個好處是求在點的值.由（5）式有其中對求導得故.從而得用秦九韶算法計算的算法如下：59則（6）

例6設，用秦九韶算法求和的值.

解用（5）和（6）式構造出計算表格（1-2）60故61

練習設，用秦九韶算法求和的值.685，116262

以開方運算為例，它不是四則運算，因此在計算機上求開方值就要轉(zhuǎn)化為四則運算，這時就要使用迭代法

迭代法是一種按同一公式重復計算逐次逼近真值的方法，是數(shù)值計算普遍使用的重要方法.2、迭代法與開方求值這種方程求根問題可以用迭代法來解決.現(xiàn)在來用簡單的方法構造迭代法

假定，求等價于解方程（7）63

由于是很小的量，所以可以舍去高階項，則得先給定一個初始近似，令是一個校正量，稱為增量，于是（7）式化為即即于是64（8）這里不是真值，但它是真值的進一步近似，重復以上過程可以得到迭代公式它可逐次求得若則，容易證明序列對任何均收斂，且收斂很快.65

例7用迭代法（8）求，取

解若計算精確到，由（8）式可求得計算停止.由于，可知只要迭代3次誤差即可保證連續(xù)兩次輸出小于.663、

以直代曲與化整為“零”

在數(shù)值計算中將非線性問題線性化是常用方法，幾何上體現(xiàn)為在局部范圍內(nèi)用直線近似曲線.

圓周率的計算是古代數(shù)學的一個光輝成就，充分體現(xiàn)了以直代曲化整為“零”的思想.67這就是方程求根的牛頓迭代法，它是以直代曲建立迭代序列的典型例子.

求函數(shù)方程的根，幾何上表現(xiàn)為平面上的一條曲線，它與軸交點的橫坐標即為方程的根.

假如已給出一個近似根，用該點處的切線逼近該曲線，令為