10 - Numerical Integration and Monte Carlo Methods

Summary

Introduction

The juxtaposition of these two topics may appear strange to many readers. Upon further reflection, the common thread of spreading points in space may become apparent. My point in combining these topics is to emphasize that this thread is not weak. Monte Carlo should be viewed as just another way to compute an integral; numerical integration should be viewed as just another way to sample points in space. Great gains can be made by exploiting the strengths of one approach when the other is floundering. Only with the willingness to adjust one's viewpoint and use these tools in combination can the full array of techniques be brought to bear on a difficult problem.

Tools such as Riemann sums and Simpson's rule characterize the set of tools known as fixed quadrature or simply quadrature. A viewpoint of these methods as a discretization of the continuous problem of integration is indeed naive. The points are spread in a fixed way in space, with the number of points set in advance. Most of these methods employ a weighting scheme, so that the points (abscissas) where a function is to be evaluated have varying importance. For estimating an integral by evaluating a function at N points in one dimension, the error converges to zero at a rate of O(N⁻²) or better, depending on the smoothness of the function. In higher dimensions, however, this rate slows considerably. Assessing the accuracy of quadrature methods is extremely difficult, and most assessments are quite naive.