2
$\begingroup$

On the wiki page for forward euler (https://en.wikipedia.org/wiki/Euler_method#Local_truncation_error), it describes the local truncation error like so:

$\mathrm{LTE} = y(t_0 + h) - y_1 = \frac{1}{2} h^2 y''(t_0) + O(h^3)$

How do you concretely interpret the $O(h^3)$?

Following the formal definition of big O notation as described here: https://en.wikipedia.org/wiki/Big_O_notation#Formal_definition, I think this would mean that there exists some $M$ and some $h_o$

$\left|\mathrm{y(t_0 + h) - y_1}\right| < M \left|h^3 \right|$ for all $0 <= h < h_o$

But in terms of having a concrete upper bound on error, (i.e. for a specific function within with a specific value of $t_0$ and $h$), I don't see why this is useful. Since $LTE = O(h^3)$ is satisfied as long as there exists any finite $M$ satisfying the above definition, doesn't that meant that the error could still be arbitrarily large? And if $M$ can be arbitrarily large, I don't even see why the error bound being $O(h^3)$ is any better than it being $O(h^2)$.

I'm asking about the concrete case because I'm trying to understand the implications for numerical computation.

$\endgroup$
  • $\begingroup$ You will note when re-reading your question that $|y(t_1)-y_1|\le \frac12·M_2|y''(t_0)|·h^2+M·h^3$ so that $LTE=O(h^2)$ as is standard for Euler methods. Or you could say that by mean value inequality $|y(t_1)-y_1|\le \frac12·M_2·h^2$ where $M_2$ bounds $y''=f'·f$. $\endgroup$ – LutzL Jul 24 '16 at 10:49
2
$\begingroup$

It's easier to think about in the integration context. Good integration rules proceed by exactly integrating a certain function which is close to the desired integrand. For example, the trapezoidal rule proceeds by exactly integrating a piecewise linear interpolant of the integrand. Its error depends on how far the integrand deviates from the piecewise linear interpolant. If you have a continuous second derivative, then this error can be bounded in terms of that second derivative (using Taylor's theorem) and the node spacing $h$. This can give you an actual bound on the constant in front.

Essentially the same thing goes through in the ODE context, but the estimates are more complicated and harder to visualize. In your case, you can, if you want, rephrase your estimate as $\frac{1}{2} h^2 y''(t_1)$ where $t_1$ now an unknown number between $t_0$ and $t_0+h$. Thus you lose concrete knowledge of the leading order term, but gain in that there aren't any other terms to think about at all.

Now in practice, you rarely can explicitly estimate the derivatives well enough to know what $h$ you need for a given tolerance. However, you can get an idea: if $|f(h)-f(0)|=Mh+o(h)$ ($f(h)$ is your numerical method, $f(0)$ is the exact value you want to calculate) then $|f(h)-f(h/2)|=Mh/2+o(h)$, so you can approximate $M$ by $\frac{2}{h} |f(h)-f(h/2)|$. This idea is used to get higher order methods in a technique called Richardson extrapolation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.