- 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?
where is the number of subintervals (which has to be even) and is the width of each subinterval, so that .
For this special case, the true area under the curve on the subinterval will be
In the above, the shorthand can be formally defined, but here we’ll just take it to mean “terms that have a factor of or higher that we’re too lazy to write out.” Since is supposed to be a small number, these terms will small in magnitude and thus can be safely ignored.
while we found the Trapezoid Rule approximation to be
Therefore, if there are subintervals, the Simpson’s Rule approximation of — that is, the area under the parabola that passes through , , and — will be . Since
,we see that
.We notice that something wonderful just happened: the first four terms of perfectly match the first four terms of the exact value of the integral! Subtracting from the actual integral, the error in this approximation will be equal to
Before moving on, there’s one minor bookkeeping issue to deal with. We note that this is the error for , where subintervals are used. However, the value of in this equal arose from and , where only subintervals are used. So let’s write the error with subintervals as
,where is the width of all of the subintervals. By analogy, we see that the error for subintervals will be
.But even after adjusting for this constant, we see that this local error behaves like , a vast improvement over both the Midpoint Rule and the Trapezoid Rule. This illustrates a general principle of numerical analysis: given two algorithms that are , an improved algorithm can typically be made by taking some linear combination of the two algorithms. Usually, the improvement will be to ; however, in this example, we magically obtained an improvement to .
One thought on “Thoughts on Numerical Integration (Part 20): Simpson’s rule and local rate of convergence”