蒙特卡罗方法1.ppt

1、蒙特卡罗方法,计算机模拟,随机性模拟方法,确定性模拟方法,直接蒙特卡罗模拟,蒙特卡罗积分,Metropolis蒙特卡罗模拟,蒙特卡罗,通过不断产生随机数序列来模拟过程,通过数值求解一个个粒子的运动方程来模拟整个系统的行为,计算机模拟和蒙特卡罗方法,间接蒙特卡罗模拟,目 录,第一节 蒙特卡罗方法概述 第二节 随机数与伪随机数 第三节 随机变量的抽样 第四节 蒙特卡罗方法的应用实例,1 蒙特卡罗方法概述-基本思想,基本思想： 针对待求问题，根据物理现象本身的统计规律，或人为构造一合适的依赖随机变量的概率模型，使某些随机变量的统计量为待求问题的解，进行大统计量（N）的统计实验方法或计算机随机模拟方法

2、。,理论依据： 大数定理：均匀分布的算术平均收敛于真值 中心极限定理：置信水平下的统计误差,两个例子： Buffen投针实验求 射击问题（打靶游戏）,Buffon投针实验(1777年）求:,各向同性随机投针，则夹角在,均匀分布，所以：,设投针N次，相交次数为M，则相交概率的期望值：,N大数定理,1 蒙特卡罗方法概述-基本思想,针与平行线垂直方向夹角为，则相交概率为：,平行线间距针长s,一些人进行了实验，其结果列于下表 ：,1 蒙特卡洛方法的基本思想,1 蒙特卡罗方法概述-基本思想,1.设r表示射击运动员弹着点到靶心的距离，(r)表示击中r处相应的 得分数（环数），f(r)为该运动员弹着点的分布

3、密度函数，它们反映运 动员的射击水平。该运动员的射击成绩为：,.用概率语言来说，是随机变量(r)的数学期望，即,.假设该运动员进行了次射击，每次射击的弹着点依次为r1，r2，rN，则次得分g(r1)，g(r2)，g(rN)的算术平均值,代表了该运动员的成绩,射击问题（打靶游戏）,1 蒙特卡罗方法概述-基本思想,.用次试验所得成绩的算术平均值作为数学期望的估计值。,例如，设射击运动员的弹着点分布为,用计算机作随机试验（射击）的方法为，选取一个随机数，按右边所列方法判断得到成绩。这样，就进行了一次随机试验（射击），得到了一次成绩(r)，作次试验后，得到该运动员射击成绩的近似值,1 蒙特卡罗方法概述

4、-基本思想,收敛性:大数定理,作为所求解的近似值。由大数定律可知，如果X1，X2，XN独 立同分布，且具有有限期望值（E(X)），则,即随机变量X的简单子样的算术平均值 ，当子样数充分大时，以概率1收敛于它的期望值E(X)。,由前面介绍可知，蒙特卡罗方法是由随机变量X的简单子样X1，X2，XN的算术平均值：,1 蒙特卡洛方法概述-大数定理,f(x)是X的分布密度函数。则当N充分大时，有如下的近似式,蒙特卡罗方法的近似值与真值的误差问题，概率论的中心极限定理给出了答案。该定理指出，如果随机变量序列X1，X2，XN独立同分布，且具有有限非零的方差2 ，即,1 蒙特卡洛方法概述-中心极限定理,其中称

5、为置信度，1称为置信水平。这表明，不等式,近似地以概率1成立，且误差收敛速度的阶为：O(N-1/2),上式中与置信度是一一对应的，根据问题的要求确定出置信水平后，查标准正态分布表，就可以确定出 。,通常，蒙特卡罗方法的误差定义为,给出几个常用的与 的数值：,两点说明：,(1)MC方法的误差为概率误差，这与其他数值计算方法是有区别的。 (2)误差中的均方差是未知的，必须使用其估计值来代替，在计算所求量的同时，可计算出估计值。,1 蒙特卡洛方法概述-中心极限定理,（2）减小估计的均方差，比如降低一半，那误差就减小一半，这相当于N增大四倍的效果。,减小方差的各种技巧:,（1）增大试验次数N。在固定的

6、情况下，要把精度提高一个数量级，试验次数N需增加两个数量级。因此，单纯增大N不是一个有效的办法。,显然当给定置信度（）后，误差由和N决定。要减小：,1 蒙特卡洛方法该概述-减小误差,效率:,一般来说，降低方差的技巧，往往会使观察一个子样的时间增加。在固定时间内，使观察的样本数减少。,所以，一种方法的优劣，需要由方差和观察一个子样的费用（使用计算机的时间）两者来衡量。这就是MC方法中效率的概念。它定义为2c ，其中c 是观察一个子样的平均费用。显然2c越小，方法越有效。,（1）能够比较逼真地描述具有随机性质的事物的特点及物理实验过程,1 蒙特卡罗方法概述-MC优点,从这个意义上讲，蒙特卡罗方法可

7、以部分代替物理实验，甚至可以得到物理实验难以得到的结果。用蒙特卡罗方法解决实际问题，可以直接从实际问题本身出发，而不从方程或数学表达式出发。它具有直观、形象的特点。,（2）受几何条件限制小,计算s维空间中的任一区域Ds上的积分：,无论区域Ds的形状多么特殊，只要能给出描述Ds的几何特征的条件，就可以从Ds中均匀产生N个点：,因此，在具有随机性质的问题中，如考虑的系统形状很复杂，难以用一般数值方法求解，而使用蒙特卡罗方法，不会有原则上的困难。,其中Ds为区域Ds的体积。这是数值方法难以作到的。,得到积分的近似值：,1 蒙特卡罗方法概述-MC优点,（3）收敛速度与问题的维数无关,由误差定义可知，在

8、给定置信水平情况下，MC方法的误差为O(N-1/2) ，与问题本身的维数无关。维数的变化，只引起抽样时间及估计量计算时间的变化，不影响误差。这一特点，决定了蒙特卡罗方法对多维问题的适应性。,而一般数值方法，比如计算定积分时，计算时间随维数的幂次方而增加，而且由于分点数与维数的幂次方成正比，需占用相当数量的计算机内存，这些都是一般数值方法计算高维积分时难以克服的问题。,（4）具有同时计算多个方案与多个未知量的能力,（2）使用蒙特卡罗方法还可以同时得到若干个所求量。,（1）对于那些需要计算多个方案的问题，使用蒙特卡罗方法有时不需要像常规方法那样逐个计算，而可以同时计算所有的方案，其全部计算量几乎与

9、计算一个方案的计算量相当。,例如对于屏蔽层为均匀介质的几何平板，要计算若干种厚度的穿透概率时，只需计算最厚的一种情况，其他厚度的穿透概率在计算最厚一种情况时稍加处理便可同时得到。,例如在模拟粒子过程中，可以同时得到不同区域的通量、能谱、角分布等，而不像常规方法那样，需要逐一计算所求量。,1 蒙特卡罗方法概述-MC优点,（5）误差容易确定,根据蒙特卡罗方法的误差公式，可以在计算所求量的同时计算出误差,（6）程序结构简单，易于实现,在计算机上进行蒙特卡罗方法计算时，程序结构简单，分块性强，易于实现。,（1）收敛速度慢,（2）误差具有概率性,蒙特卡罗方法的收敛速度为O(N-1/2) ，一般不容易得到

10、精确度较高的近 似结果。对于维数少（三维以下）的问题，不如其他方法好。,由于蒙特卡罗方法的误差是在一定置信水平下估计的，所以它 的误差具有概率性，而不是一般意义下的误差。,1 蒙特卡罗方法概述-MC缺点,（3）计算结果与系统大小有关,例如在粒子输运问题中:经验表明，只有当系统的大小与粒子的平均自由程可以相比较时（一般在十个平均自由程左右），蒙特卡罗方法计算的结果较为满意。但对于大系统或小概率事件的计算问题，计算结果往往比真值偏低。,在使用蒙特卡罗方法时，可以考虑把蒙特卡罗方法与解析（或数值）方法相结合，取长补短，既能解决解析（或数值）方法难以解决的问题，也可以解决单纯使用蒙特卡罗方法难以解决的

11、问题。,真随机数：不可重复，物理方法产生。,随机数是实现由已知分布抽样的基本量，在由已知分布的抽样过程中，将随机数作为已知量，用适当的数学方法可以由它产生具有任意已知分布的简单子样。,由具有已知分布的总体中抽取简单子样，在蒙特卡罗方法中占有非常重要的地位。总体和子样的关系，属于一般和个别的关系，或者说属于共性和个性的关系。,2 随机数的产生和检验,蒙特卡罗模拟就是边产生随机数边进行随机模拟的方法,准随机数：不具随机性质，只要处理问题能得到正确结果。,如放射性衰变，电子设备的热噪音，宇宙射线的触发时间等。,伪随机数：可重复，数学方法产生，必须通过统计检验,区分：数列的随机性和随机数的分布,一个完

12、美的随机数序列可能具有某种分布（如均匀分布，高斯分布等），但具有某种分布的数列却可能完全不是随机的。,良好统计分布，容易实现，效率高，周期长，可移植性好等,2 随机数的产生和检验,分布函数为 ：,最简单、最基本，也是最重要的随机数是在单一区间0,1上的均匀分布的随机数，其分布密度函数为,由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号表示。用1，2 ， 代表相互独立且具有相同单位均匀分布的随机数序列。独立性、均匀性是随机数必备的两个特点。,如：掷筛子游戏，投掷硬币,用来作为随机数发生器的物理源主要有两种：一种是根据放射性物质的放射性，另一种是利用计算机的固有噪声。,用物理方法产生

13、的随机数序列无法重复实现，不能进行程序复算，给验证结果带来很大困难。而且，需要增加随机数发生器和电路联系等附加设备，费用昂贵。因此，该方法也不适合在计算机上使用。,2 伪随机数的产生和检验-物理方法,在计算机上用物理方法产生随机数的基本原理是：利用某些物理现象，在计算机上增加某些特殊设备，可以在计算机上直接产生随机数。这些特殊设备称为随机数发生器。,（1）冯诺伊曼平方取中法,递推公式：,以十进制数为例，平方取中法是把一个2S位的十进制自平方后，去头截尾只保留中间2S个数字，然后用102S来除，这样就可以得到在0,1上均匀分布的伪随机数序列。,例如，设十进制数的2S=4，并取x1=6406，则有

14、：,相应的伪随机数序列是0.6406，0.3680，0.1354，0.8333，0.4388等,2 伪随机数的产生和检验-数学方法,具有周期性，有些数甚至会紧接着重复出现，很少使用。,2 伪随机数的产生和检验-数学方法,由Lehmer在1951年提出来的，它的一般形式是：对于任一初始值x0，伪随机数序列由下面递推公式确定：,（2）Lehmer 线性同余法,例如,乘同余法,x0称为种子，改变它的值就得到基本序列的不同区段随机数。,a-乘子，c-增量，m-模,乘同余法具有在计算机上容易实现、快速等特点，所以乘同余法已被广泛采用。,伪随机数的均匀性,伪随机数的独立性,均匀性是指在0,1区间内等长度子

15、区间中随机数的数量是一样的。,按先后顺序出现的随机数中，每个随机数的取值与其相距一定间隔的随机数取值之间无关。,2 伪随机数序列的统计检验,判断伪随机数序列是否满足均匀和相互独立的要求，要靠统计检验的方法实现。对于伪随机数的统计检验，一般包括两大类：均匀性检验和独立性检验,伪随机数的均匀性,将区间0,1分为K 个子区间，统计随机数落在第k 个子区间的实际频数nk，它应当趋近于理论频数mk,计算统计量,如果2 值很大，表示远远偏离理想值，因此要求2值尽可能小，但如果它趋于0则有可能N 已进入循环。通常求和中的每一项的大小约为1，因此2的值约为K 。,2 随机数的产生和检验-统计检验,K的取值不能

16、太大也不能太小，太大反映不出“小区间”的均匀性，太小反映不出“大区间”的均匀性 。,限制条件,（1）,概率论中的Pearson定理说明，上式的极限概率分布是2 分布,给出了2x的概率。整数是系统自由度表示独立测量的次数，由于存在一个限制条件，故=K-1,给出了2x的概率,余函数,2 随机数的产生和检验-统计检验,因此，当给定显著水平 (或置信度1 )后，由方程Q(2 | ) = 或P(2|）= 1 解出值，或从已有的2 表中查得值，如果由（1）式计算出来的 小于 ，则认为在此置信度下，伪随机数序列在0,1中是均匀分布的。,（1）顺序相关法,它用相邻两个随机数的自相关函数（或相关系数）来标识伪随机数序列的独立性情况，间距为l 的自相关函数是,相关系数越小，独立性越好。,2 随机数产生及检验-独立性统计检验,（2）多维频率检验,（1）将伪随机数序列用任意一种办法进行组合，每S 个随机数作为S 维空间中的一个点的坐标值，于是可以构成一个点序列。,（2）把S 维空间中的单位方体分成为K个子方体，方体边长,（3）统计落在第k 个