Quadrature formula

An approximate formula for the calculation of a definite integral:

$$ \tag{1 } \int\limits _ { a } ^ { b } p ( x) f ( x) d x \cong \sum _ { j= } 1 ^ { N } C _ {j} f ( x _ {j} ) . $$

On the left-hand side is the integral to be calculated. The integrand is written as a product of two functions. The first, $ p ( x) $, is considered to be fixed for the given quadrature formula and is called the weight function; the function $ f ( x) $ belongs to a fairly-wide class of functions, for example, continuous functions for which the integral on the left-hand side of (1) exists. The sum on the right-hand side of (1) is called the quadrature sum, the numbers $ x _ {j} $ are called the nodes of the quadrature formula, while the numbers $ C _ {j} $ are called its weights. The determination of an approximate value of the integral by means of formula (1) reduces to the calculation of the quadrature sum; the values of the nodes and the weights are usually taken from tables (see, for example, [3]).

The most widespread quadrature formulas are those based on algebraic interpolation. Let $ x _ {1} \dots x _ {N} $ be distinct points (usually $ x _ {i} \in [ a , b ] $ although this requirement is not essential) and let $ P ( x) $ be the interpolation polynomial for $ f ( x) $ constructed from its values at these points:

$$ P ( x) = \ \sum _ { i= } 1 ^ { N } L _ {i} ( x) f ( x _ {i} ) . $$

Here $ L _ {i} ( x) $ is the Lagrangian basis polynomial of the $ i $- th node (cf. Lagrange interpolation formula): $ L _ {i} ( x _ {j} ) = \delta _ {ij} $( $ \delta _ {ij} $ is the Kronecker symbol). The integral over $ [ a , b ] $ of $ p ( x) f ( x) $ is approximately replaced by the integral of $ p ( x) P ( x) $; one obtains an approximate equation of the form (1), in which

$$ \tag{2 } C _ {i} = \ \int\limits _ { a } ^ { b } p ( x) L _ {i} ( x) d x ,\ i = 1 \dots N . $$

The existence of the integral in (2) is equivalent to the existence of the moments of the weight function:

$$ \mu _ {k} = \ \int\limits _ { a } ^ { b } p ( x) x ^ {k} d x ,\ k = 0 \dots N $$

(here and in what follows it is assumed that the required moments of $ p ( x) $ exist; in particular, in the case $ p ( x) = 1 $ the interval $ [ a , b ] $ is taken to be finite, cf. Moment problem).

The quadrature formula (1) in which the weights are defined by equations (2) is called an interpolatory quadrature formula. An integer $ d \geq 0 $ is called the algebraic degree of accuracy of (1) if (1) is exact when $ f ( x) $ is any polynomial of degree not exceeding $ d $ and if it is not exact for $ f ( x) = x ^ {d+} 1 $. In order that (1) be an interpolatory quadrature formula it is necessary and sufficient that its algebraic degree of accuracy $ d $ satisfies the inequality $ d \geq N - 1 $.

Let $ p ( x) = 1 $ and $ [ a , b ] $ be finite. The interpolatory quadrature formula with equally-spaced nodes

$$ \tag{3 } x _ {j} = a + j h ,\ \ j = 0 \dots n ,\ \ h = \frac{( b - a ) }{n} , $$

where $ n $ is a positive integer, $ N = n + 1 $, is called the Newton–Cotes quadrature formula; this quadrature formula has algebraic degree of accuracy $ d = n $ when $ n $ is odd and $ d = n + 1 $ when $ n $ is even. The interpolatory quadrature formula with a single node,

$$ \int\limits _ { a } ^ { b } f ( x) d x \cong \ ( b - a ) f ( \xi ) ,\ \ a \leq \xi \leq b , $$

is called the rectangle rule or midpoint rule; its algebraic degree of accuracy $ d = 1 $ when $ \xi = ( a + b ) / 2 $ and $ d = 0 $ in the remaining cases.

Let

$$ \tag{4 } p ( x) \geq 0 \ \ \mathop{\rm on} \ [ a , b ] ,\ \ \mu _ {0} > 0 . $$

An interpolatory quadrature formula (1) in which the nodes are the roots of an orthogonal polynomial of degree $ n $ on $ [ a , b ] $ with weight function $ p ( x) $ is called a quadrature formula of Gauss type; it is also called a quadrature formula of highest algebraic degree of accuracy, since under the conditions (4) no quadrature formula with $ N $ nodes can be precise for $ x ^ {2N} $. The most widely used quadrature formulas of Gauss type are those defined by the following special cases of the weight function $ p ( x) $ and interval $ [ a , b ] $:

the Jacobi weight $ ( 1 - x ) ^ \alpha ( 1 + x ) ^ \beta $( $ \alpha , \beta > - 1 $) on $ [ - 1 , 1 ] $ with parameter values: a) $ \alpha = \beta = 0 $( the Gauss quadrature formula); b) $ \alpha = \beta = - 1 / 2 $( the Mehler quadrature formula); c) $ \alpha = \beta = 1 / 2 $; and d) $ \alpha = - \beta = 1 / 2 $;

the Hermite weight $ \mathop{\rm exp} ( - x ^ {2} ) $ on ( $ - \infty , + \infty $); and

the Laguerre weight $ x ^ \alpha \mathop{\rm exp} ( - x ) $( $ \alpha > - 1 $) on $ ( 0 , + \infty ) $.

There exist quadrature formulas in which some of the nodes are fixed in advance, while the remaining ones are chosen so that the formula will have highest algebraic degree of accuracy. Such, for example, are the Lobatto quadrature formula and the Radau quadrature formula for the calculation of an integral over $ [ - 1 , 1 ] $ with weight function 1. In the first of these the nodes are $ - 1 , 1 $, while in the second, one of these points is fixed only.

Two quadrature formulas with weight function 1,

$$ \int\limits _ { c } ^ { d } f ( t) d t \cong \ \sum _ { j= } 1 ^ { m } C _ {j} f ( t _ {j} ) ,\ \ \int\limits _ \gamma ^ \delta \phi ( \tau ) d \tau \cong \ \sum _ { j= } 1 ^ { m } \Gamma _ {j} \phi ( \tau _ {j} ) , $$

are said to be similar if $ t _ {j} - c = s ( \tau _ {j} - \gamma ) $, $ C _ {j} = s \Gamma _ {j} $, $ j = 1 \dots m $, where $ s $ is defined by the equation $ d - c = s ( \delta - \gamma ) $. In the case of a finite interval $ [ a , b ] $,

$$ \tag{5 } \int\limits _ { a } ^ { b } f ( x) d x = \ \sum _ { i= } 0 ^ { n- } 1 \int\limits _ {x _ {i} } ^ { {x _ i+} 1 } f ( x) d x , $$

where the $ x _ {i} $ are defined by (3). If for the calculation of integrals over the intervals $ [ x _ {i} , x _ {i+} 1 ) $ one applies quadrature formulas that are similar to the same quadrature formula, equation (5) leads to a composite quadrature formula for the calculation of the integral at the left-hand side. Such, for example, is the composite rectangle rule:

$$ \int\limits _ { a } ^ { b } f ( x) d x \cong h \sum _ { j= } 1 ^ { n } f ( \xi + ( j - 1 ) h ) ,\ \ \xi \in [ a , a + h ] . $$

In the case $ b - a = 2 \pi $ this quadrature formula is exact for $ \cos k x , \sin k x $ for $ k = 0 \dots n - 1 $.

It is possible to consider the interpolatory formulas obtained by integrating the Hermite interpolation polynomials of the function $ f ( x) $. In the quadrature sum of such a quadrature formula not only the values of the function itself at the nodes do enter, but also the values of its successive derivatives up to some order. The values of the derivatives of the integrand at the ends of the range of integration are also used in the Euler–MacLaurin formula.

For the error of the quadrature formula (1),

$$ R ( f ) = \ \int\limits _ { a } ^ { b } p ( x) f ( x) d x - \sum _ { j= } 1 ^ { N } C _ {j} f ( x _ {j} ), $$

there are representations in which the derivative $ f ^ { ( r) } ( x) $ enters. These representations are of little use for the actual estimation of $ R ( f ) $, since one needs an estimate of the derivative $ f ^ { ( r) } ( x) $. The error $ R ( f ) $ is an additive homogeneous functional on the vector space of functions for which it is defined.

Another approach to the construction of a quadrature formula is based on minimization of the norm of the error functional $ R( f ) $.

Let $ R ( f ) $ be the error of a quadrature formula that is exact for all polynomials of degree not exceeding $ r - 1 $, where $ [ a , b ] = [ 0 , 1 ] $ and $ p ( x) = 1 $. Let $ W _ {q} ^ {(} r) $( $ q > 1 $ and $ r $ is a positive integer) be the vector space of functions $ f ( x) $ that have on $ [ 0 , 1 ] $ an absolutely-continuous derivative of order $ r - 1 $ and a derivative of order $ r $ whose $ q $- th power is summable. Two functions in $ W _ {q} ^ {(} r) $ are considered to be equivalent if their difference is a polynomial of degree not exceeding $ r - 1 $. The set of equivalence classes (the quotient space of $ W _ {q} ^ {(} r) $ by the vector space of polynomials of degree not exceeding $ r - 1 $) is a vector space, denoted by $ L _ {q} ^ {(} r) $. A norm can be introduced into $ L _ {q} ^ {(} r) $ be setting for a class $ \psi \in L _ {q} ^ {(} r) $,

$$ \| \psi \| = \ \| f ^ { ( r) } \| _ { L _ q } = \ \left \{ \int\limits _ { 0 } ^ { 1 } | f ^ { ( r) } ( x) | ^ {q} d x \right \} ^ {1/q} , $$

where $ f $ is any function belonging to $ \psi $. The error functional of the quadrature formula can be considered on $ L _ {q} ^ {(} r) $ by setting $ R ( \psi ) = R ( f ) $, $ f \in \psi $. The error functional $ R ( \psi ) $ is continuous on the normed linear space $ L _ {q} ^ {(} r) $. Its norm $ \| R \| $ characterizes the accuracy of the quadrature formula for all functions in $ W _ {q} ^ {(} r) $: For any $ f \in W _ {q} ^ {(} r) $ the inequality

$$ | R ( f ) | \leq \ \| R \| \cdot \| f ^ { ( r) } \| _ {L _ {q} } $$

holds, and this best possible. It is clear that $ \| R \| $ is a function of the parameters $ x _ {k} , C _ {k} $, $ k = 1 \dots N $, of the quadrature formula and it is natural to try to choose them so that $ \| R \| $ has a minimal value. This leads to a quadrature formula (from the class considered) whose error allows a minimal estimate for all functions of the space $ W _ {q} ^ {(} r) $. Thus, the construction of a quadrature formula reduces to the solution of an extremal problem. This problem, even for the special case above, is extremely complicated and its solution has been obtained only for $ r = 1 $ and $ r = 2 $.

References

[1]	V.I. Krylov, "Approximate calculation of integrals" , Macmillan (1962) (Translated from Russian)
[2]	S.M. Nikol'skii, "Quadrature formulas" , Hindushtan Publ. Comp. , London (1974) (Translated from Russian)
[3]	V.I. Krylov, L.T. Shul'gina, "Handbook on numerical integration" , Moscow (1966) (In Russian)

References

[a1]	P.J. Davis, P. Rabinowitz, "Methods of numerical integration" , Acad. Press (1975)