Back to the on-screen lesson ·
Applying a quadrature rule panel by panel, the power of the panel width that survives in the total, and the combination that cancels it without new samples.
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 the order of a composite rule from its panel error, predict and measure how the error falls as panels are doubled, count the panels a target accuracy needs, and cancel the leading error term by combining two estimates.
You can apply the trapezoid, midpoint and Simpson rules over one panel, and you know each one's error term. This lesson asks what happens when the interval is cut into many panels and the rule is applied to each.
A composite rule applies a basic rule to every panel and adds the results. The order of a composite rule is the power of the panel width in its total error. Richardson extrapolation combines two estimates at different widths so that the leading error term cancels; applied repeatedly to the trapezoid rule it is Romberg integration.
Cut $[a,b]$ into $n$ panels of width $h = \dfrac{b-a}{n}$ and apply a rule to each. The bookkeeping that matters is this: a single trapezoid panel has error about $\dfrac{h^{3}}{12}f''$, and there are $n = \dfrac{b-a}{h}$ panels, so the total error is about $\dfrac{(b-a)h^{2}}{12}f''$ — one power of $h$ is handed back by the panel count. So the composite trapezoid and midpoint rules are second order (doubling $n$ divides the error by $4$) and composite Simpson is fourth (doubling $n$ divides it by $16$). Two consequences. First, the order is measurable: run at $n$, $2n$, $4n$ and take $\log_2$ of the ratios of successive errors — which is the only honest way to confirm that an implementation has the order it claims. Second, the order can be raised without new evaluations. If the error is $Ch^{2}$ then $4T(h/2) - T(h)$ cancels it, and $\dfrac{4T(h/2) - T(h)}{3}$ is exactly Simpson's rule. Doing that repeatedly up a table of halvings is Romberg integration, and it costs arithmetic rather than function values.
Another way: steps
Another way: example
$\int_0^{2}x^{3}$ is $4$. Trapezoid with one panel gives $8$, with two gives $5$. The errors are $4$ and $1$ — a factor of four, as second order predicts. And $\dfrac{4 \times 5 - 8}{3} = 4$: exact, from two second-order estimates and no new samples.
A rule's panel error and its composite error are different powers of $h$, and quoting the panel one is the commonest slip in this subject. The panel error of Simpson's rule is $h^{5}$ and the composite rule is fourth order, not fifth. The check is always the same: multiply by the number of panels, which is proportional to $1/h$, and see what survives.
Errors at $n = 10, 20, 40$ come out $4 \times 10^{-3}$, $10^{-3}$, $2.5 \times 10^{-4}$.
Ratios of four.
$\log_2 4 = 2$, so the rule is behaving as second order.
The claim is confirmed.
Had the ratios been $2$, the rule would be first order and something would be wrong — most often an endpoint the integrand is not smooth at.
The plot diagnoses as well as confirms.
$\int_0^1 \sqrt{x}$ has infinite derivative at $0$.
Not smooth at an endpoint.
The composite trapezoid error there falls like $h^{1.5}$, not $h^{2}$.
The hypothesis has failed.
So the combination $\tfrac{4T_2 - T_1}{3}$ cancels a term that is not there, and can be worse than $T_2$ alone.
Check the order before extrapolating.
Each doubling divides the error by $2^{4} = 16$.
$256 = 16^{2}$, so two doublings are needed.
The panel count is multiplied by four — against the sixteen a second-order rule would have needed.
The composite trapezoid rule is applied to $\displaystyle\int_0^{6} x^{2}\,dx$ with $1$, $2$ and $4$ panels. Give the error of each, as a fraction where it is not a whole number.
| Panels | Error | |
|---|---|---|
| One panel | 1 | |
| Two panels | 2 | |
| Four panels | 4 |
A single trapezoid panel of width $h$ has error proportional to $h^{3}$. The composite rule uses $14$ such panels to cover a fixed interval. What is the total error proportional to?
the composite midpoint rule is used on a smooth integrand, and its error with one panel is $2^{-4}$. On a plot of $\log_{2}(\text{error})$ against $\log_{2}(\text{panels})$ the points lie on a straight line. Give its slope and its value at one panel.
Slope of the line:
Value at one panel:
You want to check that a quadrature routine really has the order it claims, starting from $16$ panels. Put the five steps into order.
Number the steps in order (write the number in the box):
For $\displaystyle\int_0^{3} x^{3}\,dx$ the trapezoid rule gives $40.5$ with one panel and $25.3125$ with two. Combine them as $\dfrac{4T_2 - T_1}{3}$, and give that value and its error.
The combination is value and its error is error
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The composite trapezoid rule with $4$ panels leaves an error $E$. How many panels are needed to bring the error down to $\dfrac{E}{4^{3}}$?
Answer:
You can state and measure the order of a composite rule and extrapolate two estimates into a better one. Say in your own words why a panel error in the cube of the width gives a composite rule of second order.
8. Your turn: how many panels to improve a fourth-order rule by a factor of $256$?, step 3