Verifying the Euler Method

Recall the existence (and uniqueness) of solutions to first order initial value problems, particularised to $n = 1$ .

Theorem 1. Let $D = [a_0, b_0] \times [a_1, b_1] \subseteq \mathbb R \times \mathbb R$ be a closed rectangle. Fix $(t_0, \mathbf y_0) \in \mathrm{int}(D)$ . Suppose $f : D \to \mathbb R$ is a map that satisfies the following properties:

For any $y \in [a_1, b_1]$ , $f(\cdot, y)$ is continuous.
There exists $L > 0$ such that for any $t \in [a_0, b_0]$ , for any $y_1, y_2 \in [a_1, b_1]$ , $| f(t, y_1) - f(t, y_2) | \leq L \cdot | y_1 - y_2 |$ . In this case, we say that $f$ is $L$ -Lipschitz in the second argument.

Then there exists $\epsilon > 0$ and a unique function $y = y( \cdot )$ that satisfies the initial value problem

$y'(t) = f(t, y(t)),\quad y(t_0) = y_0$

for $t \in [t_0 - \epsilon, t_0 + \epsilon]$ .

Proof. See this post.

Many a time, even if such a function $y$ exists, we may not have any analytic solution for it, for instance:

$y'(t) = e^{-t^2},\quad y(0) = 1.$

In this exercise, we prove that the approximate solution obtained from Euler’s method converges to the unique $y$ . We will assume $(t_0, y_0) = (0, 0)$ for simplicity, and aim to compute $y(1)$ . We will also assume that $y''$ is continuous for simplicity.

Theorem 2 (Euler’s Method). Suppose we have $y' = f(t, y)$ , $y(0) = 0$ . For any $h > 0$ such that $1/h \in \mathbb N$ without loss of generality, define $n := 1/h$ . For $k = 0,1,\dots, n-1$ , define

$y_{k+1} := y_k + h \cdot f(t_k, y_k).$

Then there exists a universal constant $C > 0$ such that applying Euler’s method with $n = 1/h$ steps, $| y_n - y(1) | \leq C \cdot h$ .

Proof. Problem 3, which you will prove later.

Theorem 2 states that as we decrease the step size (that is, take $h \to 0^+$ ), we obtain an increasingly accurate estimate for $y(1)$ , since $|y_n - y(1)| \leq C \cdot h \to 0$ .

The goal of this post is to prove Theorem 2. Firstly, we fix $n \in \mathbb N$ . For each $k$ , let $z_{k+1}$ denote the result obtained from applying one step of Euler’s method to $(t_k, y(t_k))$ . Define $e_k := y(t_k) - y_k$ . In particular,

$e_{k+1} = \underbrace{y(t_{k+1}) - z_{k+1}}_{ a_{k+1}} + \underbrace{z_{k+1} - y_{k+1}}_{b_{k+1}}.$

Problem 1. Define $M := \max_{t \in [0, 1]} |y''(t)| < \infty$ . For each $k$ , prove that $|a_{k+1}| \leq Mh^2/2$ .

(Click for Solution)

Solution. By the definition of $z_{k+1}$ ,

$z_{k+1} = y(t_k) + h \cdot f(t_k, y(t_k)).$

Hence,

$a_{k+1} = y(t_{k+1}) - z_{k+1} = y(t_{k+1}) - y(t_k) - h \cdot f(t_k, y(t_k)).$

By Taylor’s theorem, there exists $\gamma_k \in (t_k, t_{k+1})$ such that

$\begin{aligned} y(t_{k+1}) &= y(t_k) + y'(t_k) + \frac{ y''(\gamma_k) }{2} \cdot h^2 \\ &= y(t_k) + h \cdot f(t_k, y(t_k)) + \frac{ y''(\gamma_k) }{2} \cdot h^2. \end{aligned}$

Therefore,

$\displaystyle |a_{k+1}| = \frac{ |y''(\gamma_k)| }{2} \cdot h^2 \leq \frac{M}{2} \cdot h^2.$

Problem 2. For each $k$ , prove that $|b_{k+1}| \leq (1 + h L) \cdot |e_k|$ .

(Click for Solution)

Solution. By definition,

$\begin{aligned} y_{k+1} &= y_k + h \cdot f(t_k, y_k), \\ z_{k+1} &= y(t_k) + h \cdot f(t_k, y(t_k)). \end{aligned}$

Since $f$ is Lipchitz in the second argument, by the triangle inequality,

$\begin{aligned} |b_{k+1}| = |z_{k+1} - y_{k+1}| &\leq |y(t_k) - y_k| + h \cdot |f(t_k, y(t_k)) - f(t_k, y_k)| \\ &\leq |y(t_k) - y_k| + h \cdot L \cdot |y(t_k) - y_k| \\ &= (1 + h L) \cdot |y(t_k) - y_k| \\ &= (1 + h L) \cdot |e_k| .\end{aligned}$

Problem 3. Find a universal constant $C > 0$ , that does not depend on $n$ , such that $|e_n| \leq C \cdot h$ .

(Click for Solution)

Solution. Combining Lemmas 1 and 2,

$\displaystyle |e_{k+1}| \leq \frac{M h^2}2 + (1 + h L) \cdot |e_k|.$

Illustrating using $k = 1$ ,

$\begin{aligned} |e_2| &\leq \frac{M h^2}2 + (1 + h L) \cdot |e_1| \\ &\leq \frac{M h^2}2 + (1 + h L) \cdot \left( \frac{M h^2}2 + (1 + h L) \cdot |e_0| \right) \\ &\leq (1 + h L)^2 \cdot |e_0|+ (1 + (1 + h L)) \cdot \frac{M h^2}2 . \end{aligned}$

In a similar manner, by induction and the geometric series,

$\begin{aligned} |e_{k+1}| &\leq (1 + h L)^{k+1} \cdot |e_0|+ (1 + (1 + h L) + \cdots + (1 + h L)^k) \cdot \frac{M h^2}2 \\ &= (1 + h L)^{k+1} \cdot |e_0|+ \frac{(1 + hL)^{k+1} - 1}{(1+hL) - 1} \cdot \frac{M h^2}2 \\ &= (1 + h L)^{k+1} \cdot |e_0|+ \frac{(1 + hL)^{k+1} - 1}{L} \cdot \frac{M h}2. \end{aligned}$