8
$\begingroup$

I am curious about the value of Simpson's rule (also called the parabolic rule or the 3-point rule) for approximating integrals. The calculus text I am now teaching from uses this rule any time an approximation is needed for an integral. For example, it may give a messy arclength integral and ask for the Simpson's rule approximation using 4 intervals (and thus 5 sample points):

$$ \int_a^{a+4h} f(x) dx \simeq \frac{h}{3}\left(f(a)+ 4f(a+h) + 2f(a+2h) + 4f(a+3h)+ f(a+4h)\right).$$

I understand the idea of Simpson's Rule. If you just sampled three evenly spaced points on a quadratic function, you could compute the integral on that interval with the weighting pattern $(1,4,1)$; this happens to give the right answer for degree 3 polynomials as well. The $(1,4,2,4,2, \ldots, 4,2,4,1)$ pattern comes from repeating this pattern over every pair of intervals.

But I'm not convinced we should always apply this rule any time we cut into $2n$ intervals. Why not just use throw out the uneven weighting and use a few more sample points? If the weighting is so helpful, why not use a more complicated weighting (like the various $n$-point rules (Newton-Cotes formulas) described here)?

The Newton-Cotes formulas and their error terms form a beautiful theory, but are probably too much for undergrad calculus! I understand showing Simpson's rule and going no further.

So I have two main questions-- is Simpson's rule so useful that calculus students should always use it for approximations? And are the other Newton-Cotes formulas (or Gaussian quadrature) always the best way to do numerical integration, or only when the values $f(x_i)$ are sufficiently expensive to compute?

  • 0
    The question's already long, so I'm posting some data here. The arclength of $y=x^2$ on $0 \leq x \leq 4$ is 16.8186... Using the trapezoidal rule with 4 intervals gives 16.9731... Using Simpson's rule with 4 intervals gives 16.8613... Using the 5-point rule (with 4 intervals) gives 16.8496... Using the trapezoidal rule with 8 intervals gives 16.8598... (better than Simpson's rule, but not than the 5-point rule).2011-08-31
  • 1
    Well, high-order Newton-Cotes formulae are very sensitive to subtractive cancellation. One good way to ascertain the quality of a quadrature rule is to check that the signs of the weights are all the same (usually, all positive). That way, any cancellation that happens is due to the integrand (e.g. when a zero of the function is within the integration interval) and not to the quadrature rule.2011-08-31
  • 1
    Additionally, it's been known a long time that high-order interpolating polynomials over evenly spaced abscissas are a **very bad** idea (and the bad properties are inherited by the quadrature rules); an ideal abscissa distribution would look like the roots of the Chebyshev (Clenshaw-Curtis) or Legendre (Gaussian) polynomials.2011-08-31
  • 0
    As to why people keep using Simpson's: the formula is rather easy to remember and/or derive, as well as to apply. For a sampling over equispaced abscissas, one could make an argument for sticking to the trapezoidal rule and just performing Richardsonian extrapolation if deemed necessary. (Simpson's rule then is a special case of this extrapolation.)2011-08-31
  • 0
    ..well anyway, for hand calculation. On a computer routine, I'd (mostly) use Gaussian quadrature myself; a two point Gaussian rule can exactly integrate polynomials up to degree $2(2)-1=3$ in only two evaluations, while Simpson's requires three evaluations.2011-08-31
  • 2
    @J.M.: Maybe four substantive comments = good answer? :)2011-08-31
  • 0
    @Mike: I was throwing in my first thoughts, and due to the rawness, I'll need to stitch them properly to be a good answer. :) Just throwing them in as an answer at their current state looks sorta... haphazard. I'll see what I can do later. (But other people are welcome to build on what I've said in the meantime!)2011-08-31
  • 0
    @J.M.: Thanks for those thoughts. I will have to read about Gaussian quadrature to appreciate its advantages. It makes sense that sampling evenly spaced x-values is not the best strategy. But I'm intrigued by what you say about the general desirability of having all weights positive. It seems that using different weights is all about improving on the naive equal weights approach-- so we want varying weights, but not *too* varying?2011-08-31
  • 1
    Indeed, we don't want too much variation! This is in the same vein as observing that interpolating polynomials of very high degree are generally quite wiggly. In that way, the interpolating polynomial does pass through the sample points, but may look nothing like the original function in between those points. (Sorry I haven't posted an answer yet; I'm still trying to stitch together those previous comments into something answer-worthy.)2011-08-31
  • 0
    @J.M.: Also, it's easy to adversarially choose a function so that any particular rule will give a poor result. Are there any classes of functions that favor some rules over others? (For example, maybe we know $f$ has a small range of values for the first $n$ derivatives, but may have a large range of values for higher derivatives?) I expect that the functions that show up in the textbook mostly belong to some fairly tame class.2011-08-31
  • 1
    Correct: since quadrature is a business of determining the behavior of a function from (hopefully well-chosen) samples, any manner of sampling that will miss "features" of a function (kinks, poles, wiggles, and stuff), no matter how fancy, will certainly yield something inaccurate. And yes, textbook example tend to be rather tame, but I suppose that's because the author does not want to scare the student (too much).2011-08-31
  • 1
    On that note: I seem to have neglected to mention the assumption that the function being integrated is nicely approximated by a polynomial. With this in mind, functions with vertical slopes or horizontal asymptotes will generally yield poor results for these quadratures, since no polynomial ever had these features. (Thus, an appropriate change of variables remains precious, whether you are dealing with integrals numerically or symbolically).2011-08-31

2 Answers 2

6

But I'm not convinced we should always apply this rule any time we cut into $2n$ intervals. Why not just throw out the uneven weighting and use a few more sample points? If the weighting is so helpful, why not use a more complicated weighting (like the various n-point rules (Newton-Cotes formulas) ... )?

The problem with Newton-Cotes methods of high order is that it inherits the same sort of problems you see with using high-order interpolating polynomials. Remember that the Newton-Cotes quadrature rules are based on integrating interpolating polynomial approximations to your function over equally spaced points.

In particular, there is the Runge phenomenon: high-order interpolating functions are in general quite oscillatory. This oscillation manifests itself in the weights of the Newton-Cotes rules: in particular, the weights of Newton-Cotes quadrature rules for 2 to 8 points and and 10 points (Simpson's is the three-point rule) are all positive, but in all the other cases, there are negative weights present. The reason for insisting on weights of the same sign for a quadrature rule is the phenomenon of subtractive cancellation, where two nearly equal quantities are subtracted, giving a result that has less significant digits. By ensuring that the all weights have the same sign, any cancellation that may occur in the computation is due to the function itself being integrated (e.g. the function has a simple zero within the integration interval) and not due to the quadrature rule.

The approach of breaking up a function into smaller intervals and applying a low-order quadrature rule like Simpson's is effectively the integration of a piecewise polynomial approximation. Since piecewise polynomials are known to have better approximation properties than interpolating polynomials, this good behavior is inherited by the quadrature method.

On the other hand, one can still salvage the interpolating polynomial approach if one no longer insists on having equally-spaced sample points. This gives rise to e.g. Gaussian and Clenshaw-Curtis quadrature rules, where the sample points are taken to be the roots of Legendre polynomials in the former, and roots (or extrema in some implementations) of Chebyshev polynomials in the latter. (Discussing these would make this answer too long, so I shall say no more about them, except that these quadrature rules tend to be more accurate than the corresponding Newton-Cotes rule for the same number of function evaluations.)

...is Simpson's rule so useful that calculus students should always use it for approximations?

As with any tool, blind use can lead you to a heap of trouble. In particular, we know that a polynomial can never have horizontal asymptotes or vertical tangents. It stands to reason that a polynomial will be a poor approximation to a function with these features, and thus a quadrature rule based on interpolating polynomials will also behave poorly. The piecewise approach helps a bit, but not much. One should always consider a (clever?) change of variables to eliminate such features before applying a quadrature rule.

  • 0
    P.S. Jonas, sorry for the late reply; it took me quite a while to figure out how to write an answer that isn't too long!2011-09-07
  • 0
    J.M., thanks for this and for all the comments above. This has given me a better perspective, and introduced me to Gaussian quadrature. I appreciate the time and thought you've given to my question.2011-09-07
  • 0
    You're quite welcome, @Jonas. I wanted to write the answer I would've wanted to see back when I was asking these very questions, and this seemed like a good opportunity. :)2011-09-07
3

The reason for teaching Simpson's rule is that it drives home the fundamentals of approximation, helping students to understand that the number of points and the path between them affects the accuracy. That's why I always paired it with a simple right hand or left hand and center sampling. The simple straight line approximation helps the student grasp the area interpretation and the more complicated form of Simpson's shows that it's not as simple as taking the sum of a bunch of rectangular areas.

I would suggest looking at the presentation of the subject in Stewart's Calculus; it's quite a good introductory text. When I was tutoring though, I found the lecture style of writing in Larson's to be a good way to inspire my verbalisation.

One thing to remember is at the level of introductory calculus, the point is less on teaching the best methods, as selecting the methods that best demonstrate the underlying concept. If they're too caught up in the mechanics of the approximation, you're not teaching calculus, you're teaching numerical methods.

  • 0
    I'll confess, numerical approximation is something I haven't used since I was in undergrad calculus myself. I would be happy just to know that my students really understand Riemann sums, and could write a program or spreadsheet to compute them long after this course is over. (I'm glad to show them Simpson's rule, too; it does present some nice ideas.) Do you know of instances where the idea of Simpson's rule or other numerical approximation methods will come up in their engineering, physics, computer science classes, etc? If so, I'll point them out in class tomorrow. Thanks!2011-08-31
  • 0
    As a mechanical engineering student, I use numerical methods extensively. However, I use them for solving differential equations in heat transfer and fluid mechanics, not for elementary integration. I suppose one case of numeric approximation I know of that nearly all sciences and engineering use for integration is the integrating the first n terms of a Fourier series of a periodic function. But that's not exactly the same thing.2011-08-31