Back to the on-screen lesson ·
Letting the integrand decide where the panels go: the local error estimate and where its divisor comes from, why the tolerance is split with the interval, and the feature such a routine cannot see.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to derive and compute a local error estimate for a rule of any order, explain why the tolerance is halved at each split, predict where an adaptive routine concentrates its panels, and say what the estimate is not evidence of.
You know composite rules, which spread panels evenly, and Richardson extrapolation, which compares a rule with itself at two step sizes. Adaptive quadrature uses the second to decide where the first should put its panels.
A panel is a subinterval the rule is applied to. A local error estimate is the difference between the rule on a panel and the rule on its halves, divided by $2^{p} - 1$ for a rule of order $p$. Tolerance splitting gives each half of a split panel half the tolerance, so that the parts' tolerances sum to the whole's. The recursion limit is the depth at which a routine gives up rather than subdividing for ever.
A composite rule spreads its panels evenly, which is the right thing to do only if the integrand is equally difficult everywhere. Adaptive quadrature asks each panel how it is doing. Apply the rule to the panel; apply it again to each half and add; the two values differ by about $2^{p} - 1$ times the error of the refined one, so
$$\text{error estimate} = \frac{A_{\text{halves}} - A_{\text{whole}}}{2^{p} - 1},$$
which for Simpson's rule is the familiar division by fifteen. If the estimate is within the panel's tolerance, accept and stop; otherwise split the panel, give each half half the tolerance, and recurse. The halving matters: without it the routine promises a tolerance per panel and delivers their sum over the interval. Two things are worth saying plainly about what this does and does not give. The estimate costs nothing extra — every value in it was computed anyway — and adding the estimated correction would raise the order by one, which most routines decline to do because a corrected value has no estimate of its own. And the estimate is a comparison of two approximations, not a bound: a feature narrower than the spacing of the sample points is invisible to both evaluations, their difference is tiny, and the panel is accepted with the feature missing entirely.
Another way: steps
Another way: picture
Draw a function that is flat across most of an interval with one narrow peak, and mark the panels an adaptive routine ends up with: three or four enormous ones across the flat part, and a cluster of tiny ones packed around the peak. Then draw the panels a composite rule would use for the same accuracy — the width of the smallest adaptive panel, all the way across. The picture is the entire argument for adapting.
The reported error estimate is read as a guarantee. It is the difference between two approximations that used the same handful of sample points, so it is reliable exactly when the coarse rule was already resolving the integrand — which is the thing it cannot check. A narrow spike between the sample points produces two identical values, a difference of zero, and an accepted panel. Tightening the tolerance does not help, because the difference was already zero. The defences are to look at the integrand first and to split the interval manually at any feature that is known about.
Simpson on a panel gives $3.140$; on the two halves it gives $3.1416$.
Two values.
Difference $0.0016$, so the estimated error of the refined value is $0.0016/15 \approx 10^{-4}$.
Divided by fifteen.
Against a panel tolerance of $10^{-6}$ this fails, and the panel is split.
The decision.
$\int_{-1}^{1}\dfrac{1}{10^{-4} + x^{2}}\,dx$: a tall narrow peak at $0$.
Difficult in one place only.
A composite rule needs a step small enough for the peak, everywhere: tens of thousands of panels.
Uniform refinement.
An adaptive routine uses a few dozen, nearly all of them near zero.
The same accuracy, a thousandth of the work.
The difference is $0.03$.
The estimated error of the refined value is $0.03/15 = 0.002$.
That is larger than $0.001$, so the panel is split and each half is given a tolerance of $0.0005$.
Simpson's rule on a panel gives $57$, and the same rule applied to each half and added gives $54$. What is the usual estimate of the error in the half-panel value? Give a fraction.
Answer:
An adaptive routine is given a tolerance of $\dfrac{1}{2}$ for the whole interval and halves the tolerance at each split. Give the tolerance handed to a panel at depth one, two and three. Give fractions.
| Depth | Tolerance for a panel | |
|---|---|---|
| Depth one | 1 | |
| Depth two | 2 | |
| Depth three | 3 |
Put the five steps of adaptive quadrature on one panel into the order they depend on each other.
Number the steps in order (write the number in the box):
Match each integrand to where an adaptive routine concentrates its panels.
| Almost no subdivision: the first panels are accepted | Panels pile up at one place and the rest is covered cheaply | Subdivision that never satisfies the tolerance, until the recursion limit | Uniform subdivision, so adaptivity buys nothing | |
|---|---|---|---|---|
| A smooth, slowly varying function | ||||
| A function with a narrow spike | ||||
| A function with a corner | ||||
| A function oscillating evenly throughout |
A composite rule has error $O(h^{4})$. It is applied to a panel and then to the two halves. Give the number the difference must be divided by to estimate the refined value's error, and the order the same combination reaches if the correction is added in.
Divide the difference by w; adding the correction reaches order z.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
An adaptive routine returns an answer and reports that every panel met its tolerance. A narrow spike of width one part in $10^{6}$ sits in the middle of the interval and is missing from the answer entirely. How did that happen?
You can derive and use an adaptive error estimate and state its limits. Say in your own words why a narrow spike can be missed by a routine that reports every panel as converged.
8. Your turn: a panel where Simpson gives $2.0$ whole and $2.03$ halved, with tolerance $0.001$, step 3