Error of midpoint method for functions that are not twice-differentiable

Question

All of the bounds I've seen for the error of the midpoint method of integration are expressed in terms of the second derivative of the function. What bounds are available when the function is not twice-differentiable? In particular, is it the case that for every continuous function $f$ on $[0,1]$, the midpoint method of estimating $\int_0^1 f(x)\: dx$ has error $o(1/n)$? If the answer to this last question is "no" (and I'm pretty sure it is, unless I've misunderstood the example Carnahan gave in response to my earlier question Dependence of error on mesh for Riemann sums), does the answer change to "yes" if we assume that $f$ has bounded variation? That $f$ is monotone?

Answer 1

If the function is monotone, then the error for the midpoint approximation with $n$ intervals is at most $\frac{f(1)-f(0)}{2n}$. Say we know $f$ is increasing and the values at the midpoints, $f(m_i)$ for $i=1,\dots n$, as well as $f(0)$ and $f(1)$, are known. Then the $g_L$ with the smallest integral that satisfies those constraints (not continuous, but arbitrarily closely approximated by continuous functions) is the stepwise function $$g_L(x) = f(m_i) \text{ whenever } m_i\leq x < m_{i+1}$$ where by convention $m_0 = 0$ and $m_{n+1}=1$. Similarly, the function with the largest integral that satisfies these constraints is $$g_U(x) = f(m_{i+1}) \text{ whenever } m_i < x \leq m_{i+1}$$ So we have $$\int_0^1 g_L(x) dx \leq \int_0^1 f(x)dx \leq \int_0^1 g_U(x)dx$$ Note that the functions $g_L$ and $g_M$ depend on $f$ and $n$, but $f$ does not depend on $n$. Then $$\int_0^1 g_L(x) dx = \sum_{i=0}^{n} (m_{i+1} - m_i)f(m_i) = \frac{1}{2n}f(0) + \frac{1}{n}\sum_{i=1}^{n-1} f(m_i) + \frac{1}{2n} f(m_n)$$ and a similar calculation gives $\int_0^1 g_U(x) dx$.

Subtracting the midpoint approximation from the integral inequality above gives $$\frac{f(0)-f(m_n)}{2n} \leq \int_0^1 f(x) dx - \frac{1}{n}\sum_i f(m_i) \leq \frac{f(1) - f(m_1)}{2n}$$ and one can see that the magnitude of the error is bounded by $\frac{f(1)-f(0)}{2n}$.

If $f$ is of bounded variation, then $f = f^+ - f^-$ where each summand is monotone increasing. Since taking integrals and taking midpoint approximations both commute with finite sums, the total error is bounded by $\frac{f^+(1)-f^+(0) + f^-(1) - f^-(0)}{2n}$. Note that the numerator is the total variation of the function.

EDIT: The following was added on 2/17/14.

To see that $O(1/n)$ is the best possible, consider the following construction of a continuous monotone increasing function $f$ with $f(0)=0, f(1)=1$, and for infinitely many $n$, the midpoint approximation at $n$ has error greater than $\frac{1}{4n}$. The function is constructed in stages, similar to the Cantor function.

First we mess up the approximation for $n=2$. Since the samples are taken at $\frac{1}{4}$ and $\frac{3}{4}$, define $$f(x) = \begin{cases} 0 &\text{ if } x \in [0,\frac{1}{4}] \\ \frac{1}{2} &\text{ if } x \in [\frac{1}{4}+\varepsilon_1, \frac{3}{4}] \\ 1 & \text{ if } x \in [\frac{3}{4}+\varepsilon_1, 1]\end{cases}$$ where $\varepsilon_1<\frac{1}{4}$ will be chosen soon. Regardless of the choice for $\varepsilon_1$, the midpoint approximation at $n=2$ is $\frac{1}{4}$. The integral of the function (based on its values where it has been defined so far) is at least $\frac{1}{2} - \frac{3}{2}\varepsilon_1$. So by choosing $\varepsilon_1$ small enough, we can guarantee an error of at least $\frac{1}{8}$.

It is convenient to make $\varepsilon_1$ of the form $2^{-k_1}$. Then the $2^{k_1+1}$ approximation will be perfect on all but four $\varepsilon_1/2$-length intervals, in two pairs. Now we have set ourselves up to recurse, messing up the $2^{k_1+1}$ midpoint approximation by putting in each $\varepsilon_1$-sized gap an appropriate increasing function of variation $\frac{1}{2}$ which is badly under-approximated by the pair of values it contributes to the overall approximation.

That is, we may define $$f(x) = \begin{cases} 0 &\text{ if } x - \frac{1}{4} \in [0,\frac{\varepsilon_1}{4}] \\ \frac{1}{4} &\text{ if } x-\frac{1}{4} \in [\frac{\varepsilon_1}{4} + \varepsilon_2, \frac{3\varepsilon_1}{4}] \\ \frac{1}{2} & \text{ if } x-\frac{1}{4} \in [\frac{3\varepsilon_1}{4} + \varepsilon_2, \varepsilon_1]\end{cases}$$ where $\varepsilon_2$ will be chosen soon. The $2^{k_1+1}$ approximation estimates the integral of $f$ on $[\frac{1}{4}, \frac{1}{4}+\varepsilon_1]$ to be $\frac{\varepsilon_1}{8}$, but the actual integral is at least $\frac{\varepsilon_1}{4} - \frac{3}{2}\varepsilon_2$, so by choosing $\varepsilon_2$ sufficiently small, we can guarantee that the error is at least $\frac{\varepsilon_1}{16}$. By defining $f$ analogously on $[\frac{3}{4},\frac{3}{4}+\varepsilon_1]$ (choosing the same $\varepsilon_2$, but all the values are shifted up by $\frac{1}{2}$), we can double the total error to at least $\frac{\varepsilon_1}{8} = \frac{1}{4\cdot 2^{k_1+1}}$.

Now there are four gaps of size $\varepsilon_2$, each of which should support an increasing function of variation $\frac{1}{4}$. Recurse.