《蒙特卡罗方法概述ppt》由会员分享,可在线阅读,更多相关《蒙特卡罗方法概述ppt(34页珍藏版)》请在金锄头文库上搜索。
1、第一章 蒙特卡罗方法概述l蒙特卡罗方法的基本思想 l蒙特卡罗方法的收敛性,误差 l蒙特卡罗方法的特点 l蒙特卡罗方法的主要应用范围作 业第一章 蒙特卡罗方法概述蒙特卡罗方法又称随机抽样技巧或统计试验方法 。半个多世纪以来,由于科学技术的发展和电子计算 机的发明 ,这种方法作为一种独立的方法被提出来, 并首先在核武器的试验与研制中得到了应用。蒙特卡 罗方法是一种计算方法,但与一般数值计算方法有很 大区别。它是以概率统计理论为基础的一种方法。由 于蒙特卡罗方法能够比较逼真地描述事物的特点及物 理实验过程,解决一些数值方法难以解决的问题,因 而该方法的应用领域日趋广泛。1.蒙特卡罗方法的基本思想二十
2、世纪四十年代中期,由于科学技术的发展和 电子计算机的发明,蒙特卡罗方法作为一种独立的方 法被提出来,并首先在核武器的试验与研制中得到了 应用。但其基本思想并非新颖,人们在生产实践和科 学试验中就已发现,并加以利用。两个例子例1. 蒲丰氏问题例2. 射击问题(打靶游戏)基本思想计算机模拟试验过程例1. 蒲丰氏问题为了求得圆周率值,在十九世纪后期,有很多人 作了这样的试验:将长为2l的一根针任意投到地面上 ,用针与一组相间距离为2a( la)的平行线相交的 频率代替概率P,再利用准确的关系式:求出值其中为投计次数,n为针与平行线相交次数。 这就是古典概率论中著名的蒲丰氏问题。一些人进行了实验,其结
3、果列于下表 :实验者年份投计次数的实验值沃尔弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼 (Lazzarini)190134083.1415929例2. 射击问题(打靶游戏) 设r表示射击运动员的弹着点到靶心的距离, (r)表示击中r处相应的得分数(环数),f(r)为该运动 员的弹着点的分布密度函数,它反映运动员的射击水 平。该运动员的射击成绩为 用概率语言来说,是随机变量(r)的数学期 望,即 现假设该运动员进行了次射击,每次射击的弹 着点依次为r1,r2,rN,则次得分g(r1),g(r2),
4、 ,g(rN)的算术平均值代表了该运动员的成绩。换言之,为积分的 估计值,或近似值。在该例中,用次试验所得成绩的算术平均值作 为数学期望的估计值(积分近似值)。 基本思想 由以上两个例子可以看出,当所求问题的解是某 个事件的概率,或者是某个随机变量的数学期望,或 者是与概率、数学期望有关的量时,通过某种试验的 方法,得出该事件发生的频率,或者该随机变量若干 个具体观察值的算术平均值,通过它得到问题的解。 这就是蒙特卡罗方法的基本思想。 当随机变量的取值仅为1或0时,它的数学期望就 是某个事件的概率。或者说,某种事件的概率也是随 机变量(仅取值为1或0)的数学期望。 因此,可以通俗地说,蒙特卡罗
5、方法是用随机试 验的方法计算积分,即将所要计算的积分看作服从某 种分布密度函数f(r)的随机变量(r)的数学期望 通过某种试验,得到个观察值r1,r2,rN(用概 率语言来说,从分布密度函数f(r)中抽取个子样r1, r2,rN,),将相应的个随机变量的值g(r1), g(r2),g(rN)的算术平均值作为积分的估计值(近似值)。 为了得到具有一定精确度的近似解,所需试验的 次数是很多的,通过人工方法作大量的试验相当困难 ,甚至是不可能的。因此,蒙特卡罗方法的基本思想 虽然早已被人们提出,却很少被使用。本世纪四十年 代以来,由于电子计算机的出现,使得人们可以通过 电子计算机来模拟随机试验过程,
6、把巨大数目的随机 试验交由计算机完成,使得蒙特卡罗方法得以广泛地 应用,在现代化的科学技术中发挥应有的作用。 计算机模拟试验过程 计算机模拟试验过程,就是将试验过程(如投针 ,射击)化为数学问题,在计算机上实现。以上述两 个问题为例,分别加以说明。例1. 蒲丰氏问题例2. 射击问题(打靶游戏)由上面两个例题看出,蒙特卡罗方法常以一个“概 率模型”为基础,按照它所描述的过程,使用由已知 分布抽样的方法,得到部分试验结果的观察值,求得 问题的近似解。 例蒲丰氏问题设针投到地面上的位置 可以用一组参数(x,)来描 述,x为针中心的坐标,为 针与平行线的夹角,如图所 示。任意投针,就是意味着 x与都是
7、任意取的,但x的范 围限于0,a,夹角的 范围限于0,。在此情 况下,针与平行线相交的数 学条件是针在平行线间的位置 如何产生任意的(x,) ?x在0,a上任意取值, 表示x在0,a上是均匀分 布的,其分布密度函数为:类似地,的分布密度函 数为:因此,产生任意的(x, )的过程就变成了由f1(x)抽样x 及由f2()抽样的过程了。由 此得到:其中1,2均为(0,1)上均匀 分布的随机变量。 每次投针试验,实际上变成在计算机上从两个均 匀分布的随机变量中抽样得到(x,),然后定义描述 针与平行线相交状况的随机变量s(x,),为如果投针次,则是针与平行线相交概率的估计值。事实上, 于是有 例射击问
8、题 设射击运动员的弹着点分布为用计算机作随机试验(射击 )的方法为,选取一个随机数 ,按右边所列方法判断得到成绩 。这样,就进行了一次随机试 验(射击),得到了一次成绩 (r),作次试验后,得到该运 动员射击成绩的近似值 环数 78910 概率 0.10.10.30.52.蒙特卡罗方法的收敛性,误差 蒙特卡罗方法作为一种计算方法,其收敛性与误 差是普遍关心的一个重要问题。收敛性误差减小方差的各种技巧 效率 收敛性 由前面介绍可知,蒙特卡罗方法是由随机变量X 的简单子样X1,X2,XN的算术平均值: 作为所求解的近似值。由大数定律可知,如X1,X2,XN独立同分布,且具有有限期望值( E(X))
9、,则 即随机变量X的简单子样的算术平均值 ,当子 样数充分大时,以概率1收敛于它的期望值E(X)。 误差 蒙特卡罗方法的近似值与真值的误差问题,概率论 的中心极限定理给出了答案。该定理指出,如果随机 变量序列X1,X2,XN独立同分布,且具有有限非 零的方差2 ,即f(X)是X的分布密度函数。则当N充分大时,有如下的近似式其中称为置信度,1称为置信水平。这表明,不等式 近似地以概率1成立,且误差收敛速度的阶为 。通常,蒙特卡罗方法的误差定义为上式中 与置信度是一一对应的,根据问题的要 求确定出置信水平后,查标准正态分布表,就可以确 定出 。下面给出几个常用的与的数值:关于蒙特卡罗方法的误差需说
10、明两点:第一,蒙特 卡罗方法的误差为概率误差,这与其他数值计算方法 是有区别的。第二,误差中的均方差是未知的,必 须使用其估计值来代替,在计算所求量的同时,可计算出 。 0.50.050.0030.674 51.963 减小方差的各种技巧 显然,当给定置信度后,误差由和N决定。要 减小,或者是增大N,或者是减小方差2。在固定 的情况下,要把精度提高一个数量级,试验次数N需 增加两个数量级。因此,单纯增大N不是一个有效的 办法。另一方面,如能减小估计的均方差,比如降低 一半,那误差就减小一半,这相当于N增大四倍的效 果。因此降低方差的各种技巧,引起了人们的普遍注 意。后面课程将会介绍一些降低方差
11、的技巧。 效率 一般来说,降低方差的技巧,往往会使观察一个 子样的时间增加。在固定时间内,使观察的样本数减 少。所以,一种方法的优劣,需要由方差和观察一个 子样的费用(使用计算机的时间)两者来衡量。这就是蒙特卡罗方法中效率的概念。它定义为 ,其中 c是观察一个子样的平均费用。显然 越小,方法越 有效。 3.蒙特卡罗方法的特点优点 l能够比较逼真地描述具有 随机性质的事物的特点及物 理实验过程。 l受几何条件限制小。 l收敛速度与问题的维数无 关。 l具有同时计算多个方案与 多个未知量的能力。 l误差容易确定。 l程序结构简单,易于实现 。 缺点 收敛速度慢。 误差具有概率性。 在粒子输运问题中
12、 ,计算结果与系统 大小有关。1)能够比较逼真地描述具有随机性 质的事物的特点及物理实验过程从这个意义上讲,蒙特卡罗方法可以部分代替物 理实验,甚至可以得到物理实验难以得到的结果。用 蒙特卡罗方法解决实际问题,可以直接从实际问题本 身出发,而不从方程或数学表达式出发。它有直观、 形象的特点。2)受几何条件限制小在计算s维空间中的任一区域Ds上的积分时,无论区域Ds的形状多么特殊,只要能给出描述Ds 的几何特征的条件,就可以从Ds中均匀产生N个点,得到积分的近似值。其中Ds为区域Ds的体积。这是数值方法难以作到的。另外,在具有随机性质的问题中,如考虑的系统 形状很复杂,难以用一般数值方法求解,而
13、使用蒙特 卡罗方法,不会有原则上的困难。 3)收敛速度与问题的维数无关由误差定义可知,在给定置信水平情况下,蒙特 卡罗方法的收敛速度为 ,与问题本身的维数 无关。维数的变化,只引起抽样时间及估计量计算时 间的变化,不影响误差。也就是说,使用蒙特卡罗方 法时,抽取的子样总数N与维数s无关。维数的增加, 除了增加相应的计算量外,不影响问题的误差。这一 特点,决定了蒙特卡罗方法对多维问题的适应性。而 一般数值方法,比如计算定积分时,计算时间随维数 的幂次方而增加,而且,由于分点数与维数的幂次方 成正比,需占用相当数量的计算机内存,这些都是一 般数值方法计算高维积分时难以克服的问题。4)具有同时计算多
14、个方案与多个未 知量的能力对于那些需要计算多个方案的问题,使用蒙特卡 罗方法有时不需要像常规方法那样逐个计算,而可以 同时计算所有的方案,其全部计算量几乎与计算一个 方案的计算量相当。例如,对于屏蔽层为均匀介质的 平板几何,要计算若干种厚度的穿透概率时,只需计 算最厚的一种情况,其他厚度的穿透概率在计算最厚 一种情况时稍加处理便可同时得到。另外,使用蒙特卡罗方法还可以同时得到若干个 所求量。例如,在模拟粒子过程中,可以同时得到不 同区域的通量、能谱、角分布等,而不像常规方法那 样,需要逐一计算所求量。 5)误差容易确定对于一般计算方法,要给出计算结果与真值的误 差并不是一件容易的事情,而蒙特卡
15、罗方法则不然。 根据蒙特卡罗方法的误差公式,可以在计算所求量的 同时计算出误差。对干很复杂的蒙特卡罗方法计算问 题,也是容易确定的。一般计算方法常存在着有效位数损失问题,而要 解决这一问题有时相当困难,蒙特卡罗方法则不存在 这一问题。 6)程序结构简单,易于实现在计算机上进行蒙特卡罗方法计算时,程序结构 简单,分块性强,易于实现。 1)收敛速度慢如前所述,蒙特卡罗方法的收敛速度为 ,一般不容易得到精确度较高的近似结果。对于维数 少(三维以下)的问题,不如其他方法好。 2)误差具有概率性由于蒙特卡罗方法的误差是在一定置信水平下估 计的,所以它的误差具有概率性,而不是一般意义下 的误差。 3)在粒子输运问题中,计算结果与 系统大小有关经验表明,只有当系统的大小与粒子的平均自由 程可以相比较时(一般在十个平均自由程左右),蒙 特卡罗方法计算的结果较为满意。但对于大系统或小 概率事件的计算问题,计算结果往往比真值偏低。而 对于大系统,数值方法则是适用的。因此,在使用蒙特卡罗方法时,可以考虑把蒙特 卡罗方法与解析(或数值)方法相结合,取长补短, 既能解决解析(或数值)方法难以解决的问题,也可 以解决单纯使用蒙特卡罗方法难以解决的问题。这样 ,可以发挥蒙特卡罗方法的特长,使其应用范围更加 广泛。 4.蒙特卡罗方法的主要应用范围 蒙特卡罗方法所特有的优点,使得它的应用范围 越来越