Newton–Cotes quadrature

Consider the approximation of $I(f) := \int_a^b f(x) \, dx$ for integrable $f : [a, b] \to \R$ by a quadrature formula of the form $I_n(f) := \sum_{j=0}^n w_j f(x_j)$, where $\set{w_j}_{j=0}^n \subseteq \R$ are weights and $\set{x_j}_{j=0}^n \subseteq [a, b]$ are distinct nodes.

The precision of a quadrature formula is the greatest $m$ for which $I_n = I$ on $P_m$ (the vector space of real polynomial functions of degree at most $m$). For such an $m$ to exist, we assume that $\sum_{j=0}^n w_j = I_n(1) = I(1) = b-a$ so that $I_n = I$ on $P_0$ by linearity, while also noting that $m \leq 2n+1$ since $I_n(\omega_{n+1}^2) = 0 < I(\omega_{n+1}^2)$ for $\omega_{n+1} := \prod_{j=0}^n (\bullet - x_j) \in P_{n+1}$. In addition, Lagrange interpolation shows that $m \geq n$ if and only if $I_n(f) = I(p_n)$ for all $f$, where $p_n \in P_n$ interpolates $f$ at the nodes; or equivalently, $w_j = I(\ell_j)$ for all $j$, where $\set{\ell_j}_{j=0}^n$ is the Lagrange basis of $P_n$. Such a formula is called interpolatory and its error can be expressed as $$ I(f) - I_n(f) = I(f-p_n) = \int_a^b f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx. $$

Closed Newton–Cotes formulas

For $n \geq 1$, the $(n+1)$-point closed Newton–Cotes formula is the interpolatory quadrature formula with $x_j := a + jh$, where $h := \frac{b-a}{n}$.

To analyze its error, we define the polynomials $\Omega_j(x) := \int_a^x \omega_j(t) \, dt$ for $1 \leq j \leq n+1$. We claim that $\Omega_j \geq 0$ or $\Omega_j \leq 0$ on $[a, x_{j-1}]$ according as $j$ is odd or even. This claim is trivial for $j = 1$, and if it holds for some $j$, integration by parts gives $\Omega_{j+1}(x) = \Omega_j(x)(x-x_j) - \int_a^x \Omega_j(t) \, dt$, which implies that the desired inequality for $\Omega_{j+1}$ holds on $[a, x_{j-1}]$. Furthermore, $\Omega_{j+1}$ is decreasing on $[x_{j-1}, x_j]$, so if $j$ is odd, then $\Omega_{j+1}(x) \leq \Omega_{j+1}(x_{j-1}) \leq 0$ for all $x \in [x_{j-1}, x_j]$, whereas if $j$ is even, then $\Omega_{j+1}(x) \geq \Omega_{j+1}(x_j) = 0$ for all $x \in [x_{j-1}, x_j]$ by the symmetry of $\omega_{j+1}$, which establishes the claim by induction.

In fact, if $j$ is odd, then $\Omega_j \geq 0$ everywhere because $\Omega_j$ is decreasing on $(-\infty, a]$ and increasing on $[x_{j-1}, \infty)$. We also note that $\int_a^b \Omega_j(x) \, dx = -\int_a^b (t-b) \omega_j(t) \, dt$ for all $j$.

Now if $n$ is even and $f \in C^{n+2}([a, b])$, integration by parts and the mean value theorems for integrals and divided differences yield $$ \begin{align*} \int_a^b f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx &= -\int_a^b f[x_0, \dots, x_n, x, x] \Omega_{n+1}(x) \, dx \\ &= - \frac{f^{(n+2)}(\xi)}{(n+2)!} \int_a^b \Omega_{n+1}(x) \, dx \quad \text{for some $\xi \in (a, b)$} \\ &= \frac{f^{(n+2)}(\xi)}{(n+2)!} \int_a^b t \omega_{n+1}(t) \, dt. \end{align*} $$ If $n$ is odd and $f \in C^{n+1}([a, b])$, we have $$ \begin{align*} \int_a^b f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx &= \int_a^b \bigl( f[x_0, \dots, x_{n-1}, x] - f[x_0, \dots, x_n] \bigr) \omega_n(x) \, dx \\ &= -\int_a^b f[x_0, \dots, x_{n-1}, x, x] \Omega_n(x) \, dx \\ &= -\frac{f^{(n+1)}(\xi)}{(n+1)!} \int_a^b \Omega_n(x) \, dx \quad \text{for some $\xi \in (a, b)$} \\ &= \frac{f^{(n+1)}(\xi)}{(n+1)!} \int_a^b \omega_{n+1}(t) \, dt. \end{align*} $$ In summary, we obtain the following (where we have changed variables affinely to exhibit the dependence of the error and the weights on $h$).

Error of closed Newton–Cotes formulas

If $n$ is even and $f \in C^{n+2}([a, b])$, then there exists a $\xi \in (a, b)$ such that $$ I(f) - I_n(f) = C_n f^{(n+2)}(\xi) h^{n+3}, \quad C_n := \frac{1}{(n+2)!} \int_0^n x^2 (x-1) \cdots (x-n) \, dx. $$ If $n$ is odd and $f \in C^{n+1}([a, b])$, then there exists a $\xi \in (a, b)$ such that $$ I(f) - I_n(f) = C_n f^{(n+1)}(\xi) h^{n+2}, \quad C_n := \frac{1}{(n+1)!} \int_0^n x(x-1) \cdots (x-n) \, dx. $$

Open Newton–Cotes formulas

For $n \geq 0$, the $(n+1)$-point open Newton–Cotes formula is the interpolatory quadrature formula with $x_j := a + (j+1)h$, where $h := \frac{b-a}{n+2}$.

As above, we define $\Omega_j(x) := \int_a^x \omega_j(t) \, dt$ for $0 \leq j \leq n+1$; an analogous argument shows that $\Omega_j \geq 0$ or $\Omega_j \leq 0$ on $[a, x_j]$ according as $j$ is even or odd, where $x_{n+1} := b$. Thus, if $n$ is even and $f \in C^{n+2}([a, b])$, the same argument as before yields $$ \begin{align*} \int_a^b f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx &= \frac{f^{(n+2)}(\xi)}{(n+2)!} \int_a^b t \omega_{n+1}(t) \, dt \quad \text{for some $\xi \in (a, b)$}. \end{align*} $$ However, if $n$ is odd and $f \in C^{n+1}([a, b])$, then $\Omega_n$ changes sign at $x_n = b - h$, so the mean value theorem for integrals is not applicable on $[a, b]$ as before. Instead, we write $$ \begin{align*} \int_a^b f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx &= \int_a^{x_n} f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx + \int_{x_n}^b f[x_0, \dots, x_n, x] \omega_{n+1}(x) \, dx \\ &= \frac{f^{(n+1)}(\xi_1)}{(n+1)!} \int_a^{x_n} \omega_{n+1}(x) \, dx + \frac{f^{(n+1)}(\xi_2)}{(n+1)!} \int_{x_n}^b \omega_{n+1}(x) \, dx \\ &\hphantom{{}={}} \text{for some $\xi_1, \xi_2 \in (a, b)$}. \end{align*} $$ Since $\int_a^{x_n} \omega_{n+1}(x) \, dx = \Omega_{n+1}(x_n) \geq 0$ and $\int_{x_n}^b \omega_{n+1}(x) \, dx \geq 0$, the intermediate value theorem implies that this sum is equal to $$ \frac{f^{(n+1)}(\xi)}{(n+1)!} \left( \int_a^{x_n} \omega_{n+1}(x) \, dx + \int_{x_n}^b \omega_{n+1}(x) \, dx \right) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \int_a^b \omega_{n+1}(x) \, dx \quad \text{for some $\xi \in (a, b)$}. $$

Error of open Newton–Cotes formulas

If $n$ is even and $f \in C^{n+2}([a, b])$, then there exists a $\xi \in (a, b)$ such that $$ I(f) - I_n(f) = C_n f^{(n+2)}(\xi) h^{n+3}, \quad C_n := \frac{1}{(n+2)!} \int_{-1}^{n+1} x^2 (x-1) \cdots (x-n) \, dx. $$ If $n$ is odd and $f \in C^{n+1}([a, b])$, then there exists a $\xi \in (a, b)$ such that $$ I(f) - I_n(f) = C_n f^{(n+1)}(\xi) h^{n+2}, \quad C_n := \frac{1}{(n+1)!} \int_{-1}^{n+1} x(x-1) \cdots (x-n) \, dx. $$