Algebraic Polynomial Integration

Willi Freeden and Martin Gutting

CRC Press

1.1 Interpolatory Integration Rules Sample text

The integration formulas are obtained by replacing the integral

$\begin{equation}IF = \int_a^b \;\;F\left( x \right)dx,\; F \in {\mathrm{C}^{\left( 0 \right)}}\left[ {a,b} \right],\end{equation}$ (1.1)

by an expression

$\begin{equation} \int_a^b \;\;P_n^F\left( x \right)dx,\end{equation}$ (1.2)

where $P_n^F$ is the uniquely determined interpolating polynomial of degree $n$ at the nodal system ${\left\{ {{x_k}} \right\}_{k = 0, \ldots ,n}} \subset \left[ {a,b} \right]$ . Well-known from classical textbooks (see, e.g., P.J. Davis, P. Rabinowitz [1967], V.I. Krylov [1962], J. Stoer [1989], J. Werner [1991]) is the following theorem.

Theorem 1.1.

Let ${x_k} \in \left[ {a,b} \right],k = 0, \ldots ,n$ , with

$\begin{equation}a \le {x_0} < {x_1} < \ldots < {x_{n - 1}} < {x_n} \le b\end{equation}$

be given knots. Suppose that $F\left( {{x_k}} \right),k = 0, \ldots ,n$ , are known from a function of class ${\mathrm{C}^{\left( 0 \right)}}\left[ {a,b} \right]$ . Then there exists a uniquely determined interpolatory quadrature formula

$\begin{equation}{{\mathcal{L}}_n}F = \sum_{k = 0}^n \;\;{w_k}F\left( {{x_k}} \right),\end{equation}$

i.e.,

$\begin{equation}\int_a^b \;\;P\left( x \right)dx = \sum_{j = 0}^n \;\;{w_j}P\left( {{x_j}} \right)\end{equation}$

for all $P \in \mathrm{Po}{\mathrm{l}_{0, \ldots ,n}}$ , i.e., for all polynomials of degree $\le n$ . The coefficients (weights) ${w_j}$ of the quadrature formula are given in the form

$\begin{equation}{w_j} = \int_a^b \;\;{L_j}\left( x \right)dx,\end{equation}$

where ${L_j}$ are the Lagrange polynomials. ${L_j}$ given by

$\begin{equation}{L_j}\left( x \right) = \prod_{\substack{ {k = 0} \\ {k \ne j}}}^n \;\;\frac{{x - {x_k}}}{{{x_j} - {x_k}}}\end{equation}$

satisfy ${L_j}\left( {{x_k}} \right) = {\delta _{j,k}}$ .

Theorem 1.1 leads to the following consequence:

$\begin{equation}{\mathcal{L}_n}F = \sum_{j = 0}^n \underbrace {\left( {\smallint_a^b {L_j}\left( x \right)dx} \right)}_{ = {w_j}}F\left( {{x_j}} \right) = \smallint_a^b \underbrace {\left( {\sum_{j = 0}^n {L_j}\left( x \right)F\left( {{x_j}} \right)} \right)}_{ = P_n^F\left( x \right)}dx. \end{equation}$ (1.8)

In other words, ${{\mathcal{L}}_n}F$ is obtained by integrating the interpolating polynomial $P_n^F$ over $\left[ {a,b} \right]$ .

Newton-Cotes Formulas. The Newton-Cotes formulas (cf. R. Cotes (1722)) are interpolatory quadratures to equidistant knots

$\begin{equation}x_j^{\left( n \right)} = a + j\tau ,\; \tau = \frac{{b - a}}{n},\; j = 0, \ldots ,n.\end{equation}$ (1.9)

The associated weights are calculated by

$\begin{align} w_j^{\left( n \right)}& = \int_a^b \;\;\prod_{\substack{{k = 0} \\ {k \ne j}}}^n \;\;\frac{{x - x_k^{\left( n \right)}}}{{x_j^{\left( n \right)} - x_k^{\left( n \right)}}}dx = \int_a^b \;\;\prod_{\substack{ {k = 0} \\ {k \ne j} }}^n \;\;\frac{{x - \left( {a + k\tau } \right)}}{{\tau \left( {j - k} \right)}}dx\nonumber \\ &= \tau \int_0^n \;\;\prod_{\substack{ {k = 0} \\ {k \ne j} } }^n \;\;\frac{{t - k}}{{j - k}}dt = \tau \alpha _j^{\left( n \right)}\end{align}$ (1.10)

with

$\begin{equation}\alpha _j^{\left( n \right)} = \frac{{{{( - 1)}^{n - j}}}}{{j!\left( {n - j} \right)!}}\int_0^n \;\;\prod_{\substack{ {k = 0} \\ {k \ne j} } }^n \;\;\left( {t - k} \right)dt.\end{equation}$ (1.11)

See Examples 1.2 and 1.3 for the derivation of the cases $n = 1$ and $n = 2$ . Further cases are summarized in Table 1.1.

Table 1.1: Newton-Cotes formulas for n = 1,…,4

n = 1, \dots, 4

$n = 1, \ldots ,4$ .

$n$	$\alpha _j^{\left( n \right)}$					Name
1	$\frac{1}{2}$	$\frac{1}{2}$				(Simple) Trapezoidal rule
2	$\frac{1}{6}$	$\frac{4}{6}$	$\frac{1}{6}$			Simpson's rule
3	$\frac{1}{8}$	$\frac{3}{8}$	$\frac{3}{8}$	$\frac{1}{8}$		Newton's 3/8-rule
4	$\frac{7}{{90}}$	$\frac{{32}}{{90}}$	$\frac{{12}}{{90}}$	$\frac{{32}}{{90}}$	$\frac{7}{{90}}$	Milne's rule

Example 1.2.

For $n = 1$ we obtain the (Simple) Trapezoidal rule, i.e.,

$\begin{equation}\alpha _0^{\left( 1 \right)} = - \int_0^1 \;\;\left( {t - 1} \right)dt = \frac{1}{2},\end{equation}$

$\begin{equation}\alpha _1^{\left( 1 \right)} = \int_0^1 \;\;tdt = \frac{1}{2}. \end{equation}$

The integrand is approximated by the linear function passing through the points $\left( {a,F\left( a \right)} \right)$ and ( $b,F\left( b \right)$ ). By integrating the linear function we obtain

$\begin{equation}{{\mathcal{L}}_1}F = \frac{{b - a}}{2}\left( {F\left( a \right) + F\left( b \right)} \right).\end{equation}$

Example 1.3.

For $n = 2$ , Simpson's rule yields

$\begin{equation}\alpha _0^{\left( 2 \right)} = \frac{1}{2}\int_0^2 \;\;\left( {t - 1} \right)\left( {t - 2} \right)dt = \frac{1}{3}, \end{equation}$

$\begin{equation} \alpha _1^{\left( 2 \right)} = - \int_0^2 \;\;t\left( {t - 2} \right)dt = \frac{4}{3},\end{equation}$

$\begin{equation} \alpha _2^{\left( 2 \right)} = \frac{1}{2}\int_0^2 \;\;t\left( {t - 1} \right)dt = \frac{1}{3}. \end{equation}$

It is derived by approximating the integrand $F$ by the quadratic polynomial passing through $\left( {a,F\left( a \right)} \right),\left( {\frac{{a + b}}{2},F\left( {\frac{{a + b}}{2}} \right)} \right)$ , and $\left( {b,F\left( b \right)} \right)$ . J. Kepler (1615) used this method over 100 years prior. Hence, in German nomenclature, the method is sometimes called “Keplersche Fassregel”.

$\begin{equation}{{\mathcal{L}}_2}F = \frac{{b - a}}{6}\left( {F\left( a \right) + 4F\left( {\frac{{a + b}}{2}} \right) + F\left( b \right)} \right).\end{equation}$

Remark 1.4.

For $n$ large, the weights are large. Moreover, they are of mixed sign for $n = 8$ and $n > 10$ (which is usually not useful). Therefore, NewtonCotes formulas of higher orders are not often in use. They must be seen with caution.

Example 1.5.

In Table 1.2 the value of the integral

$\begin{equation}2\int_0^1 \;\;\frac{1}{{1 + {x^2}}}dx = \pi \end{equation}$

is calculated by a sequence of Newton-Cotes rules (following P.J. Davis, P. Rabinowitz (1967)) for $n$ -point coefficients from $n = 2$ up to $n = 21$ . The exact value is listed in the last line.

Table 1.2: Newton-Cotes rule applied to the integral (1.19).

$n = 2$	3.0000000	$n = 12$	3.1415925
$n = 3$	3.1333333	$n = 13$	3.1415926
$n = 4$	3.1384615	$n = 14$	3.1415920
$n = 5$	3.1421176	$n = 15$	3.1415932
$n = 6$	3.1418781	$n = 16$	3.1415925
$n = 7$	3.1415708	$n = 17$	3.1415962
$n = 8$	3.1415789	$n = 18$	3.1415935
$n = 9$	3.1415925	$n = 19$	3.1415896
$n = 10$	3.1415926	$n = 20$	3.1415920
$n = 11$	3.1415925	$n = 21$	3.1415775
Exact value			3.1415926

1.2 Peano's Theorem

In discussing the truncation error of approximate integration, it is useful to regard the error (cf. P.J. Davis, P. Rabinowitz (1967)) as a linear functional defined over a certain class of functions. In the considerations that follow, we consider integrands $F$ of class ${\mathrm{C}^{\left( {m + 1} \right)}}\left[ {a,b} \right]$ and linear functionals of integral type (1.1). Note that a generalization to linear functionals of the type

$\begin{equation}IF = \int_a^b \;\;\sum_{j = 0}^m \;\;{a_j}\left( x \right){F^{\left( j \right)}}\left( x \right)dx + \sum_{j = 0}^m \;\;\sum_{i = 1}^{{n_j}} \;\;{b_{ij}}{F^{\left( j \right)}}\left( {{x_{ij}}} \right)\end{equation}$ (1.20)

is obvious. Here, it is assumed that the functions ${a_j}$ are piecewise continuous over $\left[ {a,b} \right],{b_{ij}} \in \mathbb{R}$ , and the points ${x_{ij}}$ lie in the interval $\left[ {a,b} \right]$ .

Remark 1.6.

Evidently included as particular cases of (1.20) are the integral over $\left[ {a,b} \right]$ or any subinterval, the $r$ -th derivative of $F,r \le m$ , evaluated at a point out of $\left[ {a,b} \right]$ , and any linear combination of ordinates of $F$ with abscissas in $\left[ {a,b} \right]$ .

We consider an approximation of ${\mathcal{I}}$ of the form (1.20) by a (quadrature) functional ${\mathcal{L}}$ of the form

$\begin{equation}LF = \sum_{k = 0}^n \;\;{w_k}F\left( {{x_k}} \right),\; F \in {\mathrm{C}^{\left( {m + 1} \right)}}\left[ {a,b} \right].\end{equation}$

We shall say that ${\mathcal{L}}$ is exact for the degree $m$ if ${\mathcal{L}}F = {\mathcal{I}}F$ for all polynomials of degree $\le m$ , i.e., $F \in \mathrm{Po}{\mathrm{l}_{0, \ldots ,m}}$ . The error, or remainder, when ${\mathcal{L}}$ is used to approximate ${\mathcal{I}}$ is a linear functional ${\mathcal{E}}$ defined by

$\begin{equation}\cal E = \cal I - \cal L.\end{equation}$

We shall say that ${\mathcal{E}}$ annihilates $F$ if

$\begin{equation}\cal E F = 0.\end{equation}$

Theorem 1.7. Peano's Theorem

Let ${\mathcal{E}}P = 0$ whenever $P \in \mathrm{Po}{\mathrm{l}_{0, \ldots ,m}}$ . Then, for all $F \in {\mathrm{C}^{\left( {m + 1} \right)}}\left[ {a,b} \right]$ ,

$\begin{equation}EF = \int_a^b \;\;{F^{\left( {m + 1} \right)}}\left( t \right)K\left( t \right)dt, \end{equation}$

where

$\begin{equation}K\left( t \right) = \frac{1}{{m!}}{{\mathcal{E}}_x}(x - t)_ + ^m\end{equation}$

and

$\begin{equation}(x - t)_ + ^m = \left\{ \begin{array}{ll} {{(x - t)}^m}, & {x \ge t,} \\ {0,} & {x < t,} \end{array}\right.\end{equation}$

The result is due to G. Peano [1913, 1914]. The function $K$ is called the Peano kernel for the linear functional ${\mathcal{E}}$ .

Remark 1.8.

Note that the notation ${{\mathcal{E}}_x}$ means the linear functional ${\mathcal{E}}$ is applied to the $x$ -variable in the expression $(x - t)_ + ^m$ .

Proof. From the one-dimensional Taylor formula with explicit representation of the remainder term we obtain

$\begin{equation} F\left( x \right) = \sum_{k = 0}^m \;\;\frac{{F^{\left( k \right)}}\left( a \right)}{{k!}}{{(x - a)}^k} + \frac{1}{{m!}}\int_a^x \;\;F^{\left( {m + 1} \right)}\left( t \right){{(x - t)}^m}dt .\end{equation}$ (1.27)

By virtue of the setting (1.26), the integral remainder may be rewritten as

$\begin{equation}\frac{1}{{m!}}\int_a^x \;\;{F^{\left( {m + 1} \right)}}\left( t \right){{(x - t)}^m}dt = \frac{1}{{m!}}\int_a^b \;\;{F^{\left( {m + 1} \right)}}\left( t \right)(x - t)_ + ^mdt .\end{equation}$ (1.28)

We apply ${\mathcal{E}}$ to both sides of (1.27) and use the fact that ${\mathcal{E}}$ annihilates all members of the class $\mathrm{Po}{\mathrm{l}_{0, \ldots ,m}}$ . This yields

$\begin{equation}\cal EF\left( x \right) = \frac{1}{{m!}}{{\mathcal{E}}_x}\int_a^b \;\;{F^{\left( {m + 1} \right)}}\left( t \right)(x - t)_ + ^mdt. \end{equation}$ (1.29)

Now, the type of functional we are working with allows the interchange of ${\mathcal{E}}$ and the integral. Thus it follows that

$\begin{equation}\cal E F\left( x \right) = \int_a^b \;\;{F^{\left( {m + 1} \right)}}\left( t \right)\frac{1}{{m!}}{{\mathcal{E}}_x}(x - t)_ + ^mdt\end{equation}$ (1.30)

This is the required result.

1.3 Error Truncation

From Peano's Theorem (Theorem 1.7) we immediately obtain

Corollary 1.9.

For $F \in {\mathrm{C}^{\left( {m + 1} \right)}}\left[ {a,b} \right]$ ,

$\begin{equation}\left| \mathcal{E F} \right| \le \mathop {\mathrm{max}}\limits_{x \in \left[ {a,b} \right]} \;\left| {{F^{\left( {m + 1} \right)}}\left( x \right)} \right|\int_a^b \;\;\left| {K\left( t \right)} \right|dt. \end{equation}$

If the Peano kernel does not change its sign over the interval $\left[ {a,b} \right]$ , then ${\mathcal{E}}$ may be expressed essentially as ${F^{\left( {m + 1} \right)}}$ evaluated at an intermediate point. More explicitly, we have the following result.

Corollary 1.10.

If, in addition, $K$ does not change its sign on $\left[ {a,b} \right]$ , then

$\begin{equation}\mathcal{E} F = \frac{{F^{\left( {m + 1} \right)}}\left( \xi \right)}{{\left( {m + 1} \right)!}}E\left( {{x^{m + 1}}} \right),\; a < \xi < b. \end{equation}$

Proof. Under the additional hypotheses we may apply the mean-value theorem for integrals. This leads to

$\begin{equation}\mathcal{E} F = {F^{\left( {m + 1} \right)}}\left( \xi \right)\int_a^b \;\;K\left( t \right)dt. \end{equation}$ (1.33)

Now, we insert $x \mapsto F\left( x \right) = {x^{m + 1}},x \in \left[ {a,b} \right]$ , into (1.33) and obtain

$\begin{equation}E\left( {{x^{m + 1}}} \right) = \left( {m + 1} \right)!\int_a^b \;\;K\left( t \right)dt. \end{equation}$ (1.34)

This yields the assertion (1.32).

For an arbitrary rule of approximate integration (0.1) there is no reason for the Peano kernel to have one sign. However, for integration rules of NewtonCotes type, it can be shown that the kernel does have one sign.

Example 1.11. Remainder in the (Simple) Trapezoidal Rule

If we set

$\begin{equation}\cal E F = \int_a^b \;\;F\left( x \right)dx - \frac{{b - a}}{2}\left( {F\left( a \right) + F\left( b \right)} \right), \end{equation}$

then ${\mathcal{E}}F$ is the truncation error in the (simple) trapezoidal rule. We may select $m = 1$ in Peano's Theorem and obtain

$\begin{align}K\left( t \right) & = \int_a^b \;\;{{(x - t)}_+ }dx - \frac{{b - a}}{2}\left( {{{(a - t)}_ + } + {{(b - t)}_ + }} \right)\nonumber \\ & = \int_t^b \;\;\left( {x - t} \right)dx - \frac{{b - a}}{2}\left( {b - t} \right) = \frac{1}{2}\left( {a - t} \right)\left( {b - t} \right) .\end{align}$

Therefore,

$\begin{equation}\int_a^b \;\;F\left( x \right)dx - \frac{{b - a}}{2}\left( {F\left( a \right) + F\left( b \right)} \right) = \frac{1}{2}\int_a^b \;\;{F}^{\prime \prime}\left( t \right)\left( {a - t} \right)\left( {b - t} \right)dt. \end{equation}$

The kernel $K$ , as determined by (1.36), is non-positive throughout $\left[ {a,b} \right]$ ; hence we may apply Corollary 1.10. Now it is easy to see that

$\begin{equation}E\left( {{x^2}} \right) = \int_a^b \;\;{x^2}dx - \frac{{b - a}}{2}\left( {{a^2} + {b^2}} \right) = - \frac{1}{6}{{(b - a)}^3}. \end{equation}$

Consequently,

$\begin{equation}\int_a^b \;\;F\left( x \right)dx = \frac{{b - a}}{2}\left( {F\left( a \right) + F\left( b \right)} \right) - \frac{1}{{12}}{{(b - a)}^3}{F}^{\prime \prime}\left( \xi \right),\; a < \xi < b. \end{equation}$

Example 1.12. Remainder in Simpson's rule

We consider an integral on the interval $\left[ { - 1,1} \right]$ . Let

$\begin{equation}\cal E F = \int_{ - 1}^1 \;\;F\left( x \right)dx - \frac{1}{3}F\left( { - 1} \right) - \frac{4}{3}F\left( 0 \right) - \frac{1}{3}F\left( 1 \right). \end{equation}$

Now, ${\mathcal{E}}P = 0$ whenever $P \in \mathrm{Po}{\mathrm{l}_{0, \ldots ,3}}$ . Hence, we may take $m = 3$ in Peano's Theorem. We find that $K\left( t \right) = \frac{1}{6}{{\mathcal{E}}_x}(x - t)_ + ^3$ . Explicitly written out we have

$\begin{equation}K\left( t \right) = \left\{\begin{array}{ll} { - \frac{1}{{72}}{{(1 - t)}^3}\left( {3t + 1} \right),} & {0 \le t \le 1,} \\ { - \frac{1}{{72}}{{(1 + t)}^3}\left( { - 3t + 1} \right),} & { - 1 \le t \le 0.} \end{array}\right. \end{equation}$

Obviously, $K\left( t \right) \le 0$ in the interval $\left[ { - 1,1} \right]$ so that Corollary 1.10 is applicable. Since ${\mathcal{E}}\left( {{x^4}} \right) = - \frac{4}{{15}}$ , this leads to the error in Simpson's rule:

$\begin{equation}\int_{ - 1}^1 \;\;F\left( x \right)dx = \frac{1}{3}F\left( { - 1} \right) + \frac{4}{3}F\left( 0 \right) + \frac{1}{3}F\left( 1 \right) - \frac{{F^{\left( 4 \right)}}\left( \xi \right)}{{90}},\; - 1 < \xi < 1. \end{equation}$