Discrete approximation scheme

A **discrete approximation scheme** is an algorithm for the approximate solution of equations or models that involve some continuous variable like continuous, real time. In order to use computers to calculate approximate solutions, one needs discrete approximations for any terms involving continuous variables.

The involved terminology is mostly used for approximations for ordinary or partial differential equations (ODE and PDE) and stochastic differential equations.

This page serves as a quick introduction to some elementary terms and notations and links to more advanced material.

We will use a simple ordinary differential equation as an example:

$\frac{d y}{d t} = - k y$

This is an equation for the one dimensional real function $y(t)$ with a positive real constant $k$. This equation describes exponential decay, if we further impose an initial condition for $t_0 = 0$ like

$y(t_0) = C_0$

we have as the unique solution

$y(t) = C_0 \exp(- k t)$

The ansatz of “finite differences” replaces differential quotients with finite differences for some discrete **step size** $h$. Let’s fix a positive constant $h$ and define the discrete times

$t_n := t_{n -1} + h$

Replacing the differential quotient with a finite difference we get

$\frac{y_{n+1} - y_{n}}{t_{n+1} -t_{n}} = - k y_n$

If we replace $t_{n+1} -t_{n}$ with $h$ and rearrange the terms a little bit we get

$y_{n+1} = (1 - h k) y_n$

We assume that we know the value of $y_n$ and need to calculate $y_{n+1}$.

Using a discrete approximation scheme, we only get a discrete set of values. These have to be interpolated to get a function of continuous time t - usually it is to be understood that the values are linearly interpolated.

Of course we would like to get a better approximation if we decrease the step size, that is we would like to get better results for investing more computational power. Fixing a norm $\| * \|$ on the function space that our solution - and the approximation - lives in, we need our approximation scheme to be at least **consistent**:

**Consistency of an approximation scheme**

An approximation scheme in the sense described above is **consistent**, if the numerical approximation $y_{h}$ corresponding to a step size $h$, converges to the exact solution $y$ in a prescribed norm:

$\lim_{h \to 0} \| y_{h} - y \| = 0$

In a finite difference approximation we assume that we know the value of $y_n$ and need to calculate the value of $y_{n+1}$. If a discrete approximation scheme leads us to an equation with $y_{n+1}$ on the left and terms on the right that only involve variables that we already calculated, like $y_n$, the scheme is called an **explicit** scheme. An example is taken from the first paragraph:

$y_{n+1} = (1 - h k) y_n$

In the discretization of the equation

$\frac{d y}{d t} = - k y$

we chose to write $y_n$ on the right side, but we could choose $y_{n+1}$ as well, and get

$\frac{y_{n+1} - y_{n}}{t_{n+1} -t_{n}} = - k y_{n+1}$

This is called an **implicit** scheme, because it involves the variable that we need to calculate, $y_{n+1}$, on the left and on the right side. In more general situations like this, it is not possible to get an equation for $y_{n+1}$ in closed form. Therefore, for an implicit scheme, one needs to solve an **additional algebraic equation** for the next value in each time step.

Why then are implicit schemes even considered? The reason is that implicit schemes have often better behaviour with respect to **numerical stability**.

There are different notions of numerical stability, one of them says that an approximation should stay close to the exact solution no matter how long one follows them.

Fixing a norm $\| * \|$ on the function space that our solution - and the approximation - lives in, we define

**Numerical Stability of an approximation scheme**

An approximation scheme in the sense described above is **numerically stable**, if for every exact solution $y$ it is possible to choose a step size $h$ and a constant $C$ such that

$\max_{0 \le t \le T} \| y_{h} - y \| \lt C$

is valid for every finite constant $T$.

Looking at the explicit scheme of our example

$y_{n+1} = (1 - h k) y_n$

we note that we have to choose the step size according to

$h \lt \frac{1}{k}$

if we choose a bigger h then the approximation will run off to $- \infty$ instead of approximating an exponential decay to $0$. Such a condition is known as a **condition of numerical stability**.

But if we take our implicit approximation

$\frac{y_{n+1} - y_{n}}{t_{n+1} -t_{n}} = - k y_{n+1}$

and solve for $y_{n+1}$, we get

$y_{n+1} = \frac{y_n}{1 + h k}$

As we can see this approximation will exhibit the correct qualitative behaviour independent of the chosen step size, in stark contrast to the explicit scheme. This is very important for differential equations that are **stiff**.

These have gotten their own page: Stiff differential equation.

Numerical approximations of differential equations are a part of the usual mathematical curriculum, accordingly there is a plethora of textbooks available.

- Numerical ordinary differential equations, Wikipedia

category: computational methods