Idea: improve accuracy by choosing quadrature points
carefully.
Facts: (1) with k equally spaced points, you can get
polynomial degree k if k is odd, k-1 if k is even. (2) with
k Gauss points, can get polynomial degree 2k-1.
Example. Suppose we want , , ,
such that is exact
for all on [-1,1].
So, require
System has a unique solution:
Remarks:
Derivation of Gauss rules for any k involves roots of
orthogonal polynomials as the points.
Points and weights are tabulated for many standard cases.
Points are different for each value of k, but there
are combinations of Gauss rules that allow you to reuse
function values as points are added.
Quadrature algorithms
Idea: use error (remainder) estimates to ...
Decide when your approximate solution is good enough (or when
you are not making any more progress).
Add function evaluation points only in some areas, but not in
others.
Improve the answer even more.
Example: adaptive quadrature with Simpson's method
Recall that the remainder term for Simpson looks like this:
Rn = c*h4 + O(h5).
So under reasonable assumptions, the remainder term with
twice as many points is
R2n = (c*h4)/16 + O(h5)
By simple algebra, it's easy to show that
R2n is approximately Rn/16.
And with a little more algebra,
R2n = (S2n - Sn)/15.
Remarks
So (S2n - Sn)/15 is a reasonable
stopping criterion.
Note that this error estimate can be done locally,
i.e., with respect to any subinterval of [a,b]. This is
important because it allows us to decide where to add more
points and where the answer is good enough.
Note also that we can still use the Richardson
extrapolation idea to
improve from O(h4) to O(h5) accuracy.
In this case, the appropriate formula is
(16 S2n - Sn)/15, which is
O(h5) accurate.