MATH/APPM 4650
Class notes, February 27
Romberg integration
Most of today's notes will be on the board. Here are the basic ideas.
Main idea:
Combine Richardson's extrapolation with the trapezoid rule.
Recall that Richardson's extrapolation can be used to give good estimates even if we start with pretty bad ones; we just have to understand the error.
The idea is to get a bunch of trapezoid approximations, say T1, T2, T4, T8, etc.
We use the fact that to compute e.g. T8 from T4, we only need 4 more computations.
In general,
This is not true for the midpoint rule! It doesn't even involve the same points. (Convince yourself of this.)
While Simpson's rule uses the same points, there is no similar formula; it uses the function values with different coefficients.
The other important thing to note is the general error formula for the trapezoid rule. It's not just any power series in h; it's a power series with only even terms.
Proving this is actually rather complicated. It's related to the Euler-Maclaurin formula. (Details here.)
The result is also true for the midpoint and Simpson rules, in case you were curious. (Details here.)
But we use trapezoid because it doesn't involve recomputing the entire sum to add points, unlike Simpson's rule.
Recall the general formula for Richardson's extrapolation, when the error terms are even.
We start with
then construct higher-order trapezoid sums recursively using the formula above.
This generates the first column (of just pure trapezoid approximations).
Then we apply the Richardson trick to get the future columns.
We can get really good results out of this.
Observe:
- Rk,1 (the first column) is a composite trapezoid rule with n=2k-1.
- Rk,2 (the second column) is a composite Simpson's rule.
- Rk,3 is the composite Newton-Cotes for n=4.
- Rk,4 is not any Newton-Cotes formula.
Why?