Home
|
Course Outline
|
Lectures
|
Homework
|
Files
Lecture 7: January 31
Monte Carlo Quadrature and Error Analysis
Monte Carlo quadrature works by computing the average value of the
integrand at a randomly chosen set of points in the integration
region. Unlike the trapezoid rule which is inherently one-dimensional,
this random sampling of points works just the same in any number of
dimensions - one just generates a random number for each of the
d rectangular coordinates of each point. More significantly,
the global error turns out to be independent of d!
In any dimension, the error is of order 1/n0.5 where
n is the number of sampling points. Thus Monte Carlo wins over
trapezoid when d > 4.
The following are important concepts from Chapter 11:
- The basic Monte Carlo formula is the sample mean given in
Eq. (11.9) on page 351.
- The Monte Carlo error estimate is given in Eq. (11.17b). This
result is derived in Appendix 11B on page 370. It applies to most types
of Monte Carlo algorithms, so you should carefully review its derivation.
The Monte Carlo error estimate formula shows that there are essentially
two ways to improve the accuracy of a Monte Carlo quadrature:
- Increase the number n of sampling points. Unfortunately
the error decreases only as the square root of n.
- Reduce the variance of the integrand. This second strategy is
critical in performing efficient Monte Carlo simulations.
The remainder of the chapter discusses various variance-reduction
strategies such as a change of integration variables, importance
sampling, and the Metropolis Monte Carlo Method.
Questions or comments:
phygons@acsu.buffalo.edu