蒙地卡羅積分
在數學中,蒙地卡羅積分(Monte Carlo integration)是一種使用亂數進行數值積分的技術。它是一種特殊的蒙地卡羅方法,可對定積分進行數值計算。其他演算法通常在規則網格上評估被積函數,而[1]蒙地卡羅隨機選擇被積函數評估的點。 [2]該方法對於高維積分特別有用。 [3]
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/20/MonteCarloIntegrationCircle.svg/220px-MonteCarloIntegrationCircle.svg.png)
概述
編輯在數值積分中,梯形法則等方法使用確定性方法。另一方面,蒙地卡羅積分採用非確定性方法:每種實現都提供不同的結果。在蒙地卡羅中,最終結果是帶有各自誤差線的正確值的近似值,並且正確值很可能在這些誤差線內。
考慮函數 其中 Ω 是 的一個子集,它的體積是:
樸素的蒙地卡羅方法是在Ω上均勻採樣點: [4] 給定N個均勻樣本, I可以被近似為: 這是因為大數法則確保以下結論成立: 我們使用I給出QN的I估計, QN的誤差線(error bars)可以使用方差的無偏估計通過樣本方差來估計。 由此可得: 只要以下序列 是有界的,該方差就會逐漸減小到零,即 1/N 。 那麼,QN的誤差估計就是:
我們看到,QN的誤差是自身的 ,這是平均值的標準誤差乘以 。該結果不依賴於積分的維數,這是蒙地卡羅積分相對於大多數指數依賴維數的確定性方法所具有的優勢。 值得注意的是,與確定性方法不同,誤差的估計不是嚴格的誤差界限;隨機抽樣可能無法揭示被積函數的所有重要特徵,從而導致誤差的低估。
雖然樸素蒙地卡羅適用於簡單的範例,但對確定性演算法的改進只能通過使用特定於問題的採樣分佈的演算法來實現。通過適當的樣本分佈,可以利用以下事實:幾乎所有高維被積函數都是非常局部化的,並且只有小子空間對積分有顯着貢獻。 [5]蒙地卡羅文獻的很大一部分致力於開發改進誤差估計的策略。特別是,分層採樣(將區域劃分為子體)和重要性採樣(從非均勻分佈中採樣)是此類技術的兩個範例。
例子
編輯使用蒙地卡羅方法最典型的例子是估計π。
我們考慮以下函數: 即正方形集合Ω=[−1,1]×[−1,1]的體積是V = 4。 因此,使用蒙地卡羅積分計算π值的粗略方法是在Ω上選取N個亂數並計算: 右圖中,相對誤差 被認為是一個關於N的函數,由此確認 。
C 範例
編輯請記住,以下的程式需要真正的亂數生成器。
int i, throws = 99999, insideCircle = 0;
double randX, randY, pi;
srand(time(NULL));
for (i = 0; i < throws; ++i) {
randX = rand() / (double) RAND_MAX;
randY = rand() / (double) RAND_MAX;
if (randX * randX + randY * randY < 1) ++insideCircle;
}
pi = 4.0 * insideCircle / throws;
Python範例
編輯from numpy import random
import numpy as np
throws = 2000
inside_circle = 0
i = 0
radius = 1
while i < throws:
# Choose random X and Y centered around 0,0
x = random.uniform(-radius, radius)
y = random.uniform(-radius, radius)
# If the point is inside circle, increase variable
if x**2 + y**2 <= radius**2:
inside_circle += 1
i += 1
# Calculate area and print; should be closer to Pi with increasing number of throws
area = (((2 * radius) ** 2) * inside_circle) / throws
print(area)
參見
編輯本章註記
編輯參考文獻
編輯
- Caflisch, R. E. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica. 1998, 7: 1–49. Bibcode:1998AcNum...7....1C. S2CID 5708790. doi:10.1017/S0962492900002804.
- Weinzierl, S. Introduction to Monte Carlo methods. 2000. arXiv:hep-ph/0006269 .
- Press, W. H.; Farrar, G. R. Recursive Stratified Sampling for Multidimensional Monte Carlo Integration. Computers in Physics. 1990, 4 (2): 190. Bibcode:1990ComPh...4..190P. doi:10.1063/1.4822899 .
- Lepage, G. P. A New Algorithm for Adaptive Multidimensional Integration. Journal of Computational Physics. 1978, 27 (2): 192–203. Bibcode:1978JCoPh..27..192L. doi:10.1016/0021-9991(78)90004-9.
- Lepage, G. P. VEGAS: An Adaptive Multi-dimensional Integration Program. Cornell Preprint CLNS 80-447. 1980.
- Hammersley, J. M.; Handscomb, D. C. Monte Carlo Methods. Methuen. 1964. ISBN 978-0-416-52340-9.
- Kroese, D. P.; Taimre, T.; Botev, Z. I. Handbook of Monte Carlo Methods. John Wiley & Sons. 2011.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP. Numerical Recipes: The Art of Scientific Computing 3rd. New York: Cambridge University Press. 2007. ISBN 978-0-521-88068-8.
- MacKay, David. chapter 4.4 Typicality & chapter 29.1 (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. 2003 [2024-03-15]. ISBN 978-0-521-64298-9. MR 2012999. (原始內容存檔於2016-02-17).
- Newman, MEJ; Barkema, GT. Monte Carlo Methods in Statistical Physics. Clarendon Press. 1999.
- Robert, CP; Casella, G. Monte Carlo Statistical Methods 2nd. Springer. 2004. ISBN 978-1-4419-1939-7.
外部連結
編輯- Café math : Monte Carlo Integration : A blog article describing Monte Carlo integration (principle, hypothesis, confidence interval)
- Boost.Math : Naive Monte Carlo integration: Documentation for the C++ naive Monte-Carlo routines
- Monte Carlo applet applied in statistical physics problems[失效連結]