# How to calculate the optimal number of slices to use for a Riemann sum

I wrote some code that calculates the area under a curve using Riemann sum. The way I have it working right now is that a user enters the upper and lower bounds for the integral and then the number of slices to use for the calculation. I want a way to calculate the number of slices needed for the area to converge (within a tolerance). It's easy enough to just tell the user to enter in a very large number but I want to see if I can automate this.

My initial though was to calculate the area using, for example, $10$ and $100$ slices ( $S_1, S_2$). Then try and fit that to an exponential decay.

The area of each of those trials giving me $A_1, A_2$

Using that I can get the time constant for the decay as $T = \frac{S_2-S_1}{\ln(A_1/A_2)}$ Then finding the optimal number of slices to use could just be a multiple of the time constant. For example $10T$

-
Out of curiosity, have you tried using trapezoids rather than rectangles? – littleO Oct 17 '13 at 21:14
Nope just rectangles. – JDD Oct 17 '13 at 21:45
You could use the adaptive Simpson's rule. – Rahul Oct 17 '13 at 23:28

I can give you a rough upper bound on the decay rate of the error in your approximation to the integral. For concreteness, say we have a smooth function $f : [0,1] \to \mathbb{R}$. Let $L = \|f'\|_{\infty} = \sup \{|f'(x)| \mid x \in [0,1]\}$, which is a fancy way of saying the largest magnitude of a tangential slope of $f$.
Let's say we're using a left-point rectangle approximation, so the approximation using $n$ even slices is given by $$A_n = \frac{1}{n} \sum_{k = 0}^{n-1} f(k/n)$$ Let $A = \int_0^1 f(x) dx$ be the actual value of the integral. Then I claim that $$|A - A_n| \leq L/n$$ Using the midpoint approximation, this can be improved to $L/(2n)$ (try to figure this out!).
I'll give you the main idea: if $x \in [k/n, (k+1)/n]$ is a point, then by the mean value theorem, $f(x) - f(k/n) = (x - k/n) f'(c)$ for some point $k/n \leq c \leq x$. Using what we know, we can bound $$|f(x) - f(k/n)| \leq L/n$$ The rest of the proof is straightforward from there.
In case you're curious, using trapezoids is actually a considerably better way to approximate the integral. Using the taylor expansion out to the second order derivative, it's possible to show (and a good exercise, too) that the trapezoid approximation with $n$ equal slices is within $M/n^2$ of the original integral; here $M = \|f''\|_{\infty} = \sup\{|f''(x)| \mid x \in [0,1]\}$ is the highest magnitude of the second derivative.