6
$\begingroup$

It is known that a sufficient and necessary condition for $$\dot y(t) = f(y(t), t), \quad t > 0, \quad y(0) = y_0$$ to have a unique solution is $f$ Lipschitz in $y$ and continuous in $t$. However, I didn't find in the literature that this condition could guarantee the convergence of Euler's scheme (forward or backward) to the solution. Instead, additional condition imposed on $y$ that $y$ is $C^2$ seems needed, see for example http://persson.berkeley.edu/228A/Fall10/doc/lec05-2x3.pdf. I was wondering whether it was possible to weaken the condition for convergence of Euler's scheme.

$\endgroup$
  • $\begingroup$ Clearly $y$ must be $C^1$. If $y'(t)$ fails to be differentiable at finitely many points, it seems straightforward to extend the standard proof by applying it over each interval for which $y$ is $C^2$. The situation in which $y'(t)$ is non-differentiable at infinitely many points seems more interesting. $\endgroup$ – David Ketcheson Oct 26 '14 at 11:13
  • 1
    $\begingroup$ John Hubbard presents a slick proof that Euler's method converges to a solution (assuming only a lipschitz bound on $f$) in his undergraduate ODE courses. The proof is an elementary application of the Gronwal inequality. In French ODE literature (which Hubbard follows the conventions of) they tend to call this "the fundamental theorem of differential equations" or something to that effect. $\endgroup$ – Ryan Budney Mar 18 '15 at 3:55
4
$\begingroup$

Hmmm. Be careful: there's a difference between Euler's method converging, and Euler's method converging with rate $O(h)$. If $f$ is only continuous in $t$ and Lipshitz in $y$, then the global error is only guaranteed to shrink to zero as $h$ does. There is no guarantee on the rate: it can be arbitrarily slow. (FWIW, there's also a difference between the local error -- which is $O(h)$ -- and the global error -- which is only guaranteed to shrink to zero.) I don't think the conditions can be relaxed any further.

OTOH, if stronger conditions are imposed -- such as $y$ in $C^2$ as you mention -- then the local error is $O(h^2)$ and the global error is $O(h)$.

Not sure of a good resource to point you to. I'd have to dig through my textbooks. The Wackypedia article https://en.wikipedia.org/wiki/Truncation_error_(numerical_integration) has some pointers.

If you're looking for an example where Euler's method converges slowly, consider $f(t,y)=g(t) y$ where $g(t)$ is $C^0$ but not $C^1$. Say, the Weierstrass function, for example. Another related example that's similar but a bit different conceptually is Euler's method applied to a stochastic IVP. https://en.wikipedia.org/wiki/Euler%E2%80%93Maruyama_method and the pages linked from there are a start. Note the Euler-Maruyama method has a convergence rate of $O(h^{1/2})$, slower than $O(h)$ for the smooth case.

$\endgroup$
3
$\begingroup$

Forward Euler is convergent under mild conditions on $f(t,x)$, as explained below.

Let $\delta t$ be the time step size parameter (assumed to be constant for clarity's sake), let $T$ be the time span of simulation and set $t_k = k \delta t$ for any $k \in \mathbb{N}_0$. By integration by parts: $$ y(t_{k+1}) = y(t_k) + f(t_k,y(t_k)) \delta t + \int_{t_k}^{t_{k+1}} (t_{k+1} - s) \frac{d}{ds} f(s, y(s)) ds $$ Let $\epsilon_k$ denote the global error of the forward Euler scheme. Since $f$ is Lipschitz we have that: $$ \epsilon_{k+1} \le (1+ L_f \delta t) \epsilon_k + \underbrace{\| \int_{t_k}^{t_{k+1}} (t_{k+1} - s) \frac{d}{ds} f(s, y(s)) ds \|}_{\text{local error of forward Euler}} $$ where $L_f$ is the Lipschitz constant of $f(t,x)$. The usual way to bound the local error appearing in this last inequality is to assume a uniform bound on the derivatives of $f(t,x)$ that enables you to pull these derivatives out of the time integral. Let us take a slightly differently approach that requires less stringent assumptions on $f(t,x)$.

By Cauchy-Schwarz inequality: $$ \epsilon_{k+1} \le (1+ L_f \delta t) \epsilon_k + (\int_{t_k}^{t_{k+1}} (t_{k+1} - s)^2 ds)^{1/2} (\int_{t_k}^{t_{k+1}} \|\frac{d}{ds} f(s, y(s))\|^2 ds )^{1/2} $$ This recursion inequality simplifies to: $$ \epsilon_{k+1} \le (1+ L_f \delta t) \epsilon_k + \delta t^{3/2} M $$ where we have introduced a constant $M>0$ which we assume satisfies $$ (\int_{0}^{T} \|\frac{d}{ds} f(s, y(s))\|^2 ds )^{1/2} \le M \tag{$\star$} $$ By induction (or discrete Gronwall's Lemma), it follows that: $$ \epsilon_{k} \le \frac{e^{L_f T} M}{L_f} \; \delta t^{1/2} $$ for all $k \in \mathbb{N}$ satisfying $t_k < T$. Note that ($\star$) may hold even if $f(t,x)$ is just Lipschitz-continuous in $x$. Indeed, Rademacher's Theorem implies that a Lipschitz function is differentiable almost everywhere. The price for this more mild assumption is that the theoretical rate of convergence drops from $\mathcal{O}(\delta t)$ to $\mathcal{O}(\delta t^{1/2})$.

However, numerical evidence seems to indicate this estimate is a bit pessimistic. Consider the initial value problem $$ \dot y=|y|/2-(y-1) \;, \quad y(0)=-2.3 \;, $$ where the right hand side is Lipschitz, but not differentiable at $0$. Here is a figure of the true solution over the time interval $[0,1]$. (I selected this solution so that $y(1)$ is close to the point where the right hand side of the differential equation $|x|/2-(x-1)$ is not differentiable.)

true solution

Here is a figure of the relative error of forward Euler with respect to a converged target. (This metric of convergence is commonly used in the absence of an analytical solution.)

relative error

For a MATLAB function file that reproduces this last figure click here.

$\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.