蒙特卡羅方法

1、1. 蒙特卡羅方法的基本思想蒙特卡羅方法的基本思想2. 蒙特卡羅方法的收斂性，誤差蒙特卡羅方法的收斂性，誤差3. 蒙特卡羅方法的特點(diǎn)蒙特卡羅方法的特點(diǎn)4. 蒙特卡羅方法的主要應(yīng)用范圍蒙特卡羅方法的主要應(yīng)用范圍 蒙特卡羅方法又稱隨機(jī)抽樣技巧或統(tǒng)計(jì)試驗(yàn)方法。半個(gè)多世紀(jì)以來(lái)，由于科學(xué)技術(shù)的發(fā)展和電子計(jì)算機(jī)的發(fā)明 ，這種方法作為一種獨(dú)立的方法被提出來(lái)，并首先在核武器的試驗(yàn)與研制中得到了應(yīng)用。 蒙特卡羅方法是一種計(jì)算方法，但與一般數(shù)值計(jì)算方法有很大區(qū)別。它是以概以概率統(tǒng)計(jì)理論為基礎(chǔ)的一種方法率統(tǒng)計(jì)理論為基礎(chǔ)的一種方法。由于蒙特卡羅方法能夠比較逼真地描述事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程，解決一些數(shù)值方法難以解決的

2、問(wèn)題，因而該方法的應(yīng)用領(lǐng)域日趨廣泛。 兩個(gè)例子 例1. 蒲豐氏問(wèn)題 例2. 射擊問(wèn)題（打靶游戲） 例3. 積分基本思想計(jì)算機(jī)模擬試驗(yàn)過(guò)程將長(zhǎng)為2l的一根針任意投到地面上，用針與一組相間距離為2a（la）的平行線相交的頻率代替概率P，再利用準(zhǔn)確的關(guān)系式： 求出值 其中為投計(jì)次數(shù)，n為針與平行線相交次數(shù)。alP2)(22nNalaPl 一些人進(jìn)行了實(shí)驗(yàn)，其結(jié)果列于下表 ：實(shí)驗(yàn)者年份投計(jì)次數(shù)的實(shí)驗(yàn)值沃爾弗(Wolf)185050003.1596斯密思(Smith)185532043.1553?？怂?Fox)189411203.1419拉查里尼(Lazzarini)190134083.1415929

3、設(shè)r表示射擊運(yùn)動(dòng)員的彈著點(diǎn)到靶心的距離，(r)表示擊中r處相應(yīng)的得分?jǐn)?shù)（環(huán)數(shù)），f(r)為該運(yùn)動(dòng)員的彈著點(diǎn)的分布密度函數(shù)，它反映運(yùn)動(dòng)員的射擊水平。該運(yùn)動(dòng)員的射擊成績(jī)?yōu)?用概率語(yǔ)言來(lái)說(shuō)，是隨機(jī)變量(r)的數(shù)學(xué)期望，即 )(rgEg 0)()(drrfrgg 現(xiàn)假設(shè)該運(yùn)動(dòng)員進(jìn)行了次射擊，每次射擊的彈著點(diǎn)依次為r1，r2，rN，則次得分g(r1)，g(r2)，g(rN)的算術(shù)平均值 代表了該運(yùn)動(dòng)員的成績(jī)。換言之，為積分的估計(jì)值，或近似值。 在該例中，用用次試驗(yàn)所得成績(jī)的算術(shù)平次試驗(yàn)所得成績(jī)的算術(shù)平均值作為數(shù)學(xué)期望均值作為數(shù)學(xué)期望 的估計(jì)值的估計(jì)值（積分近似值）。 NiiNrgNg1)(1 當(dāng)所求問(wèn)題

4、的解是某個(gè)事件的概率，或者是某個(gè)隨機(jī)變量的數(shù)學(xué)期望，或者是與概率、數(shù)學(xué)期望有關(guān)的量時(shí)，通過(guò)某種試驗(yàn)的方法，得出該事件發(fā)生的頻率，或者該隨機(jī)變量若干個(gè)具體觀察值的算術(shù)平均值，通過(guò)它得到問(wèn)題的解。這就是蒙特卡羅方法的基本思想。 蒙特卡羅方法是用隨機(jī)試驗(yàn)的方法計(jì)算積分，即將所要計(jì)算的積分看作服從某種分布密度函數(shù)f(r)的隨機(jī)變量(r)的數(shù)學(xué)期望 通過(guò)某種試驗(yàn)，得到個(gè)觀察值r1，r2，rN（用概率語(yǔ)言來(lái)說(shuō)，從分布密度函數(shù)f(r)中抽取個(gè)子樣r1，r2，rN，），將相應(yīng)的個(gè)隨機(jī)變量的值g(r1)，g(r2)，g(rN)的算術(shù)平均值 作為積分的估計(jì)值（近似值）。 NiiNrgNg1)(10)()(drrf

5、rgg 計(jì)算機(jī)模擬試驗(yàn)過(guò)程，就是將試驗(yàn)過(guò)程（如投針，射擊）化為數(shù)學(xué)問(wèn)題，在計(jì)算機(jī)上實(shí)現(xiàn)。以上述兩個(gè)問(wèn)題為例，分別加以說(shuō)明。 例1. 蒲豐氏問(wèn)題 例2. 射擊問(wèn)題（打靶游戲） 例3. 求積分問(wèn)題 設(shè)針投到地面上的位置可以用一組參數(shù)（x,）來(lái)描述，x為針中心的坐標(biāo)，為針與平行線的夾角，如圖所示。 任意投針，就是意味著x與都是任意取的，但x的范圍限于0，a，夾角的范圍限于0，。在此情況下，針與平行線相交的數(shù)學(xué)條件是:針在平行線間的位置 sin lx 如何產(chǎn)生任意的（x,）？X在0，a上任意取值，表示x在0，a上是均勻分布的，其分布密度函數(shù)為：類似地，的分布密度函數(shù)為：因此，產(chǎn)生任意的（x,）的過(guò)程就

6、變成了由f1(x)抽樣x及由f2() 抽樣的過(guò)程了。由此得到： 其他, 00,/1)(1axaxf其他, 00,/1)(2f21 ax 其中1，2均為0,1上均勻分布的隨機(jī)變量。 每次投針試驗(yàn)，實(shí)際上變成在計(jì)算機(jī)上從兩個(gè)均勻分布的隨機(jī)變量中抽樣得到（x,），然后定義描述針與平行線相交狀況的隨機(jī)變量s(x,)，為 如果投針次，則 是針與平行線相交概率的估計(jì)值。事實(shí)上， 于是有: 其他當(dāng), 0sin, 1),(lxxsNiiiNxsNs1),(1aladxddxdfxfxsPl2)()(),(sin0021NsalaPl22 int main() /文件地址F:PuFengShiPuFengShi

7、0 const int N = 5000000; /總的投樣次數(shù) const double PI = 3.1415926535898; /定義的初始值，用于抽樣角 const double a = 2.0, l = 1.8; /定義平行線半間距a及針半長(zhǎng)l double pi = 0.0f; /初始化所要計(jì)算的值 double x = 0.0f, theta = 0.0f; int Count = 0; /針與直線相交的次數(shù)/用該語(yǔ)句初始化Rand()函數(shù)，使得每次產(chǎn)生的隨機(jī)數(shù)均不同/參見(jiàn)http:/ srand( (unsigned int)time(NULL)*1000 ); /srand

8、函數(shù)內(nèi)為實(shí)數(shù)時(shí),每次計(jì)算結(jié)果相同 for(int i=0; i N; i+) x = a * rand()/RAND_MAX; /rand()/RAND_MAX為0,1間的隨機(jī)數(shù)，此為抽樣x與 theta = PI * rand()/RAND_MAX; if( x = l*sin(theta) ) /記錄針與平行線相交次數(shù)于Count中 Count+ ; pi = 2.0f*l/a; pi = pi * (double)N/Count; /計(jì)算值 cout PI = pi endl; /在屏幕上輸出所要計(jì)算的值及相對(duì)偏差 cout 相對(duì)誤差 = fabs(PI - pi)/PI * 100.0

9、f % endl; cout - endl; return 0;示意圖結(jié)論： 在邊長(zhǎng)為2的圓內(nèi)投點(diǎn)N次，如果有M個(gè)點(diǎn)分布在圓內(nèi)，那么當(dāng)N時(shí)，進(jìn)入圓內(nèi)點(diǎn)數(shù)的概率即為圓面積與正方形面積之積221424MMNN 設(shè)射擊運(yùn)動(dòng)員的彈著點(diǎn)分布為 用計(jì)算機(jī)作隨機(jī)試驗(yàn)（射擊）的方法為，選取一個(gè)隨機(jī)數(shù)，按右邊所列方法判斷得到成績(jī)。 這樣，就進(jìn)行了一次隨機(jī)試驗(yàn)（射擊），得到了一次成績(jī) (r)，作次試驗(yàn)后，得到該運(yùn)動(dòng)員射擊成績(jī)的近似值 環(huán)數(shù) 78910概率 0.5環(huán)中命環(huán)命中環(huán)命中環(huán)命中1095 . 082 . 071 . 0NiiNrgNg1)(1011011011011,nnbbbnnaaas

10、f x xxdx dxdx 計(jì)算下列多重積分計(jì)算下列多重積分 01111011000 1t , t ,t,0,1,1xbt ,0,1,11,biiiniijjjjjmniiinjjjiimaajnmsf xxxam方法：取之間的均勻分布的隨機(jī)數(shù)點(diǎn)列取當(dāng) 充分大時(shí)，即隨機(jī)數(shù)的個(gè)數(shù)取得足夠多時(shí)，與常見(jiàn)數(shù)值離散積分方法的比較以一次積分為例： basf x dx把積分區(qū)間a, b分割為m個(gè)均勻步長(zhǎng)，則步長(zhǎng)hhbam那么，按照微積分的思想，上述積分可以近似表示為： 110011 22mmbiiaiiibasf x dxf x hf xmixaihabam蒙特卡羅方法常以一個(gè)“概率模型”為基礎(chǔ)，按照它所描

11、述的過(guò)程，使用由已知分布抽樣的方法，得到部分試驗(yàn)結(jié)果的觀察值，求得問(wèn)題的近似解。 蒙特卡羅方法作為一種計(jì)算方法，其收斂性與誤差是普遍關(guān)心的一個(gè)重要問(wèn)題。收斂性誤差減小方差的各種技巧 效率蒙特卡羅方法是由隨機(jī)變量X的簡(jiǎn)單子樣X(jué)1，X2，XN的算術(shù)平均值： 作為所求解的近似值。由大數(shù)定律(辛欽定理)可知， 如X1，X2，XN獨(dú)立同分布，且具有有限期望值(E(X)，則 即隨機(jī)變量X的簡(jiǎn)單子樣的算術(shù)平均值 ，當(dāng)子樣數(shù)充分大時(shí)，以概率1收斂于它的期望值E(X)。NiiNXNX111)(limXEXPNNNX 概率論的中心極限定理指出，如果隨機(jī)變量序列X1，X2，XN獨(dú)立同分布，且具有有限非零的方差2 ，

12、即 f(X)是X的分布密度函數(shù)。則dtexXEXNPxxtNN2/221)(limdxxfXEx)()(022 當(dāng)N充分大時(shí)，有如下的近似式 其中稱為置信度，1稱為置信水平。 這表明，不等式 近似地以概率 1成立，且誤差收斂速度的階為 。 通常，蒙特卡羅方法的誤差定義為 上式中x與置信度是一一對(duì)應(yīng)的，根據(jù)問(wèn)題的要求確定出置信水平后，查標(biāo)準(zhǔn)正態(tài)分布表，就可以確定出x。 2/202()12xtNxPXE XedtxN ()NxXE XN)(2/1NOxN 下面給出幾個(gè)常用的與x的數(shù)值： 1.蒙特卡羅方法的誤差為概率誤差，這與其他數(shù)值 計(jì)算方法是有區(qū)別的。2.誤差中的均方差是未知的，必須使用其估計(jì)值

13、 來(lái)代替，在計(jì)算所求量的同時(shí)，可計(jì)算出 。 0.50.050.003x 0.67451.96322221111()NNiiiiD XE XE XXXNN 當(dāng)給定置信度后，誤差由和N決定。在在固定固定的情況下，要把精度提高一個(gè)數(shù)量級(jí)，的情況下，要把精度提高一個(gè)數(shù)量級(jí)，試驗(yàn)次數(shù)試驗(yàn)次數(shù)N需增加兩個(gè)數(shù)量級(jí)需增加兩個(gè)數(shù)量級(jí)。 如能減小估計(jì)的均方差，比如降低一半，那誤差就減小一半，這相當(dāng)于N增大四倍的效果。因此降低方差的各種技巧，引起了人們的普遍注意。后面課程將會(huì)介紹一些降低方差的技巧。 降低方差的技巧，往往使觀察一個(gè)子樣的時(shí)間增加。在固定時(shí)間內(nèi)，使觀察的樣本數(shù)減少。所以，一種方法的優(yōu)劣，需要由方差和觀察一個(gè)子樣的費(fèi)用（使用計(jì)算機(jī)的時(shí)間）兩者來(lái)衡量。這就是蒙特卡羅方法中效率的概念。它定義為 ，其中c是觀察一個(gè)子樣的平均費(fèi)用。顯然 越小，方法越有效。 c2c2優(yōu)點(diǎn)1) 能夠比較逼真地描述具有隨機(jī)性質(zhì)的事物的特點(diǎn)及物理實(shí)驗(yàn)過(guò)程。2) 受幾何條件限制小。3) 收斂速度與問(wèn)題的維數(shù)無(wú)關(guān)。4) 具有同時(shí)計(jì)算多個(gè)方案與多個(gè)未知量的能力。5) 誤差容易確定。6) 程序結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)。 缺點(diǎn)1) 收斂速度慢。2