Euler's method - Order of accuracy
Theorem
Let $f \in C([a,b] \times \mathbb{R})$ a function that satisfies the Lipschitz condition and let $y \in C^2[a,b]$ the solution of the ODE $\left\{\begin{matrix} y'=f(t,y(t)) &, a \leq t \leq b \\ y(a)=y_0 & \end{matrix}\right.$.
If $y^0, y^1, \dots, y^N$ are the approximations of Euler's method for uniform partition of $[a,b]$ with step $h=\frac{b-a}{N}$
then $$\max_{0 \leq n \leq N} |y(t^n)-y^n| \leq \frac{M}{2L} (e^{L(b-a)}-1)h$$
where $M=\max_{a \leq t \leq b} |y''(t)|$.
From the above theorem, we conclude that the order of accuracy of Euler's method is at least $1$.
We will show that the order of accuracy of Euler's method is exactly $1$.
We consider the following ODE:
$\left\{\begin{matrix} y'=2t &, 0 \leq t \leq 1 \\ y(0)=0 & \end{matrix}\right.$
Its only solution is $y(t)=t^2,\ \ 0 \leq t \leq 1$.
Let $N \in \mathbb{N}, \ h=\frac{1}{N}, \ \ t^n=nh, \ n=0,1, \dots, N$
$$y^{n+1}=y^n+hf(t^n, y^n) \Rightarrow y^{n+1}=y^n+h2t^n=y^n+h2nh=y^n+2nh^2$$
$$y^0=y(0)=0$$
$$y^1=y^0+2 \cdot 0 \cdot h^2=0$$
$$y^2=y^1+2h^2=2h^2$$
$$y^3=y^2+2 \cdot 2 \cdot h^2=2h^2+4h^2=2h^2(1+2)$$
$$y^4=y^3+2 \cdot 3 \cdot h^2=2h^2(1+2)+ 2 \cdot 3 \cdot h^2=2h^2(1+2+3)$$
$$\dots \dots$$
$$y^n=2h^2 \sum_{i=1}^{n-1} i=2h^2 \frac{(n-1)n}{2}=n(n-1)h^2$$
For $n=N$: $y^N=N(N-1)h^2=(Nh-h) Nh=1-h$
$|y(t^N)-y^N|=|1-1+h|=h$
Theorefore, we conclude that the order of accuracy is exactly $1$.
According to the theorem:
$$\max_{0 \leq n \leq N} |y(t^n)-y^n| \leq \frac{M}{2L} (e^{L(b-a)}-1)h$$
So, why do we conclude that the order of accuracy of Euler's method is at least $1$ and not at most $1$?
Also, we take into consideration that the order of accuracy of the method is at least $1$ and then we take an example of an ODE and see that the order of accuracy is exactly $1$. Why do we conclude in this way something for the general case?
How do we deduce that for each ODE the same holds?
$\endgroup$1 Answer
$\begingroup$You got an upper estimate that is $O(h)$. Nothing is preventing the left side to be of order $O(h^2)$, except that then the standard proof of the accuracy order would be highly inefficient.
Next you got provided an example where the left side is actually $O(h)$. This shows that there can be no general upper estimate of order $O(h^2)$, even if in special cases, $y'=const$, the method is exact.
In the general philosophy that things that go wrong (under cleanly formulated assumptions) do so in a generic manner, examples where the actual accuracy is better than $O(h)$ are the exception.
$\endgroup$ 2
