# Dependence of error on mesh for Riemann sums

Suppose $f$ is continuous on $[a,b]$ with $I = \int_a^b f(x)\: dx$, and for every $\epsilon > 0$ let $\delta(\epsilon)$ be the largest $\delta > 0$ such that every Riemann sum arising from a partition of $[a,b]$ with mesh less than $\delta$ differs from $I$ by less than $\epsilon$.

Is it true that (leaving aside the case where $f$ is constant) $\delta(\epsilon)$ goes to zero like $\epsilon^2$, in the sense that $\delta(\epsilon)/\epsilon^2$ is bounded above and below by constants as $\epsilon$ goes to zero?

-

If $f(x) = x$ on $[0,1]$, then a mesh less than $\delta$ means the Riemann sum differs from the integral by about $\delta/2$, so $\delta(\epsilon)$ is about $2\epsilon$. Thus, I presume that you mean $\epsilon$ instead of $\epsilon^2$.

A function with bounded variation satisfies a linear upper bound for the error in terms of the mesh size and total variation, hence a linear lower bound for the required $\delta(\epsilon)$.

A function without bounded variation may require a smaller mesh. For example, consider the continuous extension of $f(x) = x \cos(\pi/x^n)$ to $[0,1]$. The difference in $f$ between sampling $f$ at $x=(2k+1)^{-1/n}$ and at $x=(2k)^{-1/n}$ is about $2x$ at locations differing by about $1/n~x^{n+1}$. That means with mesh $\delta$, you can sample $f$ to be either $1$ or $-1$ up to about $x=c \delta^{1/{(n+1)}}$, for an error of $c\delta^{2/(n+1)}$.

Therefore, $\delta(\epsilon)$ can't be larger than $c \epsilon^{(n+1)/2}$.

-

It is possible to choose continuous functions $f$ with really bad approximations, i.e., so that $\delta(\epsilon)$ drops to zero arbitrarily quickly as a function of $\epsilon$. For example, let $f_0$ denote the periodic function of period 1 that linearly interpolates between $(0,0)$, $(1/2,2)$, and the horizontal translates of these points by integers. For each $n>0$, let $f_n(x) = f_0(2^n x)$, and let $f(x) = \sum_{n\geq 0} a_n f_n(x)$, for a summable sequence of positive reals $a_n$. $f$ is integrable on $[0,1]$, with integral $\sum a_n$, and meshes with spacing $2^{-N}$ yield the first N summands. However, if the partial sums converge very slowly, we can have, e.g., $\delta(1/N) \leq 2^{-N!}$.

-

In general, no. The rate at which $\delta(\epsilon)$ tends to zero depends on the regularity of the function $f$. If $f$ is regular enough (bounded derivative, say), then $\delta$ may be chosen linear in $\epsilon$.

Similar things hold with other estimates for the integral... trapezoidal rule, Simpson's rule, etc. In each case, if an appropriate derivative is bounded, then you get a good rate of convergence.

-