蒙特卡罗方法

1、1. 蒙特卡罗方法的基本思想蒙特卡罗方法的基本思想2. 蒙特卡罗方法的收敛性，误差蒙特卡罗方法的收敛性，误差3. 蒙特卡罗方法的特点蒙特卡罗方法的特点4. 蒙特卡罗方法的主要应用范围蒙特卡罗方法的主要应用范围 蒙特卡罗方法又称随机抽样技巧或统计试验方法。半个多世纪以来，由于科学技术的发展和电子计算机的发明 ，这种方法作为一种独立的方法被提出来，并首先在核武器的试验与研制中得到了应用。 蒙特卡罗方法是一种计算方法，但与一般数值计算方法有很大区别。它是以概以概率统计理论为基础的一种方法率统计理论为基础的一种方法。由于蒙特卡罗方法能够比较逼真地描述事物的特点及物理实验过程，解决一些数值方法难以解决的

2、问题，因而该方法的应用领域日趋广泛。 两个例子 例1. 蒲丰氏问题 例2. 射击问题（打靶游戏） 例3. 积分基本思想计算机模拟试验过程将长为2l的一根针任意投到地面上，用针与一组相间距离为2a（la）的平行线相交的频率代替概率P，再利用准确的关系式： 求出值 其中为投计次数，n为针与平行线相交次数。alP2)(22nNalaPl 一些人进行了实验，其结果列于下表 ：实验者年份投计次数的实验值沃尔弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼(Lazzarini)190134083.1415929

3、设r表示射击运动员的弹着点到靶心的距离，(r)表示击中r处相应的得分数（环数），f(r)为该运动员的弹着点的分布密度函数，它反映运动员的射击水平。该运动员的射击成绩为 用概率语言来说，是随机变量(r)的数学期望，即 )(rgEg 0)()(drrfrgg 现假设该运动员进行了次射击，每次射击的弹着点依次为r1，r2，rN，则次得分g(r1)，g(r2)，g(rN)的算术平均值 代表了该运动员的成绩。换言之，为积分的估计值，或近似值。 在该例中，用用次试验所得成绩的算术平次试验所得成绩的算术平均值作为数学期望均值作为数学期望 的估计值的估计值（积分近似值）。 NiiNrgNg1)(1 当所求问题

4、的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与概率、数学期望有关的量时，通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡罗方法的基本思想。 蒙特卡罗方法是用随机试验的方法计算积分，即将所要计算的积分看作服从某种分布密度函数f(r)的随机变量(r)的数学期望 通过某种试验，得到个观察值r1，r2，rN（用概率语言来说，从分布密度函数f(r)中抽取个子样r1，r2，rN，），将相应的个随机变量的值g(r1)，g(r2)，g(rN)的算术平均值 作为积分的估计值（近似值）。 NiiNrgNg1)(10)()(drrf

5、rgg 计算机模拟试验过程，就是将试验过程（如投针，射击）化为数学问题，在计算机上实现。以上述两个问题为例，分别加以说明。 例1. 蒲丰氏问题 例2. 射击问题（打靶游戏） 例3. 求积分问题 设针投到地面上的位置可以用一组参数（x,）来描述，x为针中心的坐标，为针与平行线的夹角，如图所示。 任意投针，就是意味着x与都是任意取的，但x的范围限于0，a，夹角的范围限于0，。在此情况下，针与平行线相交的数学条件是:针在平行线间的位置 sin lx 如何产生任意的（x,）？X在0，a上任意取值，表示x在0，a上是均匀分布的，其分布密度函数为：类似地，的分布密度函数为：因此，产生任意的（x,）的过程就

6、变成了由f1(x)抽样x及由f2() 抽样的过程了。由此得到： 其他, 00,/1)(1axaxf其他, 00,/1)(2f21 ax 其中1，2均为0,1上均匀分布的随机变量。 每次投针试验，实际上变成在计算机上从两个均匀分布的随机变量中抽样得到（x,），然后定义描述针与平行线相交状况的随机变量s(x,)，为 如果投针次，则 是针与平行线相交概率的估计值。事实上， 于是有: 其他当, 0sin, 1),(lxxsNiiiNxsNs1),(1aladxddxdfxfxsPl2)()(),(sin0021NsalaPl22 int main() /文件地址F:PuFengShiPuFengShi

7、0 const int N = 5000000; /总的投样次数 const double PI = 3.1415926535898; /定义的初始值，用于抽样角 const double a = 2.0, l = 1.8; /定义平行线半间距a及针半长l double pi = 0.0f; /初始化所要计算的值 double x = 0.0f, theta = 0.0f; int Count = 0; /针与直线相交的次数/用该语句初始化Rand()函数，使得每次产生的随机数均不同/参见http:/ srand( (unsigned int)time(NULL)*1000 ); /srand

8、函数内为实数时,每次计算结果相同 for(int i=0; i N; i+) x = a * rand()/RAND_MAX; /rand()/RAND_MAX为0,1间的随机数，此为抽样x与 theta = PI * rand()/RAND_MAX; if( x = l*sin(theta) ) /记录针与平行线相交次数于Count中 Count+ ; pi = 2.0f*l/a; pi = pi * (double)N/Count; /计算值 cout PI = pi endl; /在屏幕上输出所要计算的值及相对偏差 cout 相对误差 = fabs(PI - pi)/PI * 100.0

9、f % endl; cout - endl; return 0;示意图结论： 在边长为2的圆内投点N次，如果有M个点分布在圆内，那么当N时，进入圆内点数的概率即为圆面积与正方形面积之积221424MMNN 设射击运动员的弹着点分布为 用计算机作随机试验（射击）的方法为，选取一个随机数，按右边所列方法判断得到成绩。 这样，就进行了一次随机试验（射击），得到了一次成绩 (r)，作次试验后，得到该运动员射击成绩的近似值 环数 78910概率 0.5环中命环命中环命中环命中1095 . 082 . 071 . 0NiiNrgNg1)(1011011011011,nnbbbnnaaas

10、f x xxdx dxdx 计算下列多重积分计算下列多重积分 01111011000 1t , t ,t,0,1,1xbt ,0,1,11,biiiniijjjjjmniiinjjjiimaajnmsf xxxam方法：取之间的均匀分布的随机数点列取当 充分大时，即随机数的个数取得足够多时，与常见数值离散积分方法的比较以一次积分为例： basf x dx把积分区间a, b分割为m个均匀步长，则步长hhbam那么，按照微积分的思想，上述积分可以近似表示为： 110011 22mmbiiaiiibasf x dxf x hf xmixaihabam蒙特卡罗方法常以一个“概率模型”为基础，按照它所描

11、述的过程，使用由已知分布抽样的方法，得到部分试验结果的观察值，求得问题的近似解。 蒙特卡罗方法作为一种计算方法，其收敛性与误差是普遍关心的一个重要问题。收敛性误差减小方差的各种技巧 效率蒙特卡罗方法是由随机变量X的简单子样X1，X2，XN的算术平均值： 作为所求解的近似值。由大数定律(辛钦定理)可知， 如X1，X2，XN独立同分布，且具有有限期望值(E(X)，则 即随机变量X的简单子样的算术平均值 ，当子样数充分大时，以概率1收敛于它的期望值E(X)。NiiNXNX111)(limXEXPNNNX 概率论的中心极限定理指出，如果随机变量序列X1，X2，XN独立同分布，且具有有限非零的方差2 ，

12、即 f(X)是X的分布密度函数。则dtexXEXNPxxtNN2/221)(limdxxfXEx)()(022 当N充分大时，有如下的近似式 其中称为置信度，1称为置信水平。 这表明，不等式 近似地以概率 1成立，且误差收敛速度的阶为 。 通常，蒙特卡罗方法的误差定义为 上式中x与置信度是一一对应的，根据问题的要求确定出置信水平后，查标准正态分布表，就可以确定出x。 2/202()12xtNxPXE XedtxN ()NxXE XN)(2/1NOxN 下面给出几个常用的与x的数值： 1.蒙特卡罗方法的误差为概率误差，这与其他数值 计算方法是有区别的。2.误差中的均方差是未知的，必须使用其估计值

13、 来代替，在计算所求量的同时，可计算出 。 0.50.050.003x 0.67451.96322221111()NNiiiiD XE XE XXXNN 当给定置信度后，误差由和N决定。在在固定固定的情况下，要把精度提高一个数量级，的情况下，要把精度提高一个数量级，试验次数试验次数N需增加两个数量级需增加两个数量级。 如能减小估计的均方差，比如降低一半，那误差就减小一半，这相当于N增大四倍的效果。因此降低方差的各种技巧，引起了人们的普遍注意。后面课程将会介绍一些降低方差的技巧。 降低方差的技巧，往往使观察一个子样的时间增加。在固定时间内，使观察的样本数减少。所以，一种方法的优劣，需要由方差和观察一个子样的费用（使用计算机的时间）两者来衡量。这就是蒙特卡罗方法中效率的概念。它定义为 ，其中c是观察一个子样的平均费用。显然 越小，方法越有效。 c2c2优点1) 能够比较逼真地描述具有随机性质的事物的特点及物理实验过程。2) 受几何条件限制小。3) 收敛速度与问题的维数无关。4) 具有同时计算多个方案与多个未知量的能力。5) 误差容易确定。6) 程序结构简单，易于实现。 缺点1) 收敛速度慢。2