The error in some numerical quadrature depends on the number of nodes
used which the user has to select. It is desirable to have an automatic
algorithm where the user specifies the error ε that is
acceptable and the algorithm should select the number of nodes n so
that
The error clearly depends on the
smoothness of the integrand f also. If f has a singularity, e.g.,
f(x)=x has singular derivatives at x=0, then the error will
be large. To have an acceptable error we must use a large n (small
h). But this will increase the number of nodes. Actually, most of the
error will come from the region near the singularity and we can use a
small h only in those regions, and not everywhere. This requires the
ability to use non-uniformly spaced nodes in the numerical integration
formula, and all the composite rules allow us to do this.
Note that we have a decomposition of the total error into error
contributions from each of the sub-intervals. If f(4) is large in
some sub-interval, we should choose the length of that sub-interval
x2j−x2j−2 to be small, in order to reduce the error. The best
strategy is to equi-distribute the error among all the sub-intervals.
Define
We will assume that we can estimate Mj and hence we can estimate the
error. The algorithm will iteratively increase the number of
sub-intervals until the desired error level is reached.
Start with three nodes, i.e., one Simpson rule, and compute I2(f)
and estimate the error. If ∣I(f)−I2(f)∣≤ϵ, then we
stop and the answer is I2(f).
Otherwise, insert a point mid-way between the three points and use
two Simpson rules. Estimate the error from each rule. If both errors
are ≤ϵ/2, then stop.
If not, suppose first error >ϵ/2 and second error
≤ϵ/2. Refine the first Simpson rule by inserting two
points.
Now the error from the first two rules must be ≤ϵ/4. If
this is true, then we stop.
We may not be able to estimate the derivatives, and the only information
available is the function values. We can approximate the derivatives by
first constructing a local approximation and differentiating it. But we
have seen other ways to estimate the error in integral, e.g., using
Richardson extrapolation.