《蒙特卡罗方法》PPT课件.ppt

《《蒙特卡罗方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《蒙特卡罗方法》PPT课件.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 蒙蒙 特特 卡卡 罗罗 方方 法法Monte-Carlo,Monaco Monte Car1o(MC)方法方法又称随机模拟又称随机模拟或统计试验方法。或统计试验方法。源于：源于：Metropolis提出的美国在第二提出的美国在第二次世界大战中研制原子弹的次世界大战中研制原子弹的“曼哈顿计划曼哈顿计划”；研究与原子弹有关的中子输运过程。；研究与原子弹有关的中子输运过程。该计划的主持人之一、数学家该计划的主持人之一、数学家John von Neumann用驰名世界的赌城用驰名世界的赌城摩纳哥摩纳哥的的Monte Carlo来命名这种方法。来命名这种方法。1.1 引引 言言什么是什么是

2、Monte Carlo方法方法Monte Carlo方法的应用：方法的应用：1，非确定性过程的模拟，非确定性过程的模拟2，复杂程度高，不能进行模型分析的确定性系统模拟，复杂程度高，不能进行模型分析的确定性系统模拟3，维数较高，不易离散化的确定性系统模拟，维数较高，不易离散化的确定性系统模拟 例如：对中子输运过程的模拟例如：对中子输运过程的模拟 多体问题的模拟多体问题的模拟 多重积分的计算多重积分的计算 其他：道琼斯指数预测其他：道琼斯指数预测 石油矿井勘探石油矿井勘探 癌症的放射疗法癌症的放射疗法Monte Carlo方法的基本思想方法的基本思想例例1，圆周率的计算：，圆周率的计算：If yo

3、u are a very poor dart player,it is easy to imagine throwing darts randomly at the above figure,and it should be apparent that of the total number of darts that hit within the square(N),the number of darts that hit the yellow part(n)is proportional to the area of that part:.圆周率的值圆周率的值=3.14159 26535

4、89793 23846 26433 83279 50288 41971 69399 3751058209 74944 59230 78164 06286 20899 86280 34825 34211 7067982148 08651 32823 06647 09384 46095 50582 23172 53594 0812848111 74502 84102 70193 85211 05559 64462 29489 54930 3819644288 10975 66593 34461 28475 64823 37867 83165 27120 1909145648 56692 34603

5、 48610 45432 66482 13393 60726 02491 4127372458 70066 06315 58817 48815 20920 96282 92540 91715 3643678925 90360 01133 05305 48820 46652 13841 46951 94151 1609433057 27036 57595 91953 09218 61173 81932 61179 31051 1854807446 23799 62749 56735 18857 52724 89122 79381 83011 9491298336 73362 44065 6643

6、0 86021 39494 63952 24737 19070 2179860943 70277 05392 17176 29317 67523 84674 81846 76694 0513200056 81271 45263 56082 77857 71342 75778 96091 73637 1787214684 40901 22495 34301 46549 58537 10507 92279 68925 8923542019 95611 21290 21960 86403 44181 59813 62977 47713.Monte Carlo方法的基本思想方法的基本思想例例2，简单积

7、分，简单积分对边长为对边长为1的正方形里随机投点，的正方形里随机投点，点落在曲线点落在曲线y=f(x)的下面的下面对积分有贡献对积分有贡献点落在曲线点落在曲线y=f(x)的上面的上面对积分无贡献对积分无贡献积分积分I的一个估计值为的一个估计值为xyO11例例3，打靶游戏打靶游戏用概率论的语言说，用概率论的语言说，就是随机变量就是随机变量g(r)的数学期望值，即的数学期望值，即=Eg(r).Monte Carlo方法的基本思想方法的基本思想以以r表示投掷者的飞镖到靶心的距离，分布函表示投掷者的飞镖到靶心的距离，分布函数数f(r)表示该投掷者的飞镖分布，表示该投掷者的飞镖分布，g(r)表示击表示击

8、中中r处应得的分数。则投掷者的得分为：处应得的分数。则投掷者的得分为：现在，假设这个投掷者投掷了现在，假设这个投掷者投掷了N次，飞镖点分布依次是次，飞镖点分布依次是r1,r2,rN，则则，自然，自然认为认为N次次投掷得分的平均值投掷得分的平均值相当好地代表了这个运动员的成绩。换句话说，相当好地代表了这个运动员的成绩。换句话说，gN是积分是积分的一个估计值。的一个估计值。Monte Carlo方法的基本思想：方法的基本思想：将所要求解的问题转化为某事件出现的概率，再通过某种模拟将所要求解的问题转化为某事件出现的概率，再通过某种模拟试验方法，得到这一概率，并用它作为问题的解。试验方法，得到这一概率

9、，并用它作为问题的解。Monte Carlo模拟的步骤：模拟的步骤：1，根据欲研究的物理系统的性质，建立能够描述该系统特性，根据欲研究的物理系统的性质，建立能够描述该系统特性的理论模型，导出该模型的某些特征量的概率密度函数；的理论模型，导出该模型的某些特征量的概率密度函数；2，从概率密度函数出发进行随机抽样，得到特征量的一些模，从概率密度函数出发进行随机抽样，得到特征量的一些模拟结果；拟结果；3，对模拟结果进行分析总结，预言物理系统的某些特性。，对模拟结果进行分析总结，预言物理系统的某些特性。1.2 伪随机数的产生伪随机数的产生随机的重要性：随机的重要性：Non-random sequence

10、 will skew the approximation.Very advanced Monte Carlo Method computations could run for months before arriving at an approximation.If the method is not sufficiently random,it will certainly get a bad approximation and waste lots of$.随机数随机数 在具有单位矩形分布的总体中抽取简单的子样，在具有单位矩形分布的总体中抽取简单的子样，x1,x2,xN，称称为为随机数序

11、列，其中每一个个体称随机数序列，其中每一个个体称为为随机数。随机数。伪随机数伪随机数 计算机是用数论的方法来产生随机数的。用计算机生成的随机计算机是用数论的方法来产生随机数的。用计算机生成的随机数从表面上看是随机的，但实际上由于凡是计算机产生随机数都要数从表面上看是随机的，但实际上由于凡是计算机产生随机数都要依赖于某种算法，这种依赖于某种算法，这种“随机数随机数”仍然是确定的，故称伪随机数。仍然是确定的，故称伪随机数。均匀伪随机数产生方法均匀伪随机数产生方法线性同余法：线性同余法：从一个从一个种子种子 出发生长出一个随机数序列出发生长出一个随机数序列a、b、c：幻数。一般取：幻数。一般取For

12、ntran内部函数内部函数 RAN(I)输入：整型变量或数组元素，输入：整型变量或数组元素，足够大的奇数足够大的奇数 输出：输出：0,1)间的随机数间的随机数 1.3.1 简单抽样的蒙特卡罗方法简单抽样的蒙特卡罗方法1.3 蒙特卡罗方法计算积分蒙特卡罗方法计算积分求平均的做法：均匀地在求平均的做法：均匀地在0，1中随机选取中随机选取N个点个点xi，考虑，考虑f(x)在在 这些点上的函数值。这些点上的函数值。把把 I 看成看成f(x)在在0，1上的平均，则上的平均，则例：用简单抽样例：用简单抽样MC方法计算积分方法计算积分误差：根据统计力学中的大数定律和中心极限定理误差：根据统计力学中的大数定律

13、和中心极限定理两种极端情况：两种极端情况：xxf1(x)f2(x)只需一个点，就可求得积分只需一个点，就可求得积分的精确值的精确值即使在积分区间上取很多点，即使在积分区间上取很多点，也难以求得积分的精确值也难以求得积分的精确值(a)(b)1.3.2 重要抽样的蒙特卡罗方法重要抽样的蒙特卡罗方法引入分布函数，将积分变形为引入分布函数，将积分变形为做替换做替换则则因而因而xf(x)xf(x)也可以理解为：也可以理解为：重要抽样的重要抽样的MC方法方法例：用重要抽样例：用重要抽样MC方法计算积分方法计算积分解：选择分布函数解：选择分布函数1.3.3 Metropolis 算法算法对积分区间的重要抽样

14、要求我们获得对积分区间的重要抽样要求我们获得x(y)，而这只对极少数的分，而这只对极少数的分布布(x)能够解析地做到。能够解析地做到。Metropolis 算法：算法：一种很普遍的产生具有任意形状的给定概率分布随机变量的方法。一种很普遍的产生具有任意形状的给定概率分布随机变量的方法。算法的实现：算法的实现：可以用各种不同的方法落实其中最简单者：可以用各种不同的方法落实其中最简单者：假想有一个随机行走者在假想有一个随机行走者在R空间中运动，这个随机行走过程空间中运动，这个随机行走过程相继各步的终点产生出一个点的序列：相继各步的终点产生出一个点的序列：R0，R1，；随机行走的；随机行走的路程越长，

15、它连接的点就越接近所要求的分布路程越长，它连接的点就越接近所要求的分布这一随机行走在位形空间中进行的规则如下：这一随机行走在位形空间中进行的规则如下：设行走者处于序列中设行走者处于序列中Rn点上为了产生点上为了产生Rn+1点，行走者迈出试探性的点，行走者迈出试探性的一步到一个新点一步到一个新点Rt这个新点可以用任何方便的方法选取，例如可以在这个新点可以用任何方便的方法选取，例如可以在Rn点周围的一个边长点周围的一个边长很小的多维立方体中均匀地随机选取然后很小的多维立方体中均匀地随机选取然后按照比值按照比值来决定是来决定是“接受接受”还是还是“拒绝拒绝”这一试验步如果这一试验步如果r大于大于l，

16、那么接受，那么接受这一步这一步(取取Rn+1=Rt)；而如果；而如果r小于小于1，则以概率，则以概率r 接受这步这时我们接受这步这时我们把把r和一个在和一个在0，1区间上均匀分布的随机数区间上均匀分布的随机数比较，若比较，若 r就接受就接受这一步如果这一试验步不被接受，就舍弃它而取这一步如果这一试验步不被接受，就舍弃它而取Rn+1=Rn；这样；这样产生出产生出Rn+1之后，可以从之后，可以从Rn+1出发迈出一个试验步按照同样的过程产出发迈出一个试验步按照同样的过程产生生Rn+2，任意任意点点R0都可以用作随机行走的起点都可以用作随机行走的起点例：用例：用Metropolis抽样抽样MC方法计算

17、积分方法计算积分解：选择分布函数解：选择分布函数1.4 蒙特卡罗方法的特点蒙特卡罗方法的特点MC方法的误差方法的误差1，收敛速度与问题的维度无关，适宜于多维问题，收敛速度与问题的维度无关，适宜于多维问题。复化梯形求积公式的误差复化梯形求积公式的误差d维积分维积分分水岭：分水岭：d=4多体问题：多体问题：d=3N2，可计算任意形状积分区域上的积分，可计算任意形状积分区域上的积分1.5 蒙特卡罗方法应用举例蒙特卡罗方法应用举例量子变分量子变分MC方法方法用用MC方法计算上述积分方法计算上述积分优化优化 i 使使 Ei 最小最小简单应用：计算简单应用：计算He的电子结构的电子结构两种极端情况：两种极端情况：xxf1(x)f2(x)只需一个点，就可求得积分只需一个点，就可求得积分的精确值的精确值即使在积分区间上取很多点，即使在积分区间上取很多点，也难以求得积分的精确值也难以求得积分的精确值(a)(b)x0