Error propagation in adaptive Simpson algorithm
08-01-2018, 02:23 PM
Post: #10
 Albert Chan Senior Member Posts: 1,785 Joined: Jul 2018
RE: Error propagation in adaptive Simpson algorithm
I were misled to believe it is plain Simpson + correction (/15 only) ... Sorry

It is not one integral with increasing steps for better accuracy,
but increasing number of mini-integrals (2 intervals, thus 3 points) sum together.

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.

--

By setting a tolerance, adaptive Simpson rule ignore the "details", and
concern itself with the dominant sub-divided integrals, thus is faster.

This is just my opinion, speed-up by ignoring the details come with costs:
• not recommended for function where details matter (dominant peaks cancelled out)
• not recommended for non-linear transformed integral, with details suppressed.
But, how to ensure the integral not behaved like a non-linear transformed type ?
• we need information about approximate size of expected result, to set tolerance.
• tolerance too loose, important details will be ignored, and may get wrong result.
• tolerance too tight, it may reach software recursion limit and crashes.
• Since corrections are really extrapolation, by the time the corrected mini-integral
results cascade back to the top, result might be totally off.
• Good corrections should be for actual iterations, not corrected estimates (which the cascade does).
Hp thread: Simpson Revival, post #6
• returned result have higher uncertainly due to all of above

For example, this transformed exponential integral will not work well with Adatpive scheme:

$$\int_0^{500}e^{-x}dx$$ = $$\int_{-1}^{1}375(1-u^2) e^{-(125u (3 - u^2) + 250)} du$$ = 1 - $$e^{-500}$$ ~ 1.0

OTTH, if used correctly, this is a great tool. For example:

I(1000) = 4 $$\int_{0}^{\pi/2} cos(x) cos(2x) ... cos(1000x) dx$$ = 0.000274258153608 ...

Adaptive Simpson Method (eps = 1e-9) were able to give 11 digits accuracy in 0.5 sec
Romberg's Method can only reached 8 digits accuracy ... in 400 seconds !

Thanks, Claudio
 « Next Oldest | Next Newest »