Thoughts on Numerical Integration (Part 6): Connection between Simpson’s Rule, Trapezoid Rule, and Midpoint Rule

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.

There is a somewhat surprising connection between the last three formulas. Let’s divide the interval [a,b] into 2n subintervals with h = (b-a)/(2n) and x_0 = a, x_1 = x_0 + h, x_2 = x_0 + 2h, and so on. Then Simpson’s Rule becomes

S_{2n} = \displaystyle \frac{h}{3} \left[y_0 + 4 y_1 + 2 y_2 + 4 y_3 + \dots + 2y_{2n-2} + 4 y_{2n-1} +  y_{2n} \right].

Next, let’s divide the interval [a,b] into n subintervals, but let’s not redefine the values of h and the x_k. Instead, the width of each subinterval will be (b-a)/n, which is equal to 2h. (In other words, since there are half as many subintervals, each one is twice as long.) Also, the endpoints of these subintervals will be x_0 = a, x_2 = x_0 + 2h, x_4 = x_0 + 4h, and so on. So, keeping the same labeling convention as with Simpson’s Rule, the Trapezoid Rule becomes

T_n = \displaystyle \frac{2h}{2} [f(x_0) + 2f(x_2) + 2f(x_4) + \dots + 2f(x_{2n-2}) + f(x_{2n})]

= h [f(x_0) + 2f(x_2) + 2f(x_4) + \dots + 2f(x_{2n-2}) + f(x_{2n})].

(Again, the width of the subintervals in this case is 2h, where h = (b-a)/2n.) Furthermore, the midpoint of subinterval [x_0, x_2] will be x_1, the midpoint of subinterval [x_2,x_4] will be x_3, and so on. Therefore, keeping the same labeling convention, the Midpoint Rule becomes

M_n = \displaystyle 2h [f(x_1) + f(x_3) + f(x_5) + \dots + f(x_{2n-1}) ].

It turns out that \displaystyle \frac{2}{3} M_n + \frac{1}{3} T_n, a certain weighted average of T_n and M_n, is equal to

\displaystyle \frac{4h}{3} [f(x_1) + f(x_3) + \dots + f(x_{2n-1}) ] + \frac{h}{3} [f(x_0) + 2f(x_2) + \dots + 2f(x_{2n-2}) + f(x_{2n})]

= \displaystyle  \frac{h}{3} [f(x_0) + 4 f(x_1) + 2f(x_2) + \dots + 2f(x_{2n-2}) + 4 f(x_{2n-1} + f(x_{2n})]

= S_{2n}.

So, if the Midpoint Rule and the Trapezoid Rule have already been computed for n subintervals, then Simpson’s Rule for 2n subintervals can be computed at almost no additional effort.

Leave a Reply

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

You are commenting using your 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.