Numerical integration

Uses your system voice; voice and rate in settings.

Snapshot

≈ 12 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral. The term numerical quadrature (often abbreviated to quadrature) is more or less a synonym for "numerical integration", especially as applied to one-dimensional integrals. Some authors refer to numerical integration over more than one dimension as cubature; others take "quadrature" to include higher-dimensional 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 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. Numerical integration has roots in the geometrical problem of finding a square with the same area as a given plane figure (quadrature or squaring), as in the quadrature of the circle. The term is also sometimes used to describe the numerical solution of differential equations.

In analysis, numerical integration comprises a broad family of algorithms for calculating the numerical value of a definite integral. The term numerical quadrature (often abbreviated to quadrature) is more or less a synonym for "numerical integration", especially as applied to one-dimensional integrals. Some authors refer to numerical integration over more than one dimension as cubature; others take "quadrature" to include higher-dimensional 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 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. Numerical integration has roots in the geometrical problem of finding a square with the same area as a given plane figure (quadrature or squaring), as in the quadrature of the circle. The term is also sometimes used to describe the numerical solution of differential equations. 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. 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 the 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. To prove 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 Saint-Vincent investigated the area under a hyperbola (Opus Geometricum, 1647), and Alphonse Antonio de Sarasa, de Saint-Vincent'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 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.

Methods for one-dimensional integrals

A quadrature rule is an approximation of the definite integral of a function, usually stated as a weighted sum of function values at specified points within the domain of integration. 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 error. Also, each evaluation takes time, and the integrand may be arbitrarily complicated.

Quadrature rules based on step functions

A "brute force" kind of numerical integration can be done by evaluating the integrand with very small increments using a Riemann sum. These methods are some of the most general, as they only require the integrand to be piecewise continuous and of bounded variation. This simplest method approximates the function by a step function (a piecewise constant function, or a segmented polynomial of degree zero) that passes through the point \left( \frac{a+b}{2}, f \left( \frac{a+b}{2} \right)\right) . This is called the midpoint rule or rectangle rule \int_a^b f(x)\, dx \approx (b-a) f\left(\frac{a+b}{2}\right).

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. The interpolating function may be a straight line (an affine function, i.e. a polynomial of degree 1) passing through the points \left( a, f(a)\right) and \left( b, f(b)\right) . This is called the trapezoidal rule \int_a^b f(x)\, dx \approx (b-a) \left(\frac{f(a) + f(b)}{2}\right). 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{b-a}{n} \left( {f(a) \over 2} + \sum_{k=1}^{n-1} \left( f \left( a + k \frac{b-a}{n} \right) \right) + {f(b) \over 2} \right), where the subintervals have the form [a+k h,a+ (k+1)h] \subset [a,b], with h = \frac{b - a}{n} and k = 0,\ldots,n-1. Here we used subintervals of the same length h but one could also use intervals of varying length \left( h_k \right)_k . 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 re-used. 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 that uses 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. (x - a) f'(\xi_x) = f(x) - f(a), for some \xi_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'(\xi_x)\, dx \right| . 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 where the supremum was used to approximate. Hence, if we approximate the integral \int_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 \frac{n^{-1}}{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. \int_{-\infty}^{\infty} f(x) \, dx = \int_{-1}^{+1} f\left( \frac{t}{1-t^2} \right) \frac{1+t^2}{\left(1-t^2\right)^2} \, dt, and for semi-infinite intervals one could use \begin{align} \int_a^{\infty} f(x) \, dx &= \int_0^1 f\left(a + \frac{t}{1-t}\right) \frac{dt}{(1-t)^2}, \\ \int_{-\infty}^a f(x) \, dx &= \int_0^1 f\left(a - \frac{1-t}{t}\right) \frac{dt}{t^2}, \end{align} as possible transformations. Further reading . F(x) = \int_a^x f(u)\, du can be reduced to an initial value problem for an ordinary differential equation by applying the first part of the fundamental theorem of calculus. 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. 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. The differential equation F'(x) = f(x) has a special form: the right-hand side contains only the independent variable (here x ) and not the dependent variable (here F ). This simplifies the theory and algorithms considerably. The problem of evaluating integrals is thus best studied in its own right. Conversely, the term "quadrature" may also be used for the solution of differential equations: "solving by quadrature" or "reduction to quadrature" means expressing its solution in terms of integrals.

See also

Truncation error (numerical integration) Clenshaw–Curtis quadrature Gauss-Kronrod quadrature Riemann Sum or Riemann Integral Trapezoidal rule Romberg's method Tanh-sinh quadrature Nonelementary Integral

References

Philip J. Davis and Philip Rabinowitz, Methods of Numerical Integration. George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler, Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Chapter 5.) Josef Stoer and Roland Bulirsch, Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Chapter 3.) Boyer, C. B., A History of Mathematics, 2nd ed. rev. by Uta C. Merzbach, New York: Wiley, 1989 (1991 pbk ed. ). Eves, Howard, An Introduction to the History of Mathematics, Saunders, 1990, , S.L.Sobolev and V.L.Vaskevich: The Theory of Cubature Formulas, Kluwer Academic, ISBN 0-7923-4631-9 (1997).

External links

Integration: Background, Simulations, etc. at Holistic Numerical Methods Institute Lobatto Quadrature from Wolfram Mathworld Lobatto quadrature formula from Encyclopedia of Mathematics Implementations of many quadrature and cubature formulae within the free Tracker Component Library. SageMath Online Integrator

Text derived from https://en.wikipedia.org/w/index.php?oldid=1366420121 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.