Showing changes from revision #6 to #7:
Removed | Chan
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.
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:
This is an equation for the one dimensional real function with a positive real constant . This equation describes exponential decay, if we further impose an initial condition for like
we have as the unique solution
The ansatz of “finite differences” replaces differential quotients with finite differences for some discrete step size . Let’s fix a positive constant and define the discrete times
Replacing the differential quotient with a finite difference we get
If we replace with and rearrange the terms a little bit we get
We assume that we know the value of and need to calculate .
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 corresponding to a step size , converges to the exact solution in a prescribed norm:
In a finite difference approximation we assume that we know the value of and need to calculate the value of . If a discrete approximation scheme leads us to an equation with on the left and terms on the right that only involve variables that we already calculated, like , the scheme is called an explicit scheme. An example is taken from the first paragraph:
In the discretization of the equation
we chose to write on the right side, but we could choose as well, and get
This is called an implicit scheme, because it involves the variable that we need to calculate, , on the left and on the right side. In more general situations like this, it is not possible to get an equation for 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 it is possible to choose a step size and a constant such that
is valid for every finite constant .
Looking at the explicit scheme of our example
we note that we have to choose the step size according to
if we choose a bigger h then the approximation will run off to instead of approximating an exponential decay to . Such a condition is known as a condition of numerical stability.
But if we take our implicit approximation
and solve for , we get
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.