Adaptive Simpson and Romberg integration methods

[robve]

(03-25-2021 03:09 PM)Albert Chan Wrote:  Trapezoids seems to be twice as good as mid-points (in the opposite direction).
When we extrapolate with Romberg, trapezoids are *much* better
With same sub-intervals, both scheme have comparable errors. Example:
[...]
error(T32) = 1 - 1.0000000003184022 ≈ −3.18e-10
error(M64) = 1 - 0.9999999996826735 ≈ +3.17e-10

But, getting M64 required doubled the time than T32.

As this is indeed the case, I wonder how trapezoidal versus midpoint actually compare in Romberg. To come up with a ratio of the number of points for Romberg+trapezoidal versus Romberg+midpoints, we have to consider that at each midpoint step the error decreases by 1/9th in size (while evaluating three times as many points), whereas at each trapezoidal step the error decreases by 1/4th its size (while evaluating two times as many points). However, 3*1/9=1/3 versus 2*1/4=1/2 does not align with observations. Combining this with your 2 times number of points needed for midpoint gives 2*3*1/9 = 2/3 versus 1/2 per step.

Interesting.

Edit: I ran an experiment with 100 polynomials of degree 1 to 30 randomly generated. For eps=1e-9, the average number of points evaluated by method is:
Romberg trapezoid: 46.68
Romberg midpoint: 186.3
Adaptive Simpson: 431.76
For eps=1e-5 and the same 100 polynomials:
Romberg trapezoid: 19.32
Romberg midpoint: 64.8
Adaptive Simpson: 44
For eps=1e-3 and the same 100 polynomials:
Romberg trapezoid: 11
Romberg midpoint: 25.92
Adaptive Simpson: 14.92
The ratio is 1:2.5 ~ 1:4 for Romberg closed versus open, depending on eps. As expected, Adaptive Simpson is fast for lower eps values, which makes this a favorite for quick estimates especially with complicated functions (these polynomials are bit too nice to be interesting to use Adaptive Simpson).

- Rob