Ngô Quốc Anh

April 25, 2010

Explicit One-Step Schemes for the Advection Equation: The upwind scheme

Filed under: Giải tích 9 (MA5265), PDEs — Ngô Quốc Anh @ 1:56

Let us consider a very simple class of schemes solving the convection equations entitled the upwind schemes. Precisely, let us consider

\displaystyle u_t+cu_x=0, \quad x \in \mathbb R, t>0

together with the following initial data

\displaystyle u(x,0)=u_0(x), \quad x\in \mathbb R.

It is well-known that the above problem has a unique solution given by u(x, t ) = u_0(x - c t ), which is a right traveling wave of speed c.

Since the upwind schemes are well-known and appear in most of numerical analysis’s textbooks, what I am trying to do here is to give some basic ideas together with their motivation.

First of all, the original upwind schemes are just explicit one-step schemes. Upwind schemes use an adaptive or solution-sensitive finite difference stencil to numerically simulate more properly the direction of propagation of information in a flow field. The upwind schemes attempt to discretize hyperbolic partial differential equations by using differencing biased in the direction determined by the sign of the characteristic speeds. Historically, the origin of upwind methods can be traced back to the work of Courant, Isaacson, and Reeves who proposed the CIR method.

Discretization. Like the finite difference methods, we need to use a a grid with points (x_j , t_n) defined by

x_j=\pm j\Delta x, j \geqslant 0, \quad t^n = \pm n\Delta t, n \geqslant 0.

for some spatial grid size \Delta x and time step \Delta t.

As we saw in this entry, the characteristics play an important role and so we make a distinction between the cases c > 0 and c < 0.

The case c>0. Let us consider the case when c>0.

Basic idea. The key point here is to obtain a good approximation to time and spatial derivatives. As a explicit scheme, for the time derivative \frac{\partial u}{\partial t}, we use the forward difference approximation. To be exact, we use

\displaystyle\frac{{\partial u}}{{\partial t}}({x_j},{t_n}) = \frac{{u_j^{n + 1} - u_j^n}}{{\Delta t}}.

Since solutions to advection Equations are travelling waves, we have

\displaystyle u({x_j},{t^{n + 1}}) = u({x_j} - b\Delta t,{t^n}).

It follows from c>0 that

\displaystyle {x_j} - c\Delta t < {x_j}

The full picture of this is shown above where the dotted line is the characteristic through the point (x_j , t^{n+1}) facing back to the initial line t = 0. As we are going to approximate

\displaystyle\frac{{\partial u}}{{\partial x}}({x_j},{t_n})

and this scheme is just one-step, we may think about forward or backward in space.

If we use the forward in space scheme, we then have

\displaystyle \frac{{\partial u}}{{\partial x}}({x_j},{t_n}) = \frac{{u_{j + 1}^n - u_j^n}}{{\Delta x}}.

It is clear to see that the information of u_{j}^{n-1} is propagated to u_{j+1}^n. However, we need to use the information of u_{j}^{n-1} in order to evaluate u_j^n. Therefore this scheme is implicit. Therefore we need to use the backward in space scheme, precisely

\displaystyle \frac{{\partial u}}{{\partial x}}({x_j},{t_n}) =  \frac{{u_j^n - u_{j-1}^n}}{{\Delta x}}.

Adding all gives

\displaystyle\boxed{\frac{{u_j^{n + 1} - u_j^n}}{{\Delta t}} + c\frac{{u_j^n - u_{j-1}^n}}{{\Delta x}} = 0}.

This scheme is called the upwind scheme because it uses the numerical solution at the grid point (x_{j-1}, t^n), which lies upwind of (x_j,t^{n+1}).

Stability. The stability of this scheme is also well-know. In fact, one can rewrite the scheme as follows

\displaystyle u_j^{n + 1} = u_j^n - C\left( {u_j^n - u_{j - 1}^n} \right)

where C is the Courant number given by

\displaystyle C = c\frac{{\Delta t}}{{\Delta x}}.

The stability result says that the condition C\leqslant 1 yields the stability condition of the upwind scheme. In fact, once this condition is fulfilled, we have the following observation

\displaystyle {x_{j - 1}} < {x_j} - c\Delta t < {x_j}.

That means the information from u(x_{j-1},t^n) and u(x_j,t^n) used to calculate u(x_j,t^{n+1}) is enough.

The case c<0. Now when c<0, the approximation used to evaluate time derivative doesn’t change. However, regarding to spatial derivative, we need to use the forward in space scheme. Thus the scheme now reads as

\displaystyle\boxed{\frac{{u_j^{n + 1} - u_j^n}}{{\Delta t}} +  c\frac{{u_{j + 1}^n - u_j^n}}{{\Delta x}} = 0}.

This scheme is again first order consistent in \Delta t and \Delta x, since we used one-sided differences for the derivatives.

Second-order upwind scheme. The spatial accuracy of the first-order upwind scheme can be improved by choosing a more accurate finite difference stencil for the approximation of spatial derivative. For the second-order upwind scheme

If c>0, we use

\displaystyle\frac{{\partial u}}{{\partial x}}({x_j},{t_n}) = \frac{{3u_i^n - 4u_{i - 1}^n + u_{i - 2}^n}}{{2\Delta x}}

while c<0, we use

\displaystyle \frac{{\partial u}}{{\partial x}}({x_j},{t_n}) = \frac{{ - u_{i + 2}^n + 4u_{i + 1}^n - 3u_i^n}}{{2\Delta x}}.

This scheme is less diffusive compared to the first-order accurate scheme.

Third-order upwind scheme. For the third-order upwind scheme:

If c>0, we use

\displaystyle\frac{{\partial u}}{{\partial x}}({x_j},{t_n}) = \frac{{2{u_{i + 1}} + 3{u_i} - 6{u_{i - 1}} + {u_{i - 2}}}}{{6\Delta x}}

while c<0, we use

\displaystyle\frac{{\partial u}}{{\partial x}}({x_j},{t_n}) = \frac{{ - {u_{i + 2}} + 6{u_{i + 1}} - 3{u_i} - 2{u_{i - 1}}}}{{6\Delta x}}.

This scheme is less diffusive compared to the second-order accurate scheme. However, it is known to introduce slight dispersive errors in the region where the gradient is high.

See also:

  1. http://en.wikipedia.org/wiki/Upwind_scheme
  2. R. M. M. Mattheij et al., Partial Differential Equations: Modeling, Analysis, Computation, SIAM.

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: