蒙地卡罗积分
在数学中,蒙特卡罗积分(Monte Carlo integration)是一种使用随机数进行数值积分的技术。它是一种特殊的蒙特卡罗方法,可对定积分进行数值计算。其他算法通常在规则网格上评估被积函数,而[1]蒙特卡洛随机选择被积函数评估的点。 [2]该方法对于高维积分特别有用。 [3]
概述
编辑在数值积分中,梯形法则等方法使用确定性方法。另一方面,蒙特卡罗积分采用非确定性方法:每种实现都提供不同的结果。在蒙特卡罗中,最终结果是带有各自误差线的正确值的近似值,并且正确值很可能在这些误差线内。
考虑函数 其中 Ω 是 的一个子集,它的体积是:
朴素的蒙特卡罗方法是在Ω上均匀采样点: [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[失效链接]