第四章MonteCarlo積分PPT課件

1、Monte Carlo法的重要應(yīng)用領(lǐng)域之一：計算積分和多重積分法的重要應(yīng)用領(lǐng)域之一：計算積分和多重積分適用于求解：適用于求解：1. 被積函數(shù)、積分邊界復(fù)雜，難以用解析方法或一般的數(shù)被積函數(shù)、積分邊界復(fù)雜，難以用解析方法或一般的數(shù)值方法求解；值方法求解；2. 被積函數(shù)的具體形式未知，只知道由模擬返回的函數(shù)值。被積函數(shù)的具體形式未知，只知道由模擬返回的函數(shù)值。本章內(nèi)容：本章內(nèi)容：用用Monte Carlo法求定積分的幾種方法：法求定積分的幾種方法： 均勻投點法、期望值估計法、重要抽樣法、半解析均勻投點法、期望值估計法、重要抽樣法、半解析法、法、目的：計算一個定積分（一維或多維）目的：計算一個定積分

2、（一維或多維）dVg(x) dx I q數(shù)值方法：數(shù)值方法：將積分區(qū)間分成將積分區(qū)間分成n個子區(qū)間，用一些近似的方法計算各個個子區(qū)間，用一些近似的方法計算各個子區(qū)間的積分值，然后對子區(qū)間的積分值，然后對n個子區(qū)間的積分值求和個子區(qū)間的積分值求和 梯形法梯形法(trapezoidal rule)：對每個子區(qū)間用梯形近似：對每個子區(qū)間用梯形近似 Simpsons rule：approximating the integral of a function g using quadratic polynomials)()(4)(31)()(210000 xgxgxghdxxgdxxghxxxxhxxx

3、x1201q數(shù)值方法存在的問題數(shù)值方法存在的問題: :計算速度慢、精度低：計算速度慢、精度低：v 需計算的函數(shù)值的數(shù)目隨著積分維數(shù)急劇增長需計算的函數(shù)值的數(shù)目隨著積分維數(shù)急劇增長v不恰當?shù)淖訁^(qū)間劃分將導(dǎo)致不能很好地近似表示被積不恰當?shù)淖訁^(qū)間劃分將導(dǎo)致不能很好地近似表示被積函數(shù)函數(shù)g(x)g(x)導(dǎo)致計算誤差導(dǎo)致計算誤差積分維數(shù)積分維數(shù)d=10, 各方向分點數(shù)目各方向分點數(shù)目n=50, 需計算函需計算函數(shù)值的數(shù)目：數(shù)值的數(shù)目：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區(qū)間區(qū)間,ba內(nèi)均勻分布的隨機數(shù)內(nèi)均勻分布的隨機數(shù) =hr : 區(qū)間區(qū)間0,h內(nèi)均勻分布的隨機數(shù)內(nèi)均勻分布的隨機數(shù)選取選取n組組,，若其中滿足，若其中滿足g( ) 的共有的共有m組組niidibaIabhnmxdxgI)()(1積分結(jié)果的置信水平：積分結(jié)果的置信水平：對于任意給定的正數(shù)對于任意給定的正數(shù) ，怎樣才能保證積分計算值，怎樣才

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 “l(fā)arge 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 :