Back to the on-screen lesson ·
Richardson extrapolation applied to a whole table of trapezoid values: two orders per column, a family of classical rules produced without deriving any of them, and the expansion it all rests on.
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 carry out a Romberg extrapolation, say why each column gains two orders, name what each column turns out to be, count the function evaluations a row costs, and say which integrands the construction fails on.
You know the composite trapezoid rule and its $O(h^{2})$ error, and you know Richardson extrapolation: assume the error is a known power of the step, evaluate twice, and combine so that the assumed term cancels. Romberg is that device applied over and over to the same rule.
The Euler-Maclaurin expansion gives the trapezoid error as $c_2h^{2} + c_4h^{4} + \cdots$ — even powers only, for a smooth integrand on a finite interval. A Romberg table is the triangle $R_{n,k}$ whose first column is trapezoid values at halved steps and whose later columns are extrapolations. A diagonal entry $R_{n,n}$ is the most extrapolated value of its row.
The composite trapezoid rule on a smooth integrand has error $I - T(h) = c_2h^{2} + c_4h^{4} + c_6h^{6} + \cdots$, an expansion in even powers only. Halving the step divides the leading term by four, so
$$R_{n,1} = \frac{4R_{n,0} - R_{n-1,0}}{3}$$
cancels it — and what is left is Simpson's rule, with error $O(h^{4})$, derived without fitting a parabola to anything. The next term is $h^{4}$, cancelled by the same combination with $16$ in place of $4$, giving $O(h^{6})$; in general $R_{n,k} = \dfrac{4^{k}R_{n,k-1} - R_{n-1,k-1}}{4^{k} - 1}$, gaining two orders per column because the odd powers were never there. The cost is the striking part: row $n$ uses $2^{n}$ panels and so $2^{n} + 1$ function values, every one of which is reused from the rows above, and the extrapolations themselves are arithmetic on numbers already computed. The whole construction rests on the expansion, and that is where it fails: an integrand with a kink, a singular endpoint or an infinite interval has no such expansion, the columns cancel terms that are not there, and the higher ones can be worse than the first.
Another way: steps
Another way: picture
Draw the table as a lower triangle. The left column is the only one that costs anything — each entry there is a run of the trapezoid rule — and every entry to its right is a weighted difference of the two entries above and to its left. Accuracy improves downwards, because the step is halving, and rightwards, because terms are being cancelled; the bottom right corner has both and is the answer.
The table is applied to any integrand at all, on the strength of it being arithmetic that cannot fail. It cannot fail to produce numbers, which is worse. Each column removes a term the Euler-Maclaurin expansion says is there, and for $\sqrt{x}$ on $[0, 1]$ that expansion does not hold: the leading error behaves like $h^{3/2}$, the extrapolations cancel nothing, and the diagonal converges more slowly than the first column. The symptom is the diagonal entries disagreeing when they should be agreeing quickly, and the repair is to remove the singularity by substitution before integrating.
$\int_0^1 \dfrac{4}{1 + x^{2}}\,dx = \pi$. Trapezoid: $R_{0,0} = 3$, $R_{1,0} = 3.1$, $R_{2,0} = 3.131$.
The first column.
$R_{1,1} = \dfrac{4(3.1) - 3}{3} = 3.1333$, $R_{2,1} = 3.1416$.
Simpson, for free.
$R_{2,2} = \dfrac{16(3.1416) - 3.1333}{15} = 3.14212$ — from five function values.
Two orders better again.
$\int_0^1 \sqrt{x}\,dx$: the trapezoid error behaves like $h^{3/2}$, not $h^{2}$.
No even expansion.
The extrapolations remove an $h^{2}$ term that is not there and the diagonal crawls.
Arithmetic that cannot fail, failing.
The combination is $\dfrac{4T(h/2) - T(h)}{3}$.
$= \dfrac{9.2 - 2}{3} = \dfrac{7.2}{3}$.
$= 2.4$ — past both values, as an extrapolation should be, since the trapezoid rule was approaching the answer from one side.
The composite trapezoid rule gives $T(h) = 4$ and $T(h/2) = 5$. What does one Romberg extrapolation give? Give a fraction.
Answer:
The trapezoid column of a Romberg table has error $O(h^{2})$. Give the exponent of $h$ in the error after $3$, $4$ and $5$ extrapolations.
| Extrapolations | Exponent of $h$ in the error | |
|---|---|---|
| $3$ extrapolations | 3 | |
| $4$ extrapolations | 4 | |
| $5$ extrapolations | 5 |
Put the five steps of building and reading a Romberg table into order.
Number the steps in order (write the number in the box):
Match each column of a Romberg table to what it is.
| Composite trapezoid, $O(h^{2})$, the only column costing evaluations | Composite Simpson, $O(h^{4})$, from the factor $4$ | Boole's rule, $O(h^{6})$, from the factor $16$ | $O(h^{8})$, from the factor $64$, and with no common name | |
|---|---|---|---|---|
| The first column | ||||
| The second column | ||||
| The third column | ||||
| The fourth column |
Row $4$ of a Romberg table uses the composite trapezoid rule with the step halved $4$ times from the whole interval. How many function values have been used by the time that row is complete?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The composite trapezoid rule has error $10^{-2}h^{2}$ on a particular integrand. The base-ten logarithm of the error is plotted against the base-ten logarithm of $h$. Give the slope and the intercept.
the logarithm of the error against the logarithm of the step size
Slope of the line:
Intercept of the line:
You can build and read a Romberg table and state what it assumes. Say in your own words why each column gains two orders rather than one.
8. Your turn: extrapolate $T(h) = 2$ and $T(h/2) = 2.3$, step 3