Monotonicity of Trapezoid Approximations

Question

Here's a numerical analysis question which may not be very important, especially in practice, but has been bugging me.

Suppose $f$ is a continuous function on an interval $[a,b]$. Let $T_n(f)$ be the approximation to $\int_a^b f$ using the trapezoid rule with $n$ subintervals of equal length, and $E_n(f)$ the error $\int_a^b f-T_n(f)$. Simple examples show that $|E_n(f)|$ does not necessarily decrease monotonically as $n$ increases, even if $f$ is a polynomial, although $|E_n(f)|\to0$ if $f$ is continuous. The question is: if $f$ is a polynomial, does $|E_n(f)|$ eventually (for large enough $n$) decrease monotonically? What if $f$ is merely smooth? Some smoothness is obviously needed: consider $\int_{-1}^1 |x|\,dx$. The same question can be asked about the midpoint rule or other schemes.

Answer 1

For convenience let the interval be $[0,1]$, and let's look at the case $f(t) = t^p$. We have $E_n(t^p) = 0$ for $p \le 1$, while by Faulhaber's formula we have $$\eqalign{E_n(t^p) &= \dfrac{1}{p+1} + \dfrac{1}{2n} - \dfrac{1}{n^{p+1}} \sum_{i=1}^{n} i^p\cr &= - \sum_{j=0}^{p-2} {p \choose j} \dfrac{B_{p-j}}{j+1} n^{j-p} }$$ where $B_{p-j}$ is a Bernoulli number. For any polynomial $f$, $E_n(f)$ is a linear combination of these, and for its asymptotic behaviour as $n \to \infty$ we take the least negative power of $n$ whose coefficient does not cancel out: $E_n(f) \sim c n^{-k}$ for some nonzero constant $c$ and some integer $k \ge 2$. In particular its absolute value is monotonically decreasing for sufficiently large $n$.

EDIT: For smooth functions the behaviour can be more complicated. Consider e.g. a function $f$ that is periodic with period $1$. Write $f$ as a Fourier series $$ f(x) = \sum_{m=-\infty}^\infty c_m \exp(2\pi i m x)$$ and note that $T_n(\exp(2\pi i m x) = 0$ unless $m$ is a multiple of $n$, in which case $T_n(\exp(2\pi i m x) = 1$. Thus $E_n(f) = - \sum_{k \ne 0} c_{kn}$, which need not be monotonic.