数学建模十大经典算法之蒙特卡罗方法讲义课件.ppt

;目录;教材;参考书;第一章蒙特卡罗方法概述;第一章蒙特卡罗方法概述;蒙特卡罗方法的根本思想;例1.蒲丰氏问题;

一些人进行了实验，其结果列于下表：;例2.射击问题〔打靶游戏〕;;根本思想;;计算机模拟试验过程;例１．蒲丰氏问题;如何产生任意的〔x,θ〕？x在［0，a］上任意取值，表示x在［0，a］上是均匀分布的，其分布密度函数为：

类似地，θ的分布密度函数为：

因此，产生任意的〔x,θ〕的过程就变成了由f1(x)抽样x及由f2(θ)抽样θ的过程了。由此得到：

其中ξ1，ξ2均为〔0,1〕上均匀分布的随机变量。;每次投针试验，实际上变成在计算机上从两个均匀分布的随机变量中抽样得到〔x,θ〕，然后定义描述针与平行线相交状况的随机变量s(x,θ)，为

如果投针Ｎ次，那么

是针与平行线相交概率Ｐ的估计值。事实上，

于是有;例２．射击问题;蒙特卡罗方法的收敛性，误差;收敛性;误差;当N充分大时，有如下的近似式

其中α称为置信度，1－α称为置信水平。

这说明，不等式近似地以概率

1－α成立，且误差收敛速度的阶为。

通常，蒙特卡罗方法的误差ε定义为

上式中与置信度α是一一对应的，根据问题的要求确定出置信水平后，查标准正态分布表，就可以确定出。;下面给出几个常用的α与的数值：

?

关于蒙特卡罗方法的误差需说明两点：第一，蒙特卡罗方法的误差为概率误差，这与其他数值计算方法是有区别的。第二，误差中的均方差σ是未知的，必须使用其估计值

来代替，在计算所求量的同时，可计算出。;减小方差的各种技巧;效率;蒙特卡罗方法的特点;能够比较逼真地描述具有随机性质的事物的特点及物理实验过程;受几何条件限制小;收敛速度与问题的维数无关;具有同时计算多个方案与多个未知量的能力;误差容易确定;程序结构简单，易于实现;收敛速度慢;误差具有概率性;在粒子输运问题中，计算结果与系统大小有关;蒙特卡罗方法的主要应用范围;作业;第二章随机数;第二章随机数;随机数的定义及产生方法;随机数的定义及性质;由于随机数在蒙特卡罗方法中占有极其重要的位置，我们用专门的符号ξ表示。由随机数序列的定义可知，ξ1，ξ2，…是相互独立且具有相同单位均匀分布的随机数序列。也就是说，独立性、均匀性是随机数必备的两个特点。

随机数具有非常重要的性质：对于任意自然数s，由s个随机数组成的s维空间上的点〔ξn+1，ξn+2，…ξn+s〕在s维空间的单位立方体Gs上均匀分布，即对任意的ai，

如下等式成立：;

其中P(·)表示事件·发生的概率。反之，如果随机变量序列ξ1,ξ2…对于任意自然数s，由s个元素所组成的s维空间上的点〔ξn+1，…ξn+s〕在Gs上均匀分布，那么它们是随机数序列。

由于随机数在蒙特卡罗方法中所处的特殊地位，它们虽然也属于由具有分布的总体中产生简单子样的问题，但就产生方法而言，却有着本质上的差异。;随机数表;物理方法;因此，利用物理方法在计算机上产生随机数，就是要产生只取0或1的随机数字序列，数字之间相互独立，每个数字取0或1的概率均为0.5。

用物理方法产生的随机数序列无法重复实现，不能进行程序复算，给验证结果带来很大困难。而且，需要增加随机数发生器和电路联系等附加设备，费用昂贵。因此，该方法也不适合在计算机上使用。;伪随机数;伪随机数;伪随机数存在的两个问题;由于这两个问题的存在，常称用数学方法产生的随机数为伪随机数。对于以上存在的两个问题，作如下具体分析。

关于第一个问题，不能从本质上加以改变，但只要递推公式选得比较好，随机数间的相互独立性是可以近似满足的。至于第二个问题，那么不是本质的。因为用蒙特卡罗方法解任何具体问题时，所使用的随机数的个数总是有限的，只要所用随机数的个数不超过伪随机数序列出现循环现象时的长度就可以了。

用数学方法产生的伪随机数容易在计算机上得到，可以进行复算，而且不受计算机型号的限制。因此，这种方法虽然存在着一些问题，但仍然被广泛地在计算机上使用，是在计