2.1 蒙特卡洛方法(Monte Carlo simulation),引言(introduction) MC基本思想 MC收敛性及误差 MC特点,一、两种自然现象 确定性的： 日月升落，四季轮回，磁石吸铁 不确定的： 掷骰子，炮弹落点，考试成绩 二、两种研究方法 确定性问题: 解析,有限元,分子动力学,Monte-Carlo 随机性问题：Monte-Carlo，布朗动力学,1.引言,计算机模拟：,(1) 随机模拟方法或统计试验方法，又称蒙特卡洛(Monte Carlo)方法。它是通过不断产生随机数序列来模拟过程。自然界中有的过程本身就是随机的过程，物理现象中如粒子的衰变过程、粒子在介质中的输运过程等。当然蒙特卡洛方法也可以借助慨率模型来解决不直接具有随机性的确定性问题。 (2) 确定性模拟方法。它是通过数值求解一个个的粒子运动方程来模拟整个系统的行为。在统计物理中称为分子动力学（Molecular Dynamics）方法。此外, 近年来还发展了神经元网络方法和原胞自动机方法。,1.引言,MC方法，分为三种类型：,（1）直接蒙特卡洛模拟。它采用随机数序列来模拟复杂随机过程的效应。 （2）蒙特卡洛积分。这是利用随机数序列计算积分的方法。积分维数越高，该方法的积分效率就越高。 （3）Metropolis蒙特卡洛模拟。这种模拟是以所谓“马尔科夫”（Markov）鏈的形式产生系统的分布序列。该方法可以使我们能够研究经典和量子多粒子系统的问题。,1.引言,Monte Carlo方法简史,简单地介绍一下Monte Carlo方法的发展历史,1、Buffon投针实验：,1768年，法国数学家Comte de Buffon利用投针实验估计的值,1.引言,1.引言,1.引言,1.引言,2、1930年，Enrico Fermi利用Monte Carlo方法研究中子的扩散，并设计了一个Monte Carlo机械装置，Fermiac,用于计算核反应堆的临界状态,3、Von Neumann是Monte Carlo方法的正式奠基者,他与Stanislaw Ulam合作建立了概率密度函数、反累积分布函数的数学基础，以及伪随机数产生器。在这些工作中， Stanislaw Ulam意识到了数字计算机的重要性,合作起源于Manhattan工程：利用ENIAC(Electronic Numerical Integrator and Computer)计算产额,1.引言,MC的统计基础- 随机变量及其分布,定义随机变量 X=xi，概率分布F(x)是X的函数 离散分布： 连续分布： f(x)为概率分布密度 数学期望： 和 方差：,1.引言,MC的统计基础- 大数定理,设 x1, x2, xn, 为一随机变量序列, 相互独立, 具有同样分布, 且 E(xi)=a 存在, 则对任意小量 0, 有 统计含义：不论随机变量的分布如何, 只要n足够大, 则算 术平均与数学期望值可无限接近, 也就是说, 算术平均以几 率收敛于其数学期望值.,1.引言,MC的统计基础- 中心极限定理,设 x1,x2,xn, 为一随机变量序列, 相互独立, 具有同样 分布, 且 E(xi)=, D(xi)=2 存在, 则 统计含义：如果一个随机变量X，是由大量相互独立的因素 的影响形成的，其中每一个因素在总的影响中所起作用都 是微小的（被稀释） ，这种随机变量近似地服从正态分布,1.引言,MC的基础 随机过程,1 定义，XX (x,t) 随时间变化的随机变量，或时间随机变量序列 2 按分布函数，分类 a) 平稳随机过程 b) Markov 过程 c) 独立增量随机过程 d) 独立随机过程,1.引言,MC的基础 - 平稳随机过程,1 定义：X(t) , 如果它的n维（n个状态）概率密度与初始分布无关，即对任何n 和 t满足fx(x1,x2,xn; t1,t2,.,tn)=fx(x1,x2,xn; t1+t,t2 +t,.,tn +t) 含义：平稳随机过程的统计特性与所选择的时间起点无关，不随时间的推移而变化，即是“时间平稳的”。 2 统计特性 1）一维概率密度与时间无关 2）二维概率密度，只与两个状态对应的时间间隔t有关，其时间自相关仅是t的函数 3 应用： 电阻的热噪声，电子信号，,1.引言,MC的基础 - Markov 链,1 定义：在可列个离散状态x1,x2,.xN 和离散时间t1,t2,.tn, 若随 机过程在tm+k时刻变成任一状态xi的概率，只与tm时刻的 状态有关(无后效)，而与此前状态无关，称离散随机序列 PXm+k=xi,m+k | Xm=xi,m, Xm-1=xi,m-1,., X1=xi,1 = PXm+k=xi,m+k | Xm=xi,m 为Markov链. 2 概率转移矩阵 pij 条件概率： pij(m, m+k)PXm+k=xj| Xm=xi 不依赖于m的pij称，齐次Markov 链 3 应用：统计物理Ising模型（固态相变，液固相变，）,1.引言,MC的模拟方法（步骤）,1. 确定统计方案( Xi , ) 2. 确定随机变量Xi 的概率分布：fi(x) 3. 根据 fi(x) ，对Xi抽样： Xi - Ri 4. 编程进行计算机模拟 5. 获得统计量,1.引言,MC的模拟方法1 确定统计方案,1 确定统计模型 1) 现象 模型 随机现象YY(Xi)， Xi=X1, X2, X3, 2) 确定随机变量Xi的分布特征fi(x) 平均分布，指数分布，正态分布，分布 2 确定统计量,1.引言,MC的模拟方法2常见的概率分布,其他还有：分布，分布，2分布，t分布，Poisson分布,1.引言,MC的模拟方法3 概率抽样方法,1 直接抽样法：反函数法、函数变换法 2 间接抽样法：舍选法,值序抽样 设g(x,y)为X,Y的联合密度函数 如有某一分布 H(x) M 为任意函数，请对其抽样。 舍选抽样示意图,1.引言,MC的模拟方法4 随机数的产生,1 基本随机数， 2 随机数和“伪随机数” 伪随机数（序列）重演周期应足够长 3 产生办法 同余法、混合同余法、组合同余法等 4 计算机实现 a) 自定义子程序，b) 调用内部函数 强调：伪随机数的好坏，直接影响统计结果，应予重视。,1.引言,Monte Carlo模拟在物理研究中的作用,1.引言,Monte Carlo模拟的步骤：,根据欲研究的物理系统的性质，建立能够描述该系统特性的理论模型，导出该模型的某些特征量的概率密度函数；,从概率密度函数出发进行随机抽样，得到特征量的一些模拟结果；,对模拟结果进行分析总结，预言物理系统的某些特性。,1.引言,注意以下两点：,Monte Carlo方法与数值解法的不同:,Monte Carlo方法利用随机抽样的方法来求解物理问题;,数值解法:从一个物理系统的数学模型出发,通过求解一系列的微分方程来的导出系统的未知状态;,Monte Carlo方法并非只能用来解决包含随机的过程的问题:,许多利用Monte Carlo方法进行求解的问题中并不包含随机过程 例如:用Monte Carlo方法计算定积分. 对这样的问题可将其转换成相关的随机过程, 然后用Monte Carlo方法进行求解,1.引言,Monte Carlo算法的主要组成部分,概率密度函数(pdf) 必须给出描述一个物理系统的一组概率密度函数;,随机数产生器能够产生在区间0,1上均匀分布的随机数,抽样规则如何从在区间0,1上均匀分布的随机数出发,随机抽取服从给定的pdf的随机变量;,模拟结果记录记录一些感兴趣的量的模拟结果,误差估计必须确定统计误差（或方差）随模拟次数以及其它一些量的变化；,减少方差的技术利用该技术可减少模拟过程中计算的次数；,并行和矢量化可以在先进的并行计算机上运行的有效算法,1.引言,Monte Carlo模拟的应用：,自然现象的模拟：,实验探测器的模拟,数值分析：,利用Monte Carlo方法求积分,1.引言,27,1.针对实际问题建立一个简单且便于实现的概率统计模 型，使所求的量（或解）恰好是该模型某个指标的概率分布或者数字特征。,2.对模型中的随机变量建立抽样方法，在计算机上进行 模拟测试，抽取足够多的随机数，对有关事件进行统计,3.对模拟试验结果加以分析，给出所求解的估计及其精 度(方差)的估计,4.必要时，还应改进模型以降低估计方差和减少试验费 用，提高模拟计算的效率,2.MC基本思路,当问题可以抽象为某个确定的数学问题时，应当首先建立一个恰当的概率模型，即确定某个随机事件A或随机变量X，使得待求的解等于随机事件出现的概率或随机变量的数学期望值。然后进行模拟实验，即重复多次地模拟随机事件A或随机变量X。最后对随机实验结果进行统计平均，求出A出现的频数或X的平均值作为问题的近似解。,2.MC基本思想,二十世纪四十年代中期，由于科学技术的发展和电子计算机的发明，蒙特卡罗方法作为一种独立的方法被提出来，并首先在核武器的试验与研制中得到了应用。但其基本思想并非新颖，人们在生产实践和科学试验中就已发现，并加以利用。 两个例子 例1. 蒲丰氏问题 例2. 射击问题（打靶游戏） 计算机模拟试验过程,2.MC基本思想,例1. 蒲丰氏问题,为了求得圆周率值，在十九世纪后期，有很多人作了这样的试验：将长为2l的一根针任意投到地面上，用针与一组相间距离为2a（ la）的平行线相交的频率代替概率P，再利用准确的关系式： 求出值 其中为投计次数，n为针与平行线相交次数。这就是古典概率论中著名的蒲丰氏问题。,2.MC基本思想,一些人进行了实验，其结果列于下表 ：,2.MC基本思想,例2. 射击问题（打靶游戏）,设r表示射击运动员的弹着点到靶心的距离，(r)表示击中r处相应的得分数（环数），f(r)为该运动员的弹着点的分布密度函数，它反映运动员的射击水平。该运动员的射击成绩为 用概率语言来说，是随机变量(r)的数学期望，即,2.MC基本思想,现假设该运动员进行了次射击，每次射击的弹着点依次为r1，r2，rN，则次得分g(r1)，g(r2)，g(rN)的算术平均值 代表了该运动员的成绩。换言之，为积分的估计值，或近似值。 在该例中，用次试验所得成绩的算术平均值作为数学期望的估计值（积分近似值）。,2.MC基本思想,2.MC基本思想数值积分,与一般的数值积分方法比较，Monte Carlo方法 具有以下优点：,2.MC基本思想数值积分,由以上例子可以看出，当所求问题的解是某个事件的概率，或者是某个随机变量的数学期望，或者是与概率、数学期望有关的量时，通过某种试验的方法，得出该事件发生的频率，或者该随机变量若干个具体观察值的算术平均值，通过它得到问题的解。这就是蒙特卡罗方法的基本思想。 当随机变量的取值仅为1或0时，它的数学期望就是某个事件的概率。或者说，某种事件的概率也是随机变量（仅取值为1或0）的数学期望。,2.MC基本思想,因此，可以通俗地说，蒙特卡罗方法是用随机试验的方法计算积分，即将所要计算的积分看作服从某种分布密度函数f(r)的随机变量(r)的数学期望 通过某种试验，得到个观察值r1，r2，rN（用概率语言来说，从分布密度函数f(r)中抽取个子样r1，r2，rN，），将相应的个随机变量的值g(r1)，g(r2)，g(rN)的算术平均值 作为积分的估计值（近似值）。,2.MC基本思想,为了得到具有一定精确度的近似解，所需试验的次数是很多的，通过人工方法作大量的试验相当困难，甚至是不可能的。因此，蒙特卡罗方法的基本思想虽然早已被人们提出，却很少被使用。本世纪四十年代以来，由于电子计算机的出现，使得人们可以通过电子计算机来模拟随机试验过程，把巨大数目的随机试验交由计