1

When applying Richardson Extrapolation to Euler Method, when isn't the local truncation error of h^2 used to get (4*Euler(h/2) - Euler(h)) / 3 instead of using the global error of h to get 2*Euler(h/2) - Euler(h)?

languageoftheuniverse
  • 19
  • Is Euler$(h)$ the approximation of the exact solution at a specific time $T$? In this case, it is possible to answer your question. You should write Euler$(T,h)$ to emphasize this, i.e. "Let Euler(T,h) denote the approximation of the exact solution at time $T$ obtained using time step $h$." – Carl Christian Aug 09 '19 at 13:42

2 Answers2

2

You want to compare two approximations at $t=h$. The error of two Euler steps at half step size is in the leading order $$ 2\cdot C\left(\frac h2\right)^2=\frac12\cdot Ch^2 $$ if the truncation error is locally $Ch^2$ for a step of size $h$.

Thus you get, if $Euler(h)$ denotes the method application to get to a fixed time $t$ with step size $h$, $$ Euler(h)=y+Ch^2 +O(h^3) $$ and with two steps of half the step size $$ Euler(h/2) =y+\frac12Ch^2+O(h^3). $$ Eliminating the term $Ch^2$ $$ 2\cdot Euler(h/2)-Euler(h)=y+O(h^3) $$ This is incidentally the explicit midpoint method $$ y(t+h)=y(t)+hf(t+\tfrac h2,\,y(t)+\tfrac h2f(t,y(t)))+O(h^3) $$

Lutz Lehmann
  • 126,666
  • In the case of Euler(h/2), shouldn't it be $$Euler(h/2)=y+C({\frac{h}{2}})^2+O({h^3})$$ hence it's $$Euler(h/2)=y+\frac{1}{4}C{h}^2+O({h^3})$$ – languageoftheuniverse Aug 10 '19 at 04:22
  • 1
    The aim is to compare two approximations at $t=h$. Thus you need 2 steps at half the step size. – Lutz Lehmann Aug 10 '19 at 04:23
  • Thanks. Got what you meant. That makes sense now. – languageoftheuniverse Aug 10 '19 at 04:29
  • Doesn't that mean the normal formulation of R.E. e.g. on Wiki page: $$R(h,t)={\frac {t^{n}(A^{}+C\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{}+Ch^{n}+O(h^{n+1}))}{t^{n}-1}}=A^{}+O(h^{n+1})$$ is not comparing the same point? i.e. Shouldn't it be $$R(h,t)={\frac {t^{n-1}(A^{}+tC\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{}+Ch^{n}+O(h^{n+1}))}{t^{n-1}-1}}=A^{}+O(h^{n+1})$$ in order to account for the smaller step size requiring more steps to reach the same point? – languageoftheuniverse Aug 10 '19 at 04:42
  • No, there it is like Ian said, $T(h)$ expresses the problem solved with a discretization parameter $h$. In that sense you should get here $Euler(h)=y(t)+Cth+O(th^2)$ for the computation of $y(t)$ from $y(0)$, so that the error explicitly expresses the global order $1$. – Lutz Lehmann Aug 10 '19 at 05:05
2

In general when you are applying Richardson extrapolation to a method $T(h)$, it should be an approximation of a fixed quantity $I$ which doesn't depend on $h$. Thus for instance for the Euler method, $T(h)$ is the result of running the Euler method with step size $h$ for a fixed ODE up to a fixed finite time. So the error that matters is the global error.

Ian
  • 101,645
  • Thanks for the comment. I tried both (4Euler(h/2) - Euler(h)) / 3 and 2Euler(h/2) - Euler(h) and looked at the error after 1 step and at T. As you explained, the error at time T is the global error therefore it makes sense that taking p = 1 and using 2Euler(h/2) - Euler(h) gets a better result. However, when I check the error at after the first step, the result is also better using 2Euler(h/2) - Euler(h) which confuses me as the local error after 1 step is h^2 so I would have expected (4*Euler(h/2) - Euler(h)) / 3 to produce the better result for a single step. What am I missing? – languageoftheuniverse Aug 10 '19 at 04:19
  • 1
    @languageoftheuniverse The problem is that although you can do one step of Euler at one step size to estimate, say, $x(h)$, you cannot approximate the same thing by taking one step of Euler at the smaller step size. You are still taking two steps of size $h/2$, so you commit two errors of size like $C(h/2)^2$ for a total of $Ch^2/2$, about half the size of the error from the larger step size. It is not 4 times less, because there were two of them. The same trend sticks when you take $O(1/h)$ steps to reach an $h$-independent final time. – Ian Aug 10 '19 at 04:34
  • Thanks I got that part now but my question shifts to how the R.E. is normally formulated as you see on Wiki does not seem to account for this accumulation of errors with the smaller step. i.e. $$R(h,t)={\frac {t^{n}(A^{}+C\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{}+Ch^{n}+O(h^{n+1}))}{t^{n}-1}}=A^{}+O(h^{n+1})$$ is not comparing the same point? i.e. Shouldn't it be $$R(h,t)={\frac {t^{n-1}(A^{}+tC\left({\frac {h}{t}}\right)^{n}+O(h^{n+1}))-(A^{}+Ch^{n}+O(h^{n+1}))}{t^{n-1}-1}}=A^{}+O(h^{n+1})$$ to account for the smaller step size requiring more steps to reach the same point? – languageoftheuniverse Aug 10 '19 at 04:47
  • @languageoftheuniverse It is awkward to think about it with the multiple steps explicitly in mind at all. It is simply that you have a method $T(h)$ for estimating one fixed quantity $I$ and you want to cook up a method $R(h)$ which is a linear combination of $T(h)$ and (in Wikipedia's notation) $T(h/t)$. Thus in Wikipedia's notation you simply have $n=1$, the order of the global error. Now the fact that computing $T(h/t)$ requires more time steps is irrelevant to the construction of $R$; this construction only knows the order of $T$. – Ian Aug 10 '19 at 04:55
  • Makes sense. Thanks. – languageoftheuniverse Aug 10 '19 at 04:57