第九章 Monte carlo积分
第九章 Monte Carlo积分
第九章 Monte carl积分 Monte carlo法的重要应用领之一:计算积分和多重积分 适用于求解: 1.被积函数、积分边界复杂,难以用解析方法或一般的数 值方法求解; 2.被积函数的具体形式未知,只知道由模拟返回的函数值 本章内容: 用 Monte carlo法求定积分的几种方法: 均匀投点法、期望值估计法、重要抽样法、半解析 法
第九章 Monte Carlo积分 Monte Carlo法的重要应用领域之一：计算积分和多重积分 适用于求解： 1. 被积函数、积分边界复杂，难以用解析方法或一般的数 值方法求解； 2. 被积函数的具体形式未知，只知道由模拟返回的函数值。 本章内容： 用Monte Carlo法求定积分的几种方法： 均匀投点法、期望值估计法、重要抽样法、半解析 法、…
第九章 Monte carlot积分 Goal: Evaluate an integral g(×)dx Why use random methods? Computation by deterministic quadrature can become expensive and inaccurate grid points add up quickly in high dimensions .o bad choices of grid may misrepresent g(x)
第九章 Monte Carlo积分 Goal: Evaluate an integral: = b a I g(x) dx Why use random methods? Computation by “deterministic quadrature” can become expensive and inaccurate. ❖ grid points add up quickly in high dimensions ❖ bad choices of grid may misrepresent g(x)
第九章 Monte carlo积分 a Monte Carlo method can be used to compute integral of any dimension d( d-fold integrals ERror comparison of d-fold integrals o Simpsons rule, approximating the integral of a function f using quadratic polynomials E∝N-1d∫(xhk=(x)=(x)+4/()+/( x1-x0 XI h o Monte Carlo method E∝N2 purely statistica, not rely on the dimension o Monte carlo method WINs. when d>>3
第九章 Monte Carlo积分 ❑ Monte Carlo method can be used to compute integral of any dimension d (d-fold integrals) ❑Error comparison of d-fold integrals Simpson’s rule,… d E N −1/ 2 1 − E N purely statistical, not rely on the dimension ! Monte Carlo method WINS, when d >> 3 Monte Carlo method approximating the integral of a function f using quadratic polynomials [ ( ) 4 ( ) ( )] 3 1 ( ) ( ) 0 1 2 0 0 0 f x dx f x dx h f x f x f x x h x x x = + + + x1 − x0 = x2 − x1 = h
第九章 Monte car积分 ☆Hit-or- Miss Method ☆ Sample Mean Method Variance Reduction Technique & Variance Reduction using Rejection Technique % Importance Sampling Method
第九章 Monte Carlo积分 ❖Hit-or-Miss Method ❖Sample Mean Method ❖Variance Reduction Technique ❖Variance Reduction using Rejection Technique ❖Importance Sampling Method
Hit-or-Miss Method Evaluation of a definite integral Lp(rb h h≥p(x) for anyx × Probability that a random point reside inside the area b M (6-ah N o N: Total number of points ≈(b-ahM·M: points that reside inside the region
Hit-or-Miss Method •Evaluation of a definite integral I x dx b a = ( ) h (x) for any x a b h X X X X X X O O O O O O •Probability that a random point O reside inside the area N M b a h I p − = ( ) N M I (b − a)h N : Total number of points M : points that reside inside the region
Hit-or-Miss Method Sample uniformly from the rectangular region la, b]x[o, hI The probability that we are below the curve is p h( -a So, if we can estimate p, we can estimate I I=ph(b-a) where p is our estimate of p
Hit-or-Miss Method Sample uniformly from the rectangular region [a,b]x[0,h] h(b - a) I p:= The probability that we are below the curve is So, if we can estimate p, we can estimate I: I p ˆh(b - a) ˆ = where is our estimate of p p ˆ
Hit-or-Miss Method We can easily estimate p ☆ throw n" uniform darts” at the rectangle %o let m be the number of times you end up under the curve y=g(x) M ☆let p N
Hit-or-Miss Method We can easily estimate p: ❖ throw N “uniform darts” at the rectangle N M ❖ let p ˆ = ❖ let M be the number of times you end up under the curve y=g(x)
Hit-or-Miss Method Start Set N: large integer M=0 Loop Choose a point x in a, b x=(b-a)1+a n times Choosea point y in [o h] y=hu2 if [x,y] reside inside then M=M+l /=(b-a)h(MN End
Hit-or-Miss Method a b h X X X X X X O O O O O O O Start Set N : large integer M = 0 Choose a point x in [a,b] Choose a point y in [0,h] if [x,y] reside inside then M = M+1 I = (b-a) h (M/N) End Loop N times x = (b−a)u1 + a hu2 y =
Hit-or-Miss Method rError Analysis of the Hit-or-Miss Method o It is important to know how accurate the result of simulations are o note that M is binomial(M, p) E(M=Np O(M=Np( E(D=E[ph(b-a]Em h(b-a0(=0h(b-al=o/M h(b-a) h(b-wE(=h(b-ap=l h2(b-a)2 h2(b-a)2p(1-p 2(M)= N o(=h(b-a (1-p h(b-a) M N
Hit-or-Miss Method Error Analysis of the Hit-or-Miss Method It is important to know how accurate the result of simulations are note that M is binomial(M,p) ( ) ( ) (1 ) 2 E M = Np M = Np − P E M h b a p I N h b a h b a N M E I E ph b a E = − = − = = − = − ( ) ( ) ( ) ) ˆ ( ) ( ) ˆ ( N h b a p p M N h b a h b a N M I ph b a ( ) (1 ) ( ) ( ) ) ˆ ( ) ( ) ˆ ( 2 2 2 2 2 2 2 2 2 − − = − = = − = − N M p p ˆ = (1 ) ( ) ) ˆ ( N M M N h b a I − − = 2 (1 ) 1 ) ( ) ˆ ( − − = − N N p p I h b a