Richardson Extrapolation Demostration

 https://personal.math.ubc.ca/~CLP/CLP2/clp_2_ic/ap_Richardson.html

C.1 Richardson Extrapolation

🔗

🔗

There are many approximation procedures in which one first picks a step size $ℎ$ and then generates an approximation $𝐴(ℎ)$ to some desired quantity $\mathcal{𝐴}\text{.}$ For example, $\mathcal{𝐴}$ might be the value of some integral ${\int }_{𝑎}^{𝑏}𝑓(𝑥)\mathrm{d}𝑥\text{.}$ For the trapezoidal rule with $𝑛$ steps, $\mathrm{\Delta }𝑥=\frac{𝑏-𝑎}{𝑛}$ plays the role of the step size. Often the order of the error generated by the procedure is known. This means

$$\begin{array}{}\text{(E1)}& \mathcal{𝐴}=𝐴(ℎ)+𝐾{ℎ}^{𝑘}+{𝐾}_1{ℎ}^{𝑘+1}+{𝐾}_2{ℎ}^{𝑘+2}+\cdots \end{array}$$

🔗

with $𝑘$ being some known constant, called the order of the error, and $𝐾,{𝐾}_1,{𝐾}_2,\cdots$ being some other (usually unknown) constants. If $𝐴(ℎ)$ is the approximation to $\mathcal{𝐴}={\int }_{𝑎}^{𝑏}𝑓(𝑥)\mathrm{d}𝑥$ produced by the trapezoidal rule with $\mathrm{\Delta }𝑥=ℎ\text{,}$ then $𝑘=2\text{.}$ If Simpson's rule is used, $𝑘=4\text{.}$

🔗

🔗

Let's first suppose that $ℎ$ is small enough that the terms ${𝐾}^{\prime }{ℎ}^{𝑘+1}+{𝐾}^{″}{ℎ}^{𝑘+2}+\cdots$ in (E1) are small enough¹ that dropping them has essentially no impact. This would give

$$\begin{array}{}\text{(E2)}& \mathcal{𝐴}=𝐴(ℎ)+𝐾{ℎ}^{𝑘}\end{array}$$

🔗

Imagine that we know $𝑘\text{,}$ but that we do not know $𝐴$ or $𝐾\text{,}$ and think of (E2) as an equation that the unknowns $\mathcal{𝐴}$ and $𝐾$ have to solve. It may look like we have one equation in the two unknowns $𝐾\text{,}$ $\mathcal{𝐴}\text{,}$ but that is not the case. The reason is that (E2) is (essentially) true for all (sufficiently small) choices of $ℎ\text{.}$ If we pick some $ℎ\text{,}$ say ${ℎ}_1\text{,}$ and use the algorithm to determine $𝐴({ℎ}_1)$ then (E2), with $ℎ$ replaced by ${ℎ}_1\text{,}$ gives one equation in the two unknowns $\mathcal{𝐴}$ and $𝐾\text{,}$ and if we then pick some different $ℎ\text{,}$ say ${ℎ}_2\text{,}$ and use the algorithm a second time to determine $𝐴({ℎ}_2)$ then (E2), with $ℎ$ replaced by ${ℎ}_2\text{,}$ gives a second equation in the two unknowns $\mathcal{𝐴}$ and $𝐾\text{.}$ The two equations will then determine both $\mathcal{𝐴}$ and $𝐾\text{.}$

🔗

🔗

To be more concrete, suppose that we have picked some specific value of $ℎ\text{,}$ and have chosen ${ℎ}_1=ℎ$ and ${ℎ}_2=\frac{ℎ}{2}\text{,}$ and that we have evaluated $𝐴(ℎ)$ and $𝐴(ℎ/2)\text{.}$ Then the two equations are

$$\begin{array}{}\text{(E3a)}& \mathcal{𝐴}& =𝐴(ℎ)+𝐾{ℎ}^{𝑘}\text{(E3b)}& \mathcal{𝐴}& =𝐴(ℎ/2)+𝐾(\frac{ℎ}{2}{)}^{𝑘}\end{array}$$

🔗

It is now easy to solve for both $𝐾$ and $\mathcal{𝐴}\text{.}$ To get $𝐾\text{,}$ just subtract (E3b) from (E3a).

$$\begin{array}{rl}(\text{E3a})-(\text{E3b}):& 0=𝐴(ℎ)-𝐴(ℎ/2)+(1-\frac{1}{2^{𝑘}})𝐾{ℎ}^{𝑘}\\ \text{(E4a)}& ⟹& 𝐾=\frac{𝐴(ℎ/2)-𝐴(ℎ)}{[1-2^{-𝑘}]{ℎ}^{𝑘}}\end{array}$$

🔗

To get $\mathcal{𝐴}$ multiply (E3b) by $2^{𝑘}$ and then subtract (E3a).

$$\begin{array}{rl}{2}^{𝑘}(\text{E3b})-(\text{E3a}):& [2^{𝑘}-1]\mathcal{𝐴}=2^{𝑘}𝐴(ℎ/2)-𝐴(ℎ)\\ \text{(E4b)}& ⟹& \mathcal{𝐴}=\frac{2^{𝑘}𝐴(ℎ/2)-𝐴(ℎ)}{2^{𝑘}-1}\end{array}$$

🔗

The generation of a “new improved” approximation for $\mathcal{𝐴}$ from two $𝐴(ℎ)$'s with different values of $ℎ$ is called Richardson² Extrapolation. Here is a summary

🔗

Equation C.1.1. Richardson extrapolation. 

 

Let $𝐴(ℎ)$ be a step size $ℎ$ approximation to $\mathcal{𝐴}\text{.}$ If

$$\mathcal{𝐴}=𝐴(ℎ)+𝐾{ℎ}^{𝑘}$$

🔗

then

$$𝐾=\frac{𝐴(ℎ/2)-𝐴(ℎ)}{[1-2^{-𝑘}]{ℎ}^{𝑘}}\mathcal{𝐴}=\frac{2^{𝑘}𝐴(ℎ/2)-𝐴(ℎ)}{2^{𝑘}-1}$$

🔗

This works very well since, by computing $𝐴(ℎ)$ for two different $ℎ$'s, we can remove the biggest error term in (E1), and so get a much more precise approximation to $\mathcal{𝐴}$ for little additional work.

🔗

Example C.1.2. Richardson extrapolation with the trapezoidal rule. 

🔗

Example C.1.3. Example 1.11.16 revisited.