蒙特卡羅方法及應(yīng)用

何國(guó)祥

摘 要： 本文主要介紹蒙特卡羅方法的基本原理及思想特征，詳細(xì)討論了蒙特卡羅方法在計(jì)算曲線積分等實(shí)際問(wèn)題中的應(yīng)用，突出了蒙特卡羅方法的過(guò)程及優(yōu)勢(shì)。

關(guān)鍵詞： 蒙特卡羅方法 曲線積分 教學(xué)應(yīng)用

1.引言

近些年來(lái)，隨著電子計(jì)算機(jī)的迅速發(fā)展與廣泛使用，計(jì)算數(shù)學(xué)獲得了新的發(fā)展，增添了許多新內(nèi)容，蒙特卡羅方法就是其中一種。該方法的出現(xiàn)，極大地促進(jìn)了科學(xué)文明的進(jìn)步，開(kāi)辟了人們研究問(wèn)題的新途徑。

在程序編制和計(jì)算機(jī)算法設(shè)計(jì)中常采用的算法一般是確定性算法，也就是算法的每一個(gè)計(jì)算步驟都是確定的。但是在很多情況下，當(dāng)算法在執(zhí)行過(guò)程中遇到一個(gè)選擇時(shí)，隨機(jī)性選擇經(jīng)常比最優(yōu)選擇更節(jié)省時(shí)間且效率極高。我們把這種允許算法在執(zhí)行過(guò)程中隨機(jī)選擇下一個(gè)計(jì)算步驟的算法叫做概率算法。概率算法可以很大程度地降低算法的復(fù)雜程度。

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

本文的主要研究?jī)?nèi)容：

（1）蒙特卡羅方法的基本思想及其基本特點(diǎn)。

（2）蒙特卡羅方法求解問(wèn)題的基本過(guò)程。

（3）蒙特卡羅方法的應(yīng)用領(lǐng)域。

（4）蒙特卡羅方法在計(jì)算曲線積分中的應(yīng)用。

2.蒙特卡羅方法的基本思想及其基本特點(diǎn)

2.1蒙特卡羅方法的提出

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

2.2蒙特卡羅方法概述

蒙特卡羅方法又稱為隨機(jī)抽樣技術(shù)、統(tǒng)計(jì)模擬法，是一種隨機(jī)模擬方法，它是以概率和統(tǒng)計(jì)理論方法為基礎(chǔ)的一種計(jì)算方法，是使用隨機(jī)數(shù)（或更常見(jiàn)的偽隨機(jī)數(shù)）解決很多計(jì)算問(wèn)題的方法。將所求解的問(wèn)題同一定的概率模型聯(lián)系起來(lái)，用電子計(jì)算機(jī)實(shí)現(xiàn)統(tǒng)計(jì)模擬或抽樣，從而獲得問(wèn)題的近似解。為了象征性地表明這一方法的概率統(tǒng)計(jì)特征，所以借用賭城蒙特卡羅命名。

2.3蒙特卡羅方法基本思想

當(dāng)所要求解的問(wèn)題是某種隨機(jī)事件出現(xiàn)的概率，或者是某個(gè)隨機(jī)變量的期望值時(shí)，通過(guò)某個(gè)“實(shí)驗(yàn)”的方法，以這種事件出現(xiàn)的頻率估計(jì)這個(gè)隨機(jī)事件的概率，或者得到的這個(gè)隨機(jī)變量的某些數(shù)字特征，并將它們作為問(wèn)題的解。

3.蒙特卡羅方法求解問(wèn)題的基本過(guò)程

蒙特卡羅方法求解問(wèn)題的過(guò)程大致分為三個(gè)主要的步驟。

3.1描述或構(gòu)造概率過(guò)程

對(duì)于那些本身就有隨機(jī)性質(zhì)的問(wèn)題，比如粒子的輸運(yùn)問(wèn)題，主要是要對(duì)這個(gè)概率的過(guò)程進(jìn)行正確的描述和模擬；對(duì)于確定性的問(wèn)題，比如說(shuō)計(jì)算數(shù)學(xué)上的定積分，就一定要事先人為地構(gòu)造一個(gè)概率過(guò)程，而且這個(gè)概率過(guò)程的一些參量剛好是所要求的問(wèn)題的解。也就是要把不具有隨機(jī)性質(zhì)的問(wèn)題轉(zhuǎn)化為有隨機(jī)性質(zhì)的問(wèn)題。

3.2實(shí)現(xiàn)從已知概率分布抽樣

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

3.3建立各種估計(jì)量

一般來(lái)說(shuō)，概率模型被構(gòu)造出來(lái)并可以從中抽樣以后，一定要確定一個(gè)隨機(jī)變量，作為所求的問(wèn)題的解，我們把它叫做無(wú)偏估計(jì)。建立各種估計(jì)量，也就是對(duì)模擬實(shí)驗(yàn)的結(jié)果進(jìn)行觀察和記錄，從而把問(wèn)題的解求出來(lái)。

4.蒙特卡羅方法的應(yīng)用領(lǐng)域

通常蒙特卡羅方法通過(guò)構(gòu)造符合一定規(guī)則的隨機(jī)數(shù)來(lái)解決數(shù)學(xué)上的問(wèn)題。對(duì)于那些因?yàn)橛?jì)算太過(guò)復(fù)雜而很難得到解析解或根本沒(méi)有解析解的問(wèn)題，蒙特卡羅方法是一種有效的求解出數(shù)值解的方法。

除了在數(shù)學(xué)方面得到很好的應(yīng)用外，蒙特卡羅方法在其他很多領(lǐng)域也得到很好的應(yīng)用，比如說(shuō)蒙特卡羅方法在金融學(xué)、工程學(xué)、宏觀經(jīng)濟(jì)學(xué)、地質(zhì)學(xué)、生物醫(yī)學(xué)、計(jì)算物理學(xué)（如粒子輸運(yùn)計(jì)算、空氣動(dòng)力學(xué)計(jì)算、量子熱力學(xué)計(jì)算）及計(jì)算機(jī)科學(xué)等廣泛的領(lǐng)域都得到非常成功的應(yīng)用。

下面探討蒙特卡羅方法在數(shù)學(xué)領(lǐng)域中的應(yīng)用。

5.蒙特卡羅方法在計(jì)算曲線積分中的應(yīng)用

在物理的很多研究時(shí)，要求平面或空間中的一條可求長(zhǎng)度的曲線形物體的質(zhì)量，或者一個(gè)質(zhì)點(diǎn)在平面或者空間中沿曲線L從A點(diǎn)運(yùn)動(dòng)到B點(diǎn)時(shí)力F所做的功，這時(shí)就要用到曲線積分。

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

5.1第一型曲線積分的定義

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

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

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

？蘩■f（x，y）ds。

5.2第一型曲線積分的一般計(jì)算方法

設(shè)有光滑曲線

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

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

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

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

對(duì)于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）

在[α，β]上構(gòu)造一個(gè)均勻分布的隨機(jī)變量t，則密度函數(shù)為

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）式給我們傳達(dá)了：F（t）在t∈[α，β]上的數(shù)學(xué)期望就是（1）式的曲線積分[2]-[4]。

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

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

5.4實(shí)例

設(shè)L是半橢圓

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

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

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

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

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

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

用計(jì)算機(jī)程序模擬10次得到隨機(jī)表如下表所示：

模擬1000次得到隨機(jī)表如下表所示：

模擬10000次得到隨機(jī)表如下表所示：

模擬20000次得到隨機(jī)表如下表所示：

模擬30000次得到隨機(jī)表如下表所示：

由以上的模擬數(shù)據(jù)可以看出，模擬次數(shù)越多，得出的積分均值越趨于穩(wěn)定。

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

上面討論的是平面上曲線段的曲線積分，下面開(kāi)始探討蒙特卡羅法如何應(yīng)用于三維空間中的曲線積分。對(duì)于三維空間中的光滑曲線段：

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

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

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

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

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

6.結(jié)論和展望

與其他的計(jì)算方法相比較，蒙特卡羅方法有下面幾個(gè)優(yōu)點(diǎn)：

（1）問(wèn)題的維數(shù)不影響該方法的收斂速度。但是很多的數(shù)值計(jì)算方法，比如計(jì)算N重積分時(shí)，達(dá)到相同的誤差，點(diǎn)數(shù)和維數(shù)的冪次成正比。

（2）受問(wèn)題的條件限制的影響不大。

（3）程序的結(jié)構(gòu)簡(jiǎn)單，在計(jì)算機(jī)上實(shí)現(xiàn)蒙特卡羅計(jì)算時(shí)，程序的結(jié)構(gòu)簡(jiǎn)單清晰，占用內(nèi)存單位較少。

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

（1）偽隨機(jī)數(shù)的均勻性影響隨機(jī)變量取值從而影響結(jié)果。

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

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

蒙特卡羅方法與其他數(shù)值方法都有其本身的一定適用范圍，把二者結(jié)合起來(lái)，取長(zhǎng)補(bǔ)短，發(fā)揮它們各自的長(zhǎng)處，目前在國(guó)外已受到普遍重視，是蒙特卡羅方法發(fā)展的一個(gè)重要方向。

參考文獻(xiàn)：

[1]王曉東.算法設(shè)計(jì)與分析[M].北京：清華人學(xué)出版社，2008.

[2]黎鎖平.運(yùn)用蒙特卡羅方法求解隨機(jī)性問(wèn)題[J].甘肅工業(yè)大學(xué)學(xué)報(bào)，2001，27（2）：95-97.

[3]姚貴平，等.重積分近似計(jì)算方法的討論[J].內(nèi)蒙古農(nóng)業(yè)大學(xué)學(xué)報(bào)，2000，21（4）：98-101.

[4]宮野.計(jì)算多重積分的蒙特卡羅方法與數(shù)論網(wǎng)格法[J].大連理工大學(xué)學(xué)報(bào)，2001，41（1）：20-23.

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

[6]易大義，陳道琦.數(shù)值分析引論[M].杭州：浙江大學(xué)出版社，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.