|
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 quadrature is more or less a synonym for numerical integration, especially as applied to one-dimensional integrals. Two- and higher-dimensional integration is sometimes described as cubature, although the meaning of quadrature is understood for higher dimensional integration as well. Image File history File links Download high resolution version (1200x900, 15 KB) R-source code: a=0. ...
Image File history File links Download high resolution version (1200x900, 15 KB) R-source code: a=0. ...
Numerical Integration with the Monte Carlo method: Nodes are random equally distributed. ...
This article describes multidimensional Monte Carlo integration. ...
Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics). ...
In calculus, the integral of a function is an extension of the concept of a sum. ...
Numerical ordinary differential equations is the part of numerical analysis which studies the numerical solution of ordinary differential equations (ODEs). ...
The basic problem considered by numerical integration is to compute an approximate solution to a definite integral:
 If f(x) is a smooth well-behaved function and the limits of integration are fixed, the method of Gaussian quadrature is very effective. In numerical analysis, 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. ...
Reasons for numerical integration
There are several reasons for carrying out numerical integration. The integrand f 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. Sampling is that part of statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern, especially for the purposes of statistical inference. ...
What is an Embedded System? Electronic devices that incorporate a computer(usually a microprocessor) within their implementation. ...
A formula for the integrand may be known, but it may be difficult or impossible to find an antiderivative. An example of such an integrand is exp(−t2). In calculus, an antiderivative, primitive or indefinite integral of a function f is a function F whose derivative is equal to f, i. ...
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 which is not available. In mathematics, several functions are important enough to deserve their own name. ...
Connection with differential equations The problem of evaluating the integral can be reduced to an initial value problem for an ordinary differential equation. If the above integral is denoted by I(b), then the function I satisfies In mathematics, an initial value problem is a statement of a differential equation together with specified value of the unknown function at a given point in the domain of the solution. ...
In mathematics, an ordinary differential equation (or ODE) is a relation that contains functions of only one independent variable, and one or more of its derivatives with respect to that variable. ...
 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. In numerical analysis, the Runge–Kutta methods are an important family of implicit and explicit iterative methods for the approximation of solutions of ordinary differential equations. ...
This differential equation has a special form: the right-hand side contains only the dependent variable (here x) and not the independent variable (here I). This suggest that specific methods can be developed for the evaluation of an integral, and that these methods can work better than general methods for the initial value problem for differential equations. This is indeed the case, and in the remainder of this article, we shall discuss these specific methods.
Methods for one-dimensional integrals Numerical integration methods can generally be described as combining evaluations of the integrand to get an approximation to the integral. 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 which 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 round-off error. Also, each evaluation takes time, and the integrand may be arbitrarily complicated. A round-off error, also called rounding error, is the difference between the calculated approximation of a number and its exact mathematical value. ...
A 'brute force' kind of numerical integration can be done, if the integrand is reasonably well behaved (i.e. continuous), 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 which are easy to integrate. Typically these interpolating functions are polynomials. In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ...
In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...
The simplest method of this type is to let the interpolating function be a constant function (a polynomial of order zero) which passes through the point ((a+b)/2, f((a+b)/2)). This is called the midpoint rule or rectangle rule. In mathematics, the rectangle method of integral calculus uses an approximation to a definite integral, made by finding the area of a series of rectangles. ...
 The interpolating function may be an affine function (a polynomial of degree 1) which passes through the points (a, f(a)) and (b, f(b)). This is called the trapezoidal rule. The word linear comes from the Latin word linearis, which means created by lines. ...
The function f(x) (in blue) is approximated by a linear function (in red). ...
 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  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. In numerical analysis, the Newton-Cotes formulas, also called the Newton-Cotes rules, are a group of formulas for numerical integration (also called quadrature) based on evaluating the integrand at n+1 equally-spaced points. ...
The function f(x) (in blue) is approximated by a quadratic function P(x) (in red). ...
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 has many derivatives.) Other quadrature methods with varying intervals include Clenshaw-Curtis quadrature and Fejér quadrature methods. In numerical analysis, 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. ...
This article assumes an understanding of algebra, analytic geometry, and the limit. ...
Clenshaw-Curtis quadrature and Fejér quadrature are methods for numerical integration, or quadrature, that are based on an expansion of the integrand in terms of Chebyshev polynomials. ...
Clenshaw-Curtis quadrature and Fejér quadrature are methods for numerical integration, or quadrature, that are based on an expansion of the integrand in terms of Chebyshev polynomials. ...
Adaptive algorithms If f 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: Adaptive quadrature is a process in which the integral of a function is approximated using static quadrature rules on adaptively refined subintervals of the integration domain. ...
// This algorithm calculates the definite integral of a function // from 0 to 1, adaptively, by choosing smaller steps near // problematic points. // Set initial_h to the initial step size. x:=0 h:=initial_h accumulator:=0 WHILE x<1.0 DO IF x+h>1.0 THEN h=1.0-x END IF IF error from quadrature over [x,x+h] for f is too large THEN Make h smaller ELSE accumulator:=accumulator + quadrature of f over [x,x+h] x:=x+h IF error from quadrature over [x,x+h] is very small THEN Make h larger END IF END IF END WHILE 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 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 possible criterion for "too large" is that the quadrature error should not be larger than th 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. 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).
Extrapolation methods The accuracy of a quadrature rule of the Newton-Cotes type is generally a function of the number of evaluation points. The result is usually more accurate as 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 (see 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). In numerical analysis, Richardson extrapolation is a method to improve an approximation that depends on a step size. ...
In mathematics, a polynomial is an expression in which constants and variables are combined using only addition, subtraction, multiplication, and positive whole number exponents (raising to a power). ...
In mathematics, a rational function in algebra is a function defined as a ratio of polynomials. ...
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 In calculus, the mean value theorem states, roughly, that given a section of a smooth curve, there is a point on that section at which the derivative (slope) of the curve is equal to the average derivative of the section. ...
 for some yx in [a,x] depending on x. If we integrate in x from a to b on both sides and the take absolute values, we obtain  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:  (**) (See supremum.) Hence, if we approximate the integral ∫abf(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 In mathematics, the supremum of an ordered set S is the least element that is greater than or equal to each element of S. Consequently, it is also referred to as the least upper bound (also lub and LUB). ...
 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. As the degree of the Taylor series rises, it approaches the correct function. ...
This integration method can be combined with interval arithmetic to produce computer proofs and verified calculations. In mathematics, interval is a concept relating to the sequence and set-membership of one or more numbers. ...
Multidimensional integrals The quadrature rules discussed so far are all designed to compute one-dimensional integrals. To compute integrals in multiple dimensions, one approach is to phrase the multiple integral as repeated one-dimensional 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 so-called curse of dimension. It has been suggested that A counterexample related to Fubinis theorem be merged into this article or section. ...
In mathematics, a quantity that grows exponentially is one whose growth rate is always proportional to its current size. ...
Monte Carlo Monte Carlo methods and quasi-Monte Carlo methods are easy to apply to multi-dimensional integrals, and may yield greater accuracy for the same number of function evaluations than repeated integrations using one-dimensional methods. Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ...
In numerical analysis, a quasi-Monte Carlo method is a method for the computation of an integral (or some other problem) which is based on low-discrepancy sequences. ...
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. Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods) are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its stationary distribution. ...
The Proposal distribution Q proposes the next point that the random walk might move to. ...
In mathematics and physics, Gibbs sampling is an algorithm to generate a sequence of samples from the joint probability distribution of two or more random variables. ...
Sparse grids 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. Sparse grids are a numerical technique to represent, integrate or interpolate high dimensional functions. ...
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 here. - QUADPACK (part of SLATEC): description [1], source code [2]. QUADPACK is a collection of algorithms, in Fortran, for numerical integration based on Gaussian quadrature.
- GSL: The GNU Scientific Library (GSL) is a numerical library written in C which 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.
The Guide to Available Mathematical Software (GAMS) is a project of the National Institute of Standards and Technology to classify mathematical software by the type of problem that it solves. ...
References - George E. Forsythe, Michael A. Malcolm, and Cleve B. Moler. Computer Methods for Mathematical Computations. Englewood Cliffs, NJ: Prentice-Hall, 1977. (See Chapter 5.)
- William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, 1988. (See Chapter 4.)
- Josef Stoer and Roland Bulirsch. Introduction to Numerical Analysis. New York: Springer-Verlag, 1980. (See Chapter 3.)
- Background, Notes, PPTs, Simulations in Mathcad, Maple, Mathematica and Matlab at Holistic Numerical Methods Institute
|
Feeds |
Contact