Return to Answer

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

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.

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.

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

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.

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

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.

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)) + \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$. The usual way to bound this local error is to assume a uniform bound on the derivatives of $f(t,x)$. 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.)

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.

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

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.