蒙特卡洛算法案例_蒙特卡洛原理

蒙特卡洛算法案例_蒙特卡洛原理从今天开始要研究SamplingMethods,主要是MCMC算法。本文是开篇文章,先来了解蒙特卡洛算法。Contents1.蒙特卡洛介绍2.蒙特卡洛的应用3.蒙特卡洛积分1.蒙特

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

从今天开始要研究Sampling Methods,主要是MCMC算法。本文是开篇文章,先来了解蒙特卡洛算法

 

 

Contents

 

   1. 蒙特卡洛介绍

   2. 蒙特卡洛的应用

   3. 蒙特卡洛积分

 

 

 

1. 蒙特卡洛介绍

 

   蒙特卡罗方法(Monte Carlo method),也称统计模拟方法,是二十世纪四十年代中期由于科学技术的

   发展和电子计算机的发明,而被提出的一种以概率统计理论为指导的一类非常重要的数值计算方法。是指使

   用随机数(或伪随机数)来解决很多计算问题的方法。与它对应的是确定性算法。蒙特卡罗方法在融工程

   学,宏观经济学,计算物理学(如粒子输运计算、量子热力学计算、空气动力学计算)等领域应用广泛。

 

   蒙特卡罗方法于20世纪40年代美国在第二次世界大战中研制原子弹的“曼哈顿计划”计划的成员S.M.乌拉姆

   和J.冯·诺伊曼首先提出。数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法,

   为它蒙上了一层神秘色彩。在这之前,蒙特卡罗方法就已经存在。1777年,法国数学家布丰提出用投针实验

   的方法求圆周率,这被认为是蒙特卡罗方法的起源。

 

   另外,拟蒙特卡洛算法在近几年也获得迅速发展。这种方法是用确定性的超均匀分布代替蒙特卡洛算法中的

   随机数序列,对于某些特定问题计算速度比普通的蒙特卡洛算法高几百倍。

 

   由于产生随机数的随机性,当我们用N个随机点以蒙特卡罗方法来求解具体的问题时,其计算得到近似解的误

   差值有大有小,但是肯定有一个确定的平均值,即一些误差大于此值,而其余误差小于此值。鉴于此,显然肯

   定存在这样的N个点,使得误差的绝对值不大于平均值。如果我们能够构造这样的点集,就可以对原有的方法

   进行较大的改进。拟蒙特卡罗方法就是至于此而提出的,它致力于构造其误差比平均误差显著要好的那种点集,

   而其求解形式与蒙特卡罗方法一致,只不过所用的随机数不一样。用蒙特卡罗方法求解问题时,影响结果好坏

   的主要是随机数序列的均匀性。而拟蒙特卡罗方法中的具有低偏差的一致分布点集较伪随机数序列更为均匀,

   而且用拟蒙特卡罗方法求解得到的是真正的误差,避免了蒙特卡罗方法得到概率误差的缺陷。

   由此可见用拟蒙特卡罗方法求解问题的关键是如何找到一个均匀散布的点集。目前常用的点集有GLP点集(好格

   子点集,good lattice point set)、GP点集(好点集,good point set)、Halton点集及其变体、

   Hammersley点集等。

 

   蒙特卡洛方法的理论基础是大数定律。大数定律是描述相当多次数重复试验的结果的定律,根据这个定律知道

   样本数量越多,其平均就越趋近于真实值。

 

 

 

2. 蒙特卡洛的应用

 

   最经典的应用就是利用蒙特卡洛算法求圆周率。代码如下

 

代码:

 1 #include <bits/stdc++.h>
 2 
 3 #define MAX_ITERS 1000000
 4 
 5 using namespace std;
 6 
 7 double Rand(double L, double R)
 8 {
 9     return L + (R - L) * rand() * 1.0 / RAND_MAX;
10 }
11 
12 double GetPi()
13 {
14     srand(time(NULL));
15     int cnt = 0;
16     for(int i = 0; i < MAX_ITERS; i++)
17     {
18         double x = Rand(-1, 1);
19         double y = Rand(-1, 1);
20         if(x * x + y * y <= 1)
21             cnt++;
22     }
23     return cnt * 4.0 / MAX_ITERS;
24 }
25 
26 int main()
27 {
28     for(int i = 0; i < 10; i++)
29         cout << GetPi() << endl;
30     return 0;
31 }

3. 蒙特卡洛积分

 

   关于蒙特卡洛求积分,可以先参照如下文章。

 

   链接:http://cos.name/2010/03/monte-carlo-method-to-compute-integration/ 

 

   接下来用蒙特卡洛积分求自然常数蒙特卡洛算法案例_蒙特卡洛原理。这是2015年阿里的一道笔试题。

 

   首先考虑如下积分

 

       蒙特卡洛算法案例_蒙特卡洛原理

 

   接下来分别用蒙特卡洛积分牛顿莱布尼兹公式计算,在蒙特卡洛方法中样本很多时,它们的值应该相等。

 

   利用蒙特卡洛方法,图像大致如下

 

       蒙特卡洛算法案例_蒙特卡洛原理

 

    上述积分的目的是求阴影部分的面积,所以先在所标矩形内取蒙特卡洛算法案例_蒙特卡洛原理对随机点蒙特卡洛算法案例_蒙特卡洛原理

    对于每一对蒙特卡洛算法案例_蒙特卡洛原理,考察是否满足如下条件

 

         蒙特卡洛算法案例_蒙特卡洛原理

 

    假设满足上述条件的点有蒙特卡洛算法案例_蒙特卡洛原理个,而全部的点有蒙特卡洛算法案例_蒙特卡洛原理个,所以得到近似公式为

 

         蒙特卡洛算法案例_蒙特卡洛原理

 

    而依据牛顿莱布尼兹公式可以得到

 

          蒙特卡洛算法案例_蒙特卡洛原理

 

    这两种方法结果应该是相等的,即有

 

          蒙特卡洛算法案例_蒙特卡洛原理

 

    接下来写写代码吧!

 

代码:

 

 1 #include <bits/stdc++.h>
 2 
 3 #define MAX_ITERS 10000000
 4 
 5 using namespace std;
 6 
 7 struct Point
 8 {
 9     double x, y;
10 };
11 
12 double Rand(double L, double R)  
13 {  
14     return L + (R - L) * rand() * 1.0 / RAND_MAX;  
15 } 
16 
17 Point getPoint()
18 {
19     Point t;
20     t.x = Rand(1.0, 2.0);
21     t.y = Rand(0.0, 1.0);
22     return t;
23 }
24 
25 double getResult()
26 {
27     int m = 0;
28     int n = MAX_ITERS;
29     srand(time(NULL));
30     for(int i = 0; i < n; i++)
31     {
32         Point t = getPoint();
33         double res = t.x * t.y;
34         if(res <= 1.0)
35             m++;
36     }
37     return pow(2.0, 1.0 * n / m);
38 }
39 
40 int main()
41 {
42     for(int i = 0; i < 20; i++)
43         cout << fixed << setprecision(6) << getResult() << endl;
44     return 0;
45 }

 

观察一下运行结果,效果还是不错的。如下图

 

             蒙特卡洛算法案例_蒙特卡洛原理

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/166642.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • fferrone_png转换svg

    fferrone_png转换svgffmpeg-vcodecrawvideo-frawvideo-pix_fmtbgr32-s1792x2176-i~/Downloads/dumpdata/dump_src_44_0_f2_1792x2176.raw-fimage2-vcodec pngscreenshot1.png颜色不对一般是RGB的值有问题 PIX_FMT_RGB24改成PIX_FM

  • TCP和UDP的区别是什么_那跟哪的区别

    TCP和UDP的区别是什么_那跟哪的区别TCP是传输层协议,定义数据传输和连接方式的规范。握手过程中传送的包里不包含数据,三次握手完毕后,客户端与服务器才正式开始传送数据。HTTP超文本传送协议(HypertextTransferProtocol)是应用层协议,定义的是传输数据的内容的规范。HTTP协议中的数据是利用TCP协议传输的,特点是客户端发送的每次请求都需要服务器回送响应,它是TCP协议族中的一种,默认使用TCP80…

  • ubuntu安装npm

    ubuntu安装npm

  • 常用的垂直细分引擎工具

    常用的垂直细分引擎工具常用的垂直细分的引擎工具我们需要一些垂直细分的引擎工具,帮我们搞定更精准的信息。本文基于大家日常上网的需要,分类整理了不同检索需求的工具,主要包括:电子书、图片、网盘、音乐、工作机会以及商品价格检索。

  • PopupWindow错误:PopupWindow$1.onScrollChanged 出现 NullPointerException和PopupViewContainer.dispatchKeyEv…

    PopupWindow错误:PopupWindow$1.onScrollChanged 出现 NullPointerException和PopupViewContainer.dispatchKeyEv…

  • Futex系统调用,Futex机制,及具体案例分析[通俗易懂]

    Futex系统调用,Futex机制,及具体案例分析[通俗易懂]Futex1、背景1.1自己实现锁1.1.1自旋锁1.1.2sleep+自旋1.1.3小结1.2futex1.2.1什么是Futex1.2.2futex诞生之前1.2.3futex诞生之后2、Futex系统调用3、Futex机制4、具体案例分析4.1在Bionic中的实现4.2C语言实现5、参考及扩展阅读首先要区分一下futex系统调用和futex机制。futex系统调用是操作系统提供给上层的系统调用接口。而futex机制是使用futex接口实现的一种锁。1、背景线程同步可以说

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号