Numerical integration consists of finding numerical approximations for the value S
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 the numerical solution of differential equations. This article focuses on calculation of definite integrals. The term numerical quadrature (often abbreviated to quadrature) is more or less a synonym for numerical integration, especially as applied to onedimensional integrals. Some authors refer to numerical integration over more than one dimension as cubature;^{[1]} others take quadrature to include higherdimensional integration.
The basic problem in numerical integration is to compute an approximate solution to a definite integral

\int_a^b\! f(x)\, dx
to a given degree of accuracy. If f(x) is a smooth function integrated over a small number of dimensions, and the domain of integration is bounded, there are many methods for approximating the integral to the desired precision.
Contents

History 1

Reasons for numerical integration 2

Methods for onedimensional integrals 3

Quadrature rules based on interpolating functions 3.1

Adaptive algorithms 3.2

Extrapolation methods 3.3

Conservative (a priori) error estimation 3.4

Integrals over infinite intervals 3.5

Multidimensional integrals 4

Monte Carlo 4.1

Sparse grids 4.2

Bayesian Quadrature 4.3

Connection with differential equations 5

See also 6

References 7

External links 8

Free software for numerical integration 8.1
History
Quadrature is a historical mathematical term that means calculating area. Quadrature problems have served as one of the main sources of mathematical analysis. Mathematicians of Ancient Greece, according to the Pythagorean doctrine, understood calculation of area as the process of constructing geometrically a square having the same area (squaring). That is why the process was named quadrature. For example, a quadrature of the circle, Lune of Hippocrates, The Quadrature of the Parabola. This construction must be performed only by means of compass and straightedge.
For a quadrature of a rectangle with the sides a and b it is necessary to construct a square with the side x =\sqrt {ab} (the Geometric mean of a and b). For this purpose it is possible to use the following fact: if we draw the circle with the sum of a and b as the diameter, then the height BH (from a point of their connection to crossing with a circle) equals their geometric mean. The similar geometrical construction solves a problem of a quadrature for a parallelogram and a triangle.
The area of a segment of a parabola
Problems of quadrature for curvilinear figures are much more difficult. The quadrature of the circle with compass and straightedge had been proved in the 19th century to be impossible. Nevertheless, for some figures (for example Lune of Hippocrates) a quadrature can be performed. The quadratures of a sphere surface and a parabola segment done by Archimedes became the highest achievement of the antique analysis.

The area of the surface of a sphere is equal to quadruple the area of a great circle of this sphere.

The area of a segment of the parabola cut from it by a straight line is 4/3 the area of the triangle inscribed in this segment.
For the proof of the results Archimedes used the Method of exhaustion of Eudoxus.
In medieval Europe the quadrature meant calculation of area by any method. More often the Method of indivisibles was used; it was less rigorous, but more simple and powerful. With its help Galileo Galilei and Gilles de Roberval found the area of a cycloid arch, Grégoire de SaintVincent investigated the area under a hyperbola (Opus Geometricum, 1647), and Alphonse Antonio de Sarasa, de SaintVincent's pupil and commentator noted the relation of this area to logarithms.
John Wallis algebrised this method: he wrote in his Arithmetica Infinitorum (1656) series that we now call the definite integral, and he calculated their values. Isaac Barrow and James Gregory made further progress: quadratures for some algebraic curves and spirals. Christiaan Huygens successfully performed a quadrature of some Solids of revolution.
The quadrature of the hyperbola by SaintVincent and de Sarasa provided a new function, the natural logarithm, of critical importance.
With the invention of integral calculus came a universal method for area calculation. In response, the term quadrature has become traditional, and instead the modern phrase "computation of a univariate definite integral" is more common.
Reasons for numerical integration
There are several reasons for carrying out numerical integration.

The integrand f(x) may be known only at certain points, such as obtained by sampling. Some embedded systems and other computer applications may need numerical integration for this reason.

A formula for the integrand may be known, but it may be difficult or impossible to find an antiderivative that is an elementary function. An example of such an integrand is f(x) = exp(−x^{}2), the antiderivative of which (the error function, times a constant) cannot be written in elementary form.

It may be possible to find an antiderivative symbolically, but it may be easier to compute a numerical approximation than to compute the antiderivative. That may be the case if the antiderivative is given as an infinite series or product, or if its evaluation requires a special function that is not available.
Methods for onedimensional integrals
Numerical integration methods can generally be described as combining evaluations of the integrand to get an approximation to the integral. The integrand is evaluated at a finite set of points called integration points and a weighted sum of these values is used to approximate the integral. The integration points and weights depend on the specific method used and the accuracy required from the approximation.
An important part of the analysis of any numerical integration method is to study the behavior of the approximation error as a function of the number of integrand evaluations. A method that yields a small error for a small number of evaluations is usually considered superior. Reducing the number of evaluations of the integrand reduces the number of arithmetic operations involved, and therefore reduces the total roundoff error. Also, each evaluation takes time, and the integrand may be arbitrarily complicated.
A 'brute force' kind of numerical integration can be done, if the integrand is reasonably wellbehaved (i.e. piecewise continuous and of bounded variation), by evaluating the integrand with very small increments.
Quadrature rules based on interpolating functions
A large class of quadrature rules can be derived by constructing interpolating functions that are easy to integrate. Typically these interpolating functions are polynomials. In practice, since polynomials of very high degree tend to oscillate wildly, only polynomials of low degree are used, typically linear and quadratic.
Illustration of the rectangle rule.
The simplest method of this type is to let the interpolating function be a constant function (a polynomial of degree zero) that passes through the point ((a+b)/2, f((a+b)/2)). This is called the midpoint rule or rectangle rule.

\int_a^b f(x)\,dx \approx (ba) \, f\left(\frac{a+b}{2}\right).
Illustration of the trapezoidal rule.
The interpolating function may be a straight line (an affine function, i.e. a polynomial of degree 1) passing through the points (a, f(a)) and (b, f(b)). This is called the trapezoidal rule.

\int_a^b f(x)\,dx \approx (ba) \, \frac{f(a) + f(b)}{2}.
Illustration of Simpson's rule.
For either one of these rules, we can make a more accurate approximation by breaking up the interval [a, b] into some number n of subintervals, computing an approximation for each subinterval, then adding up all the results. This is called a composite rule, extended rule, or iterated rule. For example, the composite trapezoidal rule can be stated as

\int_a^b f(x)\,dx \approx \frac{ba}{n} \left( {f(a) \over 2} + \sum_{k=1}^{n1} \left( f \left( a+k \frac{ba}{n} \right) \right) + {f(b) \over 2} \right)
where the subintervals have the form [k h, (k+1) h], with h = (b−a)/n and k = 0, 1, 2, ..., n−1.
Interpolation with polynomials evaluated at equally spaced points in [a, b] yields the Newton–Cotes formulas, of which the rectangle rule and the trapezoidal rule are examples. Simpson's rule, which is based on a polynomial of order 2, is also a Newton–Cotes formula.
Quadrature rules with equally spaced points have the very convenient property of nesting. The corresponding rule with each interval subdivided includes all the current points, so those integrand values can be reused.
If we allow the intervals between interpolation points to vary, we find another group of quadrature formulas, such as the Gaussian quadrature formulas. A Gaussian quadrature rule is typically more accurate than a Newton–Cotes rule, which requires the same number of function evaluations, if the integrand is smooth (i.e., if it is sufficiently differentiable). Other quadrature methods with varying intervals include Clenshaw–Curtis quadrature (also called Fejér quadrature) methods, which do nest.
Gaussian quadrature rules do not nest, but the related Gauss–Kronrod quadrature formulas do.
Adaptive algorithms
If f(x) does not have many derivatives at all points, or if the derivatives become large, then Gaussian quadrature is often insufficient. In this case, an algorithm similar to the following will perform better:
def calculate_definite_integral_of_f(f, initial_step_size):
'''
This algorithm calculates the definite integral of a function
from 0 to 1, adaptively, by choosing smaller steps near
problematic points.
'''
x = 0.0
h = initial_step_size
accumulator = 0.0
while x < 1.0:
if x + h > 1.0:
h = 1.0  x
quad_this_step =
if error_too_big_in_quadrature_of_over_range(f, [x,x+h]):
h = make_h_smaller(h)
else:
accumulator += quadrature_of_f_over_range(f, [x,x+h])
x += h
if error_too_small_in_quadrature_of_over_range(f, [x,x+h]):
h = make_h_larger(h) # Avoid wasting time on tiny steps.
return accumulator
Some details of the algorithm require careful thought. For many cases, estimating the error from quadrature over an interval for a function f(x) isn't obvious. One popular solution is to use two different rules of quadrature, and use their difference as an estimate of the error from quadrature. The other problem is deciding what "too large" or "very small" signify. A local criterion for "too large" is that the quadrature error should not be larger than t · h where t, a real number, is the tolerance we wish to set for global error. Then again, if h is already tiny, it may not be worthwhile to make it even smaller even if the quadrature error is apparently large. A global criterion is that the sum of errors on all the intervals should be less than t. This type of error analysis is usually called "a posteriori" since we compute the error after having computed the approximation.
Heuristics for adaptive quadrature are discussed by Forsythe et al. (Section 5.4).
The accuracy of a quadrature rule of the NewtonCotes type is generally a function of the number of evaluation points. The result is usually more accurate as the number of evaluation points increases, or, equivalently, as the width of the step size between the points decreases. It is natural to ask what the result would be if the step size were allowed to approach zero. This can be answered by extrapolating the result from two or more nonzero step sizes, using series acceleration methods such as Richardson extrapolation. The extrapolation function may be a polynomial or rational function. Extrapolation methods are described in more detail by Stoer and Bulirsch (Section 3.4) and are implemented in many of the routines in the QUADPACK library.
Conservative (a priori) error estimation
Let f have a bounded first derivative over [a,b]. The mean value theorem for f, where x < b, gives

(x  a) f'(v_x) = f(x)  f(a)\,
for some v_{x} in [a,x] depending on x. If we integrate in x from a to b on both sides and take the absolute values, we obtain

\left \int_a^b f(x)\,dx  (b  a) f(a) \right = \left \int_a^b (x  a) f'(v_x)\, dx \right
We can further approximate the integral on the righthand 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) \right \leq {(b  a)^2 \over 2} \sup_{a \leq x \leq b} \left f'(x) \right (**)
(See supremum.) Hence, if we approximate the integral ∫_{a}^{b} f(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) \right
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.
Integrals over infinite intervals
Several methods exist for approximate integration over unbounded intervals. The standard technique involves specially derived quadrature rules, such as GaussHermite quadrature for integrals on the whole real line and GaussLaguerre quadrature for integrals on the positive reals.^{[2]} Monte Carlo methods can also be used, or a change of variables to a finite interval; e.g., for the whole line one could use

\int_{\infty}^{+\infty} f(x) \, dx = \int_{1}^{+1} f\left( \frac{t}{1t^2} \right) \frac{1+t^2}{(1t^2)^2} \, dt,
and for semiinfinite intervals one could use

\int_a^{+\infty}f(x) \, dx =\int_0^1 f\left(a + \frac{t}{1t}\right) \frac{dt}{(1t)^2}

\int_{\infty}^a f(x) \, dx = \int_0^1 f\left(a  \frac{1t}{t}\right) \frac{dt}{t^2}
as possible transformations.
Multidimensional integrals
The quadrature rules discussed so far are all designed to compute onedimensional integrals. To compute integrals in multiple dimensions, one approach is to phrase the multiple integral as repeated onedimensional 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 socalled curse of dimensionality.
Monte Carlo
Monte Carlo methods and quasiMonte Carlo methods are easy to apply to multidimensional integrals, and may yield greater accuracy for the same number of function evaluations than repeated integrations using onedimensional methods.
A large class of useful Monte Carlo methods are the socalled Markov chain Monte Carlo algorithms, which include the MetropolisHastings algorithm and Gibbs sampling.
Sparse grids
Sparse grids were originally developed by Smolyak for the quadrature of highdimensional functions. The method is always based on a onedimensional quadrature rule, but performs a more sophisticated combination of univariate results.
Bayesian Quadrature
Bayesian Quadrature is a statistical approach to the numerical problem of computing integrals and falls under the field of probabilistic numerics. It can provide a full handling of the uncertainty over the solution of the integral expressed as a Gaussian Process posterior variance. It is also known to provide very fast convergence rates which can be up to exponential in the number of quadrature points n.^{[3]}
Connection with differential equations
The problem of evaluating the integral

F(x) = \int_a^x f(u)\, du
can be reduced to an initial value problem for an ordinary differential equation. By differentiating both sides of the above with respect to the argument x, it is seen that the function F satisfies

\frac{d F(x)}{d x} = f(x), \quad F(a) = 0.
Methods developed for ordinary differential equations, such as Runge–Kutta methods, can be applied to the restated problem and thus be used to evaluate the integral. For instance, the standard fourthorder Runge–Kutta method applied to the differential equation yields Simpson's rule from above.
The differential equation F ' (x) = ƒ(x) has a special form: the righthand side contains only the dependent variable (here x) and not the independent variable (here F). This simplifies the theory and algorithms considerably. The problem of evaluating integrals is thus best studied in its own right.
See also
References

^ Weisstein, Eric W., "Cubature", MathWorld.

^

^ Briol, FrançoisXavier; Oates, Chris J.; Girolami, Mark; Osborne, Michael A. (20150608). "FrankWolfe Bayesian Quadrature: Probabilistic Integration with Theoretical Guarantees". arXiv:1506.02681 [stat].

Philip J. Davis and Philip Rabinowitz, Methods of Numerical Integration.

Cleve B. Moler, Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: PrenticeHall, 1977. (See Chapter 5.)


Josef Stoer and Roland Bulirsch, Introduction to Numerical Analysis. New York: SpringerVerlag, 1980. (See Chapter 3.)

Boyer, C. B., A History of Mathematics, 2nd ed. rev. by Uta C. Merzbach, New York: Wiley, 1989 ISBN 0471097632 (1991 pbk ed. ISBN 0471543977).

Eves, Howard, An Introduction to the History of Mathematics, Saunders, 1990, ISBN 0030295580,
External links

Integration: Background, Simulations, etc. at Holistic Numerical Methods Institute
Free 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 free and open source software packages here:

QUADPACK (part of SLATEC): description [3], source code [4]. QUADPACK is a collection of algorithms, in Fortran, for numerical integration based on Gaussian quadrature.

interalg: a solver from OpenOpt/FuncDesigner frameworks, based on interval analysis, guaranteed precision, license: BSD (free for any purposes)

GSL: The GNU Scientific Library (GSL) is a numerical library written in C that provides a wide range of mathematical routines, like Monte Carlo integration.

Numerical integration algorithms are found in GAMS class H2.

ALGLIB is a collection of algorithms, in C# / C++ / Delphi / Visual Basic / etc., for numerical integration (includes BulirschStoer and RungeKutta integrators).

Cuba is a freesoftware library of several multidimensional integration algorithms.

Cubature code for adaptive multidimensional integration.

Scilab is an open source software under CeCILL license (GPL compatible), providing powerful features including numerical integration.
This article was sourced from Creative Commons AttributionShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, EGovernment Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a nonprofit organization.