13.5 Finite Difference Schemes

The level set equation

$$u_{t} + F(t,\mathbf{x}) \Vert \nabla_\mathbf{x}u \Vert = 0$$ (13.2)

can be viewed as a special Hamilton-Jacobi equation

$$u_t + H(t,\mathbf{x},D_\mathbf{x}u) = 0,$$

where $D_\mathbf{x}u$ denotes first order derivatives of $u$ with respect to the space variables. The Hamiltonian $H$ is a smooth function and non-smooth solutions must be admitted (in order to model corners).

In order to discretize the level set equation (13.2), one approach is to substitute the time derivative with a forward difference and the spatial derivatives with central differences. Considering the case of a corner with a right angle at the outside (for the shape cf. Figure 13.5) and a constant speed function shows that the central difference approximation chooses a wrong value for the gradient at the point in the corner. More precisely the exact solution for $u_t$ is a constant except at the corner, where the same value should be chosen and the slope $\nabla_\mathbf{x}u$ is not defined. The central difference approximation sets the undefined slope $\nabla_\mathbf{x}u$ to the average of the left and right slopes, which yields a different limit solution. Hence the wrong calculations of the slope propagate away from the corner and form oscillations. Increasing the resolution in time only results in more oscillations, which is illustrated in [121].

Another approach is to add a viscosity term to the right hand side and thus to consider the new Hamilton-Jacobi equation

$$u_t + H(t,\mathbf{x},D_\mathbf{x}u) = \epsilon \Delta u,$$

which reads

$$u_{t} + F(t,\mathbf{x}) \Vert \nabla_\mathbf{x}u \Vert = \epsilon \Delta u$$

in the case of the level set equation. Here $\epsilon$ is a positive constant. The main idea, which has to be shown, is that the solutions $u_\epsilon$ of this equation are smooth and that the limit of these solutions yields an appropriate weak solution as $\epsilon\to0$. The viscosity solution can be proven to be the unique viscous limit of the smoothed Hamilton-Jacobi equation [26,25]. However the disadvantage of this approach is the smoothing introduced by the artificial viscosity term $\epsilon \Delta u$, which often causes significant rounding at corners [121].

The third and best approach results in the discretizations in Sections 13.5.1 and 13.5.2, which ensures that discontinuities and fronts stay sharp. In order to achieve this for equations of the form $u_t + \bigl( G(u) \bigr)_x = 0$, it is assumed in the following that the flux $G(u)$ is convex (i.e., $\mathrm{d}^2 G / \mathrm{d} u^2 = 0$). An approach introduced by S.K. Godunov [64,66,127,121] is to use the piecewise constant data at one time step to construct an exact solution by considering a local Riemann problem for each interval. The main ideas are to ensure that the conservation form of the equation is preserved, that the entropy condition is satisfied, and that the scheme is very accurate away from discontinuities. One example for such a scheme is the Engquist-Osher scheme [31,121], on which the following schemes are based. Three cases for the direction of the characteristics must be discerned when considering the properties of such a scheme: the characteristics may follow the same direction, they may meet (shock), or they may divert (rarefaction). In the shock case the Engquist-Osher scheme adds a little diffusion to the exact solution and in the other two cases it yields the exact solution.