Suppose your integrand is f(x) and f has a power series expansion about the point q whose coefficients do not go wild. We can then write, for x near q
Suppose now we want the area under f between q - d and q + d, which is an interval of width 2d.
We can figure out the answer: exactly, by integrating each and every term, or approximately, by stopping at some point and summing the results of integrating the terms up to that point.
If we do either, you will notice that the terms with an odd power in (x - q) do not contribute at all. (they just tilt the contributions in a way that averages to nothing in any interval that is symmetric about its center.) The area under f will then consist of 2d*f(q) from the first term and then from the third term and then another contribution proportional to from the fifth term, and so on.
Now suppose instead we approximate by the left hand rule: This approximates the area by 2d*f(q - d) which has a contribution from the second term, and that contribution is proportional to d2.
This d2 term is wrong, and the relative error is the ratio of it to the first term. When the contribution from the first term is not 0, this relative error is proportional to d.
On the other hand, if we approximate the area by something symmetric between the endpoints of the interval, the odd terms will cancel out, and the error, coming from the third and later terms will be proportional to d3, and the relative error (since the first term is proportional to d) will be proportional to d2.
There are two obvious choices for symmetric "rules", either of which has error that decreases as d2. These are: take half of the value at q - d and half at q + d; or take the value at q itself. The first is the trapezoid rule and the second is the no-name rule. (In practice, the no-name rule is slightly better than the trapezoid rule in accuracy.)
A sneaky trick is to take a combination of the trapezoid and no-name rules chosen to get the contribution to the area of the interval from the quadratic term in the power series expansion exactly right. Then the first term in the error will come from the quartic term in the power series expansion, and it decline relative to the main contribution as d4 does.
The result is called Simpson's rule. We can deduce what it is by noticing what the quadratic term contributes to the true area between q - d and q + d: integrating between these two points gives you (the combines with the fact that you get contributions at both endpoints to give 1). The no-name rule gets no contribution from the quadratic term while the trapezoid rule gets a contribution lacking the that comes from integrating , from the true answer. In other words, it gets a contribution, from that term, of , which is three times too much.
Simpson's rule therefore says: take of the trapezoid rule, and of the no-name rule. Since the trapezoid rule gives weight of d to each end of the interval and the no-name rule gives weight 2d to the center of it, taking the combination gives weight to each end and to the middle point. If you sum this up over a sequence of intervals you get weights of multiplied by 1 4 2 4 2 4 ... 4 1, where the 4's go in the middle of intervals and the 2's at the ends. The separation between adjacent evaluation points here is d.
How can you do better?
Most of the time you won't need to do better, because the error here goes as d4 which, for d on the order 10-4 is on the order of 10-16 and that should make the error quite negligible. If it does not, your function may have some horrible behavior in your region of integration, and no improvement in method will help it much.
However you can do better.
How? Why do you make me repeat myself?
What we can do is to put in a combination of contributions from evaluating f at q, and q plus and minus d, and also at q plus and minus 2d, so that the quartic term comes out exactly right, and the quadratic term does so as well.
And how, how, how?
Well, if you take 16 parts of Simpson's rule with separation d as above, and 1 part of Simpson's rule with separation 2d, the contributions to the error from the quartic term will cancel. So, if we call the result of applying Simpson's rule with separation j, the combination will give the correct answer in up to the terms of order
Why did you divide by 15 here?
I did so because the combination gives the correct answer 16 -1 or 15 times, as well as any error it has. This is 15 times too much.
You mean to say, you can improve the accuracy of Simpson's rule with evaluation point separation d by combining it with a less accurate (separation 2d) Simpson's rule answer?
Exactly so. And moreover, Simpson's rule is the same kind of improvement of the trapezoid rule. In fact if we define to be the result of using the trapezoid rule with evaluation separation d, then . This comes from the fact that the error in , to a first approximation, is of the error in .
So you are saying, that starting with the trapezoid rule for evaluation separation d, you can combine it with less accurate trapezoid rule results at separations 2d and 4d, and end up with something whose error is the order d6? And the trapezoid rule answer is just the average of the left and right hand rule answers?
Right you are. And this means it is quite easy to do all these things.