A Survey of the Implementation of Numerical Schemes for Linear Advection Equation

Abstract

The interpolation method in a semi-Lagrangian scheme is decisive to its performance. Given the number of grid points one is considering to use for the interpolation, it does not necessarily follow that maximum formal accuracy should give the best results. For the advection equation, the driving force of this method is the method of the characteristics, which accounts for the flow of information in the model equation. This leads naturally to an interpolation problem since the foot point is not in general located on a grid point. We use another interpolation scheme that will allow achieving the high order for the box initial condition.

Share and Cite:

Alzate, P. (2014) A Survey of the Implementation of Numerical Schemes for Linear Advection Equation. Advances in Pure Mathematics, 4, 467-479. doi: 10.4236/apm.2014.48052.

1. Introduction

The classical 1D linear advection equation is given by

(1)

We can see that Equation (1) is a 1-D version (linear) of the partial differential equations [1] , which describe advection of quantities such as energy, mass, heat, etc. Here, , and is a nonzero constant velocity. We can say that Equation (1) describes the motion of a scalar u as it is advected by a known velocity field.

We know that the unique solution of Equation (1) is determined by an initial condition where with an arbitrary function on.

An analysis of a numerical scheme implies to study the consistency, stability and accuracy. The goal of the analysis is to get an idea about how good a difference scheme is representing the linear advection equation. In the following we will make some analysis of the approximate difference schemes to the Equation (1).

Numerical problems arising with pollutions models are discussed in [2] . Textbooks that deal with advection problems are [3] and [4] The spectral-methods and finite elements for linear advection equations we refer are [5] and [6] respectively. There exists more recent bibliography on finite element methods, which can be consulted in [7] .

The paper is organized as follows. In Sections 2 and 3, we consider two cases firstly and here we study the implementation of the schemes Lax-Friedrich, Lax-Wendroff and RK3-TVD-WENO5 and we derive the expected GTE (Global Truncation Error) and we verify it by producing a convergence plot (by using the, and norm). After this, we repeat by using the box function

(2)

In Section 4, we consider linear and quadratic interpolation and we study the stability and accuracy by using semi-Lagrangian approach for linear advection equation and finally we produce a convergence plot for (2) with another interpolation scheme.

2. Implementation of the Schemes and GTE

Initially we consider the 1-D linear advection equation

(3)

(4)

We can to verify that the solution is, and therefore for [8] .

Now, we compute the global truncation error for the schemes as follows.

1) Lax-Friedrich. Here, the discretization of the advection equation by using Lax-Friedrich gives

(5)

and therefore we can verify

(6)

(7)

so the stability condition is

(8)

finally

(9)

2) Lax-Wendroff. Here, the discretization of the advection equation by using Lax-Wendroff gives

(10)

and therefore we can verify

(11)

and the stability condition (CFL) is

(12)

Therefore,

(13)

3) RK3-TVD + WENO5. For this scheme the one-step is

(14)

and the stability condition is

(15)

therefore,

(16)

Now, for all schemes we proceed by to build the spatial grid by letting, and we define the vector

(17)

(18)

which has N points. As the boundary conditions are periodic, we will have to make the following identifications,

To build the grid in time, we first for some r satisfying the CFL (condition). Therefore we define where is the final time. So we going to iterate until the time. Then, in general but at least. Here, all times steps are the same size dt. Finally, when computing the global truncation error, the only important thing is to always compute it at the same time for all grid resolutions. Now, the scheme (LF, LW or RK3-WENO5) is applied until is reached. Then the output is. The grid resolution dx, calculate what the true solution is at time and compute the norm of the errors by using

(19)

(20)

(21)

Here we iterate over the resolution by varying k in order to get a convergence plot of the various norms of the errors vs. grid size.

Lax-Friedrich. This scheme can be coded very efficiently using matrices. We can see that the scheme can be rewritten as

(22)

therefore taking into account the periodic boundary conditions

Lax-Wendroff. Similarly this scheme can be implemented by using

RK3-TVD-WENO5. For each point on the grid, we need to compute two intermediate values as follows.

(23)

(24)

(25)

Therefore, the code for WENO5, when solving a conservative equation of the form

(26)

provided u and f are. Then acts as the speed function. Then at the interior point. If, define

(27)

We can say that, then

(28)

(29)

(30)

(31)

(32)

(33)

finally we obtain

(34)

3. Test Problems

Example 1. We consider the condition, then by using the schemes we have:

• Lax-Friedrich. The convergence results are shows on Figure 1. (Convergence plot for in Log-Log scale, advected by using L-F scheme. at is plotted against.) The grid resolution was varied from to. So the expected orders of convergence were already visible at those resolutions.

• Lax-Wendroff. The convergence results are shown on Figure 2. (Convergence plot for in Log-Log scale, advected by using L-W scheme. at is plotted against.) As above, the grid resolution was varied from to.

• RK3-TVD + WENO5. The convergence results are shown on Figure 3. (Convergence plot for in Log-Log scale, advected by using L-W scheme. at is plotted against.) As above, the grid resolution was varied from to.

The norms errors behave as expected in the asymptotic behavior. This example underlines the importance of letting the error go to whenever possible. Here, since the computer time became unreasonably long for

Figure 1. Convergence plot for with L-F scheme.

Figure 2. Convergence plot for with L-W scheme.

Figure 3. Convergence plot for with RK3-TVD-WENO5 scheme.

high grid resolutions, this was not possible. However, as suggested in class, one way to observe the order of the global truncation error (GTE) is to increase the final time (for example) in order to let error in accumulate and become more significant than the error in.

Example 2. Consider the box condition (2), then we have

• Lax-Friedrich. The convergence results are shown on Figure 4. (Convergence plot for in Log-Log scale, advected by using L-W scheme. at is plotted against.) As above, the grid resolution was varied from to.

Therefore, since in deriving the LTE and GTE, we used the Taylor series of the function. But the box function being only, we cannot expect to equal its Taylor series point wise, and thereforethe above reasoning does not apply. It is interesting to watch the box evolve when advected with a L-F scheme. This is presented in a series of snapshots put together in Figure 5. (The true solution is plotted in red and the numerical solution is plotted in blue.) Clearly, the schemes fails to capture the discontinuities of the function, and its diffusive nature eventually leads to large errors near the discontinuities. This explains why the norm of the error cannot converge. This also explains why the norm, which is simply the area between the true solution and the numerical solution, improves with the grid resolution.

• Lax-Wendroff. The convergence results are shown on Figure 6. (Convergence plot for

Figure 4. Convergence plot for with L-F scheme.

Figure 5. Snapshots for with L-F scheme.

Figure 6. Convergence plot for with L-W scheme.

in Log-Log scale, advected by using L-W scheme. at is plotted against). As above, the grid resolution was varied from to. The slope for the, since there clearly isn’t convergence.

It is interesting to watch the box evolve when advected by a L-W scheme. This is presented in a series of snapshots put together in Figure 7 (true solution in red and numerical solution in blue). This scheme also fails to capture the discontinuities of the function, and its dispersive nature eventually leads to large errors near the discontinuities, where wild oscillations appear. However, the overall shape of the box is better preserved than when advected with L-F, which provides a simple explanation as to why the rate of convergence of the L1 norm is slightly better.

• RK3-TVD-WENO5. The convergence results are shown on Figure 8. (Convergence plot for box in log-log scale, advected by using RK3-TVD-WENO5 scheme.) As above, the grid resolution was varied from to The final time was increased to. Therefore We almost get first order convergence in the L1 norm, which is much better than with the previous two schemes. However, convergence is slower in the L2 norm and absent in the norm.

Again, it is interesting to watch the box evolve when advected by an RK3-TVD-WENO5 scheme. Although this scheme also fails to capture the discontinuities of the function, the overall shape is much better preserved than when advected with the previous two linear schemes. Although the norm cannot converge because of the large errors near the discontinuities, those errors do not spread out and pollute the solution, which explains why the rate of convergence of the L1 norm is almost 1.

4. Semi-Lagrangian Approach

The idea is to use various values of to build an interpolant and the get from. We use the formula for Lagrange interpolation in each case, here and. For the linear interpolation we use the two neighboring points and, therefore

Figure 7. Snapshots for with L-W scheme.

Figure 8. Convergence plot for with RK3-TVD-WENO5 scheme.

(35)

then

(36)

and finally

(37)

We can see that if we let and, then. Now, for the quadratic interpolationleft, using, and we have

(38)

then

(39)

finally

(40)

Here, if we let and, then Now, with quadratic interpolation-right and by using, and we have

(41)

therefore

(42)

finally we have

(43)

Now, if we let and, then.

We consider now a high-order interpolation, i.e. higher than quadratic. Proceeding in the same way in part above by using 4 points, in order to get a cubic interpolant. Using, , and we have

(44)

therefore,

(45)

finally,

(46)

Now, we can see the Stability as follows. Performing Von Neumann gives the following,

(47)

In order to find out for which values of r the scheme is stable, here we plotted for various values of r, ranging from and since that CFL condition for the other schemes was, the results shown on Figure 9 (plot of against for, the top straight line corresponds to and therefore for pointwise), indicate that ensures stability, since for all.

For the accuracy we compute the LTE of the scheme,

(48)

(49)

(50)

(51)

(52)

Therefore, if we use the CFL condition, we expect the GTE to be.

We can see the results for where the convergence is shown on Figure 10. Here the grid resolution was varied from to. Finally, for the convergence results are shown on Figure 11, where the grid resolution was varied from to.

Note. As for Lax-Friedrich and Lax-Wendroff, those results should not be surprising, because we cannot expect a method based on the Taylor series of a function to work for a C0 function.

We can see the box evolve when advected by a 3rd order scheme. This is presented in a series of snapshots put together in Figure 12. Although this scheme fails to capture the discontinuities of the function, just like the previous schemes, the oscillations created near the discontinuities don’t seem to grow very fast. Moreover, the overall shape of the box is (at least visually) better preserved that when advected with L-F of L-W, which provides a simple explanation as to why the rate of convergence of the L1 norm is better that with those schemes.

Figure 9. Plot of.

Figure 10. Convergence plot for advected using a 3rd order scheme.

Figure 11. Convergence plot for advected using a 3rd order scheme.

Figure 12. Snapshots for advected by a 3rd order scheme.

Acknowledgements

I would like to thank the referee for his valuable suggestions that improved the presentation of this paper and my gratitude to Department of Mathematics of the Universidad Tecnológica de Pereira (Colombia) and the group GEDNOL.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1] Strikwerda, J.C. (1989) Finite Difference Schemes and Partial Differential Equations. Wadsworth & Brooks, USA.
[2] McRea, G.J. and Godin, W.R. (1967) Numerical Solution of Atmospheric Diffusion for Chemically Reacting Flows. Journal of Computational Physics, 77, 1-42.
[3] Morton, K.W. (1980) Stability of Finite Difference Approximations to a Diffusion-Convection Equation. International Journal for Numerical Methods in Engineering, 15, 677-683.
http://dx.doi.org/10.1002/nme.1620150505
[4] Hundsdorfer, W. and Koren, B. (1995) A Positive Finite-Difference Advection Scheme Applied on Locally Refined Grids. Journal of Computational Physics, 117, 35-36. http://dx.doi.org/10.1006/jcph.1995.1042
[5] Canuto, C. and Hussaini, M. (1988) Spectral Methods in Fluids Dynamics. Springer Series in Computational Physics, Springer-Verlag, Berlin. http://dx.doi.org/10.1007/978-3-642-84108-8
[6] Mitchell, A.R. and Griffiths, D.F. (1980) The Finite Difference Method in Partial Differential Equations. John Wiley & Sons, Chichester.
[7] Mickens, R.E. (2000) Applications of Nonstandard Finite Differences Schemes. World Scientific Publishing, River Edge.
[8] Dehghan, M. (2005) On the Numerical Solution of the One-Dimensional Convection-Diffusion Equation. Mathematical Problems in Engineering, 1, 61-74. http://dx.doi.org/10.1155/MPE.2005.61

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.