蒙特卡羅方法及應用

何國祥

摘 要： 本文主要介紹蒙特卡羅方法的基本原理及思想特征，詳細討論了蒙特卡羅方法在計算曲線積分等實際問題中的應用，突出了蒙特卡羅方法的過程及優勢。

關鍵詞： 蒙特卡羅方法 曲線積分 教學應用

1.引言

近些年來，隨著電子計算機的迅速發展與廣泛使用，計算數學獲得了新的發展，增添了許多新內容，蒙特卡羅方法就是其中一種。該方法的出現，極大地促進了科學文明的進步，開辟了人們研究問題的新途徑。

在程序編制和計算機算法設計中常采用的算法一般是確定性算法，也就是算法的每一個計算步驟都是確定的。但是在很多情況下，當算法在執行過程中遇到一個選擇時，隨機性選擇經常比最優選擇更節省時間且效率極高。我們把這種允許算法在執行過程中隨機選擇下一個計算步驟的算法叫做概率算法。概率算法可以很大程度地降低算法的復雜程度。

蒙特卡羅算法、拉斯維加斯算法和舍伍德算法都是一些常用的概率算法。這些算法的基本特征是：對要求問題的同一個例子，用同一概率算法運算若干次，所得到的結果可能完全不同。但是通過多次執行反復求解，會使正確性和精確性達到令人滿意的效果，而失敗或誤差的概率則可以接近無限小[1]。

本文的主要研究內容：

（1）蒙特卡羅方法的基本思想及其基本特點。

（2）蒙特卡羅方法求解問題的基本過程。

（3）蒙特卡羅方法的應用領域。

（4）蒙特卡羅方法在計算曲線積分中的應用。

2.蒙特卡羅方法的基本思想及其基本特點

2.1蒙特卡羅方法的提出

二十世紀四十年代的二戰中美國有個研制原子彈的計劃——“曼哈頓計劃”，該計劃的成員J.馮·諾伊曼和S.M.烏拉姆首先提出蒙特卡羅方法。著名數學家馮·諾伊曼采用世界有名的賭城——摩納哥的Monte Carlo命名這一方法。而實際上，在這之前，蒙特卡羅方法就已經存在。早在1777年，法國著名數學家布豐（Georges Louis Leclere de Buffon，1707-1788）就提出用投針實驗的方法計算圓周率π。這被認為是蒙特卡羅方法的起源。

2.2蒙特卡羅方法概述

蒙特卡羅方法又稱為隨機抽樣技術、統計模擬法，是一種隨機模擬方法，它是以概率和統計理論方法為基礎的一種計算方法，是使用隨機數（或更常見的偽隨機數）解決很多計算問題的方法。將所求解的問題同一定的概率模型聯系起來，用電子計算機實現統計模擬或抽樣，從而獲得問題的近似解。為了象征性地表明這一方法的概率統計特征，所以借用賭城蒙特卡羅命名。

2.3蒙特卡羅方法基本思想

當所要求解的問題是某種隨機事件出現的概率，或者是某個隨機變量的期望值時，通過某個“實驗”的方法，以這種事件出現的頻率估計這個隨機事件的概率，或者得到的這個隨機變量的某些數字特征，并將它們作為問題的解。

3.蒙特卡羅方法求解問題的基本過程

蒙特卡羅方法求解問題的過程大致分為三個主要的步驟。

3.1描述或構造概率過程

對于那些本身就有隨機性質的問題，比如粒子的輸運問題，主要是要對這個概率的過程進行正確的描述和模擬；對于確定性的問題，比如說計算數學上的定積分，就一定要事先人為地構造一個概率過程，而且這個概率過程的一些參量剛好是所要求的問題的解。也就是要把不具有隨機性質的問題轉化為有隨機性質的問題。

3.2實現從已知概率分布抽樣

構造了概率模型以后，因為各種概率模型都可以看做是由各種各樣的概率分布而組成的，因此產生已知概率分布的隨機變量（或隨機向量），就成為實現蒙特卡羅方法模擬實驗基本的手段，這是蒙特卡羅方法被稱為隨機抽樣的原因。最基本、最簡單、最重要的一個概率分布是（0，1）上的均勻分布（或稱矩形分布）。隨機數就是具有這種均勻分布的隨機變量。隨機數序列就是具有這種分布的總體的一個簡單子樣，也就是一個具有此種分布的相互獨立的隨機變數序列。產生隨機數的問題，就是從這個分布的抽樣問題。在計算機中可以用物理方法產生隨機數，但是價格比較昂貴，且不能重復，使用不方便。另一種方法是用數學的遞推公式產生。這樣產生的序列，與真正的隨機數序列不同，所以稱為偽隨機數，或偽隨機數序列。不過，經過多種統計檢驗表明，它與真正的隨機數序列或隨機數具有很相似的性質，所以可將其作為真正的隨機數應用。由已知分布隨機抽樣有很多的方法，不同于從（0，1）上的均勻分布抽樣的是，此類方法都是憑借于隨機序列從而得到實現，也就是說，其前提都是產生隨機數。因此，實現蒙特卡羅方法的基本工具是隨機數。

3.3建立各種估計量

一般來說，概率模型被構造出來并可以從中抽樣以后，一定要確定一個隨機變量，作為所求的問題的解，我們把它叫做無偏估計。建立各種估計量，也就是對模擬實驗的結果進行觀察和記錄，從而把問題的解求出來。

4.蒙特卡羅方法的應用領域

通常蒙特卡羅方法通過構造符合一定規則的隨機數來解決數學上的問題。對于那些因為計算太過復雜而很難得到解析解或根本沒有解析解的問題，蒙特卡羅方法是一種有效的求解出數值解的方法。

除了在數學方面得到很好的應用外，蒙特卡羅方法在其他很多領域也得到很好的應用，比如說蒙特卡羅方法在金融學、工程學、宏觀經濟學、地質學、生物醫學、計算物理學（如粒子輸運計算、空氣動力學計算、量子熱力學計算）及計算機科學等廣泛的領域都得到非常成功的應用。

下面探討蒙特卡羅方法在數學領域中的應用。

5.蒙特卡羅方法在計算曲線積分中的應用

在物理的很多研究時，要求平面或空間中的一條可求長度的曲線形物體的質量，或者一個質點在平面或者空間中沿曲線L從A點運動到B點時力F所做的功，這時就要用到曲線積分。

平面或空間曲中的曲線積分有兩種類型：第一型曲線積分和第二型曲線積分。下面著重探討如何用蒙特卡羅法計算第一型曲線積分。

5.1第一型曲線積分的定義

設L為平面上可求長度的曲線段，f（x，y）為定義在L上的函數。對曲線L做分割T，它把L分成n個可求長度的小曲線段L■（i=1，2，…n），L■的弧長記為Δs■，分割T的細度為‖T‖=■Δs■，在L■上任取一點（ξ■，η■）（i=1，2，…，n），若有極限

■■f（ξ■，η■）Δs■=J，

且J的值與分割T與點（ξ■，η■）的取法無關，則稱此極限為f（x，y）在L上的第一型曲線積分，記作：

？蘩■f（x，y）ds。

5.2第一型曲線積分的一般計算方法

設有光滑曲線

L：x=φ（t），y=ψ（t），t∈[α，β]，

函數f（x，y）為定義在L上的連續函數，則

？蘩■f（x，y）ds=？蘩■■f（φ（t），ψ（t））■dt。

5.3第一型曲線積分的蒙特卡羅計算法

對于L上的曲線積分I=？蘩■f（x，y）ds=？蘩■■f（φ（t），ψ（t））■dt，其中L：x=φ（t），y=ψ（t），t∈[α，β]。令f（t）=f（φ（t），ψ（t））■，則

I=？蘩■■f（t）dt。（1）

在[α，β]上構造一個均勻分布的隨機變量t，則密度函數為

p（t）=■，α

又令

F（t）=f（t）/p（t），p（t）≠00， p（t）=0，

則

I=？蘩■■F（t）p（t）dt=E（F（t））。（2）

（2）式給我們傳達了：F（t）在t∈[α，β]上的數學期望就是（1）式的曲線積分[2]-[4]。

現在只要抽取概率密度為p（t）的隨機變量t的容量為N的隨機樣本t■（i=1，2，…，n），由大數定理就可以得到：

I≈■■f（t■）=■■f（φ（t■），ψ（t■））■。（3）

5.4實例

設L是半橢圓

L：x=2cost，y=3sint， t∈[0，π]，

求第一型曲線積分？蘩■（x■+y■）ds。

首先，由曲線積分方法得：

？蘩■（x■+y■）ds=？蘩■■（4cos■t+9sin■t）■dt。

這樣的積分很難直接求得結果，這里考慮用蒙特卡羅法計算：

？蘩■（x■+y■）ds≈■■（4cos■t■+9sin■t■）■。

用計算機程序模擬10次得到隨機表如下表所示：

模擬1000次得到隨機表如下表所示：

模擬10000次得到隨機表如下表所示：

模擬20000次得到隨機表如下表所示：

模擬30000次得到隨機表如下表所示：

由以上的模擬數據可以看出，模擬次數越多，得出的積分均值越趨于穩定。

5.5三維空間的第一型曲線積分

上面討論的是平面上曲線段的曲線積分，下面開始探討蒙特卡羅法如何應用于三維空間中的曲線積分。對于三維空間中的光滑曲線段：

L：x=φ（t），y=ψ（t），t∈[α，β]，z=ζ（t），

函數f（x，y，z）為定義在L上的連續函數，則

？蘩■f（x，y，z）ds=？蘩■■f（φ（t），ψ（t），ζ（t））■dt，（4）

類比平面上的曲線積分，很容易等到三維空間中，曲線積分的蒙特卡羅算法：

I≈■■f（t■）=■■f（φ（t■），ψ（t■），ζ（t■））■。（5）

6.結論和展望

與其他的計算方法相比較，蒙特卡羅方法有下面幾個優點：

（1）問題的維數不影響該方法的收斂速度。但是很多的數值計算方法，比如計算N重積分時，達到相同的誤差，點數和維數的冪次成正比。

（2）受問題的條件限制的影響不大。

（3）程序的結構簡單，在計算機上實現蒙特卡羅計算時，程序的結構簡單清晰，占用內存單位較少。

當然，蒙特卡羅方法并不是完美的，它也有其缺陷的地方：

（1）偽隨機數的均勻性影響隨機變量取值從而影響結果。

（2）收斂速度慢。蒙特卡羅模擬的收斂速度為O（n■），一般不容易得到精確度較高的近似結果。對于維數比較少（三維以下）的問題，不如其他方法好。

（3）如誤差是概率誤差，誤差與點數（抽樣數）的平方根成反比，而其他數值方法的誤差是確切的，一般情況下，誤差與點數成反比，因此，對于維數不高的問題，數值方法可以給出誤差很小的結果，而且計算量小。

蒙特卡羅方法與其他數值方法都有其本身的一定適用范圍，把二者結合起來，取長補短，發揮它們各自的長處，目前在國外已受到普遍重視，是蒙特卡羅方法發展的一個重要方向。

參考文獻：

[1]王曉東.算法設計與分析[M].北京：清華人學出版社，2008.

[2]黎鎖平.運用蒙特卡羅方法求解隨機性問題[J].甘肅工業大學學報，2001，27（2）：95-97.

[3]姚貴平，等.重積分近似計算方法的討論[J].內蒙古農業大學學報，2000，21（4）：98-101.

[4]宮野.計算多重積分的蒙特卡羅方法與數論網格法[J].大連理工大學學報，2001，41（1）：20-23.

[5]尹增謙，等.蒙特卡羅方法及其應用[J].物理與工程，2002，12（3）：45-49.

[6]易大義，陳道琦.數值分析引論[M].杭州：浙江大學出版社，1998，165-170.

[7]Sobol I M. Asymmetric convergence of approximations of the Monte Carlo method [J]. Computational Mathematics and Mathematical Physics，1993，33：1391-1396.