蒙特卡洛方法-

第六讲蒙特卡洛方法计算机模拟方法分类•(1)蒙特卡洛(MonteCarlo)方法，又称随机模拟方法或统计试验方法。它是通过一个合适的概率模型不断产生随机数序列来模拟过程。自然界中有的过程本身就是随机的过程，物理现象中如粒子的衰变过程、粒子在介质中的输运过程...等。当然蒙特卡洛方法也可以借助慨率模型来解决不直接具有随机性的确定性问题。•(2)确定性模拟方法。它是通过数值求解一个个的粒子运动方程来模拟整个系统的行为。如分子动力学（MolecularDynamics）方法以及原胞自动机方法等等。WhyMonteCarlo（MC）?MC方法的起源•起源于思想起源于vonNeumann（冯.诺依曼）等人在研究原子弹时对裂变材料的中子扩散问题的探讨。•目前，已经广泛的应用于社会科学，材料，物理，系统工程，科学管理，生物遗传等领域。可以说，有随机工程事件的领域，就可以应用MonteCarlo模拟。MC的基本思想•直接蒙特卡洛模拟方法。求解问题本身就具有概率和统计性的情况，该方法是按照实际问题所遵循的概率统计规律，用计算机进行直接的抽样试验，然后计算其感兴趣的统计参数（计算机实验）。•间接蒙特卡洛模拟方法。人为地构造出一个合适的概率模型，依照该模型进行大量的统计实验，使它的某些统计参量正好是待求问题的解。例：布冯(Buffon)投针实验•在平滑桌面上划一组相距为s的平行线，向此桌面随意地投掷长度l=s的细针，那末从针与平行线相交的概率就可以得到π的数值。s针与线相交概率N次投针，M次相交，当N足够大时：NM2求Pi转化为求一随机过程的参数。•一些人进行了实验，其结果列于下表：实验者年份投计次数π的实验值沃尔弗(Wolf)185050003.1596斯密思(Smith)185532043.1553福克斯(Fox)189411203.1419拉查里尼(Lazzarini)190134083.1415929例：投点试验shothitsquarecirclettSS=3.14173精度不高！！例：求解定积分•定积分计算•随机向正方形内掷点，总掷点N，落于曲线下方的为M，N足够大时，I=M/NMC思想总结•当问题可以抽象为某个确定的数学问题时，应当首先建立一个恰当的概率模型，即确定某个随机事件A或随机变量X，使得待求的解等于随机事件出现的概率或随机变量的数学期望值。然后进行模拟实验，即重复多次地模拟随机事件A或随机变量X。最后对随机实验结果进行统计平均，求出A出现的频数或X的平均值作为问题的近似解。（间接MC）MC方法概述•为了得到具有一定精确度的近似解，所需随机试验的次数是很多的，通过人工方法作大量的试验相当困难，甚至是不可能的。因此，蒙特卡罗方法的基本思想虽然早已被人们提出，却很少被使用。本世纪四十年代以来，由于电子计算机的出现，使得人们可以通过电子计算机来模拟随机试验过程，把巨大数目的随机试验交由计算机完成，使得蒙特卡罗方法得以广泛地应用，在现代化的科学技术中发挥应有的作用。MC方法随机理论的基础MC方法的随机理论基础g(u)均匀分布MC方法随机理论的基础•大数法则该定理指出，如果随机变量序列X1，X2，…，XN独立同分布，且具有有限非零的方差σ2，即f(X)是X的分布密度函数。则dtexXEXNPxxtNN2/221)(limdxxfXEx)())((022MC方法随机理论的基础中心极限定理平均值当N充分大时，有如下的近似式其中α称为置信度，1－α称为置信水平。这表明，不等式近似地以概率1－α成立，且误差收敛速度的阶为。通常，蒙特卡罗方法的误差ε定义为上式中与置信度α是一一对应的，根据问题的要求确定出置信水平后，查标准正态分布表，就可以确定出。122)(02/2dteNXEXPtNNXEXN)()(2/1NON下面给出几个常用的α与的数值：关于蒙特卡罗方法的误差需说明两点：第一，蒙特卡罗方法的误差为概率误差，这与其他数值计算方法是有区别的。第二，误差中的均方差σ是未知的，必须使用其估计值来代替，在计算所求量的同时，可计算出。α0.50.050.0030.67451.9632112)1(1ˆNiiNiiXNXNˆMC方法随机理论的基础•中心极限定理告诉我们，蒙特卡洛方法的误差与随机数的均方差和抽样模拟次数n有关。•为了减小误差，就应当选取最优的随机变量，使其方差最小。•在方差固定时，增加模拟次数可以有效地减小误差。如试验次数增加100倍，精度提高10倍。当然这样做就增加了计算的机时，提高了费用。•所以在考虑蒙特卡洛方法的精确度时，不能只是简单地减少方差和增加模拟次数，还要同时兼顾计算费用，即机时耗费。通常以方差和费用的乘积作为衡量方法优劣的标准。•误差控制蒙特卡罗方法的特点优点能够比较逼真地描述具有随机性质的事物的特点及物理实验过程。受几何条件限制小。收敛速度与问题的维数无关。具有同时计算多个方案与多个未知量的能力。误差容易确定。程序结构简单，易于实现。缺点收敛速度慢。误差具有概率性。在粒子输运问题中，计算结果与系统大小有关。1)能够比较逼真地描述具有随机性质的事物的特点及物理实验过程从这个意义上讲，蒙特卡罗方法可以部分代替物理实验，甚至可以得到物理实验难以得到的结果。用蒙特卡罗方法解决实际问题，可以直接从实际问题本身出发，而不从方程或数学表达式出发。它有直观、形象的特点。如：求连续掷两颗骰子，点数之和大于6且第一次掷出的点数大于第二次掷出点数的概率。2)受几何条件限制小在计算s维空间中的任一区域Ds上的积分时，无论区域Ds的形状多么特殊，只要能给出描述Ds的几何特征的条件，就可以从Ds中均匀产生N个点，得到积分的近似值。其中Ds为区域Ds的体积。这是数值方法难以作到的。另外，在具有随机性质的问题中，如考虑的系统形状很复杂，难以用一般数值方法求解，而使用蒙特卡罗方法，不会有原则上的困难。ssDdxdxdxxxxggs2121),,,(),,,()()(2)(1isiixxxNiisiisNxxxgNDg1)()(2)(1),,,(3)收敛速度与问题的维数无关a.由误差定义可知，在给定置信水平情况下，蒙特卡罗方法的收敛速度为，与问题本身的维数无关。b.使用蒙特卡罗方法时，抽取的子样总数N与维数s无关。维数的增加，除了增加相应的计算量外，不影响问题的误差。这决定了蒙特卡罗方法对多维问题的适应性。c.而一般数值方法，比如计算定积分时，计算时间随维数的幂次方而增加，而且需占用相当数量的计算机内存，这些都是一般数值方法计算高维积分时难以克服的问题。)(2/1NO4)具有同时计算多个方案与多个未知量的能力a.同时计算多种方案。对于那些需要计算多个方案的问题，使用蒙特卡罗方法有时不需要像常规方法那样逐个计算，而可以同时计算所有的方案，其全部计算量几乎与计算一个方案的计算量相当。b.例如，对于均匀介质的平板，要计算若干种厚度的打靶穿透概率时，只需计算最厚的一种情况，其他厚度的穿透概率在计算最厚一种情况时稍加处理便可同时得到。5)误差容易确定对于一般计算方法，要给出计算结果与真值的误差并不是一件容易的事情，而蒙特卡罗方法则不然。根据蒙特卡罗方法的误差公式，可以在计算所求量的同时计算出误差。对于很复杂的蒙特卡罗方法计算问题，也是容易确定的。6)程序结构简单，易于实现在计算机上进行蒙特卡罗方法计算时，程序结构简单，分块性强，易于实现。1)收敛速度慢如前所述，蒙特卡罗方法的收敛速度为一般不容易得到精确度较高的近似结果。对于维数少（三维以下）的问题，不如其他方法好。)(2/1NO2)误差具有概率性由于蒙特卡罗方法的误差是在一定置信水平下估计的，所以它的误差具有概率性，而不是一般意义下的误差。随机数的产生•由于MC是在计算机上的随机模拟试验。因此，如何产生随机数，如何进行给定分布的随机数抽样，是直接和间接MC方法的关键。•随机数包含：真随机数列,伪随机数列真随机数•真随机数数列是不可预计的，因而也不可能重复产生两个相同的真随机数数列。•真随机数只能用某些随机物理过程来产生。例如：放射性衰变、电子设备的热噪音、宇宙射线的触发时间等等。•如果采用随机物理过程来产生蒙特卡洛计算用的随机数，理论上不存在什么问题。但在实际应用时，要做出速度很快（例如每秒产生上百个浮点数），而又准确的随机数物理过程产生器是非常困难的。伪随机数•实际应用的随机数通常都是通过某些数学公式计算而产生的伪随机数。•这样的伪随机数从数学意义上讲已经一点不是随机的了。•只要伪随机数能够通过随机数的一系列的统计检验（证明其均匀性和独立性），我们就可以把它当作真随机数而放心地使用。这样我们就可以很经济地、重复地产生出随机数。•产生均匀伪随机数的方法有平均取中法、乘同余法。,2,1),,,,(11nTknnnkn平均取中法•该方法首先给出一个2r位的数，取它的中间的r位数码作为第一个伪随机数；然后将第一个伪随机数平方构成一个新的2r位数，再取中间的r位数作为第二个伪随机数…。如此循环便得到一个伪随机数序列。类似上述方法，利用十进制公式表示2r位数的递推公式。•例如，取2r=4,并取x0=6406,则x02=41036836,[x02/10r]=410368,而x0=410368(mod104),则x1=0368乘同余法•乘同余方法是由Lehmer在1951年提出来的，它的一般形式是：对于任一初始值x1，伪随机数序列由下面递推公式确定：•其中x1，a，M为正整数。•得到的伪随机数均匀性好，重复周期长，编程指令少等优点，被广泛采用。)(mod1Mxaxii,2,1,11iMxii已知分布的随机抽样•指的是由己知分布的总体中抽取简单子样。•伪随机数是由单位均匀分布的总体中抽取的简单子样，属于一种特殊的由已知分布的随机抽样问题。•如已知某变量x满足正态分布（高斯分布），要求抽样变量序列x1,x2,x3,…xN,使之满足给定的分布。直接抽样法•当随机变量的分布函数已知或可以通过分布密度函数积分得到，且比较简单。这时可采用直接随机抽样法•如试按以下分布密度函数，对随机变量进行抽样。elsexexfx000)(•求得分布函数为xxxxedxedxxfxF1)()(•设为[0,1]区间上均匀分布的随机数,令解得:直接抽样法)(xF)1ln(1x•注意到和同样服从[0,1]的均匀分布，故有应为分布函数在[0,1]均匀分布)1()ln(1x•直接随机抽样使用简单，但如果分布函数F(x)不能解析求出或太复杂，不易求其反函数，则不易采用该方法。直接抽样法•自变量x在区间[a,b]均匀分布，如何对其随机抽样？•其概率密度函数为：其他0],[1)(baxabxf•于是它的分布函数为：abaxdxxfxPx)()(•则最常用的在区间[a,b]上的均匀抽样是]1,0[,)(abax离散性随机变量的直接抽样•对于任意离散型分布：•其中x1，x2，…为离散型分布函数的跳跃点，P1，P2，…为相应的概率，根据前述直接抽样法，有离散型分布的直接抽样方法如下：•该结果表明，为了实现由任意离散型分布的随机抽样，直接抽样方法是非常理想的。xxiiPxF)()()(,1111IIIFxFxFxX即当＝－＝IiiIiiPP变换抽样法变换抽样法的应用正态分布的抽样变换抽样法的应用正态分布的抽样通过u，v的均匀分布样本，按上式给出符合正态分布的x，y两组随机样本x,y是正态分布吗？？变换抽样法的应用正态分布得证！！！Metropolis抽样法产生任何复杂分布密度函数f(x)的抽样的一般方法：Metropolis抽样法如何选择初始位置x0总结•MC方法计算机随机试验某一随机事件出