Abstract
These introductory lecture notes on numerical methods for hyperbolic equations are suitable for advanced undergraduate and postgraduate students in mathematics and engineering disciplines. More advanced approaches exist and will be indicated as appropriate. The material is divided into four sections. Section 1 presents an overview of hyperbolic equations and also some basic concepts on numerical discretization techniques. Section 2 deals with a specific example, the system of non-linear shallow water equations; the equations are analysed and the Riemann problem is solved exactly in complete detail. In Sect. 3 we first present the Godunov method as applied to a generic hyperbolic system and then specialised to the shallow water system in one space dimension; approximate solution methods for the Riemann problem are also given. Finally, Sect. 4 gives a brief overview of the ADER approach to construct high-order numerical methods for hyperbolic equations, based on the first order Godunov method. Much of the material of these lectures has been taken from the author’s text books (Toro, Riemann solvers and numerical methods for fluid dynamics. A practical introduction, 3rd edn. Springer, Berlin (2009) and Toro, Shock-capturing methods for free-surface shallow flows. Wiley, Chichester (2001)), where further reading material can be found. I also recommend the textbook by Godlewski and Raviart (Numerical approximation of hyperbolic systems of conservation laws. Springer, New York (1996)) and that by LeVeque (Finite volume methods for hyperbolic problems. Cambridge University Press, Cambridge (2002)).
Access provided by CONRICYT-eBooks. Download chapter PDF
Similar content being viewed by others
1 Hyperbolic Equations
Many problems in science and engineering (e.g. wave propagation and transport phenomena) are governed by advection-diffusion-reaction partial differential equations (PDEs). In the scalar case (a single equation) we may write
where q(x, t) is the unknown, called the dependent variable; q(x, t) is a function of two independent variables x and t; f(q) is a prescribed function of q called the flux, or physical flux; s(x, t, q) is also a prescribed function, called the source term. The last term is called the diffusion term; α(x, t, q(x, t)) is the diffusion coefficient. Equation (1) is parabolic due to the presence of the viscous term, a second-order term. In the rest of these lectures we shall be concerned exclusively with hyperbolic equations.
1.1 The Linear Advection Equation and Basic Concepts
A particular example of (1) is obtained by choosing
with λ a constant wave propagation speed, which leads to the linear advection equation (LAE)
Initial Value Problem (IVP) for the Linear Advection Equation
We study the simplest case of (1), the linear advection equation, in which the spatial domain is infinite and an initial condition at the initial time t = 0 is prescribed, namely
where h(x) is a prescribed function of distance x. Equation (4) defines a pure initial-value problem or Cauchy problem.
Characteristic Curves and the Solution
Characteristic curves, or characteristics, are functions x(t) in the x-t half-plane of independent variables satisfying the IVP for an ordinary differential equation (ODE), namely
whose solution is immediate and reads
Characteristic x(t) in the t-x plane given by (6); x0: foot of characteristic; positive characteristic speed λ
Family of characteristic curves x(t) in the x-t plane, for the case of positive characteristic speed λ. Compare with Fig. 1
Figure 1 illustrates solution (6). In practice it is more common to represent characteristics in the x-t plane. The inclination of the characteristics depends on the characteristic speed λ, in fact on 1∕λ. In the linear case with constant coefficients, characteristics are all parallel to each other, as seen in Fig. 2.
Consider now the time-rate of change (or total derivative) of q(x(t), t) along a characteristic curve x = x(t)
But the curve x(t) satisfies the ODE in (5). Then (7) becomes
That is, q(x, t) is constant along x = x0 + λt. Consequently, the PDE in (4) becomes an ODE, namely
This ODE states that q(x, t) is constant along the characteristic. From the above observations, the value of q(x, t) at a point (x, t) on the characteristic curve passing through (x, t) is equal to the value of q at the point x0 called the foot of the characteristic. That is
But from (6)
and therefore the solution of IVP (4) is
which is the initial condition h in (4) evaluated at the position x − λt. Figure 3 shows the three possible cases that can occur due to the value of the characteristic speed.
The solution at point \((\hat x, \hat t)\) is found by tracing the characteristic from \((\hat x,\hat t)\) back to its foot x0. There are three possibilities: (a) λ > 0, (b) λ = 0, (c) λ < 0
IVP Example
Here we study in detail the following IVP
Solution
According to formula (10) the solution of (11) is
Note that for a given speed λ and a chosen time t, the solution is simply a function of x, called a profile. See Fig. 4.
The Riemann Problem
Riemann problem for the linear advection equation is the special IVP
where qL (left of 0) and qR (right of 0) are constants.
Solution of the Riemann Problem
From (10) it is obvious that the solution is
See Fig. 5.
Solution of Riemann problem (13). Frame (a) displays piece-wise constant initial condition q(x, 0). Frame (b) displays picture of characteristics in x-t space. Frame (c) shows solution profiles q(x, tk) at different times tk
1.2 Linear Systems
We now consider a general one-dimensional, time-dependent system of m linear hyperbolic equations with source terms, namely
Here Q: unknowns, A: matrix of coefficients (constant) and S(Q): source terms. These are given as follows
Note that the linear advection equation (3) is a special case of (15).
Eigenvalues and Eigenvectors
The eigenvalues of system (15) are the roots of the characteristic polynomial
Here I: m × m unit matrix; \(\hat \lambda \): a parameter; λi: eigenvalues, that is roots of (17), which if real numbers, are conventionally written in increasing order
A right eigenvector Ri of A corresponding to λi is column vector
such that
The full set of m right eigenvectors corresponding to the eigenvalues (18) are
A left eigenvector Li of A corresponding to λi is the row vector
such that
The m eigenvalues (18) generate corresponding m left eigenvectors
Hyperbolic System
A system (15) is said to be hyperbolic if A has m real eigenvalues and a corresponding complete set of m linearly independent eigenvectors.
Note that for hyperbolicity, the eigenvalues are not required to be all distinct. What is important is that there is a complete set of linearly independent eigenvectors, corresponding to the real eigenvalues.
Strictly Hyperbolic System
A hyperbolic system is said to be strictly hyperbolic if all eigenvalues of the system are distinct.
Weakly Hyperbolic System
A system may have real but not distinct eigenvalues and still be hyperbolic if a complete set of linearly independent eigenvectors exists. However if all eigenvalues are real but no complete set of linearly independent eigenvectors exists then the system is called weakly hyperbolic, not to be mistaken with non-strictly hyperbolic.
Orthonormality of Eigenvectors
The eigenvectors Li and Rj are orthonormal if
Diagonalization and Characteristic Variables
Consider R = [R1 , … , Ri , … , Rm]: matrix whose columns are the right eigenvectors; Λ: diagonal matrix formed by eigenvalues. In full
Proposition
If A is the coefficient matrix of a hyperbolic system (15) then
In this case A is said to be diagonalisable and consequently system (15) is said to be diagonalisable. The proof is left as an exercise.
Characteristic Variables
The existence of R−1 makes it possible to define the characteristic variables C = [c1, c2, …, cm]T via
Calculating the partial derivatives, recalling that the coefficient matrix is constant, we have
and direct substitution of the these expressions into Eq. (15) gives
Multiplication of this equation from the left by R−1 and use of (27) gives
This is called the canonical form or characteristic form of system (15). Assuming \(\hat {\mathbf {S}}=\mathbf {0}\) and writing the equations in full, we have
Clearly, each equation i-th of this system is of the form
and involves the single unknown ci(x, t), which is decoupled from the remaining variables. Moreover, this equations is identical to the linear advection equation (3), with characteristic speed λi.
We have m decoupled equations, each one defining a characteristic curve. Thus, at any chosen point \((\hat x, \hat t)\) in the x-t half-plane there are m characteristic curves xi(t) passing through \((\hat x, \hat t)\) and satisfying the m ODEs
as depicted in Fig. 6.
The solution at a point \((\hat x, \hat t)\) depends on the initial condition at the foot \(x_{i}^{(0)}\) of each characteristic \(x_{i}(t) = x_{i}^{(0)} + \lambda _{i} t\)
Remarks
-
Each characteristic curve \(x_{i}(t) = x_{i}^{(0)} + \lambda _{i} t\) intersects the x-axis at the point \(x_{i}^{(0)}\), which is the foot of the characteristic passing through the point \((\hat x, \hat t)\). The point \(x_{i}^{(0)}\) is given as
$$\displaystyle \begin{aligned} x_{i}^{(0)} = \hat x - \lambda_{i} \hat t \;, \mbox{ for } i=1,2,\ldots,m \;. \end{aligned} $$(33)See Fig. 6.
-
Each Eq. (31) is just a linear advection equation whose solution at \((\hat x, \hat t)\) is given by
$$\displaystyle \begin{aligned} c_{i}(\hat x, \hat t) = c_{i}^{(0)}( x_{i}^{(0)} ) = c_{i}^{(0)}( \hat x - \lambda_{i} \hat t ) \;, \mbox{ for } i=1,2,\ldots,m \;, \end{aligned} $$(34)where \(c_{i}^{(0)}(x)\) is the initial condition, at the initial time. The initial conditions for the characteristic variables are obtained from the transformation (28) applied to the initial condition Q(x, 0).
-
Given the assumed order (18) of the distinct eigenvalues the following inequalities are satisfied.
$$\displaystyle \begin{aligned} x_{m}^{(0)} < x_{m-1}^{(0)} < \ldots < x_{2}^{(0)} < x_{1}^{(0)} \;. \end{aligned} $$(35)
Domain of Dependence
The interval \([ x_{m}^{(0)}, x_{1}^{(0)}]\) is called the domain of dependence of the point \((\hat x, \hat t)\). See Fig. 6. The solution at \((\hat x, \hat t)\) depends exclusively on initial data at points in the interval \([ x_{m}^{(0)}, x_{1}^{(0)}]\). This is a distinguishing feature of hyperbolic equations. The initial data outside the domain of dependence can be changed in any manner we wish but this will not affect the solution at the point \((\hat x, \hat t)\).
Proposition: The General Initial-Value Problem
The solution of the general IVP for the linear homogeneous hyperbolic system
is given by
The coefficient ci(x, t) of the right eigenvector Ri is a characteristic variable. The proof is left as an exercise.
Remarks
-
1.
The function ci(x, t) is the coefficient of Ri in an eigenvector expansion of the solution vector Q(x, t).
-
2.
Given a point (x, t) in the x-t plane, the solution Q(x, t) depends only on the initial data at the m points \(x_{0}^{(i)}= x - \lambda _{i}t\). See Fig. 6.
-
3.
These points are the intersections of the characteristics of speed λi with the x-axis.
-
4.
Solution (37) represents superposition of m waves of unchanged shape \(c_{i}^{(0)}(x){\mathbf {R}}_{i}\) propagated with speed λi.
Proposition: The Riemann Problem Solution
The solution of Riemann problem
with QL and QR two constant vectors, is given by
where
and I = I(x, t) is the maximum value of i for which x − λi t > 0. The proof is left as an exercise.
Remarks on the Solution of the Riemann Problem
-
1.
The initial data consists of two constant vectors QL and QR, separated by a discontinuity at x = 0.
-
2.
This is a special case of IVP (36).
-
3.
The structure of the solution of the Riemann problem (38) is depicted in Fig. 7, in the x-t plane.
Fig. 7 
Structure of the solution of the Riemann problem. There are m waves that divide the half x-t plane into m + 1 regions (wedges) \({\mathcal {R}}_{i}\), with i = 0, 1, …, m
-
4.
The solution consists of a fan of m waves emanating from the origin, one wave for each eigenvalue λi. The speed of the wave i is the eigenvalue λi.
-
5.
These m waves divide the x-t half plane into m + 1 constant regions
$$\displaystyle \begin{aligned} {\mathcal{R}}_{i} =\left\{(x,t)/ -\infty <x< \infty; \,t \ge 0;\, \lambda_{i} <\frac{x}{t} < \lambda_{i+1} \right\} \;, \end{aligned} $$(41)for i = 1, …, m − 1; \({\mathcal {R}}_{0}\) corresponds to the initial data QL and \({\mathcal {R}}_{m}\) corresponds to the initial data QR. See Fig. 7.
Solving the Riemann problem means finding constant values for Q in regions \({\mathcal {R}}_{i}\) for = 1, …, m − 1.
Corollary
The solution of the Riemann problem may be expressed as
where the coefficients ΔC = [δ1, …, δi, …, δm]T are the solution to the linear algebraic system
This form is more convenient. We only need to solve one linear system. The proof is left as an exercise. Figure 8 illustrates the solution at a point \((\hat x,\hat t)\).
The solution of the Riemann problem at a point \((\hat x,\hat t)\) depends on the associated index \(I = I(\hat x,\hat t)\)
1.3 Non-linear Scalar Equations: Definitions and Examples
Consider the first-order PDE for the unknown function q(x, t)
This equation is called a conservation law, in which q is the conserved variable; f(q) is the flux function or physical flux, a prescribed function of q. The equation is said to be written in differential, conservative form. One may express (44) in quasi-linear form as
Here λ(q) is called characteristic speed.
Equations of the type (44) may be characterised by the behaviour of the flux f(q) and its derivative, namely the characteristic speed λ(q) = f′(q). There are three cases:
-
1.
Convex flux: λ(q) is a monotone increasing function of q, that is
$$\displaystyle \begin{aligned} \frac{d}{d q} \lambda (q) = \lambda '(q) = f''(q) > 0 \;, \hspace{2mm} \forall q \;. \end{aligned} $$(46) -
2.
Concave flux: λ(q) is a monotone decreasing function of q, that is
$$\displaystyle \begin{aligned} \frac{d }{d q} \lambda (q) = \lambda '(q) = f''(q) < 0 \;, \hspace{2mm} \forall q \;. \end{aligned} $$(47) -
3.
Non-convex, non-concave flux: λ(q) vanishes for some q, that is
$$\displaystyle \begin{aligned} \frac{d }{d q} \lambda (q) = \lambda '(q)= f''(q) = 0 \;, \hspace{2mm} \mbox{for some} \; q \;. \end{aligned} $$(48)
Example: The Inviscid Burgers’ Equation
The flux is convex; the monotone increasing behaviour of λ(q) means that larger values of q propagate faster than smaller values of q. This leads to wave distortion and shock formation. We note that the true Burgers equation is viscous, namely
where α is a viscosity (or diffusion) coefficient.
Example: A Traffic Flow Equation
Here umax ≥ 0 and qmax > 0 are two constants, with 0 < q ≤ qmax. The flux is concave, larger values of q will propagate more slowly than smaller values of q, the opposite behaviour to that of Burgers’ equation.
Solution Along Characteristics
Consider the initial-value problem (or Cauchy problem)
As for LAE, solutions along characteristic curves x = x(t), with
can be defined as
Figure 9 depicts the situation.
Characteristic curve x(t) = x0 + λ(h(x0)) t emanating from x0: foot of the characteristic
Crossing Characteristics
For non-linear equations, characteristics are no longer parallel, as in the linear case. Therefore, characteristic curves may cross, as illustrated in Fig. 10.
Characteristics from \(x_{0}^{(1)}\) and \(x_{0}^{(2)}\) carry different initial values \(h(x_{0}^{(1)})\) and \(h(x_{0}^{(2)})\), leading to multi-valued solutions
Shock Formation: A Numerical Example
For non-linear equations, even if the initial data is continuous, discontinuities may develop in time. This is illustrated in Fig. 11 below, where a sequence of profiles corresponding to an increasing sequence of time values is shown, starting from t = 0, the initial condition.
Shock wave formation from smooth initial condition at time t = 0. Burgers’ equation solved numerically with the first-order Godunov method on a very fine mesh
The phenomenon of shock formation in non-linear equations calls for the extension of the definition of solution. To this end the equations are reformulated in terms of integral relations that no longer require continuity of the solution.
Integral Forms of the Equation
Consider the general case written in differential conservative form
This equation includes a source term and is thus called a balance law. If s(q(x, t)) = 0 then the equation is a conservation law.
Here we study integral forms, to accommodate discontinuous solutions. We shall also derive a condition to be satisfied at discontinuities. To this end we consider a control volume V in the x-t plane, depicted in Fig. 12, defined as
We integrate Eq. (54) in space and time in the control volume V
On rearranging the space and time integrals we obtain
Control volume V = [xL, xR] × [t1, t2] in x-t space. Equations will be integrated exactly on this volume to derive integral forms of the conservation laws
Exact space-time integration gives the integral form of the balance law (54), namely
In the absence of the source term, the integral form states that the amount of q(x, t) in the interval [xL, xR] at time t = t2 is equal to the amount of q(x, t) in the interval [xL, xR] at time t = t1 plus a difference of time integrals of the fluxes at the extreme points. In the presence of a source term this statement is modified appropriately.
It is also convenient to obtain an averaged version of (58), namely
The Finite Volume Formula
The integral expression (59) can be written as
which is exact, with the following definitions
Numerical methods called finite volume methods, use the finite volume formula (60) to compute approximate solutions in which qold is a known average of the solution at the previous time level and the remaining terms on the right hand side of (60) are found by appropriate approximations of the integrals in (61). The computational parameters Δt and Δx must be prescribed to complete the scheme to compute qnew.
Generalised Solutions and Rankine-Hugoniot Conditions
A generalised (or weak) solution of the conservation law (54) is a function q(x, t) that satisfies the integral form (58). Weak solutions admit discontinuities (shocks), which satisfy the Rankine-Hugoniot jump condition.
Proposition: Rankine-Hugoniot Condition
A discontinuity of a weak solution of the conservation law (54), no source term, satisfies the Rankine-Hugoniot jump condition across it, namely
where q(sL, t) and q(sR, t) are limiting values from left and right of the discontinuity; f(q(sR, t)) and f(q(sL, t)) are the corresponding flux values and s is the speed of the discontinuity. For the proof see [1].
Summarising
in order to admit discontinuous solutions one needs to formulate the equations in integral form and enforce the Rankine-Hugoniot condition across discontinuities, while in smooth parts of the solution one may formulate equations in differential form.
Example: Burgers’s Equation
Assume a shock wave of speed s with states qL and qR. The Rankine-Hugoniot condition gives
from which the shock speed is given by
This is a very special case. The shock speed is a simple arithmetic average of the characteristic speeds either side of the shock.
A Non-uniqueness Example
The enlarged set of solutions of the integral formulation includes smooth (classical) and discontinuous solutions. However, now the set is too large, it contains spurious, non-physical solutions. Hence this requires an admissibility criterion to discard unphysical shocks. To illustrate the question of non-uniqueness we consider the following example:
Solution 1: Rarefaction Wave
One solution of the problem is the rarefaction wave (smooth)
Figure 13 illustrates solution and the corresponding picture of characteristics.
Solution 2: Shock Wave
Another, discontinuous, solution (shock) is given as
Figure 14 shows the shock solution to problem (64). Note that characteristics diverge from the shock and the solution is therefore non-admissible. So the initial value problem (64) has at least two solutions.
Admissible Shocks: The Lax Entropy Condition
The proposed solution (66) is not accepted as a physical solution. Rarefaction shocks are excluded. Admissible discontinuities are those arising from compression. This compressibility condition is ensured by the Lax entropy condition:
s: shock speed, λ(qL) and λ(qR) are characteristic speeds. Note that characteristics run into the shock, which is compressed by the characteristics, see Fig. 15.
Picture of characteristics for an entropy-satisfying shock. Characteristic curves run into the shock path
The Riemann Problem for Burgers’s Equation
The problem is defined as
The solution is given by the following two cases, shock if qL > qR and rarefaction otherwise:
Figure 16 illustrates the solution structure for the two cases. The bottom frame shows the shock case while the top frame shows the rarefaction case.
Solution of the Riemann problem for the Burgers equation. Frame (a): shock wave if qL > qR. Frame (b): rarefaction wave if qL ≤ qR
First-Order Non-linear Systems
To end this introductory section we state that the general setting is that of non-linear systems of m hyperbolic balance laws in three space dimensions, which written in differential conservative form read
where
Here the independent variables are: x, y, z and t. Q(x, y, z, t) is the vector of dependent variables, called conserved variables; F(Q) is the flux vector in the x-direction; G(Q) is the flux vector in the y-direction and H(Q) is the flux vector in the z-direction; S(Q) is the vector of source terms. Fluxes and sources are prescribed functions of Q(x, y, z, t).
In this chapter we deal exclusively with the one-dimensional case (1D). For the more general case see for example [1,2,3] and [4].
1.4 Numerical Approximation of Hyperbolic Equations
Here we introduce some basic concepts on numerical discretization methods for hyperbolic equations, all based on the simplest equation. To this end we first consider the initial-boundary value problem (IBVP) for the linear advection equation
Here [a, b] defines the spatial domain; h(x) is the initial condition (IC) at the initial time t = 0, a prescribed function of x; bL(t) and bR(t) are prescribed functions of time and define boundary conditions (BCs) at x = a (left) and at x = b (right).
Finite Difference Discretisation
One approach to solve problem (72) is by the method of finite differences, which requires the following steps:
-
1.
Partition of the spatial domain [a, b] into M + 2 equidistant points
$$\displaystyle \begin{aligned} x_{i} = a + i \varDelta x \;, \hspace{2mm} i=0,\ldots, M+1 \;, \hspace{2mm} \varDelta x = \frac{b-a}{M+1} \;, \end{aligned} $$(73)where M is a chosen positive integer. See Fig. 17. There are M interior points: x1, x2, …, xM; and two boundary points: x0 = a and xM+1 = b.
Fig. 17 
Finite difference mesh defining a discrete set of points (xi, tn) resulting from partitions of the spatial x and temporal t domains
-
2.
Partition of the temporal domain [0, Tout] into a set of time points, or time levels,
$$\displaystyle \begin{aligned} t_{n} = n \varDelta t \;, \hspace{2mm} n=0 \;, \ldots, N_{out} \;, \ldots \;. \end{aligned} $$(74)See Fig. 17. Here t0 = 0: initial time; Tout = ΔtNout; Δt: timestep. We assume a fixed relationship between Δt and Δx of the form
$$\displaystyle \begin{aligned} \varDelta x = \varDelta t \times K \;, \hspace{2mm} K>0: \mbox{constant} \;. \end{aligned} $$(75)
The spatial mesh parameter Δx is chosen through the choice of M, that is, the number of interior points. There are no particular constraints in choosing M. The choice of the time step Δt is constrained by accuracy or stability considerations [4].
Discrete Values
The continuous domain [a, b] × [0, ∞) has been replaced by a mesh made up of a finite number of points (xi, tn). We now need to replace the continuous distribution of the function q(x, t) by a finite number of discrete values q(xi, tn) associated with these points. Then in order to solve the differential equation in this discrete setting we also need to represent in discrete form the partial derivatives ∂t q(x, t) and ∂x q(x, t) in (72). Here we do so by finite difference approximations. In this manner the partial differential equation is represented by a difference equation, an expression that relates approximate discrete values of the solution at neighbouring points. The differential operator is replaced by a numerical operator, as we shall see.
Consider the generic point (xi, tn) of the mesh, as shown in Fig. 17. We seek an approximation to q(xi, tn) and this will be denoted by \(q_{i}^{n}\), that is
The temporal partial derivative ∂t q(x, t) can be approximated in a variety of ways, such as
Analogously, for the spatial partial derivative ∂x q(x, t) in (72) at the point (xi, tn) we write
Now, various combinations of these finite difference approximations will lead to various well-known methods.
The Method of Godunov: Finite Difference Version
This method uses the following approximations to partial derivatives
Remarks
-
1.
The time derivative is approximated by a forward-in-time formula.
-
2.
The space derivative is approximated by a one-sided, upwind, space derivative discretisation, according to the sign of the wave propagation speed.
-
3.
For linear equations the method was first proposed Courant, Isaacson and Rees (1952).
-
4.
Godunov [5] extended the upwind method in conservation form to solve non-linear systems of hyperbolic equations, see Sect. 3.
The differential operator in (72) is
which when applied to the point (xi, tn) of the mesh, for λ > 0, becomes
Suppressing \(\mathcal {{O}}(\varDelta t)+\mathcal {{O}}(\varDelta x)\) and replacing q(xi, tn) by \(q_{i}^{n}\) gives
Solving for \(q_{i}^{n+1}\) we obtain the numerical scheme
The Courant-Friedrichs-Lewy number, or the CFL number, or simply Courant number is defined as
This is a dimensionless quantity, it is the ratio of the speed λ in the PDE in (72) and the mesh speed Δx∕Δt. Then the Godunov upwind scheme becomes
Figure 18 displays the stencil of scheme (84), which is the set of points of the mesh that contribute to the scheme
Stencil for Godunov’s method for positive characteristic speed λ. Note the one-sided (upwind) character of the stencil
The FTCS method (Forward-in-Time Centred-in-Space) results from the following approximations to the partial derivatives
Substituting of these into the PDE, suppressing error terms and replacing exact values by approximate values, yields
Solving for \(q_{i}^{n+1}\) we obtain the FTCS numerical scheme
Figure 19 shows the stencil.
Stencil for the FTCS method. Note the symmetric character of the stencil
Unfortunately, FTCS is useless; it is unconditionally unstable. FTCS uses the same approximation to the time derivative as the Godunov method, but the spatial derivative is approximated via a centred, second-order accurate, discretization. Naively, one would have expected a better method than Godunov’s method. There are two ways to rescue FTCS. One modification results in the explicit Lax-Friedrichs scheme. The other way is to resort to an implicit version.
The Lax-Friedrichs method results from replacing \(q_{i}^{n}\) in the approximation to the time derivative of FTCS by a mean value, that is
Then
yielding the Lax-Friedrichs scheme
whose stencil is shown in Fig. 20.
Stencil for the Lax-Friedrichs method. Note the symmetry of the stencil and the missing point (xi, tn)
The Lax-Wendroff Method
The construction of this method follows a different approach, via the following steps:
-
1.
The solution at (xi, tn+1) is expressed as a Taylor series in time
$$\displaystyle \begin{aligned} q(x_{i},t_{n+1}) = q(x_{i},t_{n}) + \varDelta t \partial_{t} q(x_{i},t_{n}) + \frac{1}{2} \varDelta t^{2} \partial^{(2)}_{t} q(x_{i},t_{n}) + \mathcal{{O}}(\varDelta t^{3}) \;. \end{aligned} $$(90) -
2.
By means of the Cauchy-Kowalewskaya method (or Lax-Wendroff procedure, as is sometimes called) one uses the PDE in (72) to replace time derivatives by space derivatives
$$\displaystyle \begin{aligned} \partial_{t} q(x,t) = - \lambda \partial_{x} q(x,t) \;, \hspace{2mm} \partial^{(2)}_{t}q(x,t) = \lambda^{2} \partial^{(2)}_{x}q(x,t)\;. \end{aligned} $$(91)In fact, for any order k, one can prove
$$\displaystyle \begin{aligned} \partial^{(k)}_{t}q(x,t) = (-\lambda)^{k} \partial^{(k)}_{x}q(x,t) \;. \end{aligned} $$(92) -
3.
By substituting (91) into (90) one obtains
$$\displaystyle \begin{aligned} q(x_{i},t_{n+1}) = q(x_{i},t_{n}) - \varDelta t \lambda \partial_{x}q(x_{i},t_{n}) + \frac{1}{2} \varDelta t^{2} \lambda^{2} \partial^{(2)}_{x} q(x_{i},t_{n}) + \mathcal{{O}}(\varDelta t^{3}) \; \end{aligned} $$(93) -
4.
The spatial derivatives are approximated by centred finite differences
$$\displaystyle \begin{aligned} \left.\begin{array}{l} \displaystyle{ \partial_{x}q(x_{i},t_{n}) = \frac{q(x_{i+1},t_{n}) - q(x_{i-1},t_{n})} {2\varDelta x}} + \mathcal{{O}}(\varDelta x^{2}) \;, \\ \\ \displaystyle{ \partial_{x}^{(2)} q(x_{i},t_{n})=\frac{q(x_{i+1},t_{n}) - 2 q(x_{i},t_{n})+q(x_{i-1},t_{n})}{\varDelta x^{2}}}+\mathcal{{O}}(\varDelta x^{2}) \;. \end{array}\right\} \end{aligned} $$(94) -
5.
Finally, by substituting (94) into (93), neglecting truncation errors and replacing exact values q(xi, tn) by \(q_{i}^{n}\) one obtains the Lax-Wendroff scheme
$$\displaystyle \begin{aligned} q_{i}^{n+1} = \frac{1}{2} c(1+c) q_{i-1}^{n} + (1-c^{2}) q_{i}^{n} - \frac{1}{2}c(1-c) q_{i+1}^{n} \;, \end{aligned} $$(95)whose stencil is shown in Fig. 21.
Fig. 21 
Stencil for the Lax-Wendroff method. Note the symmetry of the stencil
General Form of a Scheme and Examples
All explicit schemes studied so far can be written in the general form
with l, r two non-negative integers and H(…) a real-valued function of l + r + 1 arguments and
is a point-wise value that approximates the true solution q(x, t) at the mesh point (xi, tn), with xi = iΔx, tn = nΔt.
Example: The Godunov Finite Difference Method
When the Godunov scheme is written as in (96), we have
Linear Schemes
Linear schemes are a special class of schemes (96) for the linear advection equation in (72), of the form
in which the coefficients bk are constant, that is, they do not depend on the solution.
Consider now two examples.
-
1.
For the Godunov finite difference method we have two cases: For λ > 0 l = 1, r = 0, b−1 = c and b0 = 1 − c. For λ < 0 we have l = 0, r = 1, b0 = 1 + c, b1 = −c.
-
2.
For the Lax-Wendroff method we have l = 1, r = 1, \(b_{-1}=\frac {1}{2}(1+c)c\), b0 = 1 − c2, \(b_{1}=-\frac {1}{2}(1-c)c\).
Monotone Schemes
A numerical scheme of the form (96) is called monotone if H satisfies
Remark
a linear scheme is monotone if and only if all its coefficients are non-negative. This follows from the definitions of linear schemes and monotonicity.
A Shortcut to Accuracy Through the Accuracy Lemma
A linear scheme of the form (99) is p-th order accurate in space and time (p ≥ 0) in the sense of local truncation error, if and only if
For notational convenience we introduce 00 = 1.
Proof
For the proof and extensions to two and three dimensions see [1].
Example: The Godunov Upwind Finite Difference Method For λ > 0 the scheme is
l = 1, r = 0, b−1 = c, b0 = 1 − c. Then we need to verify identity (101) for all possible non-negative integer values of η.
This merely says that the sum of the coefficients of the scheme is unity.
The Godunov scheme is first-order accurate. But just for fun we try:
Thus the Godunov scheme is not second-order accurate, except for the trivial cases c = 0 and c = 1.
Godunov’s Theorem [5]
There are no monotone, linear schemes (99) for the linear advection equation with constant λ, of accuracy two or higher.
Proof
It is sufficient to prove that there is no second order, linear, monotone method for LAE. Proceed by contradiction and assume there is a second order, linear, monotone method for LAE. From the accuracy lemma we must have:
But, in particular, from (103) plus some algebraic manipulations one obtains
This implies a contradiction; for a monotone scheme all coefficients bk are non-negative but not simultaneously zero. Thus Godunov’s theorem is true \(\Box \).
Consequences of Godunov’s Theorem
From the theorem we have that linear monotone schemes are at most first-order accurate. But first-order methods are too inaccurate to be of practical use and therefore one must search for other classes of schemes. This is down to finding ways of circumventing Godunov’s theorem.The key to this lies on the assumption of linear schemes. Thus a necessary condition for a numerical scheme to be oscillation-free (without new extrema) and of high-order of accuracy (for smooth solutions) is to be non-linear. In simple terms: Schemes must be non-linear, even when applied to linear equations.
Recall that schemes can be expressed in the general form (96). In what follows we introduce other forms.
The conservative form is a particular class of schemes for hyperbolic equations and can be written in the form
where \(f_{i+\frac {1}{2}}\) is the numerical flux. See definition (60).
The Viscous Form of a Scheme
This requires a function \(d_{i+\frac {1}{2}}\) of 2k variables
such that a three-point scheme can be written as
The function \(d_{i+\frac {1}{2}}\) is called the coefficient of numerical viscosity.
Viscous Form of a Three-Point Linear Scheme
We study the viscous form a three-point linear scheme of the form
The coefficients b−1, b0 and b1 are constant. Assume the scheme to be at least first-order. Then from the accuracy lemma, see (101), we have
System (110) gives a one-parameter family of solutions. From the first equation we introduce d = b−1 + b1 = 1 − b0 and thus
Now in terms of d scheme (109) becomes
This is the viscous form of scheme (109) and d is the coefficient of numerical viscosity of the scheme.
Remarks on the Viscous Form
-
1.
Particular values of d give particular schemes, as we shall see.
-
2.
The stability condition becomes
$$\displaystyle \begin{aligned} c^{2} \le d \le 1 \;. \end{aligned} $$(113) -
3.
The monotonicity condition is
$$\displaystyle \begin{aligned} c \le d \le 1 \;. \end{aligned} $$(114) -
4.
A truncation error analysis gives coefficient of numerical viscosity
$$\displaystyle \begin{aligned} \alpha_{visc} = \frac{1}{2} \varDelta x \lambda \left( \frac{d - c^{2}}{c} \right) \;. \end{aligned} $$(115)
Thus effectively the coefficient d measures the truncation error of the scheme.
Proposition
The Godunov upwind scheme for the linear advection equation is the monotone scheme with the smallest truncation error. The proof is left as an exercise.
Well-known schemes are obtained by an appropriate choice d. The following four choices for d give four well-known numerical schemes:
Figure 22 shows the coefficient of numerical viscosity for all four schemes above. The region of monotone methods is contained in the dark triangular region. Schemes outside this region are not monotone. Of the monotone methods the least accurate method is the Lax-Friedrichs method and the most accurate method is the Godunov method. The FORCE method [6] is seen to lie in between these two methods. The Law-Wendroff method is the most accurate scheme of them all but it is not monotone. Stable schemes lie above the Lax-Wendroff method.
Coefficient of numerical viscosity d for four schemes as functions of the Courant number c. Monote schemes lie inside the triangular region defined by the Godunov method (bottom) and the Lax-Friedrichs scheme (top)
Sample Numerical Results
Figures 23 and 24 show numerical results for the linear advection equation (symbols) compared to the exact solution (line) for the Lax-Friedrichs, Godunov and the Lax-Wendroff methods. Figure 23 shows the case of a smooth solution, while Fig. 24 shows the case of a discontinuous solution. For the smooth case of Fig. 23 we see that the Lax-Friedrichs method is the least accurate, just look at the peak value (unity); this is followed by the Godunov method, with Lax-Wendroff displaying the most accurate result. However, even for this smooth test problem, the Lax-Wendroff method shows spurious oscillations (overshoots and undershoots), mainly behind the wave. In fact the numerical solution has some negative values, which would be unphysical if q(x, t) represented a concentration variable, for example.
Test 1 for smooth solution. Results at time t = 100 from the Lax-Friedrichs, Godunov and Lax-Wendroff methods. Mesh used M = 25 and Courant number CFL = 0.9
Test 2 for discontinuous solution. Results at time t = 100 from the Lax-Friedrichs, Godunov and Lax-Wendroff methods. Mesh used M = 25 and Courant number CFL = 0.9
Figure 24 shows results for the discontinuous case. Again the least accurate method is the Lax-Friedrichs method; note also the pairing of numerical values, which is a typical feature of this method. The Godunov method is a little bit more accurate but still far from representing well the square wave with its two discontinuities. The Lax-Wendroff method shows less spreading of the discontinuities (numerical diffusion) and its peak value is closer to the exact value; however the spurious oscillations, with negative values, make this method unsuitable for computing discontinuous solutions.
Note that the Lax-Friedrichs and Godunov methods do not show over and undershoots; this is due to the fact that these schemes are monotone. This property will prove useful when computing solutions to general hyperbolic systems. However, monotone methods are at most first-order accurate and thus they need to be extended to higher order of accuracy, by circumventing the Godunov theorem via the construction of non-linear methods. This subject will be addressed in Sect. 4.
Further Reading
For further reading we recommend the following books [1,2,3,4].
2 The Shallow Water Equations and the Riemann Problem
In this section we study a particular non-linear hyperbolic system of practical interest, namely the shallow water equations. We first establish the governing equations and some of their properties and then solve exactly the corresponding Riemann problem. For further reading see [2].
2.1 Equations, Properties and Wave Relations
The equation for conservation of mass reads
where h(x, t) is water depth and u(x, t) is the particle velocity. The equation for conservation of momentum reads
where g is the acceleration due to gravity. Recall that the celerity is defined as
which is analogous to the speed of sound in a gas. In certain applications it is of interest to consider an additional PDE
ψ(x, t) is transported with u(x, t) and is often called a passive scalar. If we assume that solutions are smooth, then from (117) and (120) we obtain the conservation equation
Now the three equations of interest are (117), (118) and (121). These can be written in conservation form as
with
Here Q is called the vector of conserved variables and F(Q) if the physical flux vector.
Quasi-linear Form and Eigenvalues
Equation (122) can be written in quasi-linear form as follows
where A(Q) is the Jacobian matrix given as
From (123) we have
Note that each component fk of the flux vector has been expressed in terms of the components qj of the vector of conserved variables. This is necessary before proceeding to calculate the partial derivatives. Calculating now the partial derivatives in (125) and then using the physical variables u, a and ψ we may write the Jacobian matrix as
The eigenvalues are the roots of the characteristic polynomial
where I is the identity matrix and \(\hat \lambda \) is a parameter. It is easily verified that
a cubic equation, for which three real solutions exist, and therefore the system has three real eigenvalues, namely
Note that all three roots are distinct if a≠0.
Right Eigenvectors
A right eigenvector R corresponding to \(\hat \lambda \) satisfies
For a generic R = [r1, r2, r3]T we have
To find Ri corresponding to λi we substitute λi into (132) and solve the resulting system for r1, r2 and r3 in terms of free parameters αi. The result is
where α1, α2 and α3 are arbitrary scaling factors which can be chosen as desired.
Left Eigenvectors
To compute a left eigenvector \(\mathbf {L} = \left [l_{1},l_{2},l_{3}\right ]\) corresponding to an eigenvalue \(\hat \lambda \), we solve the system of algebraic equations
The left eigenvectors of A are given by
where the coefficients β1, β2, β3 are arbitrary scaling factors.
Bi-orthonormality of Left and Right Eigenvectors
The reader can easily verify that the right and left eigenvectors (133), (135) of the Jacobian matrix A are bi-orthonormal, that is they satisfy the relations
if the scaling factors are chosen thus
Nature of Characteristic Fields
First recall that a λi-characteristic field is said to be linearly degenerate if
Now we show that the λ2 -characteristic field is linearly degenerate.
Then
for \(\mathbf {Q} \in \Re ^{3}\) and thus the λ2-characteristic field is linearly degenerate.
The λ1 - and λ3 -characteristic fields are genuinely nonlinear. First recall that a λi-characteristic field is said to be genuinely non-linear if
Simple calculations give
Therefore the λ1(Q) and λ3(Q) characteristic fields are genuinely non-linear, if a≠0.
2.2 The Riemann Problem
The Riemann problem for the shallow water equation (122) is the initial value problem
The vector of conservative variables Q and the vector of fluxes F(Q) are given in (123). QL and QR are two constant vectors that define the initial conditions of the problem.
Structure of the Solution of the Riemann Problem
The structure of the solution in the x − t plane is shown in Fig. 25. Note that there are three wave families separating four constant regions. The outer waves are non-linear and are associated with shocks or rarefactions. The middle wave is linear (called contact discontinuity). The solution in regions \({\mathcal {R}}_{0}\) and \({\mathcal {R}}_{3}\) is known, corresponding to the initial data on the left and right respectively. The solution in regions \({\mathcal {R}}_{1}\) and \({\mathcal {R}}_{2}\) (Star Region) is unknown. The full problem of solving the Riemann problem is divided into two subproblems: Problem 1: The Star Problem and Problem 2: The Complete Solution. We start with the The Star Problem for which we first establish some conventional wave relations.
Structure of the solution of the Riemann problem for the augmented 1D shallow water equations
2.2.1 Wave Relations
Rarefactions and Generalized Riemann Invariants
Generalized Riemann Invariants (GRIs) are relations that apply across the wave structure of simple waves in x − t space. For a system of m equations consider the λj(Q)-characteristic field and the corresponding right eigenvector
The GRIs apply across the wave structure and lead to m − 1 ODEs in phase space:
Equation (145) relate ratios of dqi to rij and we emphasize that the ratios are to be interpreted as meaning proportionality, that is
If rij = 0 then dqi = 0 and therefore qi does not change across the respective wave. We now apply these wave relations to study a particular class of waves.
Left Rarefaction Wave
Assume a left rarefaction wave connecting QL (left) and Q∗L (right). See Fig. 26.
Left rarefaction wave connecting states QL and Q∗L. The characteristic line x∕t = uL − aL defines the head and the characteristic line x∕t = u∗L − a∗L defines the tail
The rarefaction wave occupies a wedge \({\mathcal {R}}_{L}\) defined as
where the characteristic line x∕t = uL − aL defines the head and the characteristic line x∕t = u∗L − a∗L defines the tail. λ1(Q) increases monotonically across the wave from head to tail. Application of GRIs across the λ1-wave with Q = [h, hu, hψ]T and R1 = [1, u − a, ψ]T gives
From the first and third ratios dψ = 0 and so across the λ1 wave
Analogously, from first and second ratios, along with integration in phase space we obtain
From here we establish
which we also express as
Solution Inside a Rarefaction
Consider a left rarefaction wave and a point inside the wave. See Fig. 27.
Point \(\hat P=(\hat x, \hat t)\) inside left rarefaction wave. We seek the solution for the celerity a and the particle velocity u at the point \(\hat P\) in terms of its prescribed coordinates \(\hat x, \hat t\)
The point inside the rarefaction wave is \(\hat P=(\hat x, \hat t) \in {\mathcal {R}}_{L}\). Consider now a characteristic line through \(\hat P=(\hat x, \hat t)\) and the origin (0, 0), of slope (known)
The unknowns of the problem are \(\hat u = u(\hat x, \hat t)\) and \(\hat a=a(\hat x, \hat t)\), noting that h follows from a. Application of the left Riemann invariant (150) to connect the point \(\hat P\) to the left initial condition gives
Equations (153) and (154) are two equations for the two unknowns \(\hat a\) and \(\hat u\), whose solution is
Right Rarefaction Wave
Assume a right rarefaction wave, as depicted in Fig. 28, connecting the constant states Q∗R (left) and QR (right). The wave occupies a wedge \({\mathcal {R}}_{R}\)
λ3(Q) is monotone. The right generalized Riemann invariant gives
From here we obtain
which we also express as
Right rarefaction wave connecting states Q∗R and QR. The characteristic line x∕t = uR + aR defines the head while x∕t = u∗R + a∗R defines the tail
The solution at \(\hat P=(\hat x, \hat t) \in {\mathcal {R}}_{R}\) inside the right rarefaction wave can easily be found to be
Right-Facing Shock Wave
Consider an isolated right-facing shock wave of speed SR associated with the λ3-characteristic field, as depicted in Fig. 29. For system (122), across the shock, the Rankine-Hugoniot Conditions apply and thus we have
In addition, the shock must also satisfy the Lax entropy condition
Characteristics run into the shock path, as illustrated in Fig. 29. Now we apply the transformation
which is illustrated in Fig. 30.
Right-facing shock wave of speed SR connecting constant states QR (ahead) and Q∗R (behind)
Right shock wave in two frames of reference. Frame (a) is the original frame of reference and frame (b) is the moving frame of references in which the shock is stationary
In the new frame the shock propagation speed is 0 and the vectors of conserved variables and fluxes ahead of the shock are
while those behind the shock are
The Rankine-Hugoniot conditions in the moving frame are
which give
The above flux equality written in full gives
The first equation in (167) says that the mass flux is constant across the shock, that is
Using this into the third of Eq. (167) gives
That is, ψ is constant across the shock wave. Thus we only need to work with the first two equations in (167); the second one gives
But from (168) we write
Use of (172) into (171) followed by some manipulations yields
From (163)
Inserting (172) into (174) followed by some algebraic manipulations gives
From (163) we have
Use of (172) into (176) followed by manipulations gives
This expression relates the shock speed to the unknown depth h∗R behind the shock. Note that for the limiting case h∗R∕hR = 1 the shock speed coincides with the characteristic speed, that is SR = u + a, as expected.
Left-Facing Shock Wave
For a left-facing shock of speed SL associated with the eigenvalue λ1 = u − a the analysis is similar to that of a right shock. See Fig. 31.
Left-facing shock wave of speed SL connecting states QL (ahead) and Q∗L (behind)
First we define the transformation
Then the Rankine-Hugoniot conditions give
The first of Eq. (179) says that the mass flux
is constant across the shock wave. Using this condition into the third of Eq. (179) gives
In other words the passive scalar ψ is constant across the right shock. Analogous manipulations to those for a right-facing shock yield
and
This relates u∗L to h∗L via the function fL. Also, from (178)
Use of (180) into (184) followed by manipulations gives
This expression relates SL to h∗L. Again, in the limiting case h∗L∕hL = 1 we have SL = u − a.
Contact Discontinuity Wave
An isolated contact discontinuity connecting the (constant) states Q∗L and Q∗R associated with the λ2-characteristic field is depicted in Fig. 32.
Contact wave associated with the linearly degenerate field λ2, connecting states Q∗L and Q∗R. Characteristics either side of the wave are parallel to the wave, just as in the linear advection equation
The wave is a single discontinuity travelling with speed u∗ and characteristics either side of the discontinuity run parallel to it, namely
An eigenvector analysis provides the sought jump conditions across the contact discontinuity. The right eigenvector corresponding to λ2 is R2 = [0, 0, 1]T, from which we have
Exercise
Show that the above solution for the contact discontinuity wave satisfies the Rankine-Hugoniot conditions across the wave.
2.2.2 Solution of Problem 1: The Star Problem
Figure 33 depicts the structure of the solution of the Riemann problem in the x − t plane. The left and right waves can be shocks or rarefactions. The velocity and depth are constant in the Star Region; ψ is also constant in \({\mathcal {R}}_{1} \cup {\mathcal {R}}_{0}\) and in \({\mathcal {R}}_{2}\cup {\mathcal {R}}_{3}\) but with a discontinuous jump across the contact wave.
Structure of the solution of the Riemann problem for the augmented shallow water equations
To find the velocity u∗ and the depth h∗ we first assemble together all the wave relations derived for each elementary wave in isolation. Note that the velocity u∗ is connected to QL via a function fL and that the velocity u∗ is connected to QR via a function fR; the functions fL and fR depend on the unknown depth h∗, the wave type (shock or rarefaction) and, parametrically, on the initial conditions QL and QR, that is
Here wL and wR denote logical variables that identify the wave type; wK denotes either a shock or a rarefaction, for K = L and K = R. The complete solution procedure for the Star Problem is then summarised in the following proposition.
Proposition
The solution h∗ for the Riemann problem (143) is the root of
Once the depth h ∗ has been found the solution for the velocity u ∗ follows as
Sketch of the Proof
First note that the particle velocity u∗ and depth h∗ are constant across the contact discontinuity according to (187). In fact u∗ and h∗ are constant in the entire Star region. Then, the function fL is used to relate u∗ to the left initial condition QL across the left wave. In case the left wave is a shock we have the relation (183) and if it is a rarefaction we use (152). Analogously, the function fR is used to relate u∗ to the right initial condition QR across the right wave. If the right wave is a shock we have the relation (175) and if it is a rarefaction we use (159). As u∗ = u∗L = u∗R, see (187), we can eliminate u∗ resulting in Eq. (189). Then the particle velocity could be written in terms of the function fL, for both the shock and rarefaction cases. See (183) and (152). So we could compute u∗ directly from fL once h∗ is known. Alternatively, we could compute u∗ directly from fR using (175) or (159). Solution (192) results from a mean of the two possible solutions. This concludes the proof.
Iterative Solution for h∗
We need to solve the algebraic non-linear equation (189) for the unknown h∗ in the Star Region. To my knowledge, there is no general close-form solution available to this equation and therefore we must solve it numerically through an iteration procedure. To perform this task there are several methods available, one choice being the Newton-Raphson method
for k = 0, 1, …, K. Here f′(h) denotes the derivative of f with respect to h. The iteration (193) is stopped whenever the change in h is smaller than a prescribed small positive tolerance TOL, that is when
Usually one takes TOL = 10−6. Having formulated and solved numerically the Eq. (189) for h∗, the solution for u∗ follows directly from (192).
The Two-Rarefaction Case and Guess Value
The iterative procedure (193) requires a guess value h(0) to start the iteration. To this end we use a two-rarefaction type approximation, as we now describe. Assume a-priori that the two non-linear waves associated with the eigenvalues λ1 and λ3 are both rarefaction waves. See Fig. 33. Then the functions fL and fR in (190), (191) respectively are those corresponding to rarefaction waves. Then (189) becomes
which has exact solution, called the Two-Rarefaction Solution. For the celerity a one has
From the definition of celerity we obtain
which is used as a starting value in the iteration procedure (193).
2.2.3 Solution of Problem 2: The Complete Solution
Now we put together all the components of the solution so as to be able to compute the solution Q(x, t) for any given point (x, t) in the x-t half plane, −∞ < x < ∞ and t ≥ 0. See Fig. 34. We call this task the solution sampling procedure in which we assume that the depth h∗ and velocity u∗ in the Star Region are already known.
Sampling the solution through the complete wave structure, at a chosen time \(\hat t\)
The solution Q(x, t) is sought at a specified time \(\hat t\) for any x in a finite interval [xl, xr] containing the full wave system, as depicted in Fig. 34. Then \(\mathbf {Q}(x,\hat t)\) is a function of x alone and gives a profile at time \(\hat t\). To sample the solution we make use of the contact discontinuity to divide the full domain into the two subregions
To perform the sampling we represent the solution in terms of the vector of physical variables W = [h, u, ψ]T and make use of the similarity variable
to locate the sampling point and assign the corresponding solution W(ξ). Note that ξ has dimensions of velocity. There are two cases.
-
Sampling point lies to the left of the contact. The solution W(ξ) for \((x, \hat t) \in {\mathcal {R}}_{L}\) depends on the wave type. There are two possibilities:
Left shock. If the left wave is a shock of speed SL, then \({\mathcal {R}}_{L}\) is again subdivided into two subregions and the solution is
$$\displaystyle \begin{aligned} \mathbf{W}(\xi) \equiv \left\{ \begin{array}{cccccc} {\mathbf{W}}_{*L} & = & \left[h_{*}, u_{*}, \psi_{L} \right]^T & & \mbox{if} & S_{L} \le \xi \leq u_{*} \;, \\ {\mathbf{W}}_{L} & = & \left[h_{L}, u_{L}, \psi_{L} \right]^T & & \mbox{if} & \xi < S_{L} \;, \end{array} \right. \end{aligned} $$(200)where the shock speed SL is given by (185).
Left Rarefaction
If the left wave is a rarefaction then \({\mathcal {R}}_{L}\) is subdivided into three subregions and the solution is
$$\displaystyle \begin{aligned} \mathbf{W}(\xi) = \left\{ \begin{array}{cccccc} {\mathbf{W}}_{L} & = & \left[h_{L}, u_{L}, \psi_{L} \right]^T & & \mbox{if} & \xi \leq u_{L}-a_{L} \;, \\ {\mathbf{W}}_{Lfan} & = & \left[\hat h_{L}, \hat u_{L}, \psi_{L} \right]^T & & \mbox{if} & u_{L}-a_{L} \leq \xi \leq u_{*}-a_{*} \;, \\ {\mathbf{W}}_{*L} & = & \left[h_{*}, u_{*}, \psi_{L} \right]^T & & \mbox{if} & u_{*}-a_{*} \leq \xi \leq u_{*} \;, \end{array} \right. \end{aligned} $$(201)where \(\hat h_{L}\) and \(\hat u_{L}\) inside the left rarefaction are obtained from (155).
-
Sampling point lies to the right of the contact. The solution W(ξ) for \((x, \hat t) \in {\mathcal {R}}_{R}\) depends on the type of the left wave present. Again there are two possibilities.
Right shock. If the right wave is a shock of speed SR, then \({\mathcal {R}}_{R}\) is again subdivided into two subregions and the solution is
$$\displaystyle \begin{aligned} \mathbf{W}(\xi) \equiv \left\{ \begin{array}{cccccc} {\mathbf{W}}_{*R} & = & \left[h_{*}, u_{*}, \psi_{R} \right]^T & & \mbox{if} & u_{*} \le \xi \le S_{R} \;, \\ {\mathbf{W}}_{R} & = & \left[h_{R}, u_{R}, \psi_{R} \right]^T & & \mbox{if} & \xi > S_{R} \;, \end{array} \right. \end{aligned} $$(202)where the shock speed SR is given by (177).
Right Rarefaction
If the right wave is a rarefaction then \({\mathcal {R}}_{R}\) is subdivided into three subregions and the solution is
$$\displaystyle \begin{aligned} \mathbf{W}(\xi) = \left\{ \begin{array}{cccccc} {\mathbf{W}}_{R} & = & \left[h_{R}, u_{R}, \psi_{R} \right]^T & & \mbox{if} & \xi > u_{R}+a_{R} \;, \\ {\mathbf{W}}_{Rfan} & = & \left[\hat h_{R}, \hat u_{R}, \psi_{R} \right]^T & & \mbox{if} & u_{*R}+a_{*} \leq \xi \leq u_{R}+a_{R} \;, \\ {\mathbf{W}}_{*R} & = & \left[h_{*}, u_{*}, \psi_{R} \right]^T & & \mbox{if} & u_{*} \leq \xi \leq u_{*R}+a_{*} \;, \end{array} \right. \end{aligned} $$(203)where \(\hat h_{R}\) and \(\hat u_{R}\) inside the right rarefaction are derived from (160).
Test Problems
Here we solve two specific Riemann problems for the shallow water equations in a finite channel of length 50 m. Table 1 gives the initial conditions and computational details. Column 2 gives the position of the initial discontinuity and column 3 gives the output time. The remaining columns give the initial conditions for depth h and velocity u. Note that in these examples we have not considered the equation for a passive scalar. Figures 35 and 36 show profiles for tests 1 and 2 respectively.
Test 1. Solution profiles for h and u at the output time Tout = 7.0s. The solution consists of a left rarefaction and a right shock
Test 2. Solution profiles for h and u at the output time Tout = 2.5s. The solution consists of two rarefaction waves
2.3 Concluding Remarks
In this section we have introduced the 1D shallow water equations augmented by a passive scalar, and studied its salient mathematical properties. We have solved exactly the corresponding Riemann problem, whose solution can be used to construct Godunov-type finite volume numerical methods and discontinuous Galerkin finite element methods. Moreover, this exact solution can be used to construct approximate solutions (approximate Riemann solvers) to be used in numerical methods. Note also that the exact solution can be used to assess the correctness and accuracy of numerical computations intended for solving the shallow water equations.
Further reading material is found in [2] and [1] and in references therein.
3 Godunov’s Method for the Shallow Water Equations
We study the Godunov method [5] as applied to a general non-linear hyperbolic system, and in particular as applied to the 1D shallow water equations. We consider two approaches for computing the Godunov flux: the first requires the calculation of the Godunov state, that is the state along the t-axis in the solution of the Riemann problem, see Sect. 2. Then, the numerical flux is simply the physical flux function evaluated at this Godunov state. In the second approach one calculates a numerical flux directly.
General Initial-Boundary Value Problem (IBVP)
First we apply the Godunov’s method to a generic nonlinear hyperbolic system. Consider the IBVP for any non-linear hyperbolic system
Q(x, t) is the vector of conserved variables; F(Q) is the flux function, or physical flux; Q(0)(x) is the initial condition; BL(t) and BR(t) are the boundary conditions on the left and right boundaries respectively, two prescribed functions of time.
3.1 The Finite Volume Method
Unlike the finite difference method introduced in Sect. 1, the finite volume discretisation of the domain considers a partition of the entire x − t domain into space-time finite volumes, as in Fig. 12 of Sect. 1. In the numerical context these finite volumes are denoted as \(V_{i}=[x_{i-\frac {1}{2}}, x_{i+\frac {1}{2}}] \times [t_{n}, t_{n+1}]\). Figure 37c shows three consecutive finite volumes. Here Δt = tn+1 − tn denotes the time step and \(\varDelta = x_{i+\frac {1}{2}} - x_{i-\frac {1}{2}}\) denotes the cell spatial size, or mesh size; \(x_{i+\frac {1}{2}}\) denotes the volume interface. With this notation, the exact integration of the equations in the generic finite volume Vi gives the finite volume formula
with
Godunov’s method for a hyperbolic system: (a) integral averages for one component q of the vector Q in each interval \([x_{i- \frac {1}{2}}, x_{i+ \frac {1}{2}}]\) at time tn give piece-wise constant data; (b) structure of solutions of Riemann problems at intercell boundaries determined by piece wise constant data; (c) finite volume formula to update averages using numerical fluxes
and
See Eqs. (60) and (61) in Sect. 1. Formula (205) serves to update approximations to spatial integral averages (206) using numerical fluxes that are approximations to time integral averages (207) at the cell interface \(x_{i+\frac {1}{2}}\). See Fig. 37.
3.1.1 The Godunov Flux
To define the finite volume scheme (205) we prescribe suitable approximations to the integral (207) to obtain the numerical flux \({\mathbf {F}}_{i+\frac {1}{2}}\). The Godunov upwind numerical flux \({\mathbf {F}}_{i+\frac {1}{2}}\) is computed from (207), making use of the solution \({\mathbf {Q}}_{i+\frac {1}{2}}(x/t)\) of the local Riemann problem
The Godunov flux is computed from (207) and becomes
\({\mathbf {Q}}_{i+\frac {1}{2}}(0)\) is called the Godunov state and results from \({\mathbf {Q}}_{i+\frac {1}{2}}(x/t)\) evaluated at the interface x∕t = 0. Note that for convenience, at each interface \(x_{i+\frac {1}{2}}\) and time level tn we use local coordinates through a change from global to local coordinates as follows:
We then use (x, t) to mean the local coordinates \((\bar x, \bar t)\). See Fig. 38. In what follows we specialise Godunov’s method to the shallow water equations.
Correspondence between the global (a) and local (b) frames of reference for the solution of the Riemann problem
3.1.2 Godunov Flux with the Exact Riemann Solver
One first solves the Star problem; the solution for h∗ and u∗ in the Star Region is found. To this end one solves the non-linear equation (using Newton-Raphson method, for example)
All details on the Riemann problem are given in Sect. 2. Once the water depth h = h∗ has been found the velocity u∗ is calculated as
Note that not always the Godunov state needed for flux evaluation corresponds to the Star State, for which it is necessary to go through a sampling procedure to find the Godunov state \({\mathbf {Q}}_{i+\frac {1}{2}}(0)\) for flux evaluation, see Sect. 2.
If a passive scalar is present in the equations, then one simply chooses
This completes the description of Godunov’s flux as applied to the augmented 1D shallow water equations, using the exact Riemann solver.
In practice one resorts to approximate solution methods to find a Godunov-type flux. We next describe several approaches but before doing so we address some issues that emerge when having to choose an approximate Riemann solver. We first recall that the Godunov method is the most accurate monotone numerical method, as shown for the scalar linear case in Sect. 1. For systems, first recall that the concept of monotone method does not exist, it is only a scalar concept. Then, on the accuracy question, one knows that this depends crucially on the particular Riemann solver used. The exact solver is the best but at the cost of (i) complexity and (ii) computational expense. Computational expense however has to be seen in light of efficiency, that is, in relation to the error. The computational expense of the exact Riemann solver is not excessive for systems such as for blood flow, shallow water and ideal gas dynamics. Still, approximate Riemann solvers can and are used for these systems but great care is required in choosing the appropriate approximation. The following remarks are in order:
-
1.
Good approximate Riemann solvers are required to be:
-
Complete: their wave model contains all characteristic fields of the exact Riemann problem.
-
Non-linear. Linearised Riemann solvers have various defects and are thus to be avoided whenever possible.
-
-
2.
The simplest Riemann solver is the Rusanov solver, as we shall see its wave model contains just one wave.
-
3.
At the bottom of the hierarchy of numerical fluxes are centred methods, such as the Lax-Friedrichs and FORCE fluxes.
-
4.
Centred, or symmetric, methods may be the simplest but not the most efficient, as we shall see later.
3.2 A Simple Linearised Riemann Solver
As an academic example here, we study a linearised Riemann solver, even if in practice, such solvers are to be avoided. We look for approximations to h∗ and u∗ in the Star Region. First we re-write the governing equations in terms of primitive, or physical, variables h, u and ψ.
with
Denote the initial conditions for the Riemann problem as
Now assume PL is close to PR and linearise system (214) about
so that the nonlinear system (214) becomes the linear system
with constant coefficient matrix
The linear Riemann problem for (218) with initial conditions (216) is solved exactly by using standard methods for hyperbolic linear systems, see Sect. 1, to obtain
Remarks About the Linearised Solution
-
1.
The solution for ψ(x, y) is as given by (213), though u∗ is an approximation.
-
2.
A sampling procedure to find \({\mathbf {Q}}_{i+\frac {1}{2}}(0)\) for evaluating the numerical flux is required.
-
3.
This Riemann solver is very simple but not robust enough.
-
4.
It fails for strong rarefactions, near the vacuum state.
-
5.
It fails for trans-critical (or sonic) flow, leading to entropy violating shocks (or rarefaction shocks).
-
6.
This Riemann solver is complete but linear.
-
7.
In general, linearised Riemann solvers are not recommended for practical use.
3.3 A Two-Rarefaction Riemann Solver
Starting from the exact Riemann solver, by directly assuming that both non-linear waves are rarefactions, constancy of Riemann invariants leads to
There follows that
The solution for ψ(x, y) is as given by (213), though u∗ is an approximation. The sampling procedure to find \({\mathbf {Q}}_{i+\frac {1}{2}}(0)\) for evaluating the numerical flux is required; this is the same as for the exact Riemann solver. This Riemann solver is very simple, complete and non-linear; in practice it is also shown to be very robust.
3.4 The Harten-Lax-van Leer (HLL) Riemann Solver
We want to solve the Riemann problem (208) approximately with the aim of finding directly a numerical flux of the form
for an arbitrary time T > 0 and where Q(0, t) is an approximate solution of the Riemann problem along the t-axis (the Godunov state); see Fig. 39. Here we construct a numerical flux following the HLL approach proposed by Harten, Lax and van Leer [7]. We first establish some useful relations obtained by applying the integral form of the conservation laws on appropriately chosen control volumes.
Wave pattern used for the derivation of the HLL flux for a subcritical, or subsonic, wave pattern, SL ≤ 0 and SR ≥ 0
Consider the control volume [xL, 0] × [0, T] in the space-time configuration of Fig. 39. Assume the fastest signals perturbing the constant initial states \({\mathbf {Q}}_{L} \equiv {\mathbf {Q}}_{i}^{n}\) and \({\mathbf {Q}}_{R} \equiv {\mathbf {Q}}_{i+1}^{n}\) emerging from the Riemann problem solution are SL (for left travelling signals) and SR (for right travelling signals). Assume the wave configuration is subsonic, that is SL ≤ 0 and SR ≥ 0. Then, for an arbitrary time T > 0 we define the distances
Applying the integral form of the conservation laws (204) in the control volume [xL, 0] × [0, T] we obtain
Evaluation of the first and second terms on the right hand side gives
Inserting these into (225) and dividing through by T gives
To define F0 approximately it is sufficient to find an approximation to the integral on the right hand side of (227). This is accomplished by finding an approximate state Q(x, T) by adopting an approach analogous to the Lax-Wendroff method, or to the Godunov centred method; see [1]. Applying the integral form (225) of the conservation laws (204) in the control volume [xL, xR] × [0, T], see Fig. 39, we obtain
The first term on the right hand side gives
Substitution of this expression into (228) and evaluation of the integrals gives
On division through by xR − xL = T(SR − SL) we obtain the averaged state
We now use the state QHLL to evaluate the integral on the right hand side of (227). The resulting intercell flux is
The HLL Flux
Finally the HLL flux for the approximate Godunov method is
To complete the HLL scheme it is necessary to find estimates for SL and SR. In [2], the following estimates are suggested
Here qK (K = L, R) are obtained according to the type of non-linear waves present
The scheme is complete by defining \(\bar h_{*} \approx h_{*}\), the depth in the Star Region. Here we suggest to use the simple but robust estimate from (222). Given wave speed estimates SL and SR, HLL is most easily implemented noting also that HLL is a non-linear Riemann solver and entropy satisfying. HLL is complete but only for systems of two equations. For larger systems HLL is incomplete.
HLL Rusanov and Lax-Friedrichs Schemes
Well-known methods can be derived from HLL, as a special cases. For example, The Rusanov flux [8] can be derived from HLL by assuming S+ = SR and SL = −S+. Then we obtain
The Rusanov scheme is the simplest upwind method, it has a 1-wave model and is non-linear. But obviously the Rusanov method is incomplete for any system of equations.
The well-known Lax-Friedrichs method can also be derived from HLL and more specifically from Rusanov by choosing \(S^{+} = \frac {\varDelta x}{ \varDelta t}\), producing the Lax-Friedrichs flux
The wave model of the Lax-Friedrichs method has zero waves. It is the most diffusive (most inaccurate) stable method for hyperbolic equations. I would not recommend its use for practical computations.
3.5 The HLLC Riemann Solver
HLL ignores intermediate waves in systems of three or more equations, leading to excessive numerical dissipation for these waves. A possible improvement, called HLLC, was first proposed by Toro and collaborators in 1992 [9]; see also [10] and [11]. The HLLC approximate Riemann solver is a modification of HLL that accounts for intermediate waves in the solution of the Riemann problem. See Fig. 40.
Assumed wave pattern for the HLLC Riemann solver. The Star Region contains two sub-regions separated by the intermediate wave
Consider the wave pattern depicted in Fig. 40, where an intermediate wave of speed S∗ is present. Application of the integral form of the conservation laws in [xL, 0] × [0, T] and in [0, xR] × [0, T] yield
Here there are two vector equations for four unknown vectors Q∗L, Q∗R, F∗L and R∗R. To solve this overdetermined algebraic system we make the following additional assumptions
As a matter of fact the above assumptions are true for the exact Riemann solver, as seen in Sect. 2. From the first component of the first vector equation in (238) we write
From the first component of the second vector equation in (238) we write
From here we obtain
If SL and SR are prescribed, then h∗ is known from (242)–(243). Then the vectors Q∗L and Q∗R in (238) are given as
Now the vectors F∗L and F∗R in (238) are determined and finally the HLLC flux is given as
where the states Q∗L, Q∗R are given by (244). The wave speed estimates for SL and SR are as for the HLL flux, see (234), and for S∗ we use (243).
The use of HLLC instead of HLL for a system including the passive scalar ψ makes a dramatic difference to the resolution of the contact wave. This is particularly evident for long-time evolution problems.
3.6 The Dumbser-Osher-Toro Riemann Solver: DOT
Here we present a modification of the Osher-Solomon Riemann solver [12] that makes the approach much more practical and applicable to any hyperbolic system for which the complete eigenstructure is known, either analytically of numerically. The resulting scheme is non-linear and complete. The modification is due to Dumbser and Toro [13, 14].
3.6.1 Definitions and Notation
Consider a general m × m hyperbolic system
with conserved variables and flux vectors respectively denoted as
The real eigenvalues are λi(Q) and the corresponding right eigenvectors are Ri(Q), for i = 1, 2, …, m. Here we consider Godunov-type finite volume schemes to solve (246)
where \({\mathbf {F}}_{i+\frac {1}{2}}\) is the numerical flux found by solving the Riemann problem for (246) with initial condition
Recall that hyperbolicity of system (246) is equivalent to saying that the Jacobian matrix A(Q) of the flux F(Q) is diagonalizable, that is
where R(Q) is the matrix formed by the right eigenvectors Ri(Q), R−1(Q) is its inverse and Λ(Q) is the diagonal matrix whose diagonal entries are the eigenvalues λi(Q).
We introduce the definitions
and consider the associated diagonal matrices Λ+(Q), Λ−(Q) and |Λ−(Q)|, whose diagonal entries are \(\lambda _{i}^{+}(\mathbf {Q})\), \(\lambda _{i}^{-}(\mathbf {Q})\) and |λi(Q)| respectively. Note that
and hence
Then we introduce
Osher and Solomon [12] defined the numerical flux as
This requires the evaluation of an integral in phase space, which depends on the chosen integration path joining Q0 to Q1. Originally, Osher and Solomon proposed two ways of choosing integration paths so as to make the actual integration tractable, (a) the P-ordering and (b) the O-ordering. However, the analytical calculations to be performed are still too involved for general hyperbolic systems. Full details of the original Osher-Solomon Riemann solver are found in Chapter 12 of Toro [1].
3.6.2 The DOT Riemann Solver
Dumbser and Toro [13, 14] made two simple but effective suggestions: (i) choose any path, without considerations regarding computational tractability of the scheme; (ii) evaluate matrices by numerical integration in phase space. The simplest path to evaluate the integral in (255) is the canonical path
Obviously, other choices are available. Then, under a change of variables we obtain
Finally, the integral in (257) is computed numerically along the path ψ using a Gauss type quadrature rule with G points sj and associated weights ωj in the unit interval I = [0, 1]. We obtain
Note that \(\left | \mathbf {A}(\psi (s_{j}; {\mathbf {Q}}_{0},{\mathbf {Q}}_{1})) \right | \) must be decomposed as in (254) for each sj.
Remarks on the DOT Scheme
-
1.
The complete eigenstructure of the system is needed and is used at each integration point in (258).
-
2.
The scheme is non-linear and complete, as it contains all characteristic fields of the exact problem.
-
3.
The scheme is very general. The original version of Osher and Solomon was restricted to very simple hyperbolic systems.
-
4.
The new DOT scheme also applies to non-conservative hyperbolic systems.
3.6.3 Sample Numerical Results, Accuracy and Efficiency
The purpose here is to show some numerical results for a wider range of equations than those studied in these lecture notes. We first show some selected numerical results for the Euler equations of gas dynamics; see [1] for background. Then we also address the crucial issues of accuracy and efficiency of Riemann solvers; this is done in terms of the blood flow equations [15].
Numerical Results for the Euler Equations
Figure 41 shows computations from a linearised Riemann solver not studied here, namely the Roe Riemann solver [16]. Results shown are for the Euler equations [1]. The left frame shows results from the original Roe scheme without an entropy fix; an entropy violating shock (or rarefaction shock) is computed, which is not physically admissible. The right frame shows results from a modified Roe scheme through a so-called entropy fix; now the results look correct and also accurate, recalling that the corresponding Godunov method is only first order accurate.
Sonic flow test problem for the Euler equations taken from [1]. Comparison between numerical (symbol) and exact (line) solutions. Left: linearised Roe solver without entropy fix. Right: linearised Roe solver with entropy fix
In Fig. 42 we show results for another test problem for the Euler equations taken from [1]. Comparison between numerical (symbol) and exact (line) solutions is shown. The left frame shows results from the original Osher-Solomon scheme [12], which as seen in the figure, are completely wrong. The right frame shows results from the new DOT scheme [13, 14]; these results are very accurate, especially for the narrow region between the contact discontinuity and the shock wave.
Test problem for the Euler equations taken from [1]. Comparison between numerical (symbol) and exact (line) solutions. Left: Original Osher-Solomon scheme. Right: new DOT scheme
Figure 43 shows results for a special test problem for the Euler equations, also taken from [1]. The test problem consists of a single, isolated stationary contact discontinuity. The left frame shows numerical results from the HLL scheme [7] and the FORCE scheme [6]. Both numerical methods show large errors due to numerical diffusion of the intermediate wave in the Riemann problem for the Euler equations. The right frame shows results from HLL [7] and from HLLC [11], noting that the latter reproduces the exact solution.
Test problem for the Euler equations containing a single, isolated stationary contact discontinuity; taken from [1]. Left: FORCE and HLL versus the exact solution. Right: HLL and HLLC versus the exact solution
Accuracy and Efficiency
We have already mentioned the question of efficiency, which relates error (or accuracy) to computational cost. Figure 44 shows results from an efficiency test for the 1D blood flow equations [15], where error is measured against CPU time. Comparison is made for the Godunov method with four Riemann solvers: the exact Riemann solver, HLL, FORCE and Lax-Friedrichs.
Efficiency test for the blood flow equations. The test is a Riemann problem containing two rarefaction waves. Error against CPU time. Results are shown for the Godunov method used in conjunction with Exact Riemann solver, the HLL Riemann solver, FORCE and the Lax-Friedrichs flux (Courtesy of PhD student Christian Contarino, University of Trento, Italy)
What the results of Fig. 44 show is that for this test problem with smooth solution the Godunov method is the most efficient method. Compared to the Lax-Friedrichs method, it is about five times more efficient. To see this, imagine a horizontal line through the last point of the Lax-Friedrichs curve with the smallest error and look for its intersection with the exact Riemann solver curve; these two intersection points give two respective CPU times.
3.6.4 Concluding Remarks
The Godunov method for the augmented one-dimensional shallow water equations has been introduced. The Godunov scheme works with the exact and with approximate Riemann solvers. Examples of approximate Riemann solvers have also been presented, along with some selected numerical results for the Euler equations and for the blood flow equations, not studied here. The first-order Godunov schemes studied in this section can be extended to high order of accuracy following a variety of procedures available in the literature. In the next section we present the ADER approach to construct high-order numerical methods.
4 High Order Methods: The ADER Approach
In this section we present one approach, the ADER approach, to construct high-order accurate extensions of the first-order methods presented previously.
4.1 Overview
We are interested in time-dependent partial differential equations of the form
along with appropriate initial and boundary conditions. Here Q(x, t) is the vector of unknowns; A(Q(x, t)) is an advection differential operator in 1D, 2D or 3D; D(Q(x, t)) is a dissipative operator in 1D, 2D or 3D and S(Q(x, t)) is a source term vector, a prescribed function of the unknowns.
The ADER approach was first presented by Toro and collaborators [17] for linear hyperbolic systems in 1D, 2D and 3D on structured meshes; schemes of upto 10th order of accuracy in space and time were constructed and implemented. The ADER schemes were further developed in [18] and [19] for non-linear systems; in [20] ADER was formulated, in a unified manner, in both the finite volume and the discontinuous Galerkin finite element frameworks. For an introduction to ADER see Chapters 19 and 20 of [1] and the many references therein, up to 2009. Distinguishing features of the ADER approach include:
-
1.
Accuracy is arbitrary in both space and time.
-
2.
Schemes are non-linear schemes, in the sense of Godunov; computed shock waves and other discontinuities have none or controlled spurious oscillations.
-
3.
Schemes are suitable for general geometries in multiple space dimensions, treated with both structured or unstructured meshes.
-
4.
Schemes work in both the finite volume and the discontinuous Galerkin finite element frameworks.
-
5.
Schemes are applicable to conservative and non-conservative hyperbolic systems.
Why is High Accuracy Important? Because of Efficiency
Figure 45 shows computational results for an acoustic problem modelled by the linearised two dimensional Euler equations solved by ADER schemes taken from [21]. The original paper reports computations of orders of accuracy from 1 to 24 in space and time. Figure 45 displays some selected results from 2nd to 16th order.
Efficiency plot: error against CPU cost for nine high-order ADER schemes, from the 2nd order to the 24th order of accuracy. For a chosen fixed error there corresponds a horizontal line (e.g. black horizontal line); its intersection with the various curves gives corresponding times, which give the cost of the corresponding scheme to compute the solution with that error. Taken from [21]
4.2 ADER in the Finite Volume Framework
Consider the general system of hyperbolic equations with source terms (hyperbolic balance laws) in one space dimension
Exact integration of (260) in the control volume \([x_{i-\frac {1}{2}}, x_{i+\frac {1}{2}}] \times [0, \varDelta t]\) gives a finite volume like formula
where
Relation (261) with definitions (262) is exact and motivates an approximate formula, namely
See Sect. 1. Equation (263) defines a one-step, fully discrete finite volume numerical scheme with numerical flux
and numerical source
Figure 46 illustrates scheme (263) to solve (260). The finite volume ADER scheme (263) aims at computing approximations (264) and (265) as accurately as possible.
4.3 Ingredients of ADER
The ADER method to solve (260) is based on the finite volume formula (263) and requires the accurate evaluation of integrals (264) for the intercell numerical flux and (265) for the numerical source. In order to achieve this, the following steps are required.
-
1.
Reconstruction: high-order non-linear spatial reconstruction, once per time step, using any of the methodologies available, such as TVD, ENO and WENO. Figure 47 illustrates the reconstruction process. For background on reconstruction techniques see for example [1, 4, 22, 23] and [24].
Fig. 47 
Illustration of the reconstruction procedure for one variable q(x, t) in one space dimension on a regular mesh. From the set of (constant) integral averages \(\{q_{i}^{n}\}\) one obtains an interpolant pi(x) satisfying a conservation property and a non-linear property to circumvent Godunov’s theorem, using for example criteria such as TVD, ENO and WENO. Note that at each interface one now has reconstructed data that defines a generalised Riemann problem
-
2.
Generalised Riemann problem (GRP) and numerical flux. At each interface one must solve a Riemann problem with piece-wise smooth data, not piece-wise constant, as in the conventional case. This GRP may also include the source terms in case these are present in the equations.
-
3.
Numerical source. This is an additional term in the case in which the equations include source term.
4.4 Generalized Riemann Problem
Starting from reconstructed data, at each interface one defines the following initial value problem, called the generalized Riemann problem, or GRP
In the GRP (266) the governing equations include source terms and the initial conditions are piece-wise smooth (e.g. polynomials of any degree). This Riemann problem also generalises the case in which the data is piece-wise linear, which is associated with the second-order GRP scheme of Ben-Artzi and Falcovitz [25].
Figure 48 illustrates the classical Riemann problem (left) and the generalised Riemann problem (right). Figure 49 shows an example of a generalised Riemann problem for the Euler equations of gas dynamics.
Classical Riemann problem (left) and generalised Riemann problem (right). Bottom frames depict the initial conditions (for a single variable) and top frames depict the structure of the solution of the initial value problem in the x − t plane
Structure of the solution of a generalized Riemann problem for the Euler equations. Characteristics are curved in the x − t plane (Courtesy of Dr VA Titarev)
There are so far several published methods for solving the generalised Riemann problem for hyperbolic systems. The first practical solver for non-linear hyperbolic systems with source terms is due to Toro and Titarev [18]. This solver is suitable for non-stiff source terms. Other solvers include [26,27,28,29,30]. An important development was that in [27] in which the proposed solver can deal with stiff source terms, reconciling in this way, stiffness and high-order of accuracy.
4.5 Numerical Examples
Here we show some sample numerical results, first for the 1D linear advection equation and then for the 2D Euler equations of gas dynamics with the ideal equation of state.
Figure 50 shows computed (symbols) and the exact solution (line) for linear advection equation using a mesh of M = 50 cells, a Courant number coefficient Ccfl = 0.95 at the output time tout = 1000π. The top frame displays results from a second-order TVD method used in conjunction with the MINBEE limiter [1]. The bottom frame shows results from the 5th-order ADER scheme (5th order in space and time) with WENO (non-linear) reconstruction. The results speak by themselves. The second order TVD method is unable to resolve the wave packet and there is not even a hint of waves; the profile is virtually flat. The killer here is the long evolution time, tout = 1000π. Long time evolution problems expose the limitations of low order methods. The fifth order method is just perfect.
Computed (symbols) and exact solution (line) of linear advection equation using a mesh of M = 50 cells, Courant number coefficient Ccfl = 0.95 and output time tout = 1000π. Top frame displays results from second-order TVD method with the MINBEE limiter. Bottom frame shows results from the 5th-order ADER scheme with WENO reconstruction
Figure 51 shows computed results for the two-dimensional Euler equations of gas dynamics with the ideal gas equation of state. This test problem is well known in the gas dynamics community. The domain is a rectangular region with a solid fixed triangle in its interior (white object). The top and bottom boundaries are reflecting fixed walls, while the left and right boundaries are transmissive. The initial condition is an isolated shock wave of Mach number 1.3 positioned between the left boundary and the triangle. The evolution of this initial condition gives rise to a complex pattern of waves propagating and interacting. There are experimental visualization results for this problem. The ADER solution represents those experiments well. In addition to the dominant shock waves everywhere there are also regions of smooth flow and many low amplitude waves; these are the flow features that are difficult to capture with low order methods, they are simply wiped out, just as seen for the linear advection example of Fig. 50.
Shock wave impinging on stationary triangular body. Numerical solution of the Euler equations of gas dynamics on a triangular mesh using a fourth order ADER method (Courtesy of Prof. M Dumbser, University of Trento, Italy)
4.6 Concluding Remarks
In this last section we have given a very brief introduction to one approach to construct high-order numerical methods for hyperbolic equations, namely the ADER approach. This is a fully discrete approach that requires a spatial reconstruction procedure and the solution of the generalised Riemann problem. There are indeed alternative methods to achieve high order of accuracy. Prominent examples are the ENO and WENO semidiscrete approaches pioneered by Shu and collaborators [22,23,24].
Accumulated experience over the last few years has shown that high-order methods are much more efficient than low order methods if small errors are sought, that is if accurate solutions are sought. By efficiency we mean that given an error deemed acceptable, then high order methods attain that error much more efficiently on a coarse mesh than low order methods on a fine mesh. This is illustrated in Fig. 45.
The issues of accurate solutions and efficiency are becoming increasingly important given the growing trend to use mathematical models (PDEs) to understand the physics they embody. Only very accurate solutions of the PDEs will achieve this and also reveal limitations of the mathematical models (the governing equations and their parameters). Very long time evolution simulations, as in wave propagation problems for long distances, require the use of high order methods, as illustrated in Fig. 50.
References
Toro, E.F.: Riemann Solvers and Numerical Methods for Fluid Dynamics. A Practical Introduction, 3rd edn. Springer, Berlin (2009). ISBN 978-3-540-25202-3. http://springerlink.bibliotecabuap.elogim.com/book/10.1007%2Fb79761
Toro, E.F.: Shock-Capturing Methods for Free-Surface Shallow Flows. Wiley, Chichester (2001)
Godlewski, E., Raviart, P.A.: Numerical Approximation of Hyperbolic Systems of Conservation Laws. Springer, New York (1996)
LeVeque, R.J.: Finite Volume Methods for Hyperbolic Problems. Cambridge University Press, Cambridge (2002)
Godunov, S.K.: A Finite difference method for the computation of discontinuous solutions of the equations of fluid dynamics. Math. Sb. 47, 357–393 (1959)
Toro, E.F., Billett, S.J.: Centred TVD schemes for hyperbolic conservation laws. IMA J. Numer. Anal. 20, 47–79 (2000)
Harten, A., Lax, P.D., van Leer, B.: On spstream differencing and Godunov-type schemes for hyperbolic conservation laws. SIAM Rev. 25(1), 35–36 (1983)
Rusanov, V.V.: Calculation of interaction of non-steady shock waves with obstacles. J. Comput. Math. Phys. USSR 1, 267–279 (1961)
Toro, E.F., Spruce, M., Speares, W.: Restoration of the contact surface in the HLL Riemann solver. Technical Report, Department of Aerospace Science, College of Aeronautics, Cranfield Institute of Technology. CoA-9204 (1992)
Toro, E.F., Spruce, M., Speares, W.: Restoration of the contact surface in the HLL Riemann solver. Shock Waves 4, 25–34 (1994)
Toro, E.F., Chakraborty, A.: Development of an approximate Riemann solver for the steady supersonic Euler equations. Aeronaut. J. 98, 325–339 (1994)
Osher, S., Solomon, F.: Upwind difference schemes for hyperbolic conservation laws. Math. Comput. 38(158), 339–374 (1982)
Dumbser, M., Toro, E.F.: A simple extension of the Osher Riemann solver to general non-conservative hyperbolic systems. J. Sci. Comput. 48, 70–88 (2011)
Dumbser, M., Toro, E.F.: On universal Osher-type schemes for general nonlinear hyperbolic conservation laws. Commun. Comput. Phys. 10, 635–671 (2011)
Toro, E.F.: Brain venous haemodynamics, neurological diseases and mathematical modelling. A review. Appl. Math. Comput. 272, 542–579 (2016)
Roe, P.L.: Approximate Riemann solvers, parameter vectors and difference schemes. J. Comput. Phys. 43, 357–372 (1981)
Toro, E.F., Millington, R.C., Nejad, L.A.M.: Towards very high-order Godunov schemes. In: Toro, E.F. (ed.) Godunov Methods: Theory and Applications. Edited Review. Conference in Honour of Godunov SK, vol. 1, pp. 897–902. Kluwer Academic/Plenum Publishers, New York (2001)
Toro, E.F., Titarev, V.A.: Solution of the generalised Riemann problem for advection-reaction equations. Proc. R. Soc. London, Ser. A 458, 271–281 (2002)
Titarev, V.A., Toro, E.F.: ADER: arbitrary high order Godunov approach. J. Sci. Comput. 17, 609–618 (2002)
Dumbser, M., Balsara, D., Toro, E.F., Munz, C.D.: A unified framework for the construction of one-step finite-volume and discontinuous Galerkin schemes on unstructured meshes. J. Comput. Phys. 227, 8209–8253 (2008)
Dumbser, M., Schwartzkopff, T., Munz, C.D.: Arbitrary high order finite volume schemes for linear wave propagation. In: Computational Science and High Performance Computing II. Notes on Numerical Fluid Mechanics and Multidisciplinary Design Book Series (NNFM), vol. 91, pp. 129–144. Springer, Berlin (2006)
Shu, C.W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes. J. Comput. Phys. 77, 439–471 (1988)
Shu, C.W., Osher, S.: Efficient implementation of essentially non-oscillatory shock-capturing schemes II. J. Comput. Phys. 83, 32–78 (1989)
Jiang, G.S., Shu, C.W.: Efficient implementation of weighted ENO schemes. J. Comput. Phys. 126, 202–228 (1996)
Ben-Artzi, M., Falcovitz, J.: A second order Godunov-type scheme for compressible fluid dynamics. J. Comput. Phys. 55, 1–32 (1984)
Castro, C.E., Toro, E.F.: Solvers for the high-order Riemann problem for hyperbolic balance laws. J. Comput. Phys. 227, 2481–2513 (2008)
Dumbser, M., Enaux, C., Toro, E.F.: Finite volume schemes of very high order of accuracy for stiff hyperbolic balance laws. J. Comput. Phys. 227, 3971–4001 (2008)
Toro, E.F., Montecinos, G.I.: Implicit, semi-analytical solution of the generalized Riemann problem for stiff hyperbolic balance laws. J. Comput. Phys. 303, 146–172 (2015)
Götz, C.R., Iske, A.: Approximate solutions of generalized Riemann problems for nonlinear systems of hyperbolic conservation laws. Math. Comput. 85, 35–62 (2016)
Götz, C.R., Dumbser, M.: A novel solver for the generalized Riemann problem based on a simplified LeFloch-Raviart expansion and a local space-time discontinuous Galerkin formulation. J. Sci. Comput. 69(2), 805–840 (2016)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Toro, E.F. (2018). Lectures on Hyperbolic Equations and Their Numerical Approximation. In: Farina, A., Mikelić, A., Rosso, F. (eds) Non-Newtonian Fluid Mechanics and Complex Flows. Lecture Notes in Mathematics(), vol 2212. Springer, Cham. https://doi.org/10.1007/978-3-319-74796-5_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-74796-5_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-74795-8
Online ISBN: 978-3-319-74796-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)