Use case
It is used to improve the accuracy of a numerical method to a higher order by combining results from different step sizes. It does this by eliminating the lower-order error terms from the asymptotic error expansion.
Mathematically
For a numerical method with approximation of the exact value, where the error has convergence order :
Here,
- is the convergence order of the original method
- The new approximation has convergence order (or for methods with only even error terms)
Note: Each extrapolation step increases the convergence order. For integration methods like trapezoid rule, the order increases by 2 in each iteration as the expansion contains only even powers of .
Examples:
- Trapezoid rule ():
- Simpson’s rule ():
Quadrature Method | Order of Convergence |
---|---|
Left Hand Rule | |
Midpoint Rule | |
Trapezoidal Rule | |
Simpson’s Rule |
Derivation of the Romberg Extrapolation
Consider a numerical method with error expansion:
The dominant error term is (lowest power, largest contribution). Elimination Process With two approximations:
Step 1: Multiply the second equation by :
Step 2: Subtract the first equation:
Step 3: Solve for :
Result
The term cancels out completely, leaving only higher-order error terms . This is what we mean by “eliminating” the lower-order error term.
Example For trapezoid rule with :
- Original error:
- After extrapolation: (the term is eliminated)
The approximation becomes much more accurate because we’ve removed the largest source of error.