Page - 164 - in Programming for Computations – Python - A Gentle Introduction to Numerical Simulations with Python 3.6, Volume Second Edition

164 6 ComputingIntegralsandTestingCode be implemented in half a page of code, but requires orders of magnitude more functionevaluations indouble integralscomparedto themidpoint rule. Monte Carlo integration, however, is much more computationally efficient than the midpoint rule when computinghigher-dimensional integrals in more than three variables over hypercube domains. Our ideas for double and triple integrals can easily be generalized to handlean integral inmvariables.A midpoint formula then involvesmsums.Withncells ineachcoordinatedirection, the formularequiresnm function evaluations. That is, the computational work explodes as an exponential function of the number of space dimensions. Monte Carlo integration, on the other hand, does not suffer from this explosion of computational work and is the preferred method for computing higher-dimensional integrals. So, it makes sense in a chapter on numerical integration to address Monte Carlo methods, both for handlingcomplexdomainsand forhandling integralswith manyvariables. The Monte Carlo Integration Algorithm The idea of Monte Carlo integration of ∫b a f(x)dx is to use the mean-value theorem from calculus, which states that the integral ∫b a f(x)dx equals the length of the integration domain, here b− a, times the average value off , f¯ , in [a,b]. The average value can be computed by samplingf at a set of random points inside the domain and take the mean of the function values. In higher dimensions, an integral is estimated as the area/volume of the domain times the average value, and again one can evaluate the integrand at a set of random points in the domain and compute the mean value of those evaluations. Letus introducesomequantities tohelpusmake thespecificationof the integra- tionalgorithmmoreprecise.Supposewe havesometwo-dimensional integral ∫ Ω f(x,y)dxdx, whereΩ is a two-dimensionaldomaindefinedviaa help functiong(x,y): Ω={(x,y)|g(x,y)≥0} That is, points (x,y) for which g(x,y) ≥ 0 lie inside Ω, and points for which g(x,y) < Ω are outside Ω. The boundary of the domain ∂Ω is given by the implicit curve g(x,y) = 0. Such formulations of geometries have been very common during the last couple of decades, and one refers to g as a level- set function and the boundary g = 0 as the zero-level contour of the level-set function.For simple geometries one can easily constructg by hand, while in more complicated industrial applications one must resort to mathematical models for constructingg. LetA(Ω)be theareaofadomainΩ.Wecanestimate the integralby thisMonte Carlo integrationmethod: 1. embed thegeometryΩ in a rectangularareaR 2. drawa largenumberof randompoints (x,y) inR