Conditions for convergence of Euler's method

Question

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.

Answer 1

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{\left\| \int_{t_k}^{t_{k+1}} (t_{k+1} - s) \frac{d}{ds} f(s, y(s)) ds \right\|}_{\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 + \left(\int_{t_k}^{t_{k+1}} (t_{k+1} - s)^2 ds\right)^{1/2} \left(\int_{t_k}^{t_{k+1}} \|\frac{d}{ds} f(s, y(s))\|^2 ds \right)^{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 $$ \left(\int_{0}^{T} \|\frac{d}{ds} f(s, y(s))\|^2 ds \right)^{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.)

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.)

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

Answer 2

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.