Exponential decay ODEs

We shall now compute the truncation error of a finite difference scheme for a differential equation. Our first problem involves the following the linear ODE modeling exponential decay,

$$\tag{680} u'(t)=-au(t){\thinspace .}$$

Forward Euler scheme

We begin with the Forward Euler scheme for discretizing (680):

$$\begin{align}\begin{aligned}\tag{681} \lbrack D_t^+ u = -au \rbrack^n\\ {\thinspace .}\end{aligned}\end{align}$$

The idea behind the truncation error computation is to insert the exact solution ${u_{\small\mbox{e}}}$ of the differential equation problem (680) in the discrete equations (681) and find the residual that arises because ${u_{\small\mbox{e}}}$ does not solve the discrete equations. Instead, ${u_{\small\mbox{e}}}$ solves the discrete equations with a residual $R^n$:

$$\begin{align}\begin{aligned}\tag{682} [D_t^+ {u_{\small\mbox{e}}} + a{u_{\small\mbox{e}}} = R]^n\\ {\thinspace .}\end{aligned}\end{align}$$

From (664)-(665) it follows that

$$[D_t^+ {u_{\small\mbox{e}}}]^n = {u_{\small\mbox{e}}}'(t_n) + \frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t + {\mathcal{O}(\Delta t^2)},$$

which inserted in (682) results in

$${u_{\small\mbox{e}}}'(t_n) + \frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t + {\mathcal{O}(\Delta t^2)} + a{u_{\small\mbox{e}}}(t_n) = R^n {\thinspace .}$$

Now, ${u_{\small\mbox{e}}}'(t_n) + a{u_{\small\mbox{e}}}^n = 0$ since ${u_{\small\mbox{e}}}$ solves the differential equation. The remaining terms constitute the residual:

$$\begin{align}\begin{aligned}\tag{683} R^n = \frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t + {\mathcal{O}(\Delta t^2)}\\ {\thinspace .}\end{aligned}\end{align}$$

This is the truncation error $R^n$ of the Forward Euler scheme.

Because $R^n$ is proportional to $\Delta t$, we say that the Forward Euler scheme is of first order in $\Delta t$. However, the truncation error is just one error measure, and it is not equal to the true error ${u_{\small\mbox{e}}}^n - u^n$. For this simple model problem we can compute a range of different error measures for the Forward Euler scheme, including the true error ${u_{\small\mbox{e}}}^n - u^n$, and all of them have dominating terms proportional to $\Delta t$.

Crank-Nicolson scheme

For the Crank-Nicolson scheme,

$$\tag{684} [D_t u = -au]^{n+\frac{1}{2}},$$

we compute the truncation error by inserting the exact solution of the ODE and adding a residual $R$,

$$\tag{685} [D_t {u_{\small\mbox{e}}} + a\overline{{u_{\small\mbox{e}}}}^{t} = R]^{n+\frac{1}{2}} {\thinspace .}$$

The term $[D_t{u_{\small\mbox{e}}}]^{n+\frac{1}{2}}$ is easily computed from (658)-(659) by replacing $n$ with $n+{\frac{1}{2}}$ in the formula,

$$\lbrack D_t{u_{\small\mbox{e}}}\rbrack^{n+\frac{1}{2}} = {u_{\small\mbox{e}}}'(t_{n+\frac{1}{2}}) + \frac{1}{24}{u_{\small\mbox{e}}}'''(t_{n+\frac{1}{2}})\Delta t^2 + {\mathcal{O}(\Delta t^4)}{\thinspace .}$$

The arithmetic mean is related to $u(t_{n+\frac{1}{2}})$ by (674)-(675) so

$$[a\overline{{u_{\small\mbox{e}}}}^{t}]^{n+\frac{1}{2}} = {u_{\small\mbox{e}}}(t_{n+\frac{1}{2}}) + \frac{1}{8}{u_{\small\mbox{e}}}''(t_{n})\Delta t^2 + + {\mathcal{O}(\Delta t^4)}{\thinspace .}$$

Inserting these expressions in (685) and observing that ${u_{\small\mbox{e}}}'(t_{n+\frac{1}{2}}) +a{u_{\small\mbox{e}}}^{n+\frac{1}{2}} = 0$, because ${u_{\small\mbox{e}}}(t)$ solves the ODE $u'(t)=-au(t)$ at any point $t$, we find that

$$\tag{686} R^{n+\frac{1}{2}} = \left( \frac{1}{24}{u_{\small\mbox{e}}}'''(t_{n+\frac{1}{2}}) + \frac{1}{8}{u_{\small\mbox{e}}}''(t_{n}) \right)\Delta t^2 + {\mathcal{O}(\Delta t^4)}$$

Here, the truncation error is of second order because the leading term in $R$ is proportional to $\Delta t^2$.

At this point it is wise to redo some of the computations above to establish the truncation error of the Backward Euler scheme, see Problem B.4: Truncation error of the Backward Euler scheme.

The $\theta$-rule

We may also compute the truncation error of the $\theta$-rule,

$$[\bar D_t u = -a\overline{u}^{t,\theta}]^{n+\theta} {\thinspace .}$$

Our computational task is to find $R^{n+\theta}$ in

$$[\bar D_t {u_{\small\mbox{e}}} + a\overline{{u_{\small\mbox{e}}}}^{t,\theta} = R]^{n+\theta} {\thinspace .}$$

From (666)-(667) and (672)-(673) we get expressions for the terms with ${u_{\small\mbox{e}}}$. Using that ${u_{\small\mbox{e}}}'(t_{n+\theta}) + a{u_{\small\mbox{e}}}(t_{n+\theta})=0$, we end up with

$$R^{n+\theta} = ({\frac{1}{2}}-\theta){u_{\small\mbox{e}}}''(t_{n+\theta})\Delta t + \frac{1}{2}\theta (1-\theta){u_{\small\mbox{e}}}''(t_{n+\theta})\Delta t^2 + \nonumber$$

$$\tag{687} \frac{1}{2}(\theta^2 -\theta + 3){u_{\small\mbox{e}}}'''(t_{n+\theta})\Delta t^2 + {\mathcal{O}(\Delta t^3)}$$

For $\theta =\frac{1}{2}$ the first-order term vanishes and the scheme is of second order, while for $\theta\neq \frac{1}{2}$ we only have a first-order scheme.

Using symbolic software

The previously mentioned truncation_error module can be used to automate the Taylor series expansions and the process of collecting terms. Here is an example on possible use:

from truncation_error import DiffOp
from sympy import *

def decay():
    u, a = symbols('u a')
    diffop = DiffOp(u, independent_variable='t',
                    num_terms_Taylor_series=3)
    D1u = diffop.D(1)   # symbol for du/dt
    ODE = D1u + a*u     # define ODE

    # Define schemes
    FE = diffop['Dtp'] + a*u
    CN = diffop['Dt' ] + a*u
    BE = diffop['Dtm'] + a*u
    theta = diffop['barDt'] + a*diffop['weighted_arithmetic_mean']
    theta = sm.simplify(sm.expand(theta))
    # Residuals (truncation errors)
    R = {'FE': FE-ODE, 'BE': BE-ODE, 'CN': CN-ODE,
         'theta': theta-ODE}
    return R

The returned dictionary becomes

decay: {
 'BE': D2u*dt/2 + D3u*dt**2/6,
 'FE': -D2u*dt/2 + D3u*dt**2/6,
 'CN': D3u*dt**2/24,
 'theta': -D2u*a*dt**2*theta**2/2 + D2u*a*dt**2*theta/2 -
           D2u*dt*theta + D2u*dt/2 + D3u*a*dt**3*theta**3/3 -
           D3u*a*dt**3*theta**2/2 + D3u*a*dt**3*theta/6 +
           D3u*dt**2*theta**2/2 - D3u*dt**2*theta/2 + D3u*dt**2/6,
}

The results are in correspondence with our hand-derived expressions.

Empirical verification of the truncation error

The task of this section is to demonstrate how we can compute the truncation error $R$ numerically. For example, the truncation error of the Forward Euler scheme applied to the decay ODE $u'=-ua$ is

$$\begin{align}\begin{aligned}\tag{688} R^n = [D_t^+{u_{\small\mbox{e}}} + a{u_{\small\mbox{e}}}]^n\\ {\thinspace .}\end{aligned}\end{align}$$

If we happen to know the exact solution ${u_{\small\mbox{e}}}(t)$, we can easily evaluate $R^n$ from the above formula.

To estimate how $R$ varies with the discretization parameter $\Delta t$, which has been our focus in the previous mathematical derivations, we first make the assumption that $R=C\Delta t^r$ for appropriate constants $C$ and $r$ and small enough $\Delta t$. The rate $r$ can be estimated from a series of experiments where $\Delta t$ is varied. Suppose we have $m$ experiments $(\Delta t_i, R_i)$, $i=0,\ldots,m-1$. For two consecutive experiments $(\Delta t_{i-1}, R_{i-1})$ and $(\Delta t_i, R_i)$, a corresponding $r_{i-1}$ can be estimated by

$$\tag{689} r_{i-1} = \frac{\ln (R_{i-1}/R_i)}{\ln (\Delta t_{i-1}/\Delta t_i)},$$

for $i=1,\ldots,m-1$. Note that the truncation error $R_i$ varies through the mesh, so (689) is to be applied pointwise. A complicating issue is that $R_i$ and $R_{i-1}$ refer to different meshes. Pointwise comparisons of the truncation error at a certain point in all meshes therefore requires any computed $R$ to be restricted to the coarsest mesh and that all finer meshes contain all the points in the coarsest mesh. Suppose we have $N_0$ intervals in the coarsest mesh. Inserting a superscript $n$ in (689), where $n$ counts mesh points in the coarsest mesh, $n=0,\ldots,N_0$, leads to the formula

$$\tag{690} r_{i-1}^n = \frac{\ln (R_{i-1}^n/R_i^n)}{\ln (\Delta t_{i-1}/\Delta t_i)} {\thinspace .}$$

Experiments are most conveniently defined by $N_0$ and a number of refinements $m$. Suppose each mesh has twice as many cells $N_i$ as the previous one:

$$N_i = 2^iN_0,\quad \Delta t_i = TN_i^{-1},$$

where $[0,T]$ is the total time interval for the computations. Suppose the computed $R_i$ values on the mesh with $N_i$ intervals are stored in an array R[i] (R being a list of arrays, one for each mesh). Restricting this $R_i$ function to the coarsest mesh means extracting every $N_i/N_0$ point and is done as follows:

stride = N[i]/N_0
R[i] = R[i][::stride]

The quantity R[i][n] now corresponds to $R_i^n$.

In addition to estimating $r$ for the pointwise values of $R=C\Delta t^r$, we may also consider an integrated quantity on mesh $i$,

$$\tag{691} R_{I,i} = \left(\Delta t_i\sum_{n=0}^{N_i} (R_i^n)^2\right)^\frac{1}{2}\approx \int_0^T R_i(t)dt {\thinspace .}$$

The sequence $R_{I,i}$, $i=0,\ldots,m-1$, is also expected to behave as $C\Delta t^r$, with the same $r$ as for the pointwise quantity $R$, as $\Delta t\rightarrow 0$.

The function below computes the $R_i$ and $R_{I,i}$ quantities, plots them and compares with the theoretically derived truncation error (R_a) if available.

import numpy as np
import scitools.std as plt

def estimate(truncation_error, T, N_0, m, makeplot=True):
    """
    Compute the truncation error in a problem with one independent
    variable, using m meshes, and estimate the convergence
    rate of the truncation error.

    The user-supplied function truncation_error(dt, N) computes
    the truncation error on a uniform mesh with N intervals of
    length dt::

      R, t, R_a = truncation_error(dt, N)

    where R holds the truncation error at points in the array t,
    and R_a are the corresponding theoretical truncation error
    values (None if not available).

    The truncation_error function is run on a series of meshes
    with 2**i*N_0 intervals, i=0,1,...,m-1.
    The values of R and R_a are restricted to the coarsest mesh.
    and based on these data, the convergence rate of R (pointwise)
    and time-integrated R can be estimated empirically.
    """
    N = [2**i*N_0 for i in range(m)]

    R_I = np.zeros(m) # time-integrated R values on various meshes
    R   = [None]*m    # time series of R restricted to coarsest mesh
    R_a = [None]*m    # time series of R_a restricted to coarsest mesh
    dt = np.zeros(m)
    legends_R = [];  legends_R_a = []  # all legends of curves

    for i in range(m):
        dt[i] = T/float(N[i])
        R[i], t, R_a[i] = truncation_error(dt[i], N[i])

        R_I[i] = np.sqrt(dt[i]*np.sum(R[i]**2))

        if i == 0:
            t_coarse = t           # the coarsest mesh

        stride = N[i]/N_0
        R[i] = R[i][::stride]      # restrict to coarsest mesh
        R_a[i] = R_a[i][::stride]

        if makeplot:
            plt.figure(1)
            plt.plot(t_coarse, R[i], log='y')
            legends_R.append('N=%d' % N[i])
            plt.hold('on')

            plt.figure(2)
            plt.plot(t_coarse, R_a[i] - R[i], log='y')
            plt.hold('on')
            legends_R_a.append('N=%d' % N[i])

    if makeplot:
        plt.figure(1)
        plt.xlabel('time')
        plt.ylabel('pointwise truncation error')
        plt.legend(legends_R)
        plt.savefig('R_series.png')
        plt.savefig('R_series.pdf')
        plt.figure(2)
        plt.xlabel('time')
        plt.ylabel('pointwise error in estimated truncation error')
        plt.legend(legends_R_a)
        plt.savefig('R_error.png')
        plt.savefig('R_error.pdf')

    # Convergence rates
    r_R_I = convergence_rates(dt, R_I)
    print 'R integrated in time; r:',
    print ' '.join(['%.1f' % r for r in r_R_I])
    R = np.array(R)  # two-dim. numpy array
    r_R = [convergence_rates(dt, R[:,n])[-1]
           for n in range(len(t_coarse))]

The first makeplot block demonstrates how to build up two figures in parallel, using plt.figure(i) to create and switch to figure number i. Figure numbers start at 1. A logarithmic scale is used on the $y$ axis since we expect that $R$ as a function of time (or mesh points) is exponential. The reason is that the theoretical estimate (683) contains ${u_{\small\mbox{e}}}''$, which for the present model goes like $e^{-at}$. Taking the logarithm makes a straight line.

The code follows closely the previously stated mathematical formulas, but the statements for computing the convergence rates might deserve an explanation. The generic help function convergence_rate(h, E) computes and returns $r_{i-1}$, $i=1,\ldots,m-1$ from (690), given $\Delta t_i$ in h and $R_i^n$ in E:

def convergence_rates(h, E):
    from math import log
    r = [log(E[i]/E[i-1])/log(h[i]/h[i-1])
         for i in range(1, len(h))]
    return r

Calling r_R_I = convergence_rates(dt, R_I) computes the sequence of rates $r_0,r_1,\ldots,r_{m-2}$ for the model $R_I\sim\Delta t^r$, while the statements

R = np.array(R)  # two-dim. numpy array
r_R = [convergence_rates(dt, R[:,n])[-1]
       for n in range(len(t_coarse))]

compute the final rate $r_{m-2}$ for $R^n\sim\Delta t^r$ at each mesh point $t_n$ in the coarsest mesh. This latter computation deserves more explanation. Since R[i][n] holds the estimated truncation error $R_i^n$ on mesh $i$, at point $t_n$ in the coarsest mesh, R[:,n] picks out the sequence $R_i^n$ for $i=0,\ldots,m-1$. The convergence_rate function computes the rates at $t_n$, and by indexing [-1] on the returned array from convergence_rate, we pick the rate $r_{m-2}$, which we believe is the best estimation since it is based on the two finest meshes.

The estimate function is available in a module trunc_empir.py. Let us apply this function to estimate the truncation error of the Forward Euler scheme. We need a function decay_FE(dt, N) that can compute (688) at the points in a mesh with time step dt and N intervals:

import numpy as np
import trunc_empir

def decay_FE(dt, N):
    dt = float(dt)
    t = np.linspace(0, N*dt, N+1)
    u_e = I*np.exp(-a*t)  # exact solution, I and a are global
    u = u_e  # naming convention when writing up the scheme
    R = np.zeros(N)

    for n in range(0, N):
        R[n] = (u[n+1] - u[n])/dt + a*u[n]

    # Theoretical expression for the trunction error
    R_a = 0.5*I*(-a)**2*np.exp(-a*t)*dt

    return R, t[:-1], R_a[:-1]

if __name__ == '__main__':
    I = 1; a = 2  # global variables needed in decay_FE
    trunc_empir.estimate(decay_FE, T=2.5, N_0=6, m=4, makeplot=True)

The estimated rates for the integrated truncation error $R_I$ become 1.1, 1.0, and 1.0 for this sequence of four meshes. All the rates for $R^n$, computed as r_R, are also very close to 1 at all mesh points. The agreement between the theoretical formula (683) and the computed quantity (ref:ref:(688) <Eq:trunc:decay:FE:R:comp>) is very good, as illustrated in Figures Estimated truncation error at mesh points for different meshes and Difference between theoretical and estimated truncation error at mesh points for different meshes. The program trunc_decay_FE.py was used to perform the simulations and it can easily be modified to test other schemes (see also Exercise B.5: Empirical estimation of truncation errors).

Estimated truncation error at mesh points for different meshes

Difference between theoretical and estimated truncation error at mesh points for different meshes

Increasing the accuracy by adding correction terms

Now we ask the question: can we add terms in the differential equation that can help increase the order of the truncation error? To be precise, let us revisit the Forward Euler scheme for $u'=-au$, insert the exact solution ${u_{\small\mbox{e}}}$, include a residual $R$, but also include new terms $C$:

$$\tag{692} \lbrack D_t^+ {u_{\small\mbox{e}}} + a{u_{\small\mbox{e}}} = C + R \rbrack^n{\thinspace .}$$

Inserting the Taylor expansions for $[D_t^+{u_{\small\mbox{e}}}]^n$ and keeping terms up to 3rd order in $\Delta t$ gives the equation

$$\frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t - \frac{1}{6}{u_{\small\mbox{e}}}'''(t_n)\Delta t^2 + \frac{1}{24}{u_{\small\mbox{e}}}''''(t_n)\Delta t^3 + {\mathcal{O}(\Delta t^4)} = C^n + R^n{\thinspace .}$$

Can we find $C^n$ such that $R^n$ is ${\mathcal{O}(\Delta t^2)}$? Yes, by setting

$$C^n = \frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t,$$

we manage to cancel the first-order term and

$$R^n = \frac{1}{6}{u_{\small\mbox{e}}}'''(t_n)\Delta t^2 + {\mathcal{O}(\Delta t^3)}{\thinspace .}$$

The correction term $C^n$ introduces $\frac{1}{2}\Delta t u''$ in the discrete equation, and we have to get rid of the derivative $u''$. One idea is to approximate $u''$ by a second-order accurate finite difference formula, $u''\approx (u^{n+1}-2u^n+u^{n-1})/\Delta t^2$, but this introduces an additional time level with $u^{n-1}$. Another approach is to rewrite $u''$ in terms of $u'$ or $u$ using the ODE:

$$u'=-au\quad\Rightarrow\quad u''=-au' = -a(-au)= a^2u{\thinspace .}$$

This means that we can simply set $C^n = {\frac{1}{2}}a^2\Delta t u^n$. We can then either solve the discrete equation

$$\tag{693} [D_t^+ u = -au + {\frac{1}{2}}a^2\Delta t u]^n,$$

or we can equivalently discretize the perturbed ODE

$$\tag{694} u' = -\hat au ,\quad \hat a = a(1 - {\frac{1}{2}}a\Delta t),$$

by a Forward Euler method. That is, we replace the original coefficient $a$ by the perturbed coefficient $\hat a$. Observe that $\hat a\rightarrow a$ as $\Delta t\rightarrow 0$.

The Forward Euler method applied to (694) results in

$$[D_t^+ u = -a(1 - {\frac{1}{2}}a\Delta t)u]^n{\thinspace .}$$

We can control our computations and verify that the truncation error of the scheme above is indeed ${\mathcal{O}(\Delta t^2)}$.

Another way of revealing the fact that the perturbed ODE leads to a more accurate solution is to look at the amplification factor. Our scheme can be written as

$$u^{n+1} = Au^n,\quad A = 1-\hat a\Delta t = 1 - p + {\frac{1}{2}}p^2,\quad p=a\Delta t,$$

The amplification factor $A$ as a function of $p=a\Delta t$ is seen to be the first three terms of the Taylor series for the exact amplification factor $e^{-p}$. The Forward Euler scheme for $u=-au$ gives only the first two terms $1-p$ of the Taylor series for $e^{-p}$. That is, using $\hat a$ increases the order of the accuracy in the amplification factor.

Instead of replacing $u''$ by $a^2u$, we use the relation $u''=-au'$ and add a term $-{\frac{1}{2}}a\Delta t u'$ in the ODE:

$$u'=-au - {\frac{1}{2}}a\Delta t u'\quad\Rightarrow\quad \left( 1 + {\frac{1}{2}}a\Delta t\right) u' = -au{\thinspace .}$$

Using a Forward Euler method results in

$$\left( 1 + {\frac{1}{2}}a\Delta t\right)\frac{u^{n+1}-u^n}{\Delta t} = -au^n,$$

which after some algebra can be written as

$$u^{n+1} = \frac{1 - {\frac{1}{2}}a\Delta t}{1+{\frac{1}{2}}a\Delta t}u^n{\thinspace .}$$

This is the same formula as the one arising from a Crank-Nicolson scheme applied to $u'=-au$! It now recommended to do Exercise B.6: Correction term for a Backward Euler scheme and repeat the above steps to see what kind of correction term is needed in the Backward Euler scheme to make it second order.

The Crank-Nicolson scheme is a bit more challenging to analyze, but the ideas and techniques are the same. The discrete equation reads

$$[D_t u = -au ]^{n+\frac{1}{2}},$$

and the truncation error is defined through

$$[D_t {u_{\small\mbox{e}}} + a\overline{{u_{\small\mbox{e}}}}^{t} = C + R]^{n+\frac{1}{2}},$$

where we have added a correction term. We need to Taylor expand both the discrete derivative and the arithmetic mean with aid of (658)-(659) and (674)-(675), respectively. The result is

$$\frac{1}{24}{u_{\small\mbox{e}}}'''(t_{n+\frac{1}{2}})\Delta t^2 + {\mathcal{O}(\Delta t^4)} + \frac{a}{8}{u_{\small\mbox{e}}}''(t_{n+\frac{1}{2}})\Delta t^2 + {\mathcal{O}(\Delta t^4)} = C^{n+\frac{1}{2}} + R^{n+\frac{1}{2}}{\thinspace .}$$

The goal now is to make $C^{n+\frac{1}{2}}$ cancel the $\Delta t^2$ terms:

$$C^{n+\frac{1}{2}} = \frac{1}{24}{u_{\small\mbox{e}}}'''(t_{n+\frac{1}{2}})\Delta t^2 + \frac{a}{8}{u_{\small\mbox{e}}}''(t_{n})\Delta t^2{\thinspace .}$$

Using $u'=-au$, we have that $u''=a^2u$, and we find that $u'''=-a^3u$. We can therefore solve the perturbed ODE problem

$$u' = -\hat a u,\quad \hat a = a(1 - \frac{1}{12}a^2\Delta t^2),$$

by the Crank-Nicolson scheme and obtain a method that is of fourth order in $\Delta t$. Problem B.7: Verify the effect of correction terms encourages you to implement these correction terms and calculate empirical convergence rates to verify that higher-order accuracy is indeed obtained in real computations.

Extension to variable coefficients

Let us address the decay ODE with variable coefficients,

$$u'(t) = -a(t)u(t) + b(t),$$

discretized by the Forward Euler scheme,

$$\tag{695} [D_t^+ u = -au + b]^n {\thinspace .}$$

The truncation error $R$ is as always found by inserting the exact solution ${u_{\small\mbox{e}}}(t)$ in the discrete scheme:

$$\tag{696} [D_t^+ {u_{\small\mbox{e}}} + a{u_{\small\mbox{e}}} - b = R]^n {\thinspace .}$$

Using (664)-(665),

$${u_{\small\mbox{e}}}'(t_n) - \frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t + {\mathcal{O}(\Delta t^2)} + a(t_n){u_{\small\mbox{e}}}(t_n) - b(t_n) = R^n {\thinspace .}$$

Because of the ODE,

$${u_{\small\mbox{e}}}'(t_n) + a(t_n){u_{\small\mbox{e}}}(t_n) - b(t_n) =0,$$

so we are left with the result

$$\tag{697} R^n = -\frac{1}{2}{u_{\small\mbox{e}}}''(t_n)\Delta t + {\mathcal{O}(\Delta t^2)} \ {\thinspace .}$$

We see that the variable coefficients do not pose any additional difficulties in this case. Problem B.8: Truncation error of the Crank-Nicolson scheme takes the analysis above one step further to the Crank-Nicolson scheme.

Exact solutions of the finite difference equations

Having a mathematical expression for the numerical solution is very valuable in program verification since we then know the exact numbers that the program should produce. Looking at the various formulas for the truncation errors in (658)-(659) and (678)-(679) in the section Overview of leading-order error terms in finite difference formulas, we see that all but two of the $R$ expressions contain a second or higher order derivative of ${u_{\small\mbox{e}}}$. The exceptions are the geometric and harmonic means where the truncation error involves ${u_{\small\mbox{e}}}'$ and even ${u_{\small\mbox{e}}}$ in case of the harmonic mean. So, apart from these two means, choosing ${u_{\small\mbox{e}}}$ to be a linear function of $t$, ${u_{\small\mbox{e}}} = ct+d$ for constants $c$ and $d$, will make the truncation error vanish since ${u_{\small\mbox{e}}}''=0$. Consequently, the truncation error of a finite difference scheme will be zero since the various approximations used will all be exact. This means that the linear solution is an exact solution of the discrete equations.

In a particular differential equation problem, the reasoning above can be used to determine if we expect a linear ${u_{\small\mbox{e}}}$ to fulfill the discrete equations. To actually prove that this is true, we can either compute the truncation error and see that it vanishes, or we can simply insert ${u_{\small\mbox{e}}}(t)=ct+d$ in the scheme and see that it fulfills the equations. The latter method is usually the simplest. It will often be necessary to add some source term to the ODE in order to allow a linear solution.

Many ODEs are discretized by centered differences. From the section Overview of leading-order error terms in finite difference formulas we see that all the centered difference formulas have truncation errors involving ${u_{\small\mbox{e}}}'''$ or higher-order derivatives. A quadratic solution, e.g., ${u_{\small\mbox{e}}}(t) =t^2 + ct + d$, will then make the truncation errors vanish. This observation can be used to test if a quadratic solution will fulfill the discrete equations. Note that a quadratic solution will not obey the equations for a Crank-Nicolson scheme for $u'=-au+b$ because the approximation applies an arithmetic mean, which involves a truncation error with ${u_{\small\mbox{e}}}''$.

Computing truncation errors in nonlinear problems

The general nonlinear ODE

$$\tag{698} u'=f(u,t),$$

can be solved by a Crank-Nicolson scheme

$$\tag{699} [D_t u=\overline{f}^{t}]^{n+\frac{1}{2}}{\thinspace .}$$

The truncation error is as always defined as the residual arising when inserting the exact solution ${u_{\small\mbox{e}}}$ in the scheme:

$$\tag{700} [D_t {u_{\small\mbox{e}}} - \overline{f}^{t}= R]^{n+\frac{1}{2}}{\thinspace .}$$

Using (674)-(675) for $\overline{f}^{t}$ results in

$$\begin{split}\begin{align*} [\overline{f}^{t}]^{n+\frac{1}{2}} &= \frac{1}{2}(f({u_{\small\mbox{e}}}^n,t_n) + f({u_{\small\mbox{e}}}^{n+1},t_{n+1}))\\ &= f({u_{\small\mbox{e}}}^{n+\frac{1}{2}},t_{n+\frac{1}{2}}) + \frac{1}{8}{u_{\small\mbox{e}}}''(t_{n+\frac{1}{2}})\Delta t^2 + {\mathcal{O}(\Delta t^4)}{\thinspace .} \end{align*}\end{split}$$

With (658)-(659) the discrete equations (700) lead to

$${u_{\small\mbox{e}}}'(t_{n+\frac{1}{2}}) + \frac{1}{24}{u_{\small\mbox{e}}}'''(t_{n+\frac{1}{2}})\Delta t^2 - f({u_{\small\mbox{e}}}^{n+\frac{1}{2}},t_{n+\frac{1}{2}}) - \frac{1}{8}{u_{\small\mbox{e}}}''(t_{n+\frac{1}{2}})\Delta t^2 + {\mathcal{O}(\Delta t^4)} = R^{n+\frac{1}{2}}{\thinspace .}$$

Since ${u_{\small\mbox{e}}}'(t_{n+\frac{1}{2}}) - f({u_{\small\mbox{e}}}^{n+\frac{1}{2}},t_{n+\frac{1}{2}})=0$, the truncation error becomes

$$R^{n+\frac{1}{2}} = (\frac{1}{24}{u_{\small\mbox{e}}}'''(t_{n+\frac{1}{2}}) - \frac{1}{8}{u_{\small\mbox{e}}}''(t_{n+\frac{1}{2}})) \Delta t^2{\thinspace .}$$

The computational techniques worked well even for this nonlinear ODE.