4
$\begingroup$

I am pretty sure that, for the iterates of the backward Euler's method for $y'=f(t,y)$ one cannot obtain $\displaystyle \frac{y_n-y_{n-1}}{\delta t}\rightarrow y'(t^*)$, for a suitable choice of $n$. The reason is that $y_n=y(t_n)$, but only at first order, so that $y_n-y_{n-1} = \delta t y'(t^*) + C\delta t$, and this $C$ need not to approach $0$.

I was only able, though, to construct examples where we get convergence also of the difference quotients (e.g. $y'=ay$ ...). Do you have a counterexample, and possibly a descriptions of the class of functions $f$ on which backward Euler is of higher order than $1$? It seems that $f(t,y)=y$, for instance, is in this class.

Edit

Actually, the derivative approximation property might be true by a bootstrapping argument: $\displaystyle \frac{y_n-y_{n-1}}{\delta t} = f(t_n,y_n)=f(t^*,y(t^*)) + f_t(t^*,y(t^*))(t-t^*)+f_y(t^*,y(t^*))(y_n-y(t^*)) + o((t-t^*, y_n-y(t^*)))$.

So that $f\in C^1$ suffices, thanks to the convergence $t_n\rightarrow t^*, y_n \rightarrow y(t^*)$. What do you think?

$\endgroup$

2 Answers 2

4
$\begingroup$

The situation is indeed somewhat complicated as you have two convergences to consider, the convergence of the difference quotient and the convergence of the numerical solutions as $δt\to 0$. It should be without doubt that $$ \frac{y(t_n)-y(t_{n-1})}{t_n-t_{n-1}}\to y'(t^*) $$ where $y(t)$ is the exact solution of the IVP, $t_n\ge t^*\ge t_{n-1}$ for the selection of $n$ and $δt=t_n-t_{n-1}\to 0$ for the limit.

What remains is to explore the difference of exact solution and numerical solution for a fixed time discretization. Set $e_n=y_n-y(t_n)$. Then indeed $$ y(t-δt)=y(t)-y'(t)δt+\frac12y''(t)δt^2\mp… =y(t)-f(t,y(t))δt+\frac12(f_t+f_yf)δt^2\mp… $$ Combined with the backward Euler formula this gives \begin{align} e_{n-1}&=e_n-[f(t_n,y_n)-f(t_n,y(t_n))]δt-\frac12y''(t_n)δt^2\pm…\\ &=e_{n-1}+f_y(t_n,y(t_n))e_nδt-\frac12y''(t_n)δt^2\pm…\\ (I-f_y(t_n,y(t_n))δt)e_n&=e_{n-1}-\frac12y''(t_n)δt^2\pm…\\ \end{align} This should show that $e_n$ is a combination of $e_0$ with a coefficient that accumulates the factors $(I-f_y(t_n,y(t_n))δt)^{-1}$, which is zero if $e_0=0$, and additional terms that contain the similarly discounted sum of the higher order Taylor terms. The second order term is thus of size $O(δt)$.

Returning to the recursion equation for $e_n$ this means that $e_n-e_{n-1}=O(δt^2)$. So indeed $C\sim δt$ in the notation of the question.

$\endgroup$
3
$\begingroup$

Not really sure what you are asking, but concerning

Do you have a counterexample, and possibly a descriptions of the class of functions 𝑓 on which backward Euler is of higher order than 1?

you can examine the Taylor expansion of

$$ \frac{y_n - y_{n-1}}{\Delta t} $$ around $t_n$:

$$ \frac{y_n - y_{n-1}}{\Delta t} = \frac{y_n - \Big(y_n - \Delta t y'(t_n) + 0.5(\Delta t)^2 y''(t_n) + \dots \Big)}{\Delta t} = y'(t_n) + \sum_{i=1}^\infty \frac{y^{(i+1)}(t_n)}{(i+1)!} (\Delta t)^i .$$

So for solutions with vanishing second derivative, e.g. linear functions like $f(y) = \alpha y, \alpha \in \mathbb R$ the approximation is exact. For other functions, you can take single steps of higher order, e.g. when the true solution is for instance $\sin(t)$ and you evaluate it at some $t_n = n \pi, n \in \mathbb Z$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .