Thoughts on Numerical Integration (Part 11): Simpson’s Rule and exploration of error analysis

Numerical integration is a standard topic in first-semester calculus. From time to time, I have received questions from students on various aspects of this topic, including:

  • Why is numerical integration necessary in the first place?
  • Where do these formulas come from (especially Simpson’s Rule)?
  • How can I do all of these formulas quickly?
  • Is there a reason why the Midpoint Rule is better than the Trapezoid Rule?
  • Is there a reason why both the Midpoint Rule and the Trapezoid Rule converge quadratically?
  • Is there a reason why Simpson’s Rule converges like the fourth power of the number of subintervals?

In this series, I hope to answer these questions. While these are standard questions in a introductory college course in numerical analysis, and full and rigorous proofs can be found on Wikipedia and Mathworld, I will approach these questions from the point of view of a bright student who is currently enrolled in calculus and hasn’t yet taken real analysis or numerical analysis.

In the previous post in this series, I discussed three different ways of numerically approximating the definite integral \displaystyle \int_a^b f(x) \, dx, the area under a curve f(x) between x=a and x=b.

In this series, we’ll choose equal-sized subintervals of the interval [a,b]. If h = (b-a)/n is the width of each subinterval so that x_k = x_0 + kh, then the integral may be approximated as

\int_a^b f(x) \, dx \approx h \left[f(x_0) + f(x_1) + \dots + f(x_{n-1}) \right] \equiv L_n

using left endpoints,

\int_a^b f(x) \, dx \approx h \left[f(x_1) + f(x_2) + \dots + f(x_n) \right] \equiv R_n

using right endpoints, and

\int_a^b f(x) \, dx \approx h \left[f(c_1) + f(c_2) + \dots + f(c_n) \right] \equiv M_n

using the midpoints of the subintervals. We have also derived the Trapezoid Rule

\int_a^b f(x) \, dx \approx \displaystyle \frac{h}{2} [f(x_0) + 2f(x_1) + \dots + 2f(x_{n-1}) + f(x_n)] \equiv T_n

and Simpson’s Rule (if n is even)

\int_a^b f(x) \, dx \approx \displaystyle \frac{h}{3} \left[y_0 + 4 y_1 + 2 y_2 + 4 y_3 + \dots + 2y_{n-2} + 4 y_{n-1} +  y_{n} \right] \equiv S_n.

In the previous post in this series, we saw that both the left-endpoint and right-endpoint rules have a linear rate of convergence: if twice as many subintervals are taken, then the error appears to go down by a factor of 2. If ten times as many subintervals are used, then the error should go down by a factor of 10. However, both the Midpoint Rule and the Trapezoid Rule have a quadratic rate of convergence: if twice as many subintervals are taken, then the error appears to go down by a factor of 4. If ten times as many subintervals are used, then the error should go down by a factor of 100. Moreover, it appears that the error from the Midpoint Rule is about half that of the Trapezoid Rule if the same number of subintervals are used.

Let’s now explore the results of Simpson’s Rule applied to \displaystyle \int_1^2 x^9 \, dx = 102.3 using different numbers of subintervals. The results are summarized in the table below.

 

The first immediate observation is that these approximations are far better than even the Midpoint and Trapezoid Rules! Indeed, we see that S_{20} \approx 102.301, using only 20 subintervals, is a better approximation than (from previous posts) either M_{100} = 102.290 or T_{100} \approx 102.319 using 100 subintervals! The lesson to learn again: Simpson’s Rule is a bit more difficult to compute than the Trapezoid Rule or the Midpoint Rule because of the different weights. Nevertheless, choosing a good algorithm is often far better than simply doing lots of computations.

There’s a second observation: the rate of convergence appears to be much, much faster. Indeed, the data points appear to fit a quartic polynomial very well. Said another way, if twice as many subintervals are taken, then the error appears to go down by a factor of 16. We can actually see this in the figure, looking at the lines with 10, 20, 40, and 80 subintervals.

Error with 10 subintervals = |102.3174904 - 102.3| = 0.0174904.

Error with 20 subintervals = |102.3011002 - 102.3| = 0.0011002.

Error with 40 subintervals = |102.3000689 - 102.3| = 0.0000689.

Error with 80 subintervals = |102.3000043 - 102.3| = 0.0000043.

In all cases, the error on the next line is about the error on the previous line divided by 16.

This illustrates quartic convergence, as opposed to the mere linear convergence of the left- and right-endpoint rules or the quadratic convergence of the Midpoint and Trapezoid Rules.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.