Numerical quadrature#

One application of interpolation is the numerical integration (or quadrature) of functions. Given a complicated function \(f\) in an interval \([a,b]\). Instead of evaluating

\[ I:=\int_a^bf(x)dx \]

we evaluate

\[ I_n:=\int_a^bp_n(x)dx, \]

where \(p_n\) interpolates \(f\) at a given set of points.

Newton-Cotes formulae#

We now describe the derivation of Newton-Cotes integration formulae. Define

\[ x_j=a+ih, i=0,\dots,n \]

with \(h=\frac{b-a}{n}\).

We interpolate \(f\) using a Lagrange interpolation polynomial of the form

\[ p_n(x)=\sum_{k=0}^nL_k(x)f(x_k). \]

We obtain

\[ \int_a^bf(x)dx\approx \int_a^b\sum_{k=0}^nL_k(x)f(x_k)=\sum_{k=0}^nf(x_k)\int_a^bL_k(x)dx:=\sum_{k=0}^nf(x_k)\omega_k, \]

where the \(\omega_k:=\int_a^bL_k(x)dx\) are called integration weights. They are independent of the function to integrate and can be precomputed and tabulated.

We note two simple observations for Newton-Cotes rules:

  1. The sum of the weights \(\omega_k\) is always \(b - a\). This follows from integrating the constant function \(1\).

  2. The weights are symmetric in the sense that \(\omega_j = \omega_{n-j}\). This follows from the symmetry of the \(L_k\) with respect to the middle of the interval \([a,b]\).

Two particular examples of Newton-Cotes rules are:

Trapezoid Rule (n=1): \(\int_a^bf(x)dx\approx \frac{b-a}{2}\left[f(a)+f(b)\right]\).

Simpson’s Rule (n=2): \(\int_a^bf(x)dx\approx \frac{b-a}{6}\left[f(a)+4f((a+b)/2)+f(b)\right]\)

Error estimates#

The error \(E_n\) of a quadrature formula is defined as \(E_n(f):=\int_a^bf(x)dx-\sum_{k=0}^n\omega_kf(x_k)\). We now have

\[ |E_n(f)|=\left|\int_a^b\left[f(x)-L_k(x)f(x_k)\right]dx\right|\leq \int_a^b|f(x)-p_n(x)|dx. \]

The last integral can be estimated as

\[ |E_n(x)|\leq \frac{M_{n+1}}{(n+1)!}\int_a^b|(x-x_0)\dots(x-x_n)|dx, \]

where \(M_{n+1}=\max_{\xi\in[a,b]}|f^{(n+1)}(\xi)|\).

Runge phenomenon for Newton-Cotes rules#

If we increase the order of the Newton-Cotes rule then apart from special cases we will encounter the Runge phenomenon. Hence, in order to achieve high accuracy we need to do something else. In practice one often uses so-called composite rules. The idea is that we split \([a,b]\) into \(m\) subintervals \([\tau_i,\tau_{i+1}]\) with \(\tau_i=a+\frac{i}{m}(b-a)\), \(i=0,\dots,m-1\), and apply a low-order Newton-Cotes rule in each subinterval.