Numerical Approximation of the Maximal Solutions for a Class of Degenerate Hamilton-Jacobi Equations.
In this paper we study an approximation scheme  for a class of Hamilton--Jacobi problems  for which uniqueness of the viscosity solution does not hold. This class includes the eikonal equation arising in the shape-from-shading problem. We show that, if an appropriate stability condition is satisfied, the scheme converges to the maximal viscosity solution of the problem. Furthermore we give an estimate for  the discretization error.
Introduction
Given a Hamilton-Jacobi equation, a general result due to Barles-Souganidis [3] says that
any "reasonable" approximation scheme (based f.e. on finite differences, finite elements,
finite volumes, discretization of characteristics, etc.) converges to the viscosity solution of
the equation. Besides some simple properties that the approximation scheme has to satisfy,
it is only requested that the equation satisfies a comparison theorem for discontinuous
solutions, which in particular implies uniqueness of the viscosity solution.
This result covers a wide class of first and second order Hamilton-Jacobi equations, yet there
are interesting examples of equations coming from the applications for which uniqueness of
the viscosity solution does not hold. A significant example is given by the Eikonal equation
on some open and bounded
domain\Omega ae R n coupled for example with a Dirichlet boundary
condition on @ This equation arises in the Shape-from-Shading problem in image analysis
and a large literature has been devoted to its study (see [4] for a description of the problem
This paper was written while the second author was visiting the Dipartimento di Matematica, Universit'a
di Roma "La Sapienza" supported by DFG-Grant GR1569/2-1. The research was partially supported by
the TMR Network "Viscosity solutions and their applications".
and [16] for a viscosity solution approach). It is well known that if f vanishes at some
points, there are infinite many viscosity solutions to (1.1) (see [15]). Nevertheless, among
these solutions, in general only one is the relevant solution (for example, from the physical
point of view, from the control theoretic one, etc.
In [6] (see also [14]), requiring a stronger condition for supersolution than that for the
standard viscosity solution, a Comparison Principle, which characterizes the maximal viscosity
solution of the problem, has been obtained for the following class of Hamilton-Jacobi
problems
Here\Omega is a bounded domain of R N , H and f are nonnegative continuous functions and f
can have a very general zero set (the Eikonal equation (1.1) fits into this class of equation).
It is worth noting that this maximal solution is the value function of a control problem
associated in a suitable way to (1.2)-(1.3).
There are, in general, two approaches to the discretization of problem (1.2)-(1.3).
A first possibility is to discretize problem (1.2)-(1.3) directly, but imposing some additional
condition which among the infinite many solutions singles out the one we want to approx-
imate: for example, in [17], it is assumed that the solution is known on the zero set of f ,
which is now a part of the boundary of the domain where the problem is discretized.
A second possible approach (see [4], [5] and references therein) is to discretize a regularized
version of problem (1.2)-(1.3), obtained by cutting from below f at some positive level
(note that for f ? 0 problem (1.2)-(1.3) has a unique viscosity solution). To prove
the convergence of the scheme, both ffl and the discretization step h have to be send to 0.
Since the limit problem does not have a unique viscosity solution, it is not possible to apply
the Barles-Souganidis theorem and, to our knowledge, there is no convergence theorem for
this class of schemes, at least for a general zero set of f . Furthermore, if ffl and h are not
related by some condition, the approximation scheme shows numerical instability and it is
not really known which solution is approximated (see [12] for some numerical tests in this
sense).
Aim of this paper is to describe an approximation scheme for which it is possible to prove
the convergence to the maximal solution of problem (1.2)-(1.3), without requiring any
additional assumptions.
The scheme is based on a two step discretization of the control problem associated to the
regularized problem: first in the time variable, discretization step h, and then in the space
variable, discretization step k (see [2], [13] for related ideas).
In the first part (Sections 3, 4), we study the approximation scheme obtained by discretization
in time. We show that, if ffl and h are related in an appropriate way, the scheme
converges to the maximal solution of (1.2)-(1.3) for ffl and h going to zero. This result is in
the spirit of [3], in the sense that it is based on stability properties of the maximal viscosity
solution and on its characterization given by the comparison theorem in [6]. Therefore,
the proof of the convergence theorem can be easily modified to manage other boundary
conditions instead of (1.3) or, also, different approximation schemes not necessarely based
on the control theoretic interpretation of the problem.
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 3
In the second part (Section 5) we study the discretization error for the fully discrete scheme.
We show that, if the zero set of f is not too "wild", it is possible to estimate in terms of
ffl and of the discretization steps the L 1 -distance between the approximate solution and
the maximal solution of the continuous problem. This part deeply employs the control
theoretic interpretation both of the discrete problem and of the continuous one.
Continuous problem: assumptions and results
In this section we briefly recall the characterization of the maximal solution of problem
obtained in [6]. Here and in the remainder of the paper by (sub, super)solutions
we mean Crandall-Lions viscosity (sub, super)solutions (see [1] for a general treatment).
We first set the assumptions on the data of the problem. The hamiltonian H
:\Omega \Theta R N
is assumed to be continuous in both variables and to verify
lim
uniformly for x
strictly increasing for t 2 [0; 1]
for any (x; p)
2\Omega \Theta R N ,
and
is convex for any x
Note that the hypothesis (2.2) replaces the stronger one of convexity of H in p.
The function f
R is nonnegative, continuous
in\Omega . Moreover, defined K := fx 2
it is assumed that
Finally we assume g : R N ! R to be a continuous and bounded function.
We introduce the gauge function ae and the support function ffi of the convex set Z(x),
namely
for any (x; p)
2\Omega \Theta R N . Both these functions are convex and homogeneous in the variable
p, and are l.s.c. and respectively continuous
in\Omega (note that, if x 2 K, ae(x;
are related by the following equality
Example 2.1 Let / be a continuous function such that
strictly increasing. Consider the equation
In this case we have
We now define a nonsymmetric semidistance
on\Omega \Theta\Omega by
R T
and, for x
2\Omega and r ? 0, the open sets
fy
It can be shown that the family BL (x; r) induces a topology - L on \Omega\Gamma If K consists of
isolated points this topology is equivalent to the Euclidean topology and the problem can
be studied in the framework of viscosity solution theory (see [14]). In general, - L is weaker
than the Euclidean topology and, for x 2 K, the set of points having zero L-distance from
x is a subset of K.
To obtain the characterization of the maximal solution, the definition of viscosity solution
will be adapted to the topology - L .
Definition 2.2 Given a l.s.c. function v
continuous function OE is
called L-subtangent to v at x 0
2\Omega if, for some ffl ? 0,
The L-subtangent is called strict if OE(x) ! v(x) outside BL
0g.
We remark that the convexity assumption (2.2) allows us to use Lipschitz continuous test
functions instead of C 1 test functions as in the standard definition of viscosity solution.
For a Lipschitz continuous function OE, we denote by @OE(x) the generalized gradient of OE at
OE is differentiable at x n g:
Definition 2.3 A l.s.c. function v
is said to be a singular supersolution of
(1.2) if for any x 0
2\Omega and for any OE, L-subtangent to v at x 0 such that
there exists a sequence x n
2\Omega n K and a sequence p n 2 @OE(x n ) for
which
lim
and
lim
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 5
It is worth noting that the definition of singular supersolution reduces to the standard
definition of viscosity supersolution if x 0
In fact, in this case, since the topology
- L and the Euclidean topology are equivalent in neighborhood of x 0 , L-subtangents at
x 0 coincide with standard subtangents. Moreover,
ae(x; p) - 1) if and only if H(x; p) - f(x) (resp. H(x; p) - f(x)).
In the following theorem, we compare viscosity subsolutions and singular supersolutions of
equation (1.2).
Theorem 2.4 Let u 2
USC(\Omega
LSC(\Omega ) be a viscosity subsolution and a singular
supersolution of equation (1.2), respectively, such that u - v on @ Then
Hypothesis (2.2) allows us to give a control theoretic interpretation of problem (1.2)-(1.3).
Let U be the value function of the control problem with dynamics
where x
2\Omega and q is any bounded measurable function from [0; +1) to R n such that
cost functional
Z
The dynamic programming equation associated to the control problem (2.10)-(2.11) is
sup
This equation turns out to be equivalent to equation (1.2), in the sense that any viscosity
sub or supersolution of equation (2.12) is also a viscosity sub- or supersolution of equation
(1.2) and vice versa.
In the following we will assume that the boundary datum g verifies the compatibility
condition
It is standard to show that, under hypothesis (2.13), U is a viscosity solution of (1.2) and
satisfies the boundary condition (1.3). Furthermore we have
Proposition 2.5 The value function U is a singular supersolution of equation (1.2) in \Omega\Gamma
Theorem 2.4 and Proposition 2.5 now allow us to characterize the maximal solution of
denote the set of functions v 2
USC(\Omega ) which are viscosity subsolutions
of (1.2) and which satisfy v - g on @
\Omega\Gamma From Theorem 2.4 and Proposition 2.5 it follows
that the value function U of the control problem (2.10)-(2.11) is the maximal element of S,
i.e. the maximal subsolution of problem (1.2)-(1.3). Moreover U is a singular supersolution
of (1.2) satisfying on @
hence it is the maximal solution.
6 FABIO CAMILLI AND LARS GR -
Remark 2.6 If H is convex in p, then U coincides with the value function of control
problem with dynamics (2.10) and cost functional
where H   (x; \Delta) denotes the Legendre transform of H(x; \Delta), cp. [15]. Note, however, that
ffi(x; q) and f(x) +H   (x; q) in general do not coincide pointwise.
We conclude this section stating a particular case of a general stability theorem proved in
[6] needed for the construction of the approximation scheme.
Proposition 2.7 Set f ffl be the sequence of viscosity solutions
of
Then
lim
ffl!0
uniformly in \Omega\Gamma where U is the maximal solutions of (1.2)-(1.3).
Note that for any ffl ? 0 fixed, since f ffl ? 0 in \Omega\Gamma problem (2.14) admits a unique viscosity
solution. Moreover this solution is given by the value function of the control problem with
dynamics (2.10) and cost functional
@\Omega and ffi ffl (x; q) is defined as ffi(x; q) with f ffl instead of f .
We introduce some notations we will use in the following. We define
Moreover, for ffl ? 0, we set
Note that, for any ffl ? 0,
(r) is bounded by !
rg.
3 The semidiscrete scheme
Let us introduce the semidiscrete approximation scheme, obtained by discretizing in time
the exit time control problem (2.10)-(2.15). For a fixed ffl ? 0, we choose a step in time
define discrete dynamics by the recursive sequence
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 7
The cost is given by
where
(we assume the convention that
0). The value function for this control problem is
such that N ! +1g:
By a standard application of the discrete dynamic programming principle, the function u hffl
is a solution of the problem
The following result holds true
Proposition 3.1 There is a constant C (independent of h and ffl) such that
Moreover u hffl is the unique bounded solution of (3:1).
Proof: We first observe that it is always possible to assume, by adding a constant, that
- 0. It follows that u hffl - 0. Moreover
where M is as in (2.16).
be two bounded solution of (3.1) and set w i 2. Then
2\Omega
where
It follows that
with in R N n \Omega\Gamma
We conclude that for any ffl ? 0 and h ? 0 there exists at most one bounded solution of
(3.3) and therefore of problem (3.1). This solution is given by u hffl .
Remark 3.2 If we discretized the control problem (2.10)-(2.11) directly (which corresponds
to setting in the previous approximation scheme), the resulting approximating
equation does not have a unique bounded solution, similarly to what happens in
problem (1.2)-(1.3). This causes the drawback that any algorithm designed to solve that
approximating equation could not converge to the maximal viscosity solution and, in any
case, displays high numerical instability (see [12]).
4 Convergence of the semidiscrete scheme
In this section, we prove the convergence of the approximation scheme introduced in the
previous section to the maximal solution of (1.2)-(1.3).
Given a locally uniformly bounded sequence of functions v ffl
lim inf
ffl!0
ffl!0
lim sup
ffl!0
ffl!0
for any x 2 \Omega\Gamma The functions lim inf
ffl!0
ffl!0
are, respectively, l.s.c. and
u.s.c.
in\Omega .
Lemma 4.1 Let u hffl be a sequence of solutions of (3.1) and assume that is such
that
Then
ffl!0
2\Omega
is a singular supersolution of (1.2).
Proof: Because of (3.2), the function u is well defined in \Omega\Gamma Let OE
R be L-subtangent
to u at x 0 2 \Omega\Gamma It is possible to assume without loss of generality (see [6], Proposition 5.1)
that OE is a strict L-subtangent to u at x 0 .
Employing a standard argument in viscosity solution theory, we find a sequence x ffl of
minimum points for u tends to 0 + . Then
ae
oe
ae
oe
for some q ffl with jq ffl
From the Mean Value Theorem for Lipschitz continuous functions (see Clarke [7]), there
exist
Substituting (4.3) into (4.2), we get
Observe that x ffl 62 K, otherwise, since on K, we should have and from
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 9
which is impossible since ffi ffl is strictly positive in \Omega\Gamma
Let By the homogeneity of ffi ffl (x; q) with respect to q, we have q ffl 2 fq 2
1g. Dividing (4.4) by recalling (2.6), we get
Since the sequence x ffl belongs
to hypothesis (4.1), that u is a singular supersolution of (1.2).
Theorem 4.2 Assume that either
or
\Omega is convex: (4.6)
If u hffl is a sequence of solutions of problem (3.1) and satisfies the assumption
(4.1), then
lim
ffl!0
uniformly
in\Omega , (4.7)
where U is the maximal solution of problem (1.2)-(1.3).
Proof: We set
ffl!0
ffl!0
These function are well defined because of (3.2).
From Proposition 4.1, it follows that u is a singular supersolution of equation (1.2). Moreover
it is standard to show that u is a subsolution of (2.12) and therefore of (1.2)
in\Omega (see,
f.e., [1] or [2]). If we show that u - u on @
\Omega\Gamma then Theorem 2.4 and Proposition 2.5 imply
that
in\Omega and therefore (4.7).
We will show that
To show that u(x) - g(x) on @
\Omega\Gamma we need an estimate on the behavior of u hffl in a neighborhood
of @
sufficiently small and
jg.
For x
@\Omega be such that d(x; @
for the
discrete control problem by
and, denoted by x n the corresponding discrete trajectory, let
62\Omega g.
Observing that Nh - jy \Gamma xj, we get
where M is as in (2.16) and ! g is a modulus of continuity of g. If x
@\Omega and x ffl
2\Omega is a
sequence converging to x 0 , we have either u hffl
@\Omega is such that d(x ffl ; @
converges to x 0 ,
we get u(x 0
To get the other inequality in (4.8), if g j 0, then u
in\Omega and therefore u - 0 on
@
If (4.6) holds, by adding a constant, we can always assume that g - 0.
For x
2\Omega , let q n be an j-optimal control for u hffl (x), x n the corresponding discrete trajectory
and N the exit time
we have
with C as in (3.2).
Let q(t) be a control law for the continuous problem obtained by setting
are respectively the trajectory and the
time corresponding to q(t), we have
R
where the estimate j-(T holds because of the convexity of \Omega\Gamma Since u ffl
for any x 2
@\Omega and the assumption (4.1) is satisfied, from (4.9) we easily get other inequality
in (4.8).
Remark 4.3 For the Eikonal equation (1.1) we have
condition (4.1) reduces to
f is the modulus of continuity of the function f on \Omega\Gamma
5 Discretization error for the fully discrete scheme
In this section we will discuss a fully discrete scheme derived from the semidiscrete one as
developed in the previous sections. In order to simplify the calculations we assume that
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 11
the function g defining the boundary condition is uniformly Lipschitz with constant L g ,
and that the
domain\Omega is convex.
We will introduce a space discretization which transforms (3.1) into a finite dimensional
problem. For this purpose we choose a grid \Gamma
covering\Omega consisting of simplices S j with
nodes x i and look for the solution of (3.1) in the space
const on S j g
of piecewise linear functions on \Gamma. By the parameter k we denote the maximal diameter
of the simplices S j . For simplicity we assume that the boundary of the gridded domain
coincides with the boundary of \Omega\Gamma (In the general case we can always achieve an error
scaling linearly with the distance between these two boundaries due to the fact that g is
Lipschitz).
Thus we end up with the fully discrete scheme
ffl;h
ffl;h
for all nodes x i
2\Omega with the boundary condition u k
ffl;h for the nodes x i
62\Omega and
linear interpolation between the nodes.
Note that there exists a unique bounded solution of (5.1). The boundedness of any solution
of (5.1) follows from the fact that
ffl;h
ffl;h
holds for any q 2 R n with 1. Thus we can always choose q such that u k
ffl;h
depends on nodes which are closer to the boundary
@\Omega than x i and (if h !
but with a weight strictly less than one. Since the value in the boundary nodes is bounded
we obtain boundedness for each node by induction.
Due to the boundedness the existence of a unique solution u
ffl;h is now easily proved by
applying the Kruzkov transformation
ffl;h
as in the proof of Proposition 3.1.
Note that the function ffi ffl appearing in the scheme is defined implicitely via H and f ffl . In
order to solve the scheme we assume that we can compute this function analytically as
e.g. in Example 2.1. (In the case of a convex Hamiltonian one may alternatively use a
numerical approximation of the integrand from Remark 2.6 via the Legendre transform as
given e.g. in [10]. Note, however, that this procedure yields a different cost function than
in the following analysis.)
We will now start by estimating the discretization error ju ffl
ffl;h
we allow nonconstant boundary conditions we introduce the following auxiliary functions
which will be useful for the estimation of the error.
Definition 5.1 For each point x
2\Omega we define
where -(\Delta) is an optimal path for the initial value x and -(T
For each node x i of the grid pick a control q i minimizing (5.1) and let w 2 2 W be the
unique solution of
with the boundary condition w 2 interpolation between the nodes.
Finally we define
Remark 5.2 The existence of optimal paths follows from the continuous dependence of
the functional J(x; q) from the control function q using the weak   -metric (as defined for
control functions e.g. in [9]), using the Gronwall Lemma as in [8, Proof of Lemma 3.4(ii)]
and the structure of ffi ffl . Note that the a-priori boundedness of the length of approximately
optimal trajectories - following from the positivity of ffi ffl - is crucial for this continuous
dependence. Thus in general the existence of optimal trajectories does not hold for the
non-regularized problem since there for any sequence of approximately optimal trajectories
the length of these trajectories may grow unbounded when we restrict
Note that we do not require uniqueness of the optimal paths in Definition 5.1. In the case
that there is no unique optimal path we may use one that minimizes w 1 .
Definition 5.1 defines functions which are 0 at
@\Omega and away from
@\Omega essentially grow like
ffl;h , respectively. More precisely we have that
and
ffl;h
ffl;h
for -(\Delta) and q i as used in the definition.
Note that in particular if g(x) j c is constant we obtain
Using this w we can give the following estimate for the discretization error.
Proposition 5.3 Let u k
ffl;h 2 W be the unique solution of (5.1). Then the estimate
fi(ffl)h
holds for each x
2\Omega and for all sufficiently small k ? 0 and h ? 0 with
and ff as
defined in (2.16)-(2.18),
and some constant C independent from ffl; h and k.
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 13
The proof can be found in the appendix.
Remark 5.4 (i) Note that estimate (5.3) is stronger than the usual L1 estimate since
essentially the error scales with the function w(x) being 0 at @
\Omega\Gamma The reason for this
behaviour origins in the fact that the error is estimated along the optimal trajectories
whose length depends on the optimal value.
(ii) The constant ff(ffl) essentially depends on the growth of H in jpj, e.g. in Example 2.1 we
have (ffl). The constant fi(ffl) is determined by the difference between H(x; p) and
H(x; q) for In particular if H(x; p) 2 [C 1 jpj we have that fi(ffl) - C 1 =C 2
independently from ffl. Finally, ! ffi (which gives a bound for !
for combines the
continuity properties of H and f , i.e. in Example 2.1 we have that ! ffi
(iii) Note that the requirement on h ensuring the convergence of the fully discrete scheme is
thus it is consistent with condition (4.1) for the convergence
of the semidiscrete scheme.
(iv) The appearance of the value ff(ffl) in the denominator in (5.3) is due to the fact that
here we implicitely included the worst case, i.e. that the length of the optimal trajectories
may grow like 1=ff(ffl) for ff(ffl) ! 0. Since this is not necessarily the case in many practical
examples one can expect better convergence behaviour for ff(ffl) ! 0.
(v) A particular nice formulation of estimate (5.3) can be obtained if we consider the
Eikonal equation (1.1) (implying assume that f is uniformly
impose a homogeneous boundary condition, i.e.
(implying L 0). In this case the estimate becomes
for some constant C ? 0 independent from ffl; h and k. In particular this implies convergence
of the scheme
We will now turn to the discussion of the error obtained when equation (1.2) is replaced
by equation (2.14), i.e. the error introduced by the regularization of the problem.
Proposition 2.7 already implies that u " converges to U , where U is the maximal subsolution
of (1.2). Unfortunately, in general this convergence can be arbitrary slow. In the optimal
control interpretation this is due to the fact that the length of approximately optimal
trajectories may grow unbounded as the approximation gets better and better. Since
these long pieces of the trajectories can only appear in regions where f is sufficiently small
(otherwise the cost would be large contradicting the approximate optimality), we can derive
an estimate for the regularization error by defining a criterion for the sets where f is small
which in turn gives a bound on the length of approximately optimal trajectories.
The following definition is our main tool for this purpose.
Definition 5.5 Let B ae R d be a compact set. For each connected component B i of B we
define the inner diameter d(B i ) by
14 FABIO CAMILLI AND LARS GR -
where
and for B we define the inner diameter by
where the sum is taken over all connected components of B.
Using this definition we can state the following estimate for the regularization error.
Proposition 5.6 Let U be the maximal subsolution of (1.2) and let u ffl be the unique
viscosity solution of (2.14).
Then the estimate
holds where K ffl := fx
The proof can be found in the appendix.
Here the constant c(ffl) depends only on the sets Z ffl (x)g, i.e. on ffl
and on the Hamiltonian H. In fact an easy calculation shows that
Thus e.g. the estimate c(ffl) - C ffl fl for some constants C; fl ? 0 and all ffl ? 0 sufficiently
small holds if H(x; p) - (jpj=C) 1=fl for all x 2 K ffl , all ffl ? 0 sufficently small and all p 2 R n
with jpj sufficiently small. In particular for the Eikonal equation (1.1) this implies
Observe that if f is piecewise polynomial then bounded for all ffl ? 0 and hence
convergence with order c(ffl) follows for ffl ! 0. Piecewise polynomial maps are in particular
interesting since they include the case where f is obtained from experimental data by
some polynomial interpolation (e.g. using piecewise linear interpolations, multidimensional
splines.
The following theorem now gives the full a-priori estimates for the approximation error of
the whole numerical approximation.
Theorem 5.7 Let U be the maximal subsolution of (1.2) and let u k
ffl;h be the unique solution
of the numerical scheme (5.1).
Then the estimate
fi(ffl)h
holds for each x
2\Omega and the constants from the Propositions 5.3 and 5.6.
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 15
Proof: Follows immediately from the Propositions 5.3 and 5.6.
Remark 5.8 (i) A possible modification of the scheme can be made if we allow smaller
time steps at the boundary @ i.e. for x i
2\Omega and x
62\Omega we use the restricted time
step
2\Omega g:
Although slightly more difficult to implement this modification usually gives better numerical
results. The proof of Proposition 5.3 also applies to this modified scheme.
(ii) Due to the structural similarity of the scheme described in this section with the scheme
considered in [13], the adaptive grid scheme developed there can also be applied here.
Similar convergence results as in [13] can be obtained for our scheme using the technique
from the proof of Proposition 5.3.
6

Appendix

Proof of the Propositions 5.3 and 5.6
In order to prove Proposition 5.3 we will first state a useful estimate for the local error
along the functional.
Lemma 6.1 For each measurable q(\Delta) with almost all t 2 [0; h] and the path
-(\Delta) with -
2\Omega for all t 2 [0; h] there exists p 2 R n with
that
Z
and
Conversely, for each p 2 R n with each x
2\Omega with x
2\Omega there exists a
measurable function q(\Delta) with
Z
and
2\Omega for all t 2 [0; h].
Proof: The convexity of ffi ffl in the second argument implies
Z
Hence by defining
Z hq(t)dt
the first assertion immediately follows from the continuity of ffi ffl which is measured by !
The second assertion follows directly from the continuity of ffi ffl setting q(t) j p and using
the convexity
of\Omega .
Proof of Proposition 5.3
We start giving some preliminary estimates.
First note that the error at the boundary can be estimated by
which simply follows from the Lipschitz property of g.
Furthermore it is easy to see that on each element S j of the grid we can estimate
for each two points
We show the estimate (5.3) by estimating seperately the quantities u k
ffl;h (x). First, we consider u
Observe that for any fl ? 0 there exists an j - 0 such that
which easily follows from the fact that w 1 - 0 and u k
ffl;h is bounded.
Now we fix some arbitrary fl ? 0 and choose j - 0 to be minimal with (6.3). If the
assertion immediately follows. Otherwise by the continuity of the functions and
the compactness
of\Omega we can conclude that there exists x
2\Omega such that
ffl;h
Now consider the element S j containing x   . We can write x
where the x i are
the nodes of S j and the - i are nonnegative coefficients with
Using estimate (6.2) we obtain
ffl;h
i2I
ffl;h
Now for each of the nodes we distinguish three cases.
By (6.1) this implies
ffl;h
2\Omega and for the optimal path - i (\Delta) with - i Definition 5.1 there exists a
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 17
@\Omega and -
(t). In this case by the convexity
of\Omega we can conclude
that there exists p 2 R n with
62\Omega such that jx i
we obtain
ffl;h
2\Omega and for the optimal path - i (\Delta) with - i 5.1 the equality
Z
holds
@\Omega and -
In this case Lemma 6.1 and the definition of u k
ffl;h imply
ffl;h
where by (6.8) we can estimate
and by Definition 5.1 thus also
Taking into account that the coefficients in (6.5) sum up to 1 we derive
i2I
ffl;h
and combining (6.3), (6.4), (6.5), (6.10) and (6.11) we obtain
(w 1
from which we conclude that
Estimating
(note that - j - ff(ffl)) this becomes
h-
Now we specify the assumption "h; k ? 0 sufficiently small" by choosing them such that
h-
for some constant C ? 0 and thus
fi(")h
h- j
which implies the desired estimate for w values in this
resulting inequality are independent from fl ? 0 this also implies the estimate for
The inequality for u ffl
ffl;h (x) follows with the same technique and the obvious modifications
using note that here the convexity
of\Omega is also needed in Lemma 6.1 used in
case (iii). Proceeding in this way we end up with the analogous estimate to (6.12)
which leads to the desired result here without using the assumptions on k and h.
Proof of Proposition 5.6
For any measurable and bounded q and any x
2\Omega denote the solution of (2.10) by
arbitrary and pick some x 2 \Omega\Gamma Then by the optimal
control representation of U (2.10)-(2.11) there exists a solution -
with
@\Omega and
We now divide the connected components K i
I of K ffl into two classes by defining
I 1 :=
and I Then by the continuity of H there exists a constant fl(ffl 2 ) with
as
Furthermore by the uniform continuity of f every set K i
has a volume bounded
from below by some uniform constant depending on ffl 2 and hence there are only finitely
many of these sets; we may number them by
Now we define for each of these K i
which is hit by the trajectory - ffl 1
times
by
" g and t i
where we omit those sets K i
" for which [t i
holds. This gives
us a finite number r of pairwise disjoint intervals [t i
which we assume to be numbered
according to their order, i.e. t i
For each trajectory piece - ffl 1
we have by (6.13) and by the fact that outside K ffl
the functions ffi and ffi ffl coincide the estimate
APPROXIMATION OF DEGENERATE HAMILTON-JACOBI EQUATIONS 19
For the points - ffl 1
yielding
ffl for all t 2 [0;
ffl
is possible by the definition of d(\Delta) and the structure of the dynamics (2.10). We now define
a sequence of times t i ,
and a measurable function ~ q(\Delta) by
~
This construction yields that
(t) for all
and
thus in particular it follows that -(t r ; x; ~
obtain
dt
dt
Now letting first ffl we obtain the assertion since u ffl - U is obvious



--R

Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman equations
An approximation scheme for the minimum time function
Convergence of approximation scheme for fully nonlinear second order equations
The MIT Press
Global
"La Sapienza"
Optimization and nonsmooth analysis
Infinite fime optimal control and periodicity
Some aspects of control systems as dynamical systems
Fast Legendre-Fenchel transform and applications to Hamilton-Jacobi equations and conservation laws
A numerical approach to the infinite horizon problem of deterministic control theory
"Image analysis and processing"
An adaptive grid scheme for the discrete Hamilton-Jacobi-Bellman equation
Uniqueness results for a class of Hamilton-Jacobi equations with singular coefficients
Generalized solutions of Hamilton-Jacobi equations

A viscosity solution approach to Shape from shading
--TR
maximal solution;singular Hamilton-Jacobi equations;regularization;discretization error;numerical approximation