Best quadrature formula

optimal quadrature formula

An approximate integration formula that guarantees the minimum error for a given class of functions, relative to all formulas of a specified type. As an example, consider the quadrature formula

$$ \tag{* } \int\limits _ { a } ^ { b } \rho (x) f (x) dx = \ \sum _ {k = 1 } ^ { n } \sum _ {i = 0 } ^ { m } p _ {ki} f ^ { (i) } (x _ {k} ) + R (f), $$

where $ \rho (x) $ is a weight function. The remainder (error) term $ R (f) = R (f, X _ {n} , P _ {nm} ) $ depends both on the function $ f (x) $, and on the vector $ (X _ {n} , P _ {nm} ) $ consisting of the interpolation nodes $ x _ {k} $( it is usually assumed that $ x _ {k} \in [a, b] $) and the coefficients $ p _ {ki} $, $ k = 1 \dots n $; $ i = 0 \dots m $. Fixing $ n \geq 1 $ and $ m \geq 0 $, let $ A $ denote some set of vectors $ (X _ {n} , P _ {nm} ) $( and hence also some set of quadrature formulas), defined by some restrictions on the interpolation nodes and coefficients (in particular, one might consider the set $ A = A ( \overline{X}\; _ {n} ) $ of coefficients $ p _ {ki} $ for a fixed node vector $ \overline{X}\; _ {n} $). Let $ \mathfrak M $ be some class of functions $ f (x) $, it being assumed that the integral and the sum in (*) exist. The best quadrature formula of type (*) for the class $ \mathfrak M $ relative to the set $ A $ is defined by a vector $ (X _ {n} ^ {*} , P _ {nm} ^ {*} ) $ for which

$$ \sup _ {f \in \mathfrak M } | R (f, X _ {n} ^ {*} , P _ {nm} ^ {*} ) | = $$

$$ = \ \inf _ {(X _ {n} , P _ {nm} ) \in A } \sup _ {f \in \mathfrak M } | R (f, X _ {n} , P _ {nm} ) | . $$

The construction of best quadrature formulas is intimately connected with certain problems in spline approximation; in many cases it reduces to minimizing the norm of a monospline (see [1]). Best quadrature formulas, together with sharp estimates for the remainder term, are known for many important classes of continuous and differentiable functions. From a more general point of view, the problem of finding best quadrature formulas and the corresponding errors for a class $ \mathfrak M $ may be viewed as the problem of optimal recovery of a functional

$$ J (f) = \int\limits _ { a } ^ { b } \rho (x) f (x) dx, $$

where $ f \in \mathfrak M $, on the basis of the information $ \{ f ^ { (i) } (x _ {k} ) \} $, $ k = 1 \dots n $; $ i = 0 \dots m $. The concept of a best quadrature formula generalizes in a natural way to functions of several variables (cubature formulas).

References

[1]	S.M. Nikol'skii, "Quadrature formulae" , H.M. Stationary Office , London (1966) (Translated from Russian)
[2]	N.M. Krylov, "Approximate calculation of integrals" , Macmillan (1962) (Translated from Russian)
[3]	P.J. Laurent, "Approximation et optimisation" , Hermann (1972)
[4]	A.A. Zhensykbaev, "Monosplines of minimal norm and quadrature formulas" Uspekhi Mat. Nauk , 36 : 4 (1981) pp. 107–159 (In Russian)

Comments

The terminology "best formula" is often encountered in the literature on numerical analysis, but, as was observed in [a2], p. 75, it should be taken with a large dose of salt, because, after all, any quadrature formula, no matter how the weights $ p _ {k i } $ and the nodes $ x _ {k} $ are chosen, will exactly integrate an infinite-dimensional family of functions.

A few recent textbooks are listed below.

References

[a1]	H. Brass, "Quadraturverfahren" , Vandenhoeck & Ruprecht (1977)
[a2]	P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1984)
[a3]	H. Engels, "Numerical quadrature and cubature" , Acad. Press (1980)