📂Numerical Analysis

Initial Value Variation and the Error in the Euler Method

Theorem

The solution $Y(x)$ to the initial value problem $\begin{cases} y ' = f(x,y) \\ y( x_{0} ) = Y_{0} \end{cases}$ defined in $[x_{0} , b] \times \mathbb{R}$ with respect to $f$, is $Y \in C^{3} [ x_{0} , b ]$ if $\displaystyle f_{y} (x,y) = {{ \partial f (x,y) } \over { \partial y }}$ and $\displaystyle f_{yy} (x,y) = {{ \partial^{2} f (x,y) } \over { \partial y^{2} }}$ are both continuous and bounded. Let’s say the initial value $y_{h} (x_{0} )$ satisfies $Y_{0} - y_{h} (x_{0} ) = \delta_{0} h + O ( h^2 )$. Then, the error produced by the Euler method satisfies the following for the solution $D(x)$ to the linear initial value problem $$ \begin{cases} \displaystyle D’ (x) = f_{y} (x, Y(x) ) D(x) + {{1} \over {2}} Y’’ (x) \\ D ( x_{0} ) = \delta_{0} \end{cases} $$. $$ Y(x_{n} ) - y_{h} (x_{n} ) = D(x_{n} ) h + O (h^2) $$

Explanation

The statement that the initial value $y_{h} (x_{0} )$ satisfies $Y_{0} - y_{h} (x_{0} ) = \delta_{0} h + O ( h^2 )$ implies that the initial value can slightly differ from the true value. Moreover, the error that arises from this difference can further be reduced if one can calculate $D$.

Proof ¹

Strategy: Assume a strong Lipschitz condition and establish $\epsilon_{n} = O ( h^2)$, $g_{n}$, and $k_{n}$ to prove it. The proof technique might seem a bit stubborn due to the extensive manipulation of formulas, which is quite common in numerical analysis. Though it might not be a beautiful proof, becoming familiar with this method itself is beneficial.

$x_{i} : = x_{0} + ih$, especially, $x_{n+1} - x_{n} = h$. For convenience, let’s use $$ Y(x_{n} ) := Y_{n} $$ $$ y(x_{n}) := y_{n} $$ and express the error at the $n$th step as $\epsilon_{n}$ like this. $$ \epsilon_{n} : = Y(x_{n}) - y (x_{n} ) $$

---

Part 1.

If we take the $3$rd Taylor expansion of $Y(x_{n+1} )$ with respect to $ x_{n}$, for some $x_{n} \le \xi_{n} \le x_{n+1}$, $$ Y_{n+1} = Y_{n} + h Y’_{n} + {{h^2} \over {2}} Y’’ ( x_{n} ) + {{h^3} \over {6}} Y’’’ ( \xi_{n} ) $$ from which we get the following formula using the Euler approximation. $$ \begin{align} \displaystyle \epsilon_{n+1} = \epsilon_{n} + h ( f( x_{n} , Y_{n} ) - f (x_{n} , y_{n}) ) + {{h^2} \over {2}} Y’’ ( x_{n} ) + {{h^3} \over {6}} Y’’’ ( \xi_{n} ) \end{align} $$ Viewing $f(x_{n} , y_{n})$ of $(1)$ as a function of $y_{n}$ and taking its Taylor expansion, for some $\zeta_{n} \in \mathscr{H} \left\{ y_{n} , Y_{n} \right\} $, $$ f(x_{n} , y_{n} ) = f(x_{n} , Y_{n} ) + (y_{n } - Y_{n}) f_{y} (x_{n} , Y_{n} ) + {{1} \over {2}} ( y_{n} - Y_{n} )^2 f_{yy} (x_{n} , \zeta_{n} ) $$ Therefore, $$ \epsilon_{n+1} = \epsilon_{n} + h \left( \epsilon_{ n } f_{y} (x_{n} , Y_{n} ) - {{1} \over {2}} \epsilon^2 f_{yy} (x_{n} , \zeta_{n} ) \right) + {{h^2} \over {2}} Y’’ ( x_{n} ) + {{h^3} \over {6}} Y’’’ ( \xi_{n} ) $$ Summarizing, $$ \epsilon_{n+1} = [ 1+ f_{y} (x_{n} , Y_{n} ) ] \epsilon_{n} + {{h^2} \over {2}} Y’’ ( x_{n} ) + {{h^3} \over {6}} Y’’’ ( \xi_{n} ) - {{1} \over {2}} h f_{yy} (x_{n} , \zeta_{n} ) \epsilon_{n}^{2} $$

---

Part 2.

Strong Lipschitz condition and error in the Euler method: $$\max_{ x_{0 } \le x_{n} \le b } | Y_{x_{n}} - y_{h} (x_{n}) | \le \epsilon^{( b - x_{0} ) K} | \epsilon_{0} | + \left[ {{ \epsilon^{(b- x_{0}) K } - 1 } \over {K}} \right] \tau (h)$$

Since $\epsilon = O (h)$, $$ {{h^3} \over {6}} Y’’’ ( \xi_{n} ) - {{1} \over {2}} h f_{yy} (x_{n} , \zeta_{n} ) \epsilon_{n}^{2} = O (h^{3} ) $$ and assuming $O ( h^3)$ is sufficiently small, we can define $g_{n+1}$ with $O ( h^3)$ eliminated as follows. $$ g_{n+1} : = [ 1+ f_{y} (x_{n} , Y_{n} ) ] g_{n} + {{h^2} \over {2}} Y’’ ( x_{n} ) $$ Given $g_{0} = h \delta_{0}$ from the assumption, we set $g_{n} = h \delta_{n}$, and eliminating $h$ from both sides gives $$ \delta_{n+1} : = \delta_{n} + h \left[ f_{y} (x_{n} , Y_{n} ) \delta_{n} + {{1} \over {2}} Y’’ ( x_{n} ) \right] $$ Slightly organizing this gives $$ {{\delta_{n+1} - \delta_{n} } \over {h}} = f_{y} (x_{n} , Y_{n} ) \delta_{n} + {{1} \over {2}} Y’’ ( x_{n} ) $$ noticing the form of this equation, it resembles the linear initial value problem $\begin{cases} \displaystyle D’ (x) = f_{y} (x, Y(x) ) D(x) + {{1} \over {2}} Y’’ (x) \\ D ( x_{0} ) = \delta_{0} \end{cases}$. Eventually, $\delta_{n}$ is the Euler approximate solution of $D(x_{n} )$, i.e., $D(x_{n} ) - \delta_{n} = O (h) $. By the definition of $g_{n}$, multiplying both sides by $h$ gives $$ g_{n} = D ( x_{n} ) h + O ( h^2 ) $$

---

Part 3.

If we set $k_{n} : = e_{n} - g_{n}$, $$ k_{n+1} = [ 1 + h f_{h} (x_{n} , y_{n} ) ] k_{n} + O(h^3) $$ and since $f_{y}$ is bounded, for some $K \ge 0$, $$ | k_{n+1} | \le ( 1 + h K ) | k_{n} | + O(h^3) $$ Unfolding recursively gives $$ |k_{n}| = O(h^2) + O (h^3 ) = O(h^2) $$ Therefore, $$ \begin{align*} \epsilon_{n} =& g_{n} + k_{n} \\ =& [ h D (x_{n} ) + O(h^2) ] + O(h^2) \\ =& O(h^2) \end{align*} $$

■