Module

for

Monte Carlo Integration

Background

We will be discussing how to approximate the value of an integral based on the average of function values.  The following concept is useful.

Theorem  (Mean Value Theorem for Integrals).  If    is continuous over  ,  then there exists a number  ,  with  ,  such that

.

This can be written in the equivalent form:

.

Remark.  This computation shows that the area under the curve is the base width    times the "average height"  .

Example 1.  Let  .  Find    so that

.

Solution 1.

Composite Midpoint Rule

An intuitive method of finding the area under a curve    is to approximate that area with a series of rectangles that lie above the intervals  .

Theorem (Composite Midpoint Rule).  Consider    over .  Let the interval   be subdivided into    subintervals    of equal width  .  Form the equally spaced nodes    for  .  The composite midpoint rule for  n  subintervals is

.

This can be written in the equivalent form

,     where     .

Module  Midpoint Rule

Corollary (Remainder term for the Midpoint Rule)  The composite midpoint rule    is an numerical approximation to the integral, and

.

Furthermore, if ,  then there exists a value    with    so that the error term    has the form

.

This is expressed using the "big " notation  .

Module  Midpoint Rule

Animations  Midpoint Rule

Algorithm Composite Midpoint Rule.  To approximate the integral

,

by sampling    at the    equally spaced points    for  ,  where  .

Computer Programs  Midpoint Rule

Mathematica Subroutine (Midpoint Rule).

``````
``````

Example 2.  Let  .  Use the midpoint rule to calculate approximations to the integral  .
Solution 2.

Monte Carlo Method

Monte Carlo methods can be thought of as statistical simulation methods that utilize a sequences of random numbers to perform the simulation. The name "Monte Carlo'' was coined by Nicholas Constantine Metropolis (1915-1999) and inspired by Stanslaw Ulam (1909-1986), because of the similarity of statistical simulation to games of chance, and because Monte Carlo is a center for gambling and games of chance.

Approximation for an Integral

The Monte Carlo method can be used to numerically approximate the value of an integral.  For a function of one variable the steps are:

(i)    Pick n randomly distributed points   in the interval  .

(ii)    Determine the average value of the function

.

(iii)    Compute the approximation to the integral

.

(iv)    An estimate for the error is

,     where     .

Every time a Monte Carlo simulation is made using the same sample size it will come up with a slightly different value.  Larger values of    will produce more accurate approximations.  The values converge very slowly of the order  .  This property is a consequence of the Central Limit Theorem.

Computer Programs  Monte Carlo Integration

Mathematica Subroutine (Monte Carlo for 1 Dimensional Integrals).

The above subroutine is all we need to "do the math."  The following subroutine presents the results in a nice format.

``````
``````

Example 3.  Let  .  Use the Monte Carlo method to calculate approximations to the integral  .
Solution 3.

Example 4.  Let  .  Use the Monte Carlo method to calculate approximations to the integral  .
Solution 4.

Example 5.  Let  .  Use the Monte Carlo method to calculate approximations to the integral  .
Solution 5.

Approximation for a Double Integral

The Monte Carlo method can be used to numerically approximate the value of a double integral.  For a function of two variables the steps are:

(i)    Pick n randomly distributed points   in the rectangle  .

(ii)    Determine the average value of the function

.

(iii)    Compute the approximation to the integral

.

(iv)    An estimate for the error is

,     where     .

Mathematica Subroutine (Monte Carlo for 2 Dimensional Integrals).

The above subroutine is all we need to "do the math."  The following subroutine presents the results in a nice format.

``````
``````

Example 6.  Let  .  Use the Monte Carlo method to calculate approximations to the double integral

.

Solution 6.

Example 7.  Let  .  Use the Monte Carlo method to calculate approximations to the double integral

.

Solution 7.

Iterated Integrals in Higher Dimensions

Sometimes we are given integrals which cannot be done analytically, especially in higher dimensions where the standard  methods of discretization can become computationally expensive.  For example, the error in the composite midpoint rule (and the composite trapezoidal rule) of an d-dimensional integral has the order of convergence   .  We can apply the inequality

when

to see that  Monte-Carlo integration will usually converge faster for quintuple multiple integrals and higher, i.e. , etc.

Approximation for a Multiple Integral

The Monte Carlo method can be used to numerically approximate the value of a multiple integrals.  For a function of d variables the steps are:

(i)    Pick n randomly distributed points    in the "volume"   .

(ii)    Determine the average value of the function

.

(iii)    Compute the approximation to the integral

.

(iv)    An estimate for the error is

,     where     .

Mathematica Subroutine (Monte Carlo for 3 Dimensional Integrals).

``````
``````

Example 8.  Let  .  Use the Monte Carlo method to calculate approximations to the triple integral

.

Solution 8.

Mathematica Subroutine (Monte Carlo for 4 Dimensional Integrals).

``````
``````

Example 9.  Let  .  Use the Monte Carlo method to calculate approximations to the integral

.

Solution 9.

Mathematica Subroutine (Monte Carlo for 5 Dimensional Integrals).

``````
``````

Example 10.  Let  .  Use the Monte Carlo method to calculate approximations to the integral

.

Solution 10.

Example 11.  Let  .  Use the Monte Carlo method to calculate approximations to the integral

.

Solution 11.

Example 12.  Let  .  Use the Monte Carlo method to calculate approximations to the integral

.

Solution 12.

Example 13.  Let  .  Use the Monte Carlo method to calculate approximations to the integral

.

Solution 13.

Example 14.  Let  .  Use the Monte Carlo method to calculate approximations to the integral

.

Compare the Monte Carlo method with the midpoint rule.

Solution 14.

Monte Carlo Integration  Internet hyperlinks to web sites and a bibliography of articles.

(c) John H. Mathews 2005