Error propagation in adaptive Simpson algorithm

[Claudio L.]

Quote:Dieter wrote:
The additional "non-Simpson"-step then is the extrapolation (16·Snew – Sold)/15 which gives an improved, more accurate value for the integral. When two successive values of this improved approximation match with the desired accuracy the iteration exits.

The adaptive algorithm I implemented uses the exact same extrapolation, somewhat disguised in the code but it's there as Snew+ (Snew-Sold)/15 . It does it for each individual strip.

Quote:Dieter wrote:
The essential point here is that we cannot and do not know the error of the calculated approximation.

Exactly, which means we can play with the criteria, since "nobody" knows the right answer. Ideally I want the final output to be close to the tolerance the user provided, so if the user wants 1E-8 we don't waste a lot of time computing beyond that.
So I think my relaxed tolerance, which still overshoots accuracy by a long shot, is a fair compromise.

Quote:Albert Chan wrote:
The question really is, when sub-dividing integral into a bunch of recursive
mini-integrals, what should their tolerance be ?

Mini-integrals don't talk to each other, so don't know which is the more important.
Adaptive Simpson method have to be conservative, tolerance cut in half for each step.
So, even if both splitted integrals equally important, total error still below tolerance.

This is probably an overkill, but without knowing the integral, it is the best it can do.
For one sided function, say exp(-x), tolerance can really stay the same all the way down.

Yes, normally I wouldn't care and agree with you that it's better to be conservative. However, we are deciding between getting the answer you want within a few seconds or waiting a long time (in other words, whether the calculator would be useful or not to the user).
On a PC, both cases would feel instantaneous, so it wouldn't make sense to sacrifice accuracy.
Another good point (that Dieter made clear) is that we are really comparing that tolerance with the difference between two consecutive runs, on a little single strip, which is very loosely related to the actual tolerance on the total area, and I think that's why there is a disconnect between the tolerance the user requests on the final result and the tolerance we should be comparing to.
In the end, the user is getting way more than requested, at the expense of a lot of wasted time and coffee.