Numerical integration
The ancient Babylonians used the trapezoidal rule to integrate the motion of Jupiter along the ecliptic.
The similar geometrical construction solves a problem of a quadrature for a parallelogram and a triangle.
The quadratures of a sphere surface and a parabola segment done by Archimedes became the highest achievement of the antique analysis.
In medieval Europe the quadrature meant calculation of area by any method.
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.
The quadrature of the hyperbola by Saint-Vincent 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.
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 large class of quadrature rules can be derived by constructing interpolating functions that are easy to integrate.
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 re-used.
The accuracy of a quadrature rule of the Newton–Cotes type is generally a function of the number of evaluation points.
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.
We can further approximate the integral on the right-hand side by bringing the absolute value into the integrand, and replacing the term in
We can convert this into an error analysis for the Riemann sum, giving an upper bound of
This integration method can be combined with interval arithmetic to produce computer proofs and verified calculations.
[4] 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
The quadrature rules discussed so far are all designed to compute one-dimensional integrals.
This approach requires the function evaluations to grow exponentially as the number of dimensions increases.
A great many additional techniques for forming multidimensional cubature integration rules for a variety of weighting functions are given in the monograph by Stroud.
They may yield greater accuracy for the same number of function evaluations than repeated integrations using one-dimensional methods.
[citation needed] 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.
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.
It can provide a full handling of the uncertainty over the solution of the integral expressed as a Gaussian process posterior variance.
By differentiating both sides of the above with respect to the argument x, it is seen that the function F satisfies Numerical methods 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 fourth-order Runge–Kutta method applied to the differential equation yields Simpson's rule from above.
