Monte-Carlo-方法

MonteCarlo方法黄世萍起源这一方法源于美国在第二次世界大战进研制原子弹的曼哈顿计划。MonteCarlo方法创始人主要是这四位：StanislawMarcinUlam,EnricoFermi,JohnvonNeumann和NicholasMetropolis。１MonteCarlo方法基础MonteCarlo（MC）方法是在简单的理论准则基础上（如简单的物质与物质以及物质与环境相互作用），采用反复随机抽样的手段，解决复杂系统的问题。该方法采用随机抽样的手法，可以模拟对象的概率与统计的问题。通过设计适当的概率模型，该方法还可以解决确定性问题，如定积分等。随着计算机的迅速发展，MC方法已在应用物理、原子能、固体物理、化学、材料、生物、生态学、社会学以及经济学等领域得到了广泛的应用。MCmeothdsclassicalMonteCarlo:samplesaredrawnfromaprobabilitydistribution,oftentheclassicalBoltzmanndistribution,toobtainthermodynamicpropertiesorminimum-energystructures;quantumMonteCarlo:randomwalksareusedtocomputequantum-mechanicalenergiesandwavefunctions,oftentosolveelectronicstructureproblems,usingSchrödinger’sequationasaformalstartingpoint;volumetricMonteCarlo:randomnumbergeneratorsareusedtogeneratevolumesperatomortoperformothertypesofgeometricalanalysis;kineticMonteCarlo:simulateprocessesusingscalingargumentstoestablishtimescalesorbyintroducingstochasticeffectsintomoleculardynamics.MonteCarlo方法的基本思想MonteCarlo方法的基本思想是:为了求解某个问题，建立一个恰当的概率模型或随机过程，使得其参量（如事件的概率、随机变量的数学期望等）等于所求问题的解，然后对模型或过程进行反复多次的随机抽样试验，并对结果进行统计分析，最后计算所求参量，得到问题的近似解。MonteCarlo方法是随机模拟方法；它不仅限于模拟随机性问题，还可以解决确定性的数学问题。对随机性问题，可以根据实际问题的概率法则，直接进行随机抽样试验，即直接模拟方法。对于确定性问题采用间接模拟方法，即通过统计分析随机抽样的结果获得确定性问题的解。用MonteCarlo方法解决确定性的问题主要是在数学领域，如计算重积分、求逆矩阵、解线性代数方程组、解积分方程、解偏微分方程边界问题和计算微分算子的特征值等。用MonteCarlo方法解决随机性问题则在众多的科学及应用技术领域得到广泛的应用，如中子在介质中的扩散问题、库存问题、随机服务系统中的排队问题、动物的生态竞争、传染病的蔓延等。简单的例子对积分进行变换，构造新的被积函数g（x），使得该函数满足下列条件：g（x）是连续随机变量ξ的概率密度函数。定积分是概率积分，其积分值等于概率Pr（a≤ξ≤b），即这个步骤就是将一个积分转化为一个概率模型的过程；然后，反复多次的随机抽样试验，以抽样结果的统计平均作为索求概率的近似值，从而求得该积分。具体试验步骤如下：（1）产生服从给定分布函数g（x）的随机变量值xi（2）检查xi是否落入积分区域（a≤x≤b），如果满足条件，则记录一次。反复进行上述试验。假设在N次试验后，xi落入积分区域的总次数为m，那么，积分值近似表示为对于随机性问题，可直接将实际的随机问题抽象为概率数学模型，然后与求解确定性问题一样进行抽样试验和统计计算。MonteCarlo方法解决实际问题的过程中，主要有以下几个内容①建立简单而又便于实现的概率统计模型，使所求的解正是该模型的某一事件的概率或数学期望，或该模型能够直接描述实际的随机过程。②根据概率统计模型的特点和计算的需求，改进模型，以便减小方差和减低费用，提高计算效率。③建立随机变量的抽样方法，包括伪随机数和服从特定分布的随机变量的产生方法。④给出统计估计值及其方差或标准误差。One-DimensionalIntegralsMethodicalapproachesrectanglerule,trapezoidrule,Simpson’sruleQuadratureformulanuniformlyseparatedpointsSumareasofshapesapproximatingshapeofcurve()baIfxdxEvaluatingthegeneralintegral()fxx11()()nniiiibaIxfxfxn假设对于下列积分()baIfxdx首先，按照均匀分布，随即采样区域[a,b]，记采样点为Xi，每个采样点的值p(x)=1/(b-a)。利用MonteCarlo算法，上述积分可以模拟为：当N趋近于无穷大的时候，我们认为两者的值是一致的，所以可以利用上述离散的方式模拟这个积分MonteCarloIntegrationStochasticapproachSamequadratureformula,differentselectionofpoints1()niibaIfxnnpointsselectedfromuniformdistributionp(x)xp(x)我们在对于[a,b]进行采样的时候，完全没有必要进行均匀采样，这样做只是简单而已，我们可以根据一种概率分布来进行采样，从而使得某些区域的采样密度更大。加入采样点的概率分布函数为P(x)，那么我们可以利用如下公式计算定积分的值：证明：3MonteCarlo方法的收敛性和基本特点设所求的量x是随机变量ξ的数学期望E（x），那么，MonteCarlo方法通常使用随机变量ξ的简单子样ξ１，ξ２，…，ξN的算术平均值，即作为所求量x的近似值。由柯尔莫哥罗夫（Kolmogorov）大数定理可知，即当N充分大时，有成立的概率等于１，亦即可以用ξN作为所求量x的估计值。根据中心极限定理，如果随机变量ξ的标准差σ不为零，那么MonteCarlo方法的误差ε为式中，λα为正态差，是与置信水平有关的常量。MonteCarlo方法的收敛速度的阶为o（N-1/2），误差是由随机变量的标准差s和抽样次数N决定的。提高精度一位数，抽样次数要增加１００倍；减小随机变量的标准差，可以减小误差。MonteCarlo方法具有以下四个重要特征：①由于MonteCarlo方法是通过大量简单的重复抽样来实现的，因此，方法和程序的结构十分简单。②收敛速度比较慢，因此，较适用于求解精度要求不高的问题。③收敛速度与问题的维数无关，因此，较适用于求解多维问题。④问题的求解过程取决于所构造的概率模型，而受问题条件限制的影响较小，因此，对各种问题的适应性很强。随机数的产生1随机数与伪随机数MonteCarlo方法的核心是随机抽样。在该过程中往往需要各种各样分布的随机变量其中最简单、最基本的是在［０，１］区间上均匀分布的随机变量。在该随机变量总体中抽取的子样ξ１，ξ２，…，ξN称为随机数序列，其中每个个体称为随机数。用数学的方法产生随机数是目前广泛使用的方法。该方法的基本思想是利用一种递推公式：对于给定的初始值ξ１，逐个地产生ξ２，ξ３，…数学方法产生的随机数存在两个问题：①整个随机数序列是完全由递推函数形式和初始值唯一确定的，严格地说不满足随机数的相互独立的要求。②存在周期现象。基于这两个原因，将用数学方法所产生的随机数称为伪随机数。伪随机数的优点是适用于计算机，产生速度快，费用低廉。目前，多数计算机均附带有“随机数发生器”。选择递推函数必须注意以下几点：①随机性好；②在计算机上容易实现；③省时；④伪随机数的周期长。2伪随机数的产生方法最基本的伪随机数是均匀分布的伪随机数。该方法是首先给一个２r位的数，取其中间的r位数码作为第一个伪随机数，然后将这个数平方，构成一个新的２r位的数，再取中间的r位数作为第二个伪随机数。如此循环可得到一个伪随机数序列。该方法的递推公式为［x］表示对x取整，运算B（ModM）表示B被M整除后的余数。数列｛ξi｝是分布在［０，１］上的。该方法由于效率较低，有时周期较短，甚至会出现零。同余法该方法也是由选定的初始值出发，通过递推产生伪随机数序列。由于该递推公式可写成数论中的同余式，故称同余法。该方法的递推公式为a，c，m分别称作倍数（multiplier）、增值（Increment）和模（modulus），均为正整数。x０称为种子或初值，也为正整数。该方法所产生伪随机数的质量，如周期的长度、独立性和均匀性都与式中三个参数有关。3伪随机数的统计检验伪随机数的特性好坏将直接影响到MonteCarlo的计算结果，因此要对所产生的伪随机数序列进行随机性检验。随机性检验主要包括均匀性检验、独立性检验、组合规律性检验和无连贯性检验。χ检验是伪随机数检验最常用的方法。1.均匀性就是伪随机数列的N个数是否均匀分布在［０，１］区间上。若将［０，１］区间分成k个相等的子区间（一般k＝８，１６，３２），若所得伪随机数在［０，１］区间上是均匀分布的，则虚假设H０应为“每个伪随机数属于第i组的概率为2.频率检验检验每组观测频数ni与理论频数mi＝N１/k之间相差的显著性3.独立性按先后顺序排列的N个伪随机数中，每个数的出现是否与其前后各个数独立无关。对于两组伪随机数来说，独立性就是指它们不相关。4.组合规律性将N个伪随机数按一定的规律组合起来，则各种组合的出现具有一定的概率。5.无连贯性将一次出现的N个伪随机数，按其大小分为两类或k类，则各类数的出现是否没有连贯现象。确定性问题的MonteCarlo方法求解MonteCarlo方法所能解决的问题可以分为两大类确定性问题随机性问题确定性问题主要包括：求解线性和非线性方程组、逆矩阵、椭圆型差分方程的边值、积分方程以及多重积分等。用MonteCarlo方法求解确定性问题的基本思想是：对于给定的确定性问题，设计一个概率统计模型（或随机过程模型），然后采用一定的抽样方法，按照所设计的概率统计模型进行抽样，最后把这个模型产生的一个数字特征作为该确定性问题的近似解。蒲丰试验１７７７年法国著名学者蒲丰（Buffon）就发表了采用随机抽样法计算圆周率的论文。这就是蒲丰随机投针试验，即著名的蒲丰问题。蒲丰概率模型是:在平面上画相距均为２a的平行线束，向该平面上随机投置一枚长为２l的针。为了避免针同时与两条平行线相交的复杂情况，设定０＜l＜a。如图所示，M为针的中点，y为针的中点M到与之最近的平行线的距离，φ为针与平行线的夹角。显然，０≤y≤a，０≤φ≤π。该随机试验所有可能的集为针与平行线相交的充分必要条件是y≤lsinφ，针与平行线相交事件的集为则针与平行线相交的概率为由于l和a均为已知常数，只要通过大量抽样试验求得该概率p，由上式即可算出圆周率。设投针总次数为N，其中针与平行线相交次数为v，由贝努里（Bernoulli）定理可知，当N充分大时，该事件出现的频率接近于其概率，即这就是蒲丰试验求圆周率的过程。虽然，该方法要想获得较高的精确度，需要数以百万次的抽样试验，效率很低，但蒲丰试验具有MonteCarlo方法解决确定性问题的基本思想。AClassicExample–TheCalculationof随机性问题的MonteCarlo模拟该过程是先建立一个随机过程模型，使得该过程的随机变量的数学期望等于所要求解确定问题的解。这种计算方法叫做间接模拟方法。另一方面，采用