第四章MonteCarlo积分PPT课件

1、Monte Carlo法的重要应用领域之一：计算积分和多重积分法的重要应用领域之一：计算积分和多重积分适用于求解：适用于求解：1. 被积函数、积分边界复杂，难以用解析方法或一般的数被积函数、积分边界复杂，难以用解析方法或一般的数值方法求解；值方法求解；2. 被积函数的具体形式未知，只知道由模拟返回的函数值。被积函数的具体形式未知，只知道由模拟返回的函数值。本章内容：本章内容：用用Monte Carlo法求定积分的几种方法：法求定积分的几种方法： 均匀投点法、期望值估计法、重要抽样法、半解析均匀投点法、期望值估计法、重要抽样法、半解析法、法、目的：计算一个定积分（一维或多维）目的：计算一个定积分

2、（一维或多维）dVg(x) dx I q数值方法：数值方法：将积分区间分成将积分区间分成n个子区间，用一些近似的方法计算各个个子区间，用一些近似的方法计算各个子区间的积分值，然后对子区间的积分值，然后对n个子区间的积分值求和个子区间的积分值求和 梯形法梯形法(trapezoidal rule)：对每个子区间用梯形近似：对每个子区间用梯形近似 Simpsons rule：approximating the integral of a function g using quadratic polynomials)()(4)(31)()(210000 xgxgxghdxxgdxxghxxxxhxxx

3、x1201q数值方法存在的问题数值方法存在的问题: :计算速度慢、精度低：计算速度慢、精度低：v 需计算的函数值的数目随着积分维数急剧增长需计算的函数值的数目随着积分维数急剧增长v不恰当的子区间划分将导致不能很好地近似表示被积不恰当的子区间划分将导致不能很好地近似表示被积函数函数g(x)g(x)导致计算误差导致计算误差积分维数积分维数d=10, 各方向分点数目各方向分点数目n=50, 需计算函需计算函数值的数目：数值的数目：nd = 5010qMonte Carlo方法可用于计算任何的方法可用于计算任何的d重积分重积分q两种方法计算两种方法计算 d-重积分的误差比较重积分的误差比较Simpso

4、ns rule, dNE/121 NEpurely statistical, not rely on the dimension !Monte Carlo method WINS, when d 3Monte Carlo method 1.Hit-or-Miss Method2.Sample Mean Method3.Variance Reduction: Importance Sampling Method4.Correlation methods for variance reduction Evaluation of a definite integraldxxgIba)(xxghxg

5、anyfor )(, 0)(abhXXXXXXOOOOOOOProbability that a random point reside inside the areaNMhabIp)(NMhabI)( N : Total number of points M : points that reside inside the regionSample uniformly from the rectangular regiona,bx0,ha)-h(bI p The probability that we are below the curve isSo, if we can estimate p

6、, we can estimate I:a)-h(bpIwhere is our estimate of pp We can easily estimate p:v throw N “uniform darts” at the rectangleNMp v letv let M be the number of times you end up under the curve y=g(x)abhXXXXXXOOOOOOOStartSet N : large integer M = 0 Choose a point x in a,bChoose a point y in 0,hif x,y re

7、side inside then M = M+1I = (b-a) h (M/N)EndLoopN timesauabx1)(2huy Error Analysis of the Hit-or-Miss MethodIt is important to know how accurate the result of simulations are note that M is binomial(M,p)1 ()()(2PNpMNpMEIpabhMENabhabhNMEabhpEIE)()()()()()(NppabhMNabhabhNMabhpI)1 ()()()()()()(22222222

8、2NMpp )1 ()()(NMMNabhI21)1 ()()(NNppabhI推广到多重积分：推广到多重积分：,)(, 0)(,),()(212121211122baxxghxgbbbbaaaadxdxdxxxxgxdxgIddbaddbababaddd,21区间区间,ba内均匀分布的随机数内均匀分布的随机数 =hr : 区间区间0,h内均匀分布的随机数内均匀分布的随机数选取选取n组组,，若其中满足，若其中满足g( ) 的共有的共有m组组niidibaIabhnmxdxgI)()(1积分结果的置信水平：积分结果的置信水平：对于任意给定的正数对于任意给定的正数 ，怎样才能保证积分计算值，怎样才

9、能保证积分计算值In与真与真值值I之差的绝对值之差的绝对值 小于小于 的概率大于的概率大于 (0 - g(X1), g(X2), , g(Xn) iidv Let Yi=g(Xi) for i=1,2,nThenY a)-(b I and we can once again invoke the CLT.)N(I, I2IFor n “large enough” (n30),So, a confidence interval for I is roughly given byI/2 z Ibut since we dont know , well have to be content with

10、 the further approximation:II/2s z Iba2x1/2dx e x: IBy the wayNo one ever said that you have to use the uniform distributionExample:0ba,2x1/2dx (x)I 2e x21(X)I XE21ba,1/2where Xexp(rate=2).v1.2 Hit-or-Miss Methodv1.3 Sample Mean Methodv2.1 Variance Reduction Techniquev2.3 Variance Reduction using Re

11、jection Techniquev2.4 Importance Sampling MethodVariance Reduction TechniqueVariance Reduction for Hit-or-Miss methodIn the domain a,b choose a comparison functiondxxwAdxxwxWxxwbax)()()()()(r)(xwAu )(1AuWxabw(x)XXXXXOOOOOOOr(x)Points are generated on the area under w(x) functionRandom variable that

12、follows distribution w(x)Variance Reduction TechniquePoints lying above r(x) is rejectedNNAInnnuxwy)()( if 0)( if 1nnnnnxyxyqrrq10P(q)r1-rAIr/abw(x)XXXXXOOOOOOOr(x)Variance Reduction TechniqueError Analysis)1 ()( ,)(rrQVrQE)(QAEArINIAIIRJerror)(67. 0Hit or Miss method Error reductionhabA)( 0Error then IAVariance Reduction TechniqueStartSet N :