# The Azimuth Project Discrete approximation scheme (changes)

Showing changes from revision #6 to #7: Added | Removed | Changed

# Contents

## Idea

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.

## Details

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)$

### Finite Differences

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:

###### Definition

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$

### Explicit Scheme

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$

### Implicit Scheme

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.

### 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

###### Definition

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$.

### Numerical Stability for Explicit and Implicit Schemes

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.

### Stiff Equations

These have gotten their own page: Stiff differential equation.

## References

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