Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.