The Azimuth Project
Discrete approximation scheme (Rev #6, changes)

Skip the Navigation Links | Home Page | All Pages | Recently Revised | Authors | Feeds | Export |

Showing changes from revision #5 to #6: 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.

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

Details

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

dydt=−ky \frac{d y}{d t} = - k y

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

y(t 0)=C 0 y(t_0) = C_0

we have as the unique solution

y(t)=C 0exp(−kt) 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 hh. Let’s fix a positive constant hh and define the discrete times

t n:=t n−1+h t_n := t_{n -1} + h

Replacing the differential quotient with a finite difference we get

y n+1−y nt n+1−t n=−ky n \frac{y_{n+1} - y_{n}}{t_{n+1} -t_{n}} = - k y_n

If we replace t n+1−t nt_{n+1} -t_{n} with hh and rearrange the terms a little bit we get

y n+1=(1−hk)y n y_{n+1} = (1 - h k) y_n

We assume that we know the value of y ny_n and need to calculate y n+1y_{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 hy_{h} corresponding to a step size hh, converges to the exact solution yy in a prescribed norm:

lim h→0‖y h−y‖=0 \lim_{h \to 0} \| y_{h} - y \| = 0

Explicit Scheme

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

y n+1=(1−hk)y n y_{n+1} = (1 - h k) y_n

Implicit Scheme

In the discretization of the equation

dydt=−ky \frac{d y}{d t} = - k y

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

y n+1−y nt n+1−t n=−ky n+1 \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+1y_{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+1y_{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 yy it is possible to choose a step size hh and a constant CC such that

max 0≤t≤T‖y h−y‖<C \max_{0 \le t \le T} \| y_{h} - y \| \lt C

is valid for every finite constant TT.

Numerical Stability for Explicit and Implicit Schemes

Looking at the explicit scheme of our example

y n+1=(1−hk)y n y_{n+1} = (1 - h k) y_n

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

h<1k 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 00. Such a condition is known as a condition of numerical stability.

But if we take our implicit approximation

y n+1−y nt n+1−t n=−ky n+1 \frac{y_{n+1} - y_{n}}{t_{n+1} -t_{n}} = - k y_{n+1}

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

y n+1=y n1+hk 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.

category: computational methods

sex shop sex shop sex shop sex shop sex shop lingerie sex shop atacado calcinhas uniformes profissionais uniformes dicas de sexo
Revision from November 6, 2011 22:22:44 by Odysseus
Forward in time (to current) | Back in time (5 more) | See current | Hide changes | History | Rollback | View: Source