A Numerical Scheme for Evacuation Dynamics

Abstract

We give a stability condition for a semi–implicit numerical scheme and prove unconditional stability for an implicit scheme for a nonlinear advection – diffusion equation, meant as a model of crowd dynamics. Numerical stability is given for a wider class of equations and schemes.

Supported by ICM, University of Warsaw.

1 Introduction

We consider a macroscopic description of how pedestrians exit a space, typically a room. We identify the crowd through the pedestrians’ density, say $\rho = \rho (t,x)$, and assume that the crowd behavior is well described by

$$\begin{aligned} \partial _{t}\rho +\nabla \cdot \left( {\rho }\,\overrightarrow{V}\right) -\kappa \,\varDelta \rho =0 \qquad \text { in }{\mathbb {R}}^+ \times \varOmega \;, \end{aligned}$$

(1)

which is a regularization ($\kappa >0$) of the continuity equation

$$\begin{aligned} \partial _t \rho + \,\text {div}\left( \rho \, \overrightarrow{V} \right) = 0 \;, \qquad \text { in }{\mathbb {R}}^+ \times \varOmega \;, \end{aligned}$$

(2)

where $\varOmega \subset {\mathbb {R}}^2$ is the environment available to pedestrians, $\overrightarrow{V} = \overrightarrow{V} (x,\rho ) \in {\mathbb {R}}^2$ is the velocity of the individual at x, given the presence of the density $\rho$. The (small) parameter $\kappa >0$ describes the diffusion part, allowing people to spread independently of the direction they are given so as to reach the exit.

The velocity vector should be given as a function of x, possibly also of $\rho (x)$ or even some nonlocal average of $\rho$. Several choices for the velocity function are available in the literature, see for instance [1, 4,5,6] for velocities depending nonlocally on the density, and  [7, Sect. 4.1], [2, 10] for velocities depending locally on the density. In this last case, the following assumption is usually made:

$$\begin{aligned} \begin{aligned}&\overrightarrow{V} = \overrightarrow{V} (x,\rho ) = v (\rho ) \; \overrightarrow{w} (x), \quad \text {where } \overrightarrow{w} \text { is a vector field in } \varOmega ,\\&\text {and }v:\mathbb {R}\rightarrow [0,v_{\max }) \text { is a scalar function, smooth and non-increasing.} \end{aligned} \end{aligned}$$

(3)

So, $\overrightarrow{w}(x)$, often normalized, is here the direction given for an individual at x, and $v(\rho )$ its velocity value, translating the common attitude of moving faster when the density is lower. In this case, the velocity value depends on the density, but not on its direction. The correction proposed in (1) allows a direction change by spreading, and seems to be a realistic model of the crowd behaviour.

We assume that the boundary $\partial \varOmega$ of $\varOmega$ is a union of three disjoint parts: the walls ${\varGamma }_w$, the exit ${\varGamma }$ and the corners $\varGamma _c$. The set of corners is finite; $\varGamma _w$ and $\varGamma$ possess a field of exterior normal vectors $\overrightarrow{n}$. Their natural functions translate into the following conditions on $\overrightarrow{V} = \overrightarrow{V}(x,\rho (x))$:

$$\begin{aligned}&\partial \varOmega = \varGamma \cup \varGamma _w \cup \varGamma _c; \end{aligned}$$

(4)

$$\begin{aligned}&\overrightarrow{V}\cdot \overrightarrow{n} = 0 \text { on } \varGamma _w, \end{aligned}$$

(5)

$$\begin{aligned}&\overrightarrow{V}\cdot \overrightarrow{n} > 0 \text { on } \varGamma . \end{aligned}$$

(6)

As for the boundary conditions on $\rho$, there are again several choices for these. A natural one seems to be a homogeneous Dirichlet or Neumann boundary condition on the walls $\varGamma _w$. As for the condition on the exit, it can be of Dirchlet or Neummann.

The main point of interest in this particular phenomenon is the widely known now Braess paradox. It consists in the fact that what seems to improve the traffic can make it slower and, on the contrary, an obstacle to the traffic may accelerate it. In evacuation, this mean that an obstacle placed in front of the exit may shorten the evacuation time. Our aim is to check this paradox on some examples, so as to be able, later on, to compare diverse obstacles and their respective effect on evacuation.

In this paper, we propose several finite elements (FE) numerical schemes to solve our problem, in particular a semi-implicit scheme, and discuss its stability. Such a scheme has been proposed in [8] for the case inspired by hydrodynamics, where $\overrightarrow{V}$ is a function of x only, and additionally $\overrightarrow{V}$ is divergence free. The advection term is then linear. We treat here the fully nonlinear case $\overrightarrow{V} = \overrightarrow{V}(\rho ,x)$, and we relax the zero divergence condition to:

$$\begin{aligned} \,\text {div}\overrightarrow{V}=\,\text {div}\overrightarrow{V}(x,\rho (x))\ge 0. \end{aligned}$$

(7)

We also assume the existence of a weak solution, in a sense that we define in Sect. 2. This weak formulation is formulated in more abstract terms, so as the numerical schemes that we give in Sect. 3. We prove there, in Theorem 2, stability of the semi–implicit scheme, which is the main result of this paper. The CFL condition required in Theorem 2 is given in a general abstract form, we give also its special forms in the following corollaries. In Sect. 4, we show an important example of $\overrightarrow{V}$ coming from the eikonal equation, for which the condition (7) seems to be satisfied in the numerical tests.

In the forthcoming [3] we will show the well posedeness of (1) and perform the simulations of its dynamics using the numerical schemes that we present here.

2 Weak Formulation

In what follows, we assume that our problem has a unique solution. For the well–posedeness of the problem (1), we refer to the forthcoming paper [3]. Clearly, we will be dealing with its weak solution in order to build a FE approximation. As far as weak solutions are considered, it is clear that the finite set $\varGamma _c$ has no importance and we can restrict our attention to the $\varGamma _w\,\cup \,\varGamma$ part of the boundary. More regularity for the solution can be easily obtained if the boundary and the boundary conditions are regular enough.

In order to build a numerical scheme, we adapt the main ideas of [8], where such a scheme is built for the linear divergence free case (which is the case (3) with $v \equiv const$ and $\,\text {div}\overrightarrow{w} =0$). These assumptions are clearly too much restrictive for our case.

Let us define $H = L^2(\varOmega )$, with $(\cdot ,\cdot )$ the scalar product in H and ${\left\| \cdot \right\| }$ the norm in H. Let $V \subset H^1(\varOmega )$ be a Hilbert space, being our working space. The choice of V shall depend on the boundary conditions imposed on our problem, e.g. it is $H^1(\varOmega )$ if we impose a homogeneous Neumann boundary condition on $\partial \varOmega$, and $V = \{u\in H^1(\varOmega ):\, u = 0 \text { on } \varGamma \}$ if a homogeneous Dirichlet condition is imposed on $\varGamma$. We call W the space containing the traces of functions from V and of their normal derivatives. This flexibility in the boundary condition will be allowed by our abstract approach. We observe the following fact relating the situation we are modeling and the boundary condition on the exit.

Lemma 1

Consider (1) with the boundary assumptions (4)–(6); assume additionally that a homogeneous boundary condition $\nabla \rho \cdot \overrightarrow{n}$ is imposed on $\varGamma _w$. At time $t\ge 0$, evacuation happens, i.e.  $\displaystyle \frac{d}{dt}\int _\varOmega \rho (t,x)\,dx < 0$, if and only if

$$\begin{aligned} \int _\varGamma \left\{ \kappa {{\,\mathrm{\nabla }\,}}\rho (t,\xi ) - \rho (t,\xi )\,\overrightarrow{V}(\rho (t,\xi ))\right\} \cdot \overrightarrow{n}(\xi )\, d\xi < 0. \end{aligned}$$

(8)

Proof

Integrate (1) on $\varOmega$ by parts.

This lemma says that a homogeneous Neumann boundary condition on $\rho$ on the walls as well as on the exits ensures the evacuation process.

Our aim is now to write the Eq. (1) in the abstract form as:

$$\begin{aligned} (\rho _t, \eta ) + A_0(\rho )(\rho , \eta ) + A_1(\rho )(\rho , \eta ) -A_2(\rho )(\rho , \eta ) = 0, \qquad \forall \eta \in V, \end{aligned}$$

(9)

where, for $i = 0, \, 1,\, 2,\,$ $A_i(\varphi )(\cdot , \cdot )$ are bilinear forms.

Definition 1

Let $\alpha >0$ be an arbitrary constant. Define the operator (nonlinear in the first, linear in the second variable),

$$\begin{aligned} B: W\times W\rightarrow W, \quad B(\varphi )\rho = \left( \kappa \,\nabla \rho - \frac{1}{2}\rho \,\overrightarrow{V}(\varphi )\right) \cdot \overrightarrow{n} \end{aligned}$$

and the following functionals (nonlinear in the first, linear in the other variables)

$$\begin{aligned}&\qquad \qquad \; A_0:V\times V^2 \rightarrow {\mathbb {R}}, \quad A_1, A_2: W\times W^2 \rightarrow {\mathbb {R}},\\&\quad \; A_0(\varphi )(\rho , \eta ) = \int _\varOmega \left\{ -\rho \,\overrightarrow{V}(\varphi )\cdot \nabla \eta +2\kappa \, \nabla \rho \cdot \nabla \eta +\kappa \,\rho \varDelta \eta \right\} ,\\&A_1(\varphi )(\rho , \eta ) \equiv A_1^\alpha (\varphi )(\rho , \eta ) = \frac{1}{2\alpha } \int _{\partial \varOmega } \left[ B(\varphi )\rho - \alpha \rho \right] \left[ B(\varphi )\eta - \alpha \eta \right] ,\\&\,A_2(\varphi )(\rho , \eta ) \equiv A_2^\alpha (\varphi )(\rho , \eta ) = \frac{1}{2\alpha } \int _{\partial \varOmega } \left[ B(\varphi )\rho + \alpha \rho \right] \left[ B(\varphi )\eta + \alpha \eta \right] . \end{aligned}$$

We will in general omit the dependence on $\alpha$ in the functionals $A_1, \, A_2$. Note that $A_1$, $A_2$ are by definition positive and symmetric and that

$$\begin{aligned} A_2(\varphi )(\rho ,\eta ) - A_1(\varphi )(\rho ,\eta ) = \int _{\partial \varOmega } \left\{ \rho B(\varphi )\eta +\eta B(\varphi )\rho \right\} \end{aligned}$$

(10)

Lemma 2

With the forms $A_0$, $A_1$, $A_2$ given in Definition 1, the weak form of (1) can be written as (9).

Proof

Multiply (1) by $\eta$, integrate on $\varOmega$ and apply integration by parts (twice on the diffusive term), use the definition of $A_0$ and B and (10).

Lemma 3

Assume (5), (6), (7). The forms $A_0, A_1$, $A_2$ given in Definition 1 satisfy, for any $\varphi ,\rho \in V$

$$\begin{aligned} A_2(\varphi )(\rho , \rho ) - A_1(\varphi )(\rho ,\rho ) \le 2 A_0(\varphi )(\rho ,\rho ). \end{aligned}$$

(11)

Assume also a homogenous (Neumann or Dirichlet) boundary condition for $\rho$ on $\varGamma$. Then for any $\varphi ,\rho \in V$

$$\begin{aligned} A_2(\varphi )(\rho ,\rho )- A_1(\varphi )(\rho ,\rho ) \le 0. \end{aligned}$$

(12)

Proof

By integration by parts and noting that

$$2\int _\varOmega \rho \nabla \rho \cdot \overrightarrow{V} = -\int _\varOmega \rho ^2\,\text {div}\overrightarrow{V} +\int _{\partial \varOmega }\rho ^2\overrightarrow{V}\cdot \overrightarrow{n} \,, $$

the inequality (11) writes, by virtue of (10), (5),

$$ \frac{1}{2}\int _\varOmega \rho ^2\,\text {div}\overrightarrow{V}(\varphi ) + \kappa \int _\varOmega |\nabla \rho |^2 \ge 0, $$

which is satisfied by (7). This proves (11). Now, by virtue of (10),

$$A_2(\varphi )(\rho ,\rho ) - A_1(\varphi )(\rho ,\rho ) = 2\int _{\partial \varOmega } \rho B(\varphi )\rho = 2\kappa \int _\varGamma \rho \nabla \rho \cdot \overrightarrow{n} - \int _\varGamma \rho ^2 \overrightarrow{V}(\varphi )\cdot \overrightarrow{n}. $$

This is clearly negative by (6) and the homogeneous boundary condition on $\varGamma$.

Remark 1

We may also assume here $\nabla \rho \cdot \overrightarrow{n} \le 0$ on $\varGamma$.

Corollary 1

As $A_1(\varphi )$, $A_2(\varphi )$ are symmetric and positive, (12) implies

$$\begin{aligned} A_2(\varphi )(u,v)\le \frac{1}{2} \left[ A_1(\varphi )(u,u)+A_2(\varphi )(v,v) \right] . \end{aligned}$$

(13)

Proof

By positivity, symmetry and bilinearity of $A_2$ we have

$$ 0\le A_2(\varphi )(u-v, u-v) =A_2(\varphi )(u, u) - 2 A_2(\varphi )(u,v) +A_2(\varphi )(v,v) $$

which together with (12) gives the desired conclusion.

Remark 2

Corollary 1 implies that conditions (11)–(12), together with the additional assumption that the bilinear form $A_2(\varphi )$ is positive, imply a condition of the form of (2.2) of [8] for $\mathcal{A}_i = A_i(\varphi )$. Take $\mathcal{A}_3=A_2(\varphi )$.

3 Numerical Scheme and Its Stability

Lemma 4

Let $A_i:V\times V^2 \rightarrow {\mathbb {R}}$ for $i = 0, 1, 2$ be such that $A_i(\varphi )(\cdot , \cdot )$ are bilinear symmetric forms satisfying (11), (12) for any $\varphi , \rho \in V$. Let $\rho$ be the solution to (9). Then $t \mapsto (\rho , \rho )(t)$ decreases, i.e. the solution $\rho$ is $L^2$ stable.

Proof

Note that (11)–(12) imply

$$\begin{aligned} A_0(\rho )(\rho , \rho ) + A_1(\rho )(\rho , \rho ) -A_2(\rho )(\rho , \rho ) \ge 0. \end{aligned}$$

(14)

From (9) one gets directly the desired conclusion.

We will now consider a family of finite element spaces $V_h\subset V$, where H is, as usual, the mesh parameter and consider approximated solutions in these spaces.

Preserving the important solution’s property given by Lemma 4 is not obvious when dealing with a numerical approximation, especially with schemes that are not fully implicit. Any disturbance of this property, however, may cause a geometrically growing error. Schemes preserving it will be called stable.

Definition 2

Let $V_h \subset V$ be a finite-dimensional vectorial subspace of V. Denote the unknown at time step n by $\rho ^n_h \in V_h$. Denote the test function as $\eta _h \in V_h$. The fully implicit first order scheme for (9) reads: find a sequence $\rho ^n_h \in V_h$, $n=0,\,1,\,\ldots$ such that for any test function $\eta _h \in V_h$

$$\begin{aligned} \left( \frac{\rho ^{n+1}_h - \rho ^n_h}{\varDelta t}, \eta _h\right) + A_0\left( \rho ^{n+1}_h\right) \left( \rho ^{n+1}_h, \eta _h\right) + A_1\left( \rho ^{n+1}_h\right) \left( \rho ^{n+1}_h, \eta _h\right) \quad \!&\nonumber \\ -A_2\left( \rho ^{n+1}_h\right) \left( \rho ^{n+1}_h, \eta _h\right)&= 0. \end{aligned}$$

(15)

The semi–implicit first order scheme for (9) reads: find a sequence $\rho ^n_h \in V_h$, $n=0,\,1,\,\ldots$ such that for any test function $\eta _h \in V_h$

$$\begin{aligned} \left( \frac{\rho ^{n+1}_h - \rho ^n_h}{\varDelta t}, \eta _h\right) + A_0\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \eta _h\right) + A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \eta _h\right) -A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \eta _h\right) = 0. \end{aligned}$$

(16)

The explicit first order scheme for (9) reads: find a sequence $\rho ^n_h \in V_h$, $n=0,\,1,\,\ldots$ such that for any test function $\eta _h \in V_h$

$$\begin{aligned} \left( \frac{\rho ^{n+1}_h - \rho ^n_h}{\varDelta t}, \eta _h\right) + A_0\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \eta _h\right) + A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \eta _h\right) -A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \eta _h\right) = 0. \end{aligned}$$

(17)

We say that a scheme is stable if $(\rho ^{n+1}_h,\rho ^{n+1}_h) \le (\rho ^{n}_h,\rho ^{n}_h)$ for any n.

Theorem 1

(Unconditional stability). Assume that $A_i(\varphi )(\cdot , \cdot )$, $i = 0, 1, 2$, are bilinear forms satisfying (11)–(12). Then the fully implicit scheme (15) is unconditionally stable. If (12) is replaced by a stronger condition

$$\begin{aligned} A_2(\varphi )(\rho ,\eta )- A_1(\varphi )(\rho ,\eta )\le 0 \quad \forall \rho , \eta \in V, \end{aligned}$$

(18)

the semi–implicit scheme (16) is also unconditionally stable. If, additionally, (11) is replaced by a stronger condition

$$\begin{aligned} A_2(\varphi )(\rho , \eta ) - A_1(\varphi )(\rho ,\eta ) \le 2 A_0(\varphi )(\rho ,\eta ) \quad \forall \rho , \eta \in V, \end{aligned}$$

(19)

the explicit scheme (17) is also unconditionally stable.

Proof

Take $\eta _h = \rho _h^{n+1}$. For the implicit scheme, use (14) and the Schwarz inequality. For the semi–implicit scheme,

$$\begin{aligned}&\;\;\left( \rho ^{n+1}_h,\rho ^{n+1}_h\right) \le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) - \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \\&\qquad \qquad \;\;- {\varDelta t}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) + {\varDelta t}\,A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \quad (\text {by }(11))\\&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h-\rho ^{n+1}_h, \rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h-\rho ^{n+1}_h, \rho ^{n+1}_h\right) \\&\qquad \quad \; - \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \quad \text {(by linearity)}\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) \quad (\text {by }(18)). \end{aligned}$$

We conclude by the Schwarz inequality. For the explicit scheme, we have

$$\begin{aligned} \left( \rho ^{n+1}_h,\rho ^{n+1}_h\right)&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) - \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \\&\qquad \!\! - {\varDelta t}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) + {\varDelta t}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \quad (\text {by }(19))\\&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) \quad (\text {by }(18)). \end{aligned}$$

The conclusion comes again by the Schwarz inequality.

Remark 3

As in Theorem 1 the fully implicit scheme does not require symmetry of the forms $A_1$, $A_2$, it can also be applied for a stronger variational formulation, where the diffusive term is integrated by part just once.

Theorem 2

(CFL condition for stability). Assume that $A_i(\varphi )$, for $i\in \{0,1,2\}$, are bilinear forms such that $A_1(\varphi )$, $A_2(\varphi )$ are symmetric and positive, and the conditions (11), (12) are satisfied. The semi–implicit scheme (16) is stable under the abstract CFL condition

$$\begin{aligned} \varDelta t\, A_1(\rho _h)(u_h,u_h) \le (u_h,u_h) \qquad \forall \rho _h, u_h\in V_h. \end{aligned}$$

(20)

The explicit scheme is stable under the above condition and (18)–(19).

Proof

Take again $\eta _h = \rho _h^{n+1}$. We have

$$\begin{aligned} \left( \rho ^{n+1}_h,\rho ^{n+1}_h\right)&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - {\varDelta t}\,A_0\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \\&\quad \;\; - {\varDelta t}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) + {\varDelta t}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \\&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - {\varDelta t}\,A_0\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) - {\varDelta t}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \\&\quad \;\; + \frac{\varDelta t}{2}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n}_h\right) + \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \quad (\text {by }(13))\\&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - {\varDelta t}\,A_0\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \\&\quad \;\; + \frac{\varDelta t}{2}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h-\rho ^{n}_h, \rho ^{n+1}_h-\rho ^{n}_h,\right) \\&\quad \;\; - \frac{\varDelta t}{2}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \\&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h-\rho ^n_h, \rho ^{n+1}_h-\rho ^n_h\right) \quad (\text {by }(11)), \end{aligned}$$

which gives $\left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \le \left( \rho ^{n}_h,\rho ^{n}_h\right)$ by (20). For the explicit scheme,

$$\begin{aligned}&\left( \rho ^{n+1}_h,\rho ^{n+1}_h\right) \le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - {\varDelta t}\,A_0\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) - {\varDelta t}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \\&\qquad \qquad + \frac{\varDelta t}{2}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n}_h\right) + \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \quad (\text {by }(13))\\&\qquad \quad \;\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - \frac{\varDelta t}{2}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) - \frac{\varDelta t}{2}\,A_2\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h\right) \\&\qquad \quad \;\; + \frac{\varDelta t}{2}\,A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n}_h\right) + \frac{\varDelta t}{2}A_2\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h\right) \qquad (\text {by } (19))\\&\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) - \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n}_h, \rho ^{n+1}_h-\rho ^n_h\right) + \frac{\varDelta t}{2} A_2(\rho ^n_h)\left( \rho ^{n+1}_h, \rho ^{n+1}_h - \rho ^{n}_h\right) \\&\qquad \qquad \quad \;\le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h-\rho ^{n}_h, \rho ^{n+1}_h-\rho ^n_h\right) \\&\qquad \quad - \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h, \rho ^{n+1}_h-\rho ^n_h\right) + \frac{\varDelta t}{2} A_2(\rho ^n_h)\left( \rho ^{n+1}_h, \rho ^{n+1}_h - \rho ^{n}_h\right) \\&\qquad \qquad \le \left( \rho ^{n}_h,\rho ^{n+1}_h\right) + \frac{\varDelta t}{2}A_1\left( \rho ^{n}_h\right) \left( \rho ^{n+1}_h-\rho ^{n}_h, \rho ^{n+1}_h-\rho ^n_h\right) \qquad (\text {by } (18)). \end{aligned}$$

This gives again stability by (20).

Theorem 2 and Lemma 3 imply immediately the following.

Corollary 2

Assume (5), (6), (7) and a homogenous Neumann boundary condition $\nabla \rho \cdot \overrightarrow{n}=0$ on $\varGamma _w\,\cup \,\varGamma$. If $\alpha$, h and $\varDelta t$ are positive constants such that for any $\rho _h, u_h\in V_h$ the CFL condition

$$\begin{aligned} \frac{\displaystyle \varDelta t\, \int _\varGamma u_h^2\left( \overrightarrow{V}(\rho _h)\cdot \overrightarrow{n} - 2\alpha \right) ^2}{\displaystyle 8\alpha \,\int _{\varOmega _h} u_h^2} \le 1 \end{aligned}$$

(21)

is satisfied, the semi–implicit scheme is stable.

Corollary 3

Assume (5), (6), (7), a homogenous Neumann boundary condition $\nabla \rho \cdot \overrightarrow{n}=0$ on $\varGamma _w$ and a homogenous Dirichlet boundary condition $\rho =0$ on $\varGamma$. If $\alpha$, h and $\varDelta t$ are positive constants such that for any $u_h\in V_h$ the CFL condition

$$\begin{aligned} \frac{\displaystyle \varDelta t\, \int _\varGamma \left( \kappa \,\nabla u_h\cdot \overrightarrow{n} - \alpha \, u_h\right) ^2}{\displaystyle 2\alpha \,\int _{\varOmega _h} u_h^2} \le 1 \end{aligned}$$

(22)

is satisfied, the semi–implicit scheme is stable.

Remark 4

The CFL condition giving stability of the semi–implicit scheme can also be written for the case when $\nabla \rho \cdot \overrightarrow{n}\le 0$ on $\varGamma$.

Fig. 1.

Some examples for $-\nabla \varPhi$, a vector field giving approximately the shortest path to the exit. The legend gives the values of ${\left\| {{\,\mathrm{\nabla }\,}}\varPhi \right\| }$.

4 Example

An interesting example that seems, by a numerical evidence, to satisfy (7), is $\overrightarrow{V} = -\nabla \varPhi$ where $\varPhi$ is a solution to the regularized eikonal equation

$$\begin{aligned} \left\{ \begin{array}{l@{\qquad }r@{\;}c@{\;}l} {\left\| {{\,\mathrm{\nabla }\,}}\varPhi \right\| }^2 - \delta \; \varDelta \varPhi = 1 &{} x &{} \in &{} \varOmega \\ {{\,\mathrm{\nabla }\,}}\varPhi (\xi ) \cdot \overrightarrow{n} (\xi ) = 0 &{} \xi &{} \in &{} \varGamma _w \\ \varPhi (\xi ) = 0 &{} \xi &{} \in &{} \varGamma \;, \end{array} \right. \end{aligned}$$

If $\delta =0$, this equation is known as the eikonal equation it comes from optics. $-\nabla \varPhi$ gives the shortest path to $\varGamma$ followed by a light ray. With the regularization ($\delta >0$), the vector field $-\nabla \varPhi$ can be seen as giving an approximation to the shortest way to $\varGamma$, having the advantage that different paths do not cross; see Fig. 1. We show in [2] that $-{{\,\mathrm{\nabla }\,}}\varPhi$ satisfies conditions (5), (6).

By integration by parts, it clearly follows that

$$\int _\varOmega - \varDelta \varPhi = \int _\varOmega \,\text {div}(-\nabla \varPhi ) = \int _\varOmega \,\text {div}\overrightarrow{V} > 0. $$

Although we have not got a formal proof yet, the numerical simulations suggest that the same inequality is satisfied pointwise: ${\left\| {{\,\mathrm{\nabla }\,}}\varPhi \right\| }\le 1$, which would mean $- \varDelta \varPhi = \,\text {div}\overrightarrow{V} \ge 0$.

The density–dependent case $\overrightarrow{V} = - v(\rho )\nabla \varPhi$ is to be considered. More simulations are given in [9].