《MonteCarlo方法》由会员分享，可在线阅读，更多相关《MonteCarlo方法（48页珍藏版）》请在金锄头文库上搜索。
1、Monte Carlo 方法 黄世萍 起源 这一方法源于美国在第二次世界大战进研制原子弹的曼哈顿计划。Monte Carlo方法创始人主要是这四位：Stanislaw Marcin Ulam, Enrico Fermi, John von Neumann和 Nicholas Metropolis。 Monte Carlo 方法基础 Monte Carlo（MC）方法是在简单的理论准则基础上（如简单 的物质与物质以及物质与环境相互作用） ， 采用反复随机抽样 的手段 ， 解决复杂系统的问题 。 该方法采用随机抽样的手法 ，可以模拟对象的概率与统计的问题。通过设计适当的概率模 型 ， 该方法还可以
2、解决确定性问题 ， 如定积分等。 随着计算 机的迅速发展 ， MC 方法已在应用物理、原子能、固体物理 、 化学、材料、生物、生态学、社会学以及经济学等领域得到了 广泛的应用。 MC meothds classical Monte Carlo: samples are drawn from a probability distribution, often the classical Boltzmann distribution, to obtain thermodynamic properties or minimum-energy structures; quantum Monte Car
3、lo: random walks are used to compute quantum-mechanical energies and wavefunctions, often to solve electronic structure problems, using Schrdingers equation as a formal starting point; volumetric Monte Carlo: random number generators are used to generate volumes per atom or to perform other types of
4、 geometrical analysis; kinetic Monte Carlo: simulate processes using scaling arguments to establish timescales or by introducing stochastic effects into molecular dynamics. Monte Carlo方法的基本思想 Monte Carlo 方法的基本思想是: 为了求解某个问题 ， 建立一个恰 当的概率模型或随机过程 ， 使得其参量（如事件的概率、随机变 量的数学期望等）等于所求问题的解 ， 然后对模型或过程进行反 复多次的随机抽
5、样试验 ， 并对结果进行统计分析 ， 最后计算所求 参量 ， 得到问题的近似解。 Monte Carlo 方法是随机模拟方法 ； 它不仅限于模拟随机性问题 ， 还可 以解决确定性的数学问题。 对随机性问题 ， 可以根据实际问题的概率法 则 ， 直接进行随机抽样试验 ， 即直接模拟方法。 对于确定性问题采用 间接模拟方法 ， 即通过统计分析随机抽样的结果获得确定性问题的解。 用 Monte Carlo 方法解决确定性的问题主要是在数学领域 ， 如计算重积 分、求逆矩阵、解线性代数方程组、解积分方程、解偏微分方程边界问题 和计算微分算子的特征值等。 用 Monte Carlo 方法解决随机性问题则
6、在 众多的科学及应用技术领域得到广泛的应用 ， 如中子在介质中的扩散问 题、库存问题、随机服务系统中的排队问题、动物的生态竞争、传染病的 蔓延等。 简单的例子 对积分进行变换 ， 构造新的被积函数 g（x） ， 使得该函数满足下列条件 ： g（x）是连续随机变量 的概率密度函数。 定积分是概率积分 ， 其积分值等于概率 Pr （a b） ， 即 这个步骤就是将一个积分转化为一个概率模型的过程 ； 然后 ， 反复多次的 随机抽样试验 ，以抽样结果的统计平均作为索求概率的近似值 ， 从而求得 该积分。 具体试验步骤如下 ： （1） 产生服从给定分布函数 g（x）的随机变量值 xi （2）检查 xi
7、是否落入积分区域（a x b） ， 如果满足条件 ， 则记录一次。 反复进行上述试验。 假设在 N 次试验后 ， xi落入积分区域的总次数为 m ， 那么 ， 积分值近似表示为 对于随机性问题 ， 可直接将实际的随机问题抽象为概率数学模型 ， 然后 与求解确定性问题一样进行抽样试验和统计计算。 Monte Carlo 方法解决实际问题的过程中 ， 主要有以下几个内容 建立简单而又便于实现的概率统计模型 ， 使所求的解正是该模型的某 一事件的概率或数学期望 ， 或该模型能够直接描述实际的随机过程。 根据概率统计模型的特点和计算的需求 ， 改进模型 ， 以便减小方差和 减低费用 ， 提高计算效率。
8、 建立随机变量的抽样方法 ， 包括伪随机数和服从特定分布的随机变量 的产生方法。 给出统计估计值及其方差或标准误差。 One-Dimensional Integrals nMethodical approaches rectangle rule, trapezoid rule, Simpsons rule nQuadrature formula n uniformly separated points Sum areas of shapes approximating shape of curve Evaluating the general integral 假设对于下列积分 首先，按照均匀
9、分布，随即采样区域a,b，记采样点为Xi，每个采样点的 值p(x)=1/(b-a)。利用Monte Carlo算法，上述积分可以模拟为： 当N趋近于无穷大的时候，我们认为两者的值是一致的，所以可以利用上 述离散的方式模拟这个积分 Monte Carlo Integration nStochastic approach nSame quadrature formula, different selection of points n points selected from uniform distribution p(x) p(x) 我们在对于a,b进行采样的时候，完全没有必要进行均匀采样，这
10、样 做只是简单而已，我们可以根据一种概率分布来进行采样，从而使得 某些区域的采样密度更大。加入采样点的概率分布函数为P(x)，那么 我们可以利用如下公式计算定积分的值： 证明： 3 Monte Carlo方法的收敛性和基本特点 设所求的量 x是随机变量的数学期望 E（x） ， 那么 ， Monte Carlo 方法通常使用随机变量的简单子样， ， ，N 的算术平均值 ， 即 作为所求量 x 的近似值。 由柯尔莫哥罗夫（Kolmogorov）大数定理可知 ， 即当 N 充分大时 ， 有 成立的概率等于 ， 亦即可以用 N 作为所求量 x 的估计值。 根据中心极限定理 ， 如果随机变量 的标准差
11、不为零 ， 那么 Monte Carlo 方法的误差为 式中 ， 为正态差 ， 是与置信水平有关的常量。 Monte Carlo 方法 的收敛速度的阶为 o（N -1/2） ， 误差是由随机变量的标准差 s和抽样次 数 N 决定的。 提高精度一位数 ， 抽样次数要增加 倍 ； 减小随机变量的标准 差 ， 可以减小误差 。 Monte Carlo 方法具有以下四个重要特征 ： 由于 Monte Carlo 方法是通过大量简单的重复抽样来实现的 ， 因 此 ， 方法和程序的结构十分简单 。 收敛速度比较慢 ， 因此 ， 较适用于求解精度要求不高的问题。 收敛速度与问题的维数无关 ， 因此 ， 较适
12、用于求解多维问题。 问题的求解过程取决于所构造的概率模型 ， 而受问题条件限制的 影响较小 ， 因此 ， 对各种问题的适应性很强。 随机数的产生 1 随机数与伪随机数 Monte Carlo 方法的核心是随机抽样。 在该过程中往往需要各种各样分 布的随机变量其中最简单、最基本的是在 ，区间上均匀分布的 随机变量。 在该随机变量总体中抽取的子样 ， ， ，N 称为随 机数序列 ， 其中每个个体称为随机数。 用数学的方法产生随机数是目前广泛使用的方法。 该方法的基本思想 是利用一种递推公式 ： 对于给定的初始值 ， 逐个地产生 ， ， 数学方法产生的随机数存在两个问题 ： 整个随机数序列是完全由递
13、推函数形式和初始值唯一确定的 ， 严格 地说不满足随机数的相互独立的要求。 存在周期现象。 基于这两个原因 ， 将用数学方法所产生的随机数称为伪随机数。 伪 随机数的优点是适用于计算机 ， 产生速度快 ， 费用低廉。 目前 ， 多数计算机均附带有“随机数发生器” 。 选择递推函数必须注意以下几点 ： 随机性好 ； 在计算机上容易实现 ； 省时 ； 伪随机数的周期长。 2 伪随机数的产生方法 最基本的伪随机数是均匀分布的伪随机数。 该方法是首先给一个 r位的数 ， 取其中间的 r位数码作为第一个伪随机数 ， 然后将这个数平方 ， 构成一个新的 r位的数 ， 再取中间的 r位数作为第 二个伪随机数
14、。 如此循环可得到一个伪随机数序列。 该方法的递推公式为 x表示对 x 取整 ， 运算 B（Mod M）表示 B被 M 整除后的余数。 数列i 是分布在 ，上的。 该方法由于效率较低 ， 有时周期较短 ， 甚至会出现零 。 同余法 该方法也是由选定的初始值出发 ， 通过递推产生伪随机数序列。由于 该递推公式可写成数论中的同余式 ， 故称同余法。 该方法的递推公式 为 a ， c ， m分别称作倍数（multiplier） 、增值（Increment ）和模（ modulus） ， 均为正整数 。 x 称为种子或初值 ， 也为正整数。 该方法所产生伪随机数的质量 ， 如周期的长度、独立性和均匀性
15、 都与式中三个参数有关。 3 伪随机数的统计检验 伪随机数的特性好坏将直接影响到 Monte Carlo 的计算结果 ， 因此要对 所产生的伪随机数序列进行随机性检验。 随机性检验主要包括均匀性检 验 、独立性检验、组合规律性检验和无连贯性检验。 检验是伪随机数 检验最常用的方法。 1. 均匀性就是伪随机数列的 N 个数是否均匀分布在 ， 区间上。 若将 ，区间分成 k个相等的子区间（一般 k ， ， ） ， 若所得伪随机数在 ，区 间上是均匀分布的 ， 则虚假设H 应为“每个伪随机数属于第 i 组的概率为 2. 频率检验 检验每组观测频数 ni与理论频数mi N /k之间相差的显著性 3. 独立性 按先后顺序排列的 N 个伪随机数中 ， 每个数的出现是否与 其前后各个数独立无关。 对于两组伪随机数来说 ， 独立性 就是指它们不相关 。 4. 组合规律性 将 N 个伪随机数按一定的规律组合起来 ， 则各种组合的出现具 有一定的概率。 5. 无连贯性 将一次出现的 N 个伪随机数 ， 按其大小分为两类或 k类 ， 则各 类数的出现是否没有连贯现象。 确定性问题的 Monte Carlo 方法求解 Monte Carlo 方法所能解决的问题可以分为两大类 确定性问题 随机性问题 确定性问题主要包括： 求解线性和非线性方程组、逆矩阵、椭圆
