Estimating $\int_0^1f$ for an unknown Lipschitz $f$ to within 0.0001

Question

A friend of mine has a Lipschitz function $f\colon [0,1]\to\mathbb R$ satisfying (Some more characters, and yet a few more...) $$|f(a)-f(b)| \le 5 |a-b| \qquad\text{for all }a,b\in[0,1],$$ and s/he would like to estimate the integral $\int_0^1 f$ to within $0.00001$; i.e., to find a number $E$ such that $$\left| E-\int_0^1 f\right| \le 0.0001.$$

Even though the formula for the function is very complicated (and will not be divulged here), my friend can and will calculate the value of the function at any input to within $0.000006$. My friends is also willing and able to program a calculator to carry out basic arithmetic instructions as instructed, but s/he does not know Calculus at all.

1. Argue that $f$ is indeed Riemann integrable.
2. Provide a list of detailed instructions for simple arithmetic calculations that can be carried out by my friend (described above), so that the result of these calculations is guaranteed to be within $0.0001$ of $\int_0^1 f$
3. Supply a proof showing that the calculation on your list will indeed yield an answer that is within $0.0001$ of $\int_0^1 f$.

Part 1 seems easy, all I need to do is to show that Lipschitz implies continuous and bounded which implies Riemann integrable. It's the other stuff which are more challenging.

Part 2/3: The instructions I am thinking of are attempting to divide the interval [0,1] into n subintervals and calculating the area under these intervals, (using the average of the function at the beginning of each interval as an evaluation point to take into account the error in computing the function), and then the error will/should decrease as n increases.

I am not sure I am going in the right direction, and if so, not sure how to formally represent this. Can someone show me a detailed proof for how to do this?

Answer 1

That Lipschitz condition means that the largest absolute value of the error in approximating $\int_a^{a+h} f(x) dx$ by $hf(a)$ (exactly evaluating $f$) is $\int_0^h 5x dx = \frac{5h^2}{2}$. (Why?) The composite rectangle rule on $[0,1]$ which you are proposing has $N$ subintervals of length $1/N$, so the maximum possible error is $\frac{5N}{2N^2}=\frac{5}{2N}$.

At the same time, if you evaluate $f$ at $N$ points in the fashion of the prompt, you could potentially make an error of $6 \cdot 10^{-6} N$ from inaccurate evaluations of $f$ itself. So your overall error could be as bad as $\frac{5}{2N} + 6 \cdot 10^{-6} N$. Try to minimize that over $N$ and see if the result is small enough.

Answer 2

You can start to formalize your ideas by taking an estimation $$\left|\frac{f(p)}{n}-\int_p^{p+1/n}f(x)dx\right| = \left| \int_p^{p+1/n}(f(p)-f(x))dx\right|\le \int_p^{p+1/n}|f(p)-f(x)|dx $$$$ \le \int_p^{p+1/n}5|p-x|dx = \frac{5}{2n^2} $$ with $n\in\Bbb N$.

This would give $$\left|\sum_{k=0}^{n-1}\frac{f(k/n)}{n}-\int_0^1f(x)dx\right|\le \frac{5}{2n} $$

All you now is to estimate the error in the terms $\frac{f(k/n)}{n}$.