1、第一章 蒙特卡羅方法概述 蒙特卡羅方法的根本思想蒙特卡羅方法的根本思想 蒙特卡羅方法的收斂性，誤差蒙特卡羅方法的收斂性，誤差 蒙特卡羅方法的特點蒙特卡羅方法的特點 蒙特卡羅方法的主要應用范圍蒙特卡羅方法的主要應用范圍作作 業業第一章 蒙特卡羅方法概述 蒙特卡羅方法又稱隨機抽樣技巧或統計試驗方法。半個多世紀以來，由于科學技術的開展和電子計算機的創造 ，這種方法作為一種獨立的方法被提出來，并首先在核武器的試驗與研制中得到了應用。蒙特卡羅方法是一種計算方法，但與一般數值計算方法有很大區別。它是以概率統計理論為根底的一種方法。由于蒙特卡羅方法可以比較逼真地描繪事物的特點及物理實驗過程，解決一些數值方法

2、難以解決的問題，因此該方法的應用領域日趨廣泛。蒙特卡羅方法的根本思想 二十世紀四十年代中期，由于科學技術的開展和電子計算機的創造，蒙特卡羅方法作為一種獨立的方法被提出來，并首先在核武器的試驗與研制中得到了應用。但其根本思想并非新穎，人們在消費理論和科學試驗中就已發現，并加以利用。兩個例子 例1. 蒲豐氏問題 例2. 射擊問題打靶游戲根本思想計算機模擬試驗過程例1. 蒲豐氏問題 為了求得圓周率值，在十九世紀后期，有很多人作了這樣的試驗：將長為2l的一根針任意投到地面上，用針與一組相間間隔 為2a la的平行線相交的頻率代替概率P，再利用準確的關系式： 求出值 其中為投計次數，n為針與平行線相交次

3、數。這就是古典概率論中著名的蒲豐氏問題。alP2)(22nNalaPl 一些人進展了實驗，其結果列于下表 ：實驗者年份投計次數的實驗值沃爾弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼(Lazzarini)190134083.1415929例2. 射擊問題打靶游戲 設r表示射擊運發動的彈著點到靶心的間隔 ，r表示擊中r處相應的得分數環數，fr為該運發動的彈著點的分布密度函數，它反映運發動的射擊程度。該運發動的射擊成績為 )(rgEg 0)()(drrfrgg 現假設該運發動進展了次射擊，每次射擊的彈

4、著點依次為r1，r2，rN，那么次得分gr1，gr2，grN的算術平均值 代表了該運發動的成績。換言之，為積分的估計值，或近似值。 在該例中，用次試驗所得成績的算術平均值作為數學期望的估計值積分近似值。 NiiNrgNg1)(1 根本思想 由以上兩個例子可以看出，當所求問題的解是某個事件的概率，或者是某個隨機變量的數學期望，或者是與概率、數學期望有關的量時，通過某種試驗的方法，得出該事件發生的頻率，或者該隨機變量假設干個詳細觀察值的算術平均值，通過它得到問題的解。這就是蒙特卡羅方法的根本思想。 因此，可以通俗地說，蒙特卡羅方法是用隨機試驗的方法計算積分，即將所要計算的積分看作服從某種分布密度函

5、數fr的隨機變量r的數學期望 通過某種試驗，得到個觀察值r1，r2，rN用概率語言來說，從分布密度函數fr中抽取個子樣r1，r2，rN，將相應的個隨機變量的值gr1，gr2，grN的算術平均值 作為積分的估計值近似值。 NiiNrgNg1)(10)()(drrfrgg 為了得到具有一定準確度的近似解，所需試驗的次數是很多的，通過人工方法作大量的試驗相當困難，甚至是不可能的。因此，蒙特卡羅方法的根本思想雖然早已被人們提出，卻很少被使用。本世紀四十年代以來，由于電子計算機的出現，使得人們可以通過電子計算機來模擬隨機試驗過程，把宏大數目的隨機試驗交由計算機完成，使得蒙特卡羅方法得以廣泛地應用，在現代

6、化的科學技術中發揮應有的作用。 計算機模擬試驗過程 計算機模擬試驗過程，就是將試驗過程如投針，射擊化為數學問題，在計算機上實現。以上述兩個問題為例，分別加以說明。 例1. 蒲豐氏問題 例2. 射擊問題打靶游戲 由上面兩個例題看出，蒙特卡羅方法常以一個“概率模型為根底，按照它所描繪的過程，使用由分布抽樣的方法，得到部分試驗結果的觀察值，求得問題的近似解。 例蒲豐氏問題 設針投到地面上的位置可以用一組參數x,來描繪，x為針中心的坐標，為針與平行線的夾角，如下圖。 任意投針，就是意味著x與都是任意取的，但x的范圍限于0，a，夾角的范圍限于0，。在此情況下，針與平行線相交的數學條件是針在平行線間的位置

7、 sin lx 如何產生任意的x,？x在0，a上任意取值，表示x在0，a上是均勻分布的，其分布密度函數為： 類似地，的分布密度函數為： 因此，產生任意的x,的過程就變成了由f1x抽樣x及由f2抽樣的過程了。由此得到： 其中1，2均為0,1上均勻分布的隨機變量。 其他, 00,/1)(1axaxf其他, 00,/1)(2f21 ax 每次投針試驗，實際上變成在計算機上從兩個均勻分布的隨機變量中抽樣得到x,，然后定義描繪針 與 平 行 線 相 交 狀 況 的 隨 機 變 量sx,，為 假如投針次，那么 是針與平行線相交概率的估計值。事實上， 于是有 其他當, 0sin, 1),(lxxsNiiiN

8、xsNs1),(1aladxddxdfxfxsPl2)()(),(sin0021NsalaPl22例射擊問題 設射擊運發動的彈著點分布為 用計算機作隨機試驗射擊的方法為，選取一個隨機數，按右邊所列方法判斷得到成績。 這樣，就進展了一次隨機試驗射擊，得到了一次成績 r，作次試驗后，得到該運發動射擊成績的近似值 環數 78910概率 0.10.10.30.5環中命環命中環命中環命中1095 . 082 . 071 . 0NiiNrgNg1)(1蒙特卡羅方法的收斂性，誤差 蒙特卡羅方法作為一種計算方法，其收斂性與誤差是普遍關心的一個重要問題。收斂性誤差減小方差的各種技巧 效率 收斂性 由前面介紹可知

9、，蒙特卡羅方法是由隨機變量X的簡單子樣X1，X2，XN的算術平均值： 作為所求解的近似值。由大數定律可知， 如X1，X2，XN獨立同分布，且具有有限期望值EX，那么 即隨機變量X的簡單子樣的算術平均值 ，當子樣數充分大時，以概率1收斂于它的期望值EX。NiiNXNX111)(limXEXPNNNX 誤差 蒙特卡羅方法的近似值與真值的誤差問題，概率論的中心極限定理給出了答案。該定理指出，假如隨機變量序列X1，X2，XN獨立同分布，且具有有限非零的方差2 ，即 fX是X的分布密度函數。那么dtexXEXNPxxtNN2/221)(limdxxfXEx)()(022 當N充分大時，有如下的近似式 其

10、中稱為置信度，1稱為置信程度。 這說明，不等式 近似地以概率 1成立，且誤差收斂速度的階為 。 通常，蒙特卡羅方法的誤差定義為 上式中 與置信度是一一對應的，根據問題的要求確定出置信程度后，查標準正態分布表，就可以確定出 。122)(02/2dteNXEXPtNNXEXN)()(2/1NON 下面給出幾個常用的與的數值： 關于蒙特卡羅方法的誤差需說明兩點：第一，蒙特卡羅方法的誤差為概率誤差，這與其他數值計算方法是有區別的。第二，誤差中的均方差是未知的，必須使用其估計值 來代替，在計算所求量的同時，可計算出 。 0.50.050.003 0.67451.9632112)1(1NiiNiiXNXN

11、 減小方差的各種技巧 顯然，當給定置信度后，誤差由和N決定。要減小，或者是增大N，或者是減小方差2。在固定的情況下，要把精度進步一個數量級，試驗次數N需增加兩個數量級。因此，單純增大N不是一個有效的方法。 另一方面，如能減小估計的均方差，比方降低一半，那誤差就減小一半，這相當于N增大四倍的效果。因此降低方差的各種技巧，引起了人們的普遍注意。后面課程將會介紹一些降低方差的技巧。 效率 一般來說，降低方差的技巧，往往會使觀察一個子樣的時間增加。在固定時間內，使觀察的樣本數減少。所以，一種方法的優劣，需要由方差和觀察一個子樣的費用使用計算機的時間兩者來衡量。這就 是蒙特卡羅方法中效率的概念。它定義為

12、 ，其中c 是觀察一個子樣的平均費用。顯然 越小，方法越有效。 c2c2蒙特卡羅方法的特點優點 可以比較逼真地描繪具有隨機性質的事物的特點及物理實驗過程。 受幾何條件限制小。 收斂速度與問題的維數無關。 具有同時計算多個方案與多個未知量的才能。 誤差容易確定。 程序構造簡單，易于實現。 缺點 收斂速度慢。 誤差具有概率性。 在粒子輸運問題中，計算結果與系統大小有關。可以比較逼真地描繪具有隨機性質的事物的特點及物理實驗過程 從這個意義上講，蒙特卡羅方法可以部分代替物理實驗，甚至可以得到物理實驗難以得到的結果。用蒙特卡羅方法解決實際問題，可以直接從實際問題本身出發，而不從方程或數學表達式出發。它有

13、直觀、形象的特點。受幾何條件限制小 在計算s維空間中的任一區域Ds上的積分 時，無論區域Ds的形狀多么特殊，只要能給出描繪Ds的幾何特征的條件，就可以從Ds中均勻產生N個點 ，得到積分的近似值。 其中Ds為區域Ds的體積。這是數值方法難以作到的。 另外，在具有隨機性質的問題中，如考慮的系統形狀很復雜，難以用一般數值方法求解，而使用蒙特卡羅方法，不會有原那么上的困難。 ssDdxdxdxxxxggs2121),( ),()()(2)(1isiixxxNiisiisNxxxgNDg1)()(2)(1),(收斂速度與問題的維數無關 由誤差定義可知，在給定置信程度情況下，蒙特卡羅方法的收斂速度為，與問

14、題本身的維數無關。維數的變化，只引起抽樣時間及估計量計算時間的變化，不影響誤差。也就是說，使用蒙特卡羅方法時，抽取的子樣總數N與維數s無關。維數的增加，除了增加相應的計算量外，不影響問題的誤差。這一特點，決定了蒙特卡羅方法對多維問題的適應性。而一般數值方法，比方計算定積分時，計算時間隨維數的冪次方而增加，而且，由于分點數與維數的冪次方成正比，需占用相當數量的計算機內存，這些都是一般數值方法計算高維積分時難以抑制的問題。)(2/1NO具有同時計算多個方案與多個未知量的才能 對于那些需要計算多個方案的問題，使用蒙特卡羅方法有時不需要像常規方法那樣逐個計算，而可以同時計算所有的方案，其全部計算量幾乎

15、與計算一個方案的計算量相當。例如，對于屏蔽層為均勻介質的平板幾何，要計算假設干種厚度的穿透概率時，只需計算最厚的一種情況，其他厚度的穿透概率在計算最厚一種情況時稍加處理便可同時得到。 另外，使用蒙特卡羅方法還可以同時得到假設干個所求量。例如，在模擬粒子過程中，可以同時得到不同區域的通量、能譜、角分布等，而不像常規方法那樣，需要逐一計算所求量。 誤差容易確定 對于一般計算方法，要給出計算結果與真值的誤差并不是一件容易的事情，而蒙特卡羅方法那么不然。根據蒙特卡羅方法的誤差公式，可以在計算所求量的同時計算出誤差。對干很復雜的蒙特卡羅方法計算問題，也是容易確定的。 一般計算方法常存在著有效位數損失問題

16、，而要解決這一問題有時相當困難，蒙特卡羅方法那么不存在這一問題。 程序構造簡單，易于實現 在計算機上進展蒙特卡羅方法計算時，程序構造簡單，分塊性強，易于實現。 收斂速度慢 如前所述，蒙特卡羅方法的收斂速度為 ，一般不容易得到準確度較高的近似結果。對于維數少三維以下的問題，不如其他方法好。 )(2/1NO誤差具有概率性 由于蒙特卡羅方法的誤差是在一定置信程度下估計的，所以它的誤差具有概率性，而不是一般意義下的誤差。 在粒子輸運問題中，計算結果與系統大小有關 經歷說明，只有當系統的大小與粒子的平均自由程可以相比較時一般在十個平均自由程左右，蒙特卡羅方法計算的結果較為滿意。但對于大系統或小概率事件的計算問題，計算結果往往比真值偏低。而對于大系統，數值方法那么是適用的。 因此，在使用蒙特卡羅方法時，可以考慮把蒙特卡羅方法與解析或數值方法相結合，取長補短，既能解決解析或數值方法難以解決的問題，也可以解決單純使用蒙特卡羅方法難以解決的問題。這樣，可以發揮蒙特卡羅方法的特長，使其應用范圍更加廣泛。 蒙特卡羅方法的主要應用范圍 蒙特卡羅方法所特有的優點，使得它的應用范圍越來越廣。它的主要應用范圍包括：粒子輸運問題，統計物理，典型