1

I am using the Simpson's composite rule for evaluating integrals, this is $O(h^4)$, where $h$ is the step size. We can use the Richardson's trick to improve things (I denote the integral to be evaluated by $f_I$):

$$\frac{16}{15}S(\frac{1}{2}h)-\frac{1}{15}S(h)=f_I+C\frac{16}{15}(\frac{1}{2}h)^4-C\frac{1}{15}h^4+O(h^5)=f_I+O(h^5) $$

Ok, so the order of error improved by one. But yet when I actually run the imrpoved algorithm the error of order always increases by 2 so that it goes towards $1/64$ on each halving, up from $1/16$. Why is this?

Tony
  • 1,044

1 Answers1

2

Assuming that your integrand is sufficiently differentiable, then Simpson's rule obeys an asymptotic error expansion of the form $$ I - S_h = \alpha h^4 + \beta h^6 + O(h^8), \quad h \rightarrow 0, \quad h > 0.$$ Richardson extrapolation $$R_h = S_h + \frac{S_h - S_{2h}}{15}$$ eliminates the primary error term, i.e., the term $\alpha h^4$ and satisfies an asymptotic error expansion of the form $$ I - R_h = \beta' h^6 + O(h^8) , \quad h \rightarrow 0, \quad h > 0.$$ The fact that your are observing orders of convergence which are $4$ for Simpson's rule and $6$ for the extrapolated rule is a strong indication that your integrand is many differentiable.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37
  • Good answer, is there a chance you could expand upon what is meant by sufficiently differentiable? In particular, Is the general derivation of the Simpson's rule already this way or do we need something more? – Tony Apr 29 '20 at 17:16
  • I recall that for Simpson's rule to be $O(h^4)$ the function has to already be 4 times differentiable. – Tony Apr 29 '20 at 17:27
  • It should be $16S_h-S_{2h}$. @Tony : Yes, to get the 6th order error behavior the function needs to be 6 times differentiable. With some effort one could reduce this to 5 times continuously differentiable, as the leading error term can be expressed as an integral over the 6th derivative. Note that Simpson is already the Richardson extrapolation of the trapezoidal rule. – Lutz Lehmann Apr 30 '20 at 07:44
  • @LutzLehmann Great! Do you have a source for why the error behaves this way? Also, is there some easy example of a function that is exactly 4 times (continuously?) differentiable. – Tony Apr 30 '20 at 07:57
  • 1
    @Tony : Because the quadrature method is time symmetric there can be no odd error term. Functions of the form $x^m|x|$ are exactly $m$ times continuously differentiable in $x=0$. – Lutz Lehmann Apr 30 '20 at 08:00