计算机在材料科学与工程中的应用ch08 蒙特卡罗方法.ppt
第八章 蒙特卡洛方法蒙特卡罗方法又称统计模拟(Statistical Simulation)方法，它用随机数对问题的概率模型进行数值模拟从而获得问题的解。Nicholas Metropolis(1915-1999)Monte-Carlo,Monaco是由是由Metropolis在二次世界大战期间提出的：在二次世界大战期间提出的：Manhattan计计划，研究与原子弹有关的中子输运过程；划，研究与原子弹有关的中子输运过程；Monte Carlo是摩纳哥（是摩纳哥（monaco)的首都，该城以赌博闻名的首都，该城以赌博闻名亦称统计模拟方法，亦称统计模拟方法，statistical simulation method 利用随机数进行数值模拟的方法利用随机数进行数值模拟的方法第一节 掷针实验（蒲丰实验）为了求得圆周率值，在十九世纪后期，有很多人作了这样的试验：将长为2l的一根针任意投到地面上，用针与一组相间距离为2a（la）的平行线相交的频率代替概率P，再利用准确的关系式：求出值其中为投计次数，n为针与平行线相交次数。这就是古典概率论中著名的蒲丰问题。n n 一些人进行了实验，其结果列于下表：实验者年份投计次数的实验值沃尔弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼(Lazzarini)190134083.1415929n n 设针投到地面上的设针投到地面上的位置可以用一组参数位置可以用一组参数（x,）来描述，）来描述，x为针为针中心的坐标，中心的坐标，为针与为针与平行线的夹角，如图所示。针在平行线间的位置 n 任意投针，就是意味着x与都是任意取的，但x的范围限于0，a，夹角的范围限于0，。在此情况下，针与平行线相交的数学条件是x l sin则投针N次，相交次数为n，则相交的概率为：说明：1，用随机方法可以解决一些比较难于用确定性方法解决的问题。2，随机方法要达到一定的精度，所耗时间较长。3，用随机方法计算，一个关键的问题是随机数的取得。第二节 0,1区间均匀分布的随机数是蒙特卡罗方法研究的一个重要内容。如果得到0,1区间均匀分布的随机数，则任何区间a,b之内的随机数都可以得到：随机数的要求：1，足够多个随机数能遍布0,1范围，非周期性，遍历性。2，在0,1中每个小区间出现的机会相等，等概率性。并不是一个简单的问题。stdlib.h里面的random()函数可以在低精度的情况下使用。2)随机数表n为了产生随机数，可以使用随机数表。随机数表是由0，1，9十个数字组成，每个数字以0.1的等概率出现，数字之间相互独立。这些数字序列叫作随机数字序列。如果要得到n位有效数字的随机数，只需将表中每n个相邻的随机数字合并在一起，且在最高位的前边加上小数点即可。例如，某随机数表的第一行数字为7634258910，要想得到三位有效数字的随机数依次为0.763，0.425，0.891。n因为随机数表需在计算机中占有很大内存，而且也难以满足蒙特卡罗方法对随机数需要量非常大的要求，因此，该方法不适于在计算机上使用。3)物理方法产生随机数n用物理方法产生随机数的基本原理是：利用某些物理现象，在计算机上增加些特殊设备，可以在计算机上直接产生随机数。这些特殊设备称为随机数发生器。用来作为随机数发生器的物理源主要有两种：一种是根据放射性物质的放射性，另一种是利用计算机的固有噪声。n 用物理方法产生的随机数序列无法重复实现，不能进行程序复算，给验证结果带来很大困难。而且，需要增加随机数发生器和电路联系等附加设备，费用昂贵。因此，该方法也不适合在计算机上使用。在计算机上产生随机数最实用、最常见的方法是数学方法，即用如下递推公式：伪随机数经常使用的是k=1的情况，其递推公式为：用数学方法产生的随机数，存在两个问题：a)1,递推公式和初始值确定后，整个随机数序列便被唯一确定。不满足随机数相互独立的要求。b)2,由于随机数序列是由递推公式确定的，而在计算机上所能表示的0，1上的数又是有限的，因此，这种方法产生的随机数序列就不可能不出现无限重复。对于k=1的情况，只要有一个随机数重复，其后面的随机数全部重复，这与随机数的要求是不相符的。由于这两个问题的存在，常称用数学方法产生的随机数为伪随机数。利用计算机产生随机数的方法：1，乘方取中法：设x0为一个4s位数。把x02截头去尾，只保留中间2s位，作为数列的下一个数x1。对于十进制：MOD是求余数运算。则0,1区间的随机数为：缺点：a,周期较短，b,所得序列有向小端偏移的倾向。2,乘同余法对于xi-1，乘积xi-1除以M后余数为xi其中x0,M为选定的常数，例如：x0=1,=513,M=242等。得到的周期 T 21010，基本满足一般需要。随机数的检验：目的：确认它在0,1区间内部均匀分布的可靠程度。主要有四个方面。a,均匀性检验：把0,1区间分成m个子区间，统计i落入第j个子区间的个数nj，若分布均匀，则i落入各子区间的几率相同，均为：b,独立性检验：考虑随机数应该是前后独立的，通常考虑它们的相关系数等于0。c,组合规律性检验：将N个随机数按一定的规律组合起来，则各种组合的概率分布不相关。d,无连贯性检验：把数按大小分成两类，要求各类数的出现没有连贯现象。第三节 蒙特卡罗方法应用举例优点：1,用该方法，程序结构简单。2,收敛速度与问题的维数无关，可用简单思路处理复杂问题。缺点：速度一般较慢。根据以上特点，本节介绍下面的例子：1，计算经过多次统计而得到的概率。2，计算定积分，特别是高维积分。3，可应用于解方程和方程组。赌徒的概率问题：赌场中，长期以来赌徒认为：3个骰子扔出9点和10点的几率是相同的。理由：9点和10点都有6种组合。长期下去，发现似乎有不同。试通过蒙特卡罗方法，设计一种计算机算法，来讨论这个问题。用蒙特卡罗方法计算，模拟投掷20万次。随机数产生函数设定为C语言中的random()，所得到的结果为：9点概率：0.11435；10点概率：0.12785.醉汉回家（随机行走问题）：在热力学问题中抽象出一个模型：一个粒子，每一步向左和向右的概率均为0.5。问：1，走100步以后，在原位置右边50步处的概率多大?2，在原位置右边50步100步处的概率有多大？思考：利用蒙特卡罗方法设计一种算法来计算上述问题。计算定积分：在a,b区间内选定大量（N个）随机数xi，并计算出相应的f(xi)，则有：推广后即可计算二重积分：在a,b选N个xi，在c,d选N个yi优点：方法简单易懂。程序简单（只需进行简单求和运算，做平均即可）。可直接推广至高维定积分。解非线性方程组：构造目标函数：确定各自变量的取值域，在取值域内选取随机变量，直到目标函数Q。最后得到的一组随机变量(x1,x2,.,xn)，就是方程的解。
