Introduction to Numerical Methods/Integration

Resources:

• notes on Trapezoidal Rule
• notes on Simpson’s 1/3 Rule
• notes on Romberg Rule
• notes on integrating discrete functions

The fundamental theorem of calculus states that differentiation and integration are inverse operations: when a continuous function is first integrated and then differentiated or vice versa, the original function will be obtained. However the integrand $f(x)$ may be known only at certain points, such as data measured from an experiment or from sampling, which is common in computer applications. Sometimes even though the formula for an integrand is known, it is difficult or impossible to find the antiderivative in an elementary function form, e.g the antiderivative of $f(x)=exp(-x^{2})$, cannot be written in elementary form. Computing a numerical integration (approximation) can be easier than solving the integral symbolically.

http://mathworld.wolfram.com/NumericalIntegration.html

Trapezoidal Rule

The trapezoidal rule approximates the area under the curve of the function $f(x)$ as a trapezoid:

$\int _{a}^{b}f(x)\,dx\approx (b-a)\left[{\frac {f(a)+f(b)}{2}}\right].$

Effectively we are estimating the average function value using two samples.

The trapezoidal rule belongs to a class of formulas called Newton–Cotes formulas (evaluating the integrand at equally spaced points). Another way to look at it is that trapezoidal rule approximates the integrand by a first order polynomial and then integrating the polynomial over interval of integration as illustrated in the figure.

The function f(x) (in blue) is approximated by a linear function (in red).

The multiple segment Trapezoidal Rule can be used to improve the accuracy of the approximation by using a sequence of samples:

Illustration of trapezoidal rule used on a sequence of samples (in this case, a non-uniform grid).

Lets look at an example that approximate the area of a swimming pool.

Simpson's 1/3 Rule

Simpson's rule is a numerical integration method that uses the following approximation formula:

$\int _{a}^{b}f(x)\,dx\approx {\tfrac {b-a}{6}}\left[f(a)+4f\left({\tfrac {a+b}{2}}\right)+f(b)\right].$

The Simpson's rule can be derived by approximating the integrand as a second order polynomial (quadratic) function as shown in the figure:

Simpson's rule can be derived by approximating the integrand f (x) (in blue) by the quadratic interpolant P(x) (in red).

$P(x)=f(a){\tfrac {(x-m)(x-b)}{(a-m)(a-b)}}+f(m){\tfrac {(x-a)(x-b)}{(m-a)(m-b)}}+f(b){\tfrac {(x-a)(x-x2-x3....-m)}{(b-a)(b-m)}}.$

Another way to look at it is that Simpson’s rule is an extension of Trapezoidal rule where the integrand is approximated by a second order polynomial.

A sample implementation of Simpson's rule is available.

Romberg's Rule

The true errors result from the trapezoidal rule is negatively proportional to the number of segments cubed. Richardson extrapolation is a sequence acceleration method for getting a better estimate by refining such errors. A practical application of Richardson extrapolation is Romberg integration.

A geometric example is available.

http://www.oscer.ou.edu/AreaUnderCurveExample.pdf

Integration of Discrete Functions

The trapezoidal rule with unequal segments can be used to integrate discrete functions, which are defined by a set of data points. Interpolation methods, such as polynomial interpolation and spline interpolation, can be applied to find the function profile, which can be integrated as a continuous function. In addition linear regression can also be used for the same purpose.

Multi-dimensional Integration

Monte Carlo method is class of computational methods that uses repeated random sampling to obtain numerical results. To estimate multi-dimensional integrals Monte Carlo method may yield greater accuracy for the same number of function evaluations than repeated integrations using one-dimensional methods.

For example we can estimate the value of $\pi$ as shown in the example.

Monte Carlo method applied to approximating the value of Template:Pi. After placing 30000 random points, the estimate for Template:Pi is within 0.07% of the actual value. This happens with an approximate probability of 20%.

The path tracing algorithm in computer graphics applies the Monte Carlo method to render 3D scenes. It uses repeated random sampling to achieve more accurate estimation making it one of the most physically accurate 3D graphics rendering methods in existence source.