蒙特卡罗算法

蒙特卡罗算法蒙特卡罗法(MonteCarlomethod)是以概率和统计的理论、方法为基础的一种计算方法，将所求解的问题同肯定的概率模型相联系，用电子计算机实现统计模拟或抽样，以获得问题的近似解，故又称统计模拟法或统计试验法。蒙特卡罗是摩纳哥的一个城市,以赌博著名于世界。蒙特卡罗法借用这一城市的名称是为了象征性地表明该方法的概率统计的特点。蒙特卡罗法作为一种计算方法，是由S.M.乌拉姆和J.冯•诺伊曼在20世纪40年月中叶为研制核武器的需要而首先提出来的。在此之前，该方法的基本思想实际上早已被统计学家所采纳了。例如，早在17世纪，人们就知道了依频数来打算概率的方法。20世纪40年月中叶，消失了电子计算机，使得用数学方法模拟大量的试验成为可能。此外，随着科学技术的不断进展，消失了越来越多的简单而困难的问题，用通常的解析方法或数值方法都很难加以解决。蒙特卡罗法就是在这些状况下，作为一种可行的而且是不行缺少的计算方法被提出和快速进展起来的。基本原理考虑一个射击运动员的射击成果Go令x表示弹着点到靶心的距离，g(x)表示得分，而“X)表示该运动员的弹着点的分布密度,则O另一方面，假如该运动员进行了实弹射击，弹着点依次为XI,X2,…，XN,则平均得分为O很明显，骞N是G的一个近似估量。蒙特卡罗法正是用骞N作为G的近似估量。假设x不是一维空间的点，而是一个S维空间的点(xl,x2,xs),则上述积分变为O蒙特卡罗法计算此积分是用作为G的近似估量，式中(X为,X2n,…，Xsn)是由〃xl,x2,…，xs)中抽取的第n个样本点。同上述一维积分比较，相同点是，都以某随机变量的N个独立抽样值的算术平均作为近似估量；不同点仅仅是，打算随机量的样本点不同，一个是一维空间的点，另一个是S维空间的点。由上式可见，打算近似估量骞N好坏的仅仅是随机变量g(x)或g(xl,x2,…，xs)的分布状况，而与它们是由怎样的样本点对应过来的无关。换言之，假如随机变量g(x)和g(xl,x2,…，XS)具有相同分布，在不计抽样，不计计算g(x)和g(xl,x2,xs)的差别的状况下，S维状况与一维状况无任何差异。这是其他计算方法所不具有的、一个特别重要的性质。蒙特卡罗法解题的一般过程是，首先构成一个概率空间；然后在该概率空间中确定一个随机变量g(x),其数学期望正好等于所要求的值G,其中F(x)为x的分布函数；最终，以所确定的随机变量的简洁子样的算术平均值作为G的近似估量。由于其他缘由，如确定数学期望为G的随机变量g(x)有困难，或为其他目的，蒙特卡罗法有时也用G的渐近无偏估量代替一般过程中的无偏估量骞N来作为G的近似估量。收敛性、误差和费用蒙特卡罗法的近似估量骞N依概率1收敛于G的充分必要条件是随机变量g(x)满意O假如随机变量g(x)满意条件9式中1WM2,则9亦即骞N依概率1收敛于G的速度为。总之，蒙特卡罗法的收敛性取决于所确定的随机变量是否肯定可积，而蒙特卡罗法的收敛速度取决于该随机变量是几次肯定可积的。依据中心极限定理,只要随机变量g(x)具有有限的异于零的方差。2,当N足够大时便有蒙特卡罗法的误差公式如下：式中1-a为置信水平，x由置信水平所惟一确定。依据上述误差公式,为满意问题的误差和置信水平的要求，子样容量N必需大于(x/£)2。2,其中£表示误差。进一步假设每观看一个样本所需要的费用是C,则蒙特卡罗法的费用是。这一结果表明，在相同误差和置信水平要求下，一个蒙特卡罗法的优劣完全取决于02c的值的大小，它的值越小相应的方法越好，或者说，蒙特卡罗法的效率与02c成反比。提高效率的方法降低方差技巧降低方差是提高蒙特卡罗法效率的重要途径之一。考虑二重积分9式中/(X,y)为X和y的分布密度函数，g(x,y)的方差存在。蒙特卡罗法计算Eg的一般技巧是用g=g(x,y)作为所确定的随机变量，其中x和y听从分布〃x,y)o降低方差的详细方法有：统计估量技巧用“X)和/x(y)分别表示分布〃x,y)的边缘分布和条件分布。计算Eg的统计估量技巧是用y的统计估量量作为所确定的随机变量，其中X听从分布了(X)。g的方差恰好为两个方差的和，它们分别是对随机变量X和随机变量y采纳抽样方法而产生的。gSE的方差正好等于前者，因此gSE的方差肯定比g的方差小。统计估量技巧的一般原理是，对于问题中所消失的诸随机变量，能够确定其相应的统计估量量的，就不要再对它们采纳随机抽样的方法。重要抽样技巧引入任意分布密度函数/*(x,y),则的数学期望同样为Eg,其中x和y听从分布/*(x,y)。当/*(x,y)〜g(x,y)|/(x,y)时，gIS的方差达到最小。在g(x,y)NO时，方差等于零，gIS实际上变成了与其中消失的随机变量无关的常数。重要抽样技巧的一般原理是，尽量使所确定的随机变量与问题中所消失的随机变量关系不大。③相关抽样技巧考虑一个新的、积分值已知的二重积分9可得知的数学期望同样为Eg,式中x和y听从分布/(x,y),a为任意常数。当为随机变量g(x,y)和g*(x,y)的均方差og、入g*之比时，gCS的方差达到最小。此时的方差等于g的方差「P2倍，P为随机变量g(x,y)和g*(x,y)的相关系数。当P=1时，方差变为零。相关抽样技巧的一般原理是，查找一个数学期望已知的且与原确定的随机变量正相关的随机变量，使相应的相关系数尽量接近1,然后用这两个随机变量的线性组合作为蒙特卡罗法最终所确定的随机变量。降低方差的技巧还有对偶变数技巧、系统抽样技巧和分层抽样技巧等。对偶变数技巧的一般原理是，除了原确定的随机变量外，查找另一个(或多个)具有相同数学期望的随机变量，使得它们之间尽量是对偶负相关的,然后用它们的线性组合作为蒙特卡罗法最终所确定的随机变量。系统抽样技巧的一般原理是，对问题中所消失的某些随机变量按相应分布所确定的比例进行抽样，而不是进行随机抽样。分层抽样技巧的一般原理是，对问题中所消失的某些随机变量进行分层，尽量使所确定的随机变量在各层中相对平稳，各层间的抽样按相应分布所确定的比例进行。其他途径为了提高蒙特卡罗法的效率，除了简洁地降低方差外，还有为降低费用设计的分裂和轮盘赌技巧，为逐步降低方差而设计的多极抽样技巧，为改善收敛速度而设计的拟蒙特卡罗法，为计算条件期望而设计的条件蒙特卡罗法等等。分裂和轮盘赌技巧的一般原理是，将x的积分区域分为重要和非重要两部分，对于抽样确定的X,当它属于重要区域时，对相应的丫进行多次抽样；当它属于非重要区域时，只有在赌获胜时才对相应的丫进行抽样。多级抽样技巧的一般原理是，在进行某一级抽样计算的同时，依据它所供应的抽样观看值，设计更好的抽样技巧，用新设计的抽样技巧进行新的一级的抽样计算，依次类推，最终用各级的结果的线性组合作为蒙特卡罗法的近似估量。拟蒙特卡罗法与一般蒙特卡罗法的最大区分是，前者不像后者那样要求子样g(Xl),g(X2),…，g(Xn)是相互独立的。用全都分布点列替代由随机数组成的点列的所谓数论方法，实际上就是一种拟蒙特卡罗法。条件蒙特卡罗法的一般原理是，首先将条件期望问题转化成为非条件期望问题，然后用解非条件期望的一般方法来解决条件期望计算问题。由于条件蒙特卡罗法中引进了任意分布密度函数，因此，可以选取合适的分布密度函数来实现进一步降低方差的目的。优缺点蒙特卡罗法的最大优点是，在方差存在的状况下，问题的维数不影响它的收敛速度，而只影响它的方差；问题几何外形的简单性对它的影响不大；它不象其他数值方法那样对问题肯定要进行离散化处理，而是常可以进行连续处理；它的程序结构简洁，所需计算机存贮单元比其他数值方法少，这对于宣维问题差别尤其显著。蒙特卡罗法的最大缺点是，对于维数少的问题它不如其他数值方法好；它的误差是概率误差，而不是一般意义下的误差。应用随着电子计算机的快速进展和科学技术问题日趋简单，蒙特卡罗法的应用越来越广泛，已经渗透到科学技术的各个领域。在一些典型数学问题方面的应用主要有：多重积分计算、线性代数方程组求解、矩阵求逆、常微分方程边值问题求解、偏微分方程求解、非齐次线性积分方程求解、本征值计算和最优化计算等等。其中的多重积分计算、非齐次线性积分方程求解和齐次线性积分方程本征值计算等，不仅特别有代表性，而且有很大的有用价值，对于高维问题常比其他数值方法好。在一些实际问题