Consider the initial value problem $x' = x+e^{-x}$ , $x(0)= 0$. This problem can’t be solved analytically.
Using the Euler method, compute $x$ at $t = 1$, correct to three decimal places. How small does the stepsize need to be to obtain
the desired accuracy? (Give the order of magnitude, not the exact number.
I am not sure how to go about this, I was thinking guess and check but figured that would take too long. Is there a method for determining the stepsize given these conditions?
Any help or intuition would be greatly appreciated.
Best Answer
Consider a Taylor series expansion with the Lagrange remainder $$x(t+d) = x(t) + x'(t)d + \frac{x''(c)}{2}d^2,$$ where $t \leq c \leq t+d$. The Euler's method is basically a truncation of this expansion, so the error at each step is bound by the remainder term. Now $$x'' = \frac{df}{dx}x' = \frac{df}{dx}f(x) = (x + e^{-x})(1 - e^{-x}) < (x+1)x $$ So each step may introduce an error $\delta = \frac{(x(c) + 1)\cdot x(c)}{2}d^2$. To estimate it we need some bounds on $x$. Note that if $y' = y + 1,\ y(0) = 0$, then $x < y$, and there is an analytic solution $y(t) = e^t - 1$. So per step $$\delta = \frac{(x(c) + 1)\cdot x(c)}{2}d^2 < \frac{(y(c) + 1)\cdot y(c)}{2}d^2 < \frac{(y(1) + 1)\cdot y(1)}{2}d^2 = \frac{(e + 1)\cdot e}{2}d^2$$ Altogether there are $N = 1/d$ steps, and the full error is $$N\delta < \frac{(e + 1)\cdot e}{2}d \approx 5.054 \ d$$ You need $5.054\ d < 0.001$, so $d < 0.0002$ is enough. There might be a tighter estimate if you choose $y(t)$ more ingeniously.
UPDATE As LutzL poined out in his comment, we can take $y(t) = \sqrt 2\tan\frac{t}{\sqrt{2}}$. Then $y(1) \approx 1.208$ and $$N\delta < \frac{(y(1) + 1)\cdot y(1)}{2}d \approx 1.334\ d$$ which gives for the desired precision: $d < 0.0007$