培训程序MonteCarlo幻灯片.ppt

与Monte Carlo方法相似，但理论基础不同的方法—“拟蒙特卡罗方法”(Quasi-Monte Carlo方法)—近年来也获得迅速发展。这种方法的基本思想是“用确定性的超均匀分布序列(数学上称为Low Discrepancy Sequences)代替Monte Carlo方法中的随机数序列。对某些问题该方法的实际速度一般可比Monte Carlo方法提高数百倍。   Monte Carlo方法的优点 能够比较逼真地描述具有随机性质的事物的特点及物理实验过程 受几何条件限制小 收敛速度与问题的维数无关 误差容易确定 程序结构简单，易于实现 Monte Carlo方法的缺点 收敛速度慢 误差具有概率性 进行模拟的前提是各输入变量是相互独立的 * Monte Carlo 内容提纲 1.引言 2.Monte Carlo模拟基本思想 3.应用实例举例 4.排队论模拟 5.Monte Carlo模拟求解规划问题 6.Monte Carlo方法的优缺点 引言(Introduction) Monte Carlo方法： 蒙特卡罗方法，又称随机模拟方法，属于计算数学的一个分支，它是在上世纪四十年代中期为了适应当时原子能事业的发展而发展起来的。亦称统计模拟方法，statistical simulation method ?利用随机数进行数值模拟的方法 Monte Carlo名字的由来： Monte Carlo是摩纳哥（monaco)的首都，该城以赌博闻名 Nicholas Metropolis (1915-1999) Monte-Carlo, Monaco Monte Carlo方法的基本思想 蒙特卡罗方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。源于美国在第二次世界大战研制原子弹的“曼哈顿计划”，该计划的主持人之一数学家冯·诺伊曼用驰名世界的赌城—摩纳哥的Monte Carlo—来命名这种方法，为它蒙上了一层神秘色彩。 蒙特卡罗方法的基本思想很早以前就被人们所发现和利用。早在17世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。19世纪人们用蒲丰投针的方法来计算圆周率π，上世纪40年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。 蒲丰投针实验： 法国科学家蒲丰(Buffon)在1777年提出的蒲丰 投针实验是早期几何概率一个非常著名的例子。蒲丰 投针实验的重要性并非是为了求得比其它方法更精确 的π值，而是它开创了使用随机数处理确定性数学问 题的先河，是用偶然性方法去解决确定性计算的前导。由此可以领略到从“概率土壤”上开出的一朵瑰丽的鲜花-蒙特卡罗方法(MC) 蒲丰投针实验可归结为下面的数学问题：平面上画有距离为a的一些平行线，向平面上任意投一根长为l (la)的针，假设针落在任意位置的可能性相同，试求针与平行线相交的概率P(从而求π) 蒲丰投针实验： 如右图所示，以M表示针落下 后的中点，以x表示M到最近一条平行 线的距离，以φ表示针与此线的交角： 针落地的所有可能结果满足： 其样本空间视作矩形区域Ω, 面积是: 针与平行线相交的条件： 它是样本空间Ω子集A，面积是： 因此，针与平行线相交的概率为： 从而有： 一些人进行了实验，其结果列于下表 ： 实验者 年份 投计次数 π的实验值 沃尔弗(Wolf) 1850 5000 3.1596 斯密思(Smith) 1855 3204 3.1553 福克斯(Fox) 1894 1120 3.1419 拉查里尼(Lazzarini) 1901 3408 3.1415929 蒙特卡罗投点法是蒲丰投针实验的推广： 在一个边长为a的正方形内随机投点，该点落在此正方形的内切圆中的概率应为该内切圆与正方形的面积比值， 即 x y o (a/2,a/2) 基本思想 由上面的例子可以看出，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与之有关的量时，通过某种试验的方法，得出该事件发生的频率，再通过它得到问题的解。这就是蒙特卡罗方法的基本思想。 蒙特卡罗方法的关键步骤在于随机数的产生，计算机产生的随机数都不是真正的随机数(由算法确定的缘故)，如果伪随机数能够通过一系列统计检验，我们也可以将其当作真正的随机数使用。 rand(seed,0.1); rand(1) ％每次运行程序产生的值是相同的 rand(state,sum(100*clock)*rand); rand(1) %每次重新启动matlab时，输出的随机数不一样 注意: 产生一个参数为λ的指数