Numerical integration

In numerical analysis, numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe numerical algorithms for solving differential equations.

left| int_a^b (x - a) f'(y_x), dx ight|

We can further approximate the integral on the right-hand side by bringing the absolute value into the integrand, and replacing the term in f' by an upper bound:

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: left| int_a^b f(x),dx - (b - a) f(a) ight| leq {(b - a)^2 over 2} sup_{a leq x leq b} left| f'(x) ight| (**)

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

(See supremum.) Hence, if we approximate the integral ∫abf(x)dx by the quadrature rule (b-a)f(a) our error is no greater than the right hand side of (**). We can convert this into an error analysis for the Riemann sum (*), giving an upper bound of

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

: {n^{-1} over 2} sup_{0 leq x leq 1} left| f'(x) ight|

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

for the error term of that particular approximation. (Note that this is precisely the error we calculated for the example f(x) = x.) Using more derivatives, and by tweaking the quadrature, we can do a similar error analysis using a Taylor series (using a partial sum with remainder term) for f. This error analysis gives a strict upper bound on the error, if the derivatives of f are available.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This integration method can be combined with interval arithmetic to produce computer proofs and verified calculations.

Related Topics:
Interval arithmetic - Computer proof

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Multidimensional integrals

The quadrature rules discussed so far are all designed to compute one-dimensional integrals.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

To compute integrals in multiple dimensions,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

one approach is to phrase the multiple integral as repeated one-dimensional integrals by appealing to Fubini's theorem.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

This approach requires the function evaluations to grow exponentially as the number of dimensions increases. Two methods are known to overcome this so-called curse of dimension.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Monte Carlo

Monte Carlo methods and quasi-Monte Carlo methods are easy to apply to multi-dimensional integrals,

Related Topics:
Monte Carlo method - Quasi-Monte Carlo method

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

and may yield greater accuracy for the same number of function evaluations than repeated integrations using one-dimensional methods.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A large class of useful Monte Carlo methods are the so-called Markov chain Monte Carlo algorithms,

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

which include the Metropolis-Hastings algorithm and Gibbs sampling.

Related Topics:
Metropolis-Hastings algorithm - Gibbs sampling

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Sparse grids

Sparse grids were originally developed by Smolyak for the quadrature of high dimensional functions. The method is always based on a one dimensional quadrature rule, but performs a more sophisticated combination of univariate results.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Software for numerical integration

Numerical integration is one of the most intensively studied problems in numerical analysis.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Of the many software implementations we list a few here.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

• QUADPACK (part of SLATEC): description http://www.netlib.org/slatec/src/qpdoc.f, source code http://www.netlib.org/slatec/src. QUADPACK is a collection of algorithms, in Fortran, for numerical integration based on Gaussian quadrature.
• GSL: The GNU Scientific Library (GSL) is a numerical library written in C which provides a wide range of mathematical routines, like Monte Carlo integration.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Numerical integration algorithms are found in GAMS class H2.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

References

• George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Chapter 5.)
• William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, 1988. (See Chapter 4.)
• Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Chapter 3.)