Truncation error of Backward Euler applied to IVP I am looking at the IVP $u'(t)=f(u(t),t)$, $u(0)=n$. I am using this method
$$\frac{U^{n+1}-U^n}{k}=f(U^{n+1},t_{n+1})$$ where $U^n$ is meant to approximate the solution $u(t)$ at $t=t_n=nk$.
So far, I have that the location truncation error ($\tau$):
$$\tau=\frac{U^{n+1}-U^n}{k}-f(U^{n+1},t_{n+1})$$
$$=\frac{1}{k}[U^n+k\frac{d}{dt}U^n+\frac{k^2}{2}\frac{d^2}{dt^2}U^n+O(k^3)-U^n]-\frac{d}{dt}U^{n+1}$$
$$=[\frac{d}{dt}U^n+\frac{k}{2}\frac{d^2}{dt^2}U^n+O(k^2)]-\frac{d}{dt}U^{n+1}$$
But I don't know how to finish this. I should know, but I can't figure it out. Thank you for your time.
 A: This type of questions is always based on the following two conventional assumptions.


*

*$f(x,t)$ is Lipchitz continuous with respect to $x$, i.e., there exists some fixed $C_1$, such that
$$
\left|f(x_1,t)-f(x_2,t)\right|\le C_1\left|x_1-x_2\right|
$$
holds for all $t$, $x_1$ and $x_2$.

*$U(t)$, the exact solution to the IVP, is twice differentiable for $t\in\left[0,T\right]$, i.e., $U$, $U'$ and $U''$ are all continuous on $\left[0,T\right]$.


As per your notations, $U^n$ is the numerical approximation to $U(t_n)$. Therefore, we have from the numerical scheme that
$$
\frac{U^{n+1}-U^n}{k}=f(U^{n+1},t_{n+1}),
$$
and by Taylor theorem with mean-value forms of the remainder that
$$
\frac{U(t_{n+1})-U(t_n)}{k}=U'(t_{n+1})-\frac{1}{2}U''(\xi_{n+1})k=f(U(t_{n+1}),t_{n+1})-\tau^{n+1},
$$
where
$$
\tau^{n+1}=\frac{1}{2}U''(\xi_{n+1})k
$$
for some $\xi_{n+1}\in\left(t_n,t_{n+1}\right)$. Since $U''$ is continuous on $\left[0,T\right]$, it is bounded. Therefore, there exists some fixed $C_2$, such that
$$
\left|\tau^n\right|=\left|\frac{1}{2}U''(\xi_n)k\right|\le C_2k
$$
holds for all $n$ with $t_n\in\left(0,T\right]$.
Now, define the error at $t_n$ as
$$
e^n:=U^n-U(t_n).
$$
With this notation, the difference between the scheme and the Taylor approximation yields
$$
\frac{e^{n+1}-e^n}{k}=f(U^{n+1},t_{n+1})-f(U(t_{n+1}),t_{n+1})+\tau^{n+1}.
$$
Thanks to the Lipchitz continuity of $f$ as well as the estimate of $\tau^n$,
$$
\left|\frac{e^{n+1}-e^n}{k}\right|\le\left|f(U^{n+1},t_{n+1})-f(U(t_{n+1}),t_{n+1})\right|+\left|\tau^{n+1}\right|\le C_1\left|e^{n+1}\right|+C_2k,
$$
or equivalently,
$$
\left|e^{n+1}-e^n\right|\le C_1k\left|e^{n+1}\right|+C_2k^2.
$$
Note that $e^0=U^0-U(t_0)=0$. We thus have
$$
\left|e^n\right|=\left|\sum_{j=1}^n\left(e^j-e^{j-1}\right)\right|\le\sum_{j=1}^n\left|e^j-e^{j-1}\right|\le\sum_{j=1}^n\left(C_1k\left|e^j\right|+C_2k^2\right)=C_1k\sum_{j=1}^n\left|e^j\right|+C_2nk^2.
$$
Specifically, since $nk=t_n\le T$,
$$
\left|e^n\right|\le C_1k\sum_{j=1}^n\left|e^j\right|+C_2Tk.
$$
Finally, thanks to Gronwall's inequality (discrete), the above inequality immediately leads to
\begin{align}
\left|e^n\right|&\le C_2Tk+C_1C_2Tk^2\sum_{j=1}^n\exp\left(\sum_{i=j}^nC_1k\right)\\
&\le C_2Tk+C_1C_2Tk^2\sum_{j=1}^n\exp\left(\sum_{i=1}^nC_1k\right)\\
&=C_2Tk+C_1C_2Tk^2\sum_{j=1}^n\exp\left(C_1nk\right)\\
&\le C_2Tk+C_1C_2Tk^2\sum_{j=1}^n\exp\left(C_1T\right)\\
&=C_2Tk+C_1C_2Tk^2n\exp\left(C_1T\right)\\
&\le C_2Tk+C_1C_2T^2k\exp\left(C_1T\right)\\
&=\left(C_2T+C_1C_2T^2e^{C_1T}\right)k\\
&\sim O(k),
\end{align}
where $nk\le T$ has been used for several times in above. The last line definitely indicates the first-order global accuracy of the scheme.
