# 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

\_\_TOC\_\_

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). (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). (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
. After placing 30000 random points, the estimate
for  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.

