A Survey of the Implementation of Numerical Schemes for Linear Advection Equation ()
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,
![](https://www.scirp.org/html/htmlimages\7-5300739x\8596b7ff-481f-4182-a9e0-85da50194595.png)
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
![](https://www.scirp.org/html/htmlimages\7-5300739x\528b61db-2749-468e-9280-0add753305df.png)
Lax-Wendroff. Similarly this scheme can be implemented by using
![](https://www.scirp.org/html/htmlimages\7-5300739x\988de55a-9cc8-4910-860c-690362d06d92.png)
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
![](https://www.scirp.org/html/htmlimages\7-5300739x\098e8676-ddc9-4489-8e58-2309ce6ff7fc.png)
Figure 1. Convergence plot for
with L-F scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\e87cd522-c161-4ff1-b34e-a7fd60509b3e.png)
Figure 2. Convergence plot for
with L-W scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\66623138-87ff-4f9f-ad56-17c5b4bd3e78.png)
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 ![](https://www.scirp.org/html/htmlimages\7-5300739x\9da8ac3b-6cf0-4cc0-a04c-a203cc195034.png)
![](https://www.scirp.org/html/htmlimages\7-5300739x\e394d2d3-1d3f-4d15-b127-21531bd3b75c.png)
Figure 4. Convergence plot for
with L-F scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\c0810a2b-87e2-43e6-90cd-c76bd165d381.png)
Figure 5. Snapshots for
with L-F scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\820a01c7-5e20-4457-bcf7-b400ac9a068b.png)
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
![](https://www.scirp.org/html/htmlimages\7-5300739x\e35267f3-ed27-411e-83c4-f0d456816858.png)
Figure 7. Snapshots for
with L-W scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\b3db5931-eb21-4bc6-b3f8-ef63ec58b1bd.png)
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.
![](https://www.scirp.org/html/htmlimages\7-5300739x\3a80ec65-50ea-4d8c-be0a-29d3af0c6351.png)
Figure 10. Convergence plot for
advected using a 3rd order scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\d17705bf-e1ef-45c9-86d7-de3a7927bce5.png)
Figure 11. Convergence plot for
advected using a 3rd order scheme.
![](https://www.scirp.org/html/htmlimages\7-5300739x\e93ee5df-ed4a-4412-bdf5-43afc6eabe9c.png)
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.