Is there a definition for the LTE in implicit numerical ODE solvers?

Question

While writing down some basic definitions for my thesis I noticed that the Local Truncation Error (LTE), and, therefore, consistency, is defined only for explicit numerical integration methods. Take wikipedia as an example but on my reference book (Quarteroni Sacco Saleri, Numerical Mathematics) and over the web I couldn't find an analogus for implicit methods.

My reference book says that for an explicit method of the form $$ u_{n+1} = u_n + h\,\Phi(t_n, u_n, f_n, h), $$ having $f_n=f(t_n, u_n)$, and $u_n$ the $n$-th numerical approximation. Assuming we got the exact solution $y(t)$, with $y_n=y(t_n)$ we can write: $$ y_{n+1} = y_n + h\,\Phi(t_n, y_n, f(t_n, y_n), h) + \varepsilon_{n+1}, $$ where $\varepsilon_{n+1}$ is the residual error generating in $t_{n+1}$. Thus we can write $\varepsilon_{n+1} = h\,\tau_{n+1}(h)$ and we can define $\tau_{n+1}(h)$ as the LTE, and iff $\tau_{n+1}(h)\to0$ for $h\to0$ the method is consistent.

Could there be an analogus for a generical implicit method? My guess is that every implicit method has got its own definition for the LTE.

Answer 1

Also for implicit one-step methods you can write the step as $$ u_{n+1} = u_n + h\,\Phi_f(t_n, u_n, h), $$ as the next value is computed, via the implicit solver, from $t_n, u_n$ and $h$. For $h$ small enough the implicit equations of the stages satisfy, usually as system, the conditions of the implicit function theorem. Thus there is, for $(t_n,u_n)$ fixed, a solution $$h\mapsto k_i(h)~\text{ to }~~k_i(h)=f(t_n+c_ih,u_n+h[a_{i1}k_1(h)+...+a_{is}k_s(h)])$$ that is as smooth as $f$, and $$u_{n+1}=u_n+h[b_1k_1(h)+...+b_sk_s(h)]$$ has the above form.

---

It makes little sense to include $f_n$ in the arguments of $Φ$, as most one-step methods use more slopes in the computation of the step. $f$ and the coefficients of the method are global parameters of $Φ_f$, a different method or a different function will give a different propagator $Φ_f$.

Answer 2

I'm digging up an old question here, but since I was working on this problem a while ago, I might help you (or someone else) by contributing to this question.

As you mentioned,

we can define $\tau_{n+1}(h)$ as the LTE, and iff $\tau_{n+1}(h)$ $\rightarrow 0$ for $h \rightarrow 0$ the method is consistent. Could there be an analogus for a generical implicit method?

Regarding this question, if I understood you correctly and you want to "measure" the LTE to see, if an implicit method is converging, then yes, we can do something similar for implicit methods too. For this we will rely on the theorem which says: Consistency + zero-stability implies convergence.

We know that for the forward Euler method, the LTE is $\mathcal{O}(h^{2})$. In general, higher-order schemes have a lower LTE for the same step size. Normally, we do not know the exact solution of our problem, so the global error is not easy to calculate. Nevertheless, we say that a convergent numerical method is the one which approaches the true solution as $h \rightarrow 0$. However, we can also show convergence if the coefficient of our scheme satisfy a specific property called absolute stability.

Let us consider the IVP \begin{align*} \begin{cases} y^\prime &= \lambda y \\ y(0) &= 1. \end{cases} \end{align*}

We know that the solution to this IVP is $\mathrm{e}^{\lambda t}$ for $\lambda \in \mathbb{C}$. Thus, $\lambda = \mathrm{Re}{(\lambda)} + \mathrm{i}\cdot\mathrm{Im}(\lambda t)$. The solution now can be rewritten as \begin{align*} y(t) = \mathrm{e}^{\lambda t} &= \mathrm{e}^{(\mathrm{Re}\lambda)t}\mathrm{e}^{\mathrm{i}(\mathrm{Im}\lambda)t} \\ &= \mathrm{e}^{(\mathrm{Re})t} \left[\cos(\mathrm{Im}\lambda t) + \mathrm{i} \cdot \sin(\mathrm{Im}\lambda t)\right]. \end{align*}

The key observation here is that if $\mathrm{Re}\lambda < 0 \Rightarrow y(t) \rightarrow 0$ for $t \rightarrow +\infty$. In this case we say that the ODE is stable which means in other words that the equilibrium $y=0$ is asymptotically stable. (Think of a pendulum that stops swinging with time progress). So far so good, for analytical solutions. The question is, do we retain this property of the ODE also in discrete settings? In other words, after discretising the ODE with our favourite scheme, do we observe the same property, that if $\mathrm{Re}\lambda < 0$ we actually get to $0$? In general, no we do not! But if this property holds, then we can say that the scheme is absolutely stable, which means that $u_n \rightarrow 0$ for $n \rightarrow +\infty$.

I will give you an example for the implicit Euler scheme $u_{n+1} = u_n + hf_{n-1}$ applying to the IVP problem above.

\begin{align} u_{n+1} &= u_n + h\lambda u_{n+1} \\ (1-h\lambda)u_{n+1} &= u_n \\ u_n &= (1-h\lambda)^{-n} u_0, \end{align} so the condition is $|1-h\lambda|^{-1} < 1$ or $|1-h\lambda| > 1$. Now, let's say $z = h\lambda$, we can draw a unit circle in the complex plane to visualise the region of absolute stability. If you do so, see here, you will see that the region of abs. stability for the implicit Euler is the entire area around the unit circle centred at 1, so the complement of that circle. Hence, for implicit Euler, if $\mathrm{Re}\lambda < 0$, then $\forall h$, $u_n \rightarrow 0$, which is the entire left half of the complex plane. This is a very important fact, because, no matter how small/large your $h$ is, we will always end up in the absolute stability region. Therefore we say that the implicit Euler is unconditionally stable. This makes them especially suitable for the stiff problems.

And that, in my opinion, is the beauty of implicit schemes, because they very often come with absolute stability ''for free''. However, the problem with implicit schemes is that we have to solve an implicit system, which is way more expensive computationally wise. BUT, because implicit schemes are unconditionally stable, we can choose a larger $h$ to reduce the computation. So, even though we did not calculate the LTE per se, or discussed consistency, we are able to observe important properties regarding the convergence and stability of ODE systems.