6
$\begingroup$

In case of numerical integration, is it true that higher degree of precision always gives better accuracy? Justify your answer.

I know the definition of degree of precision. For Trapezoidal and Simpson's 1/3 rule they are 1 and 3 respectively. Simpson's 1/3 gives better accuracy than Trapezoidal rule. Then whether the above statement is true always. If not, why? If yes, then why we learn Trapezoidal/ Simpson rule? Why we shall not establish/go for higher and higher DOP from generalized Newton-Cote's rule or other general quadrature formula .

$\endgroup$
  • 1
    $\begingroup$ Usually, but not always. Consider the function $f(x) = \left\{\matrix{1 & x < 1/2\\0 & x \geq 1/2}\right.$. The trapesoidal rule with $n=3$ points ($x=0,1/2,1$) gets the integral $\int_0^1f(x){\rm d}x$ exactly, but if we use an even number of points we will always be a bit off the true result no matter how large $n$ is. $\endgroup$ – Winther Jan 3 '16 at 8:00
  • $\begingroup$ @Winther Please give me the answer when higher degree of precision gives better accuracy and when higher degree of precision does not give better accuracy with analytical justification. $\endgroup$ – user1942348 Jan 3 '16 at 8:10
  • 1
    $\begingroup$ That is almost impossible I think (for general functions). The key to the proofs of the order of the different methods is that as long as functions have bounded derivatives (of some order) then the error will grow roughly as $\frac{1}{N^k}$ for some some integer $k$ (and consequently go to zero when $N\to\infty$). However we usually don't have any control if $N=38$ will give better results than $N=40$. $\endgroup$ – Winther Jan 3 '16 at 8:12
  • $\begingroup$ @Winther What do you mean by " a bit off the true result"? $\endgroup$ – user1942348 Jan 3 '16 at 8:18
  • $\begingroup$ @winther Somewhere I read that In particular, "when range of integration is large", the statement above is not correct. Whether it ("when range of integration is large, higher DOP gives less accuracy") is correct. If correct, would you explore why? $\endgroup$ – user1942348 Jan 3 '16 at 8:24
7
+50
$\begingroup$

Increasing the precision, both in terms of the order of the method and in the number of gridpoints used, usually (most of the time) leads to a more accurate estimate for the integral we are trying to compute. However this is not always the case as the following (aritficial) example shows.


$$\bf \text{Example where higher order does not imply better accuracy}$$

Let

$$f(x) = \left\{\matrix{1 & x < \frac{1}{2}\\0 & x \geq \frac{1}{2}}\right.$$

and consider the integral $I=\int_0^1f(x){\rm d}x = \frac{1}{2}$. If we use the trapezoidal rule with $n$ gridpoints then

$$I_{n} = \frac{1}{n}\sum_{i=1}^{n}\frac{f(\frac{i-1}{n})+f(\frac{i}{n})}{2} \implies I_n = \left\{\matrix{\frac{1}{2} & n~~\text{odd}\\\frac{1}{2} - \frac{1}{n} & n~~\text{even}}\right.$$

so for $n=3$ we have the exact answer which is better than any even $n$ no matter how large it is. This shows that increasing the number of gridpoints does not always improve the accuracy. With Simpson's rule we find

$$I_n = \frac{1}{3n}\sum_{i=1}^{n/2}f\left(\frac{2i-2}{n}\right)+4f\left(\frac{2i-1}{n}\right)+f\left(\frac{2i}{n}\right) \implies I_n = \left\{\matrix{\frac{1}{2} - \frac{1}{3n}&n\equiv 0\mod 4\\\frac{1}{2}&n\equiv 1\mod 4\\\frac{1}{2} + \frac{2}{3n} & n\equiv 2\mod 4\\\frac{1}{2} - \frac{5}{6n} & n\equiv 3\mod 4}\right.$$

so even if Simpson's rule has higher order we see that it does not always do better than the trapezoidal rule.


$$\bf \text{What does higher degree of precision really mean?}$$

If we have a smooth function then a standard Taylor series error analysis gives that the error in estimating the integral $\int_a^bf(x){\rm d}x$ using $n$ equally spaced points is bounded by (here for Simpsons and the trapezoidal rule)

$$\epsilon_{\rm Simpsons} = \frac{(b-a)^5}{2880n^4}\max_{\zeta\in[a,b]}|f^{(4)}(\zeta)|$$ $$\epsilon_{\rm Trapezoidal} = \frac{(b-a)^3}{12n^2}\max_{\zeta\in[a,b]}|f^{(2)}(\zeta)|$$

Note that the result we get from such an error analysis is always an upper bound (or in some cases an order of magnitude) for the error apposed to the exact value for the error. What this error analysis tell us is that if $f$ is smooth on $[a,b]$, so that the derivatives are bounded, then the error with a higher order method will tend to decrease faster as we increase the number of gridpoints and consequently we typically need fewer gridpoints to get the same accuracy with a higher order method.

The order of the method only tell us about the $\frac{1}{n^k}$ fall-off of the error and says nothing about the prefactor in front so a method that has an error of $\frac{100}{n^2}$ will tend to be worse than a method that has an error $\frac{1}{n}$ as long as $n\leq 100$.


$$\bf \text{Why do we need all these methods?}$$

In principle we don't need any other methods than the simplest one. If we can compute to arbitrary precision and have enough computation power then we can evaluate any integral with the trapezoidal rule. However in practice there are always limitations that in some cases forces us to choose a different method.

Using a low-order method requires many gridpoints to ensure good enough accuracy which can make the computation take too long time especially when the integrand is expensive to compute. Another problem that can happen even if we can afford to use as many gridpoints as we want is that truncation error (errors due to computers using a finite number of digits) can come into play so even if we use enough points the result might not be accurate.

Other methods can elevate these potential problems. Personally, whenever I need to integrate something and has to implement the method myself I always start with a low-precision method like the trapezoidal rule. This is very easy to implement, it's hard to make errors when coding it up and it's usually good enough for most purposes. If this is not fast enough or if the integrand has properties (e.g. rapid osccilations) that makes it bad I try a different method. For example I have had to compute (multidimensional) integrals where a trapezoidal rule would need more than a year to compute it to good enough accuracy, but with Monte-Carlo integration the time needed was less than a minute! It's therefore good to know different numerical integration methods in case you encounter a problem where the simplest method fails.

$\endgroup$
  • $\begingroup$ Your answer is very impressive. Thanks a lot. You have given an example of $f(x) $. It is not differentiable at x=1/2. For such non-smooth function, the Trap is better than Simp. Is there any example where $f(x)$ is continuous and smooth but Trap gives better accuracy than Simp? $\endgroup$ – user1942348 Jan 4 '16 at 13:50
  • $\begingroup$ @user1942348 Yes there is. For example take $f(x)$ and connect $x = 1/2 - \epsilon$ to $x = 1/2 + \epsilon$ with a line (smoothed at the corners). Take $\epsilon$ to be tiny and you'll get pretty much the same result as I got here. $\endgroup$ – Winther Jan 4 '16 at 14:21
  • $\begingroup$ I just googled and see that for periodic function with limits of integration one with its period, Trap works better. self.gutenberg.org/articles/trapezoidal_rule Do you know is this correct. Can you give such example for me? $\endgroup$ – user1942348 Jan 4 '16 at 15:55
  • $\begingroup$ @user1942348 I think the statement on that page is that Trap does better than what we naively would expect from looking at the error term for functions that oscillate, not that it neccesarily is much better than say Simpsons. I tried some random test cases like $\sin(2\pi x)$ and $[x(1-x)]^4$ and Trap does indeed do better than expected and the acctual error as function of $n$ is similar to Simpsons for these two functions ($\epsilon \propto 1/n^6$ for the latter function). $\endgroup$ – Winther Jan 4 '16 at 16:49
  • $\begingroup$ @user1942348 btw let me know if you have Mathematica and I can add the code I used to test this so you can play with it and see for yourself. $\endgroup$ – Winther Jan 4 '16 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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