2021 UNC Greensboro PDE Conference, Electronic Journal of Differential Equations, Conference 26 (2022), pp. 13–32. ISSN: 1072-6691. URL: http://ejde.math.txstate.edu or http://ejde.math.unt.edu DISCRETE ALEKSANDROV SOLUTIONS OF THE MONGE-AMPÈRE EQUATION GERARD AWANOU Abstract. We make two relaxations of the Oliker-Prussner method for the Dirichlet problem for the Monge-Ampère equation. First we relax the convex- ity requirement and consider mesh functions which are only discrete convex. The second relaxation consists in using a finite stencil. The discrete nonlinear equations are solved with a damped Newton’s method. We give two proofs of convergence of the resulting scheme for right-hand side a density, on domains which are convex and not necessarily strictly convex, under the assumption that the boundary data has a continuous convex extension. The first proof is based on the notion of Aleksandrov solution while the second uses viscosity solutions. 1. Introduction In this paper we prove the convergence of a finite difference scheme to weak solutions, in the sense of Aleksandrov and in the sense of viscosity, for the Dirichlet problem for the Monge-Ampère equation detD2u = f in Ω u = g on ∂Ω, (1.1) where f ∈ L1(Ω) ∩ C(Ω) is a non negative function and Ω is a convex bounded domain of Rd with boundary ∂Ω. It is assumed that g ∈ C(∂Ω) can be extended to a convex function g̃ ∈ C(Ω). The domain is not assumed to be strictly convex. Problem (1.1) can be solved through polygonal approximations [28], i.e. with the Oliker-Prussner method [27]. For recent developments on the discretization of (1.1), we refer for example to [12, 23, 24]. The purpose of this paper is to present a tech- nique which can be used to prove convergence of a class of approximations to (1.1) when the domain is convex and not assumed to be strictly convex. As with [22], we consider a method which is medius between the Oliker-Prussner method and finite difference methods. It is relatively simpler to implement than the Oliker-Prussner method, a possible advantage in three dimensions. This is achieved by relaxing the convexity requirement on the approximate solutions. That relaxation leads to a wide stencil scheme, which we further relax by using a finite stencil. The discrete nonlinear equations are solved with a damped Newton’s method. Convergence of 2020 Mathematics Subject Classification. 39A12, 35J60, 65N12, 65M06. Key words and phrases. Discrete Monge-Ampère; Aleksandrov solution; weak convergence of measures. ©2022 This work is licensed under a CC BY 4.0 license. Published August 25, 2022. 13 14 G. AWANOU EJDE-2022/CONF/26 the method is first given in the setting of Aleksandrov solutions, using an equicon- tinuity argument and a recent result [2] stating conditions under which the uniform limit of discrete solutions satisfies the boundary condition strongly. The scheme we analyze, leads to a set function that overestimates the discrete Monge-Ampère measure defined through a discrete version of the subdifferential. This allows us to use essentially the same tools as in the Aleksandrov theory of (1.1), c.f. [2]. Under the above assumptions, Aleksandrov solutions are equivalent to viscos- ity solutions. The hallmark of the Barles-Souganidis approach for convergence to viscosity solutions, is that no equicontinuity is used. Ingredients are stability, con- sistency and monotonicity of the scheme. As well as a comparison principle for Dirichlet boundary conditions in the sense of viscosity, which is not available for the Monge-Ampère equation [10, 13, 18, 23, 25]. Here, using the equicontinuity of the discrete solutions, and under the assumption that our scheme is (pointwise) consistent, we obtain a uniform limit of discrete solutions which is shown to be a vis- cosity solution of the equation satisfying the boundary condition strongly, hence is unique by the comparison principle for boundary conditions imposed strongly. This argument requires f to be integrable and is applicable to some other discretizations. We also give some convergence results in the case where the right hand side is a sum of Dirac masses instead of a positive density. However, in that case the right-hand side becomes singular unlike in the case of the Oliker-Prussner method, making the use of a damped Newton’s method for the relaxed scheme not feasible. Nethertheless, these results could be useful for the analysis of schemes such as the one in [7]. This article is organized as follows. In the next section we collect some notation used throughout the paper, present and study the numerical scheme. Convergence results are given in section 3. We finish with some numerical experiments. 2. Preliminaries We use the notation ‖ · ‖ for the Euclidean norm of Rd. Let h be a small positive parameter and let Zdh = {mh : m ∈ Zd}, denote the orthogonal lattice with mesh length h. Let also (r1, . . . , rd) denote the canonical basis of Rd. We define Ωh = Ω ∩ Zdh. For a function u ∈ C(Ω) its restriction on Ωh is also denoted u by an abuse of notation. For x ∈ Ωh and e ∈ Zd let hex = sup{rh : r ∈ [0, 1] and x+ rhe ∈ Ω}. Next, let V ⊂ Zd \{0} such that {r1, . . . , rd} ⊂ V and such that for e ∈ V , −e ∈ V . We define ∂Ωh = {x ∈ ∂Ω : ∃y ∈ Ωh and e ∈ V such that x = y + heye}, (2.1) and denote by Uh the linear space of mesh functions, i.e. real-valued functions defined on Nh := Ωh ∪ ∂Ωh. EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 15 For x ∈ Ωh, e ∈ Zd, e 6= 0 such that x± he ∈ Nh and uh ∈ Uh, let ∆euh(x) = 2 hex + h−ex (uh(x+ hexe)− uh(x) hex + uh(x− h−ex e)− uh(x) h−ex ) . Definition 2.1. We say that a mesh function vh is discrete convex if ∆evh(x) ≥ 0 for all x ∈ Ωh and e ∈ V ⊂ Zd. We denote by Ch the cone of discrete convex mesh functions. The restriction of a convex function to Ωh is a discrete convex mesh function. 2.1. Aleksandrov solutions. The material in this subsection is taken from [15] to which we refer for proofs. Let Ω be an open subset of Rd and let us denote by P(Rd) the set of subsets of Rd. Definition 2.2. Let u : Ω→ R. The normal mapping of u, or subdifferential of u is the set-valued mapping ∂u : Ω→ P(Rd) defined by ∂u(x0) = {p ∈ Rd : u(x) ≥ u(x0) + p · (x− x0), for all x ∈ Ω}. (2.2) Let |E| denote the Lebesgue measure of the measurable subset E ⊂ Ω. For E ⊂ Ω, we define ∂u(E) = ∪x∈E∂u(x). Theorem 2.3 ([15, Theorem 1.1.13]). If u is continuous on Ω, the class S = {E ⊂ Ω : ∂u(E) is Lebesgue measurable}, is a Borel σ-algebra and the set function M [u] : S → R defined by M [u](E) = |∂u(E)|, is a measure, finite on compact subsets, called the Monge-Ampère measure associ- ated with the function u. We can now define the notion of Aleksandrov solution of the Monge-Ampère equation. Definition 2.4. Let Ω ⊂ Rd be open and convex. Given a Borel measure ν on Ω, a convex function u ∈ C(Ω) is an Aleksandrov solution of detD2u = ν, if the associated Monge-Ampère measure M [u] is equal to ν. We recall an existence and uniqueness result for the solution of (1.1). Proposition 2.5 ([16, Theorem 1.1]). Let Ω be a bounded convex domain of Rd. Assume ν is a finite Borel measure and g ∈ C(∂Ω) can be extended to a function g̃ ∈ C(Ω) which is convex in Ω. Then the Monge-Ampère equation (1.1) has a unique convex Aleksandrov solution in C(Ω). Definition 2.6. A sequence µn of Borel measures converges to a Borel measure µ if µn(B)→ µ(B) for any Borel set B with µ(∂B) = 0. We note that there are several equivalent definitions of weak convergence of measures which can be found for example in [11, Theorem 1, section 1.9]. 16 G. AWANOU EJDE-2022/CONF/26 2.2. Discretizations of the normal mapping. For a mesh function uh ∈ Ch, the discrete normal mapping of uh at the point x ∈ Ω ∩ Zdh is defined as ∂huh(x) = {p ∈ Rd : uh(x+ hexe) ≥ uh(x) + p · (hexe)∀e ∈ Zd}. For a subset E ⊂ Ω, we define ∂huh(E) = ∪x∈E∩Zdh∂huh(x), which is Borel measurable for E Borel measurable. The proof is essentially the same as the corresponding one at the continuous level [4, p. 117–118]. Put Mh[uh](E) = |∂huh(E)| for a Borel set E. Note that if E ∩ Zdh = {x}, we have Mh[uh](E) = Mh[uh]({x}). We will make the abuse of notation Mh[uh](x) = Mh[uh]({x}). A numerical scheme based on Mh[uh] would require a wide scheme. We will use Mh[uh] in our proof of convergence. We now consider a discrete Monge-Ampère measure based on the finite stencil V . Put ∂V uh(x) = {p ∈ Rd, uh(x+ hexe) ≥ uh(x) + p · (hexe)∀e ∈ V }, and ∂V uh(E) = ∪x∈E∩Zdh∂V uh(x) with MV [uh](E) = |∂V uh(E)| for a Borel set E. We have MV [uh](x) ≥Mh[uh](x), ∀x ∈ Ωh, (2.3) since ∂huh(x) ⊂ ∂V uh(x). 2.3. Viscosity solutions of the elliptic Monge-Ampère equation. A convex function u ∈ C(Ω) is a viscosity solution of (1.1) if u = g on ∂Ω and for all φ ∈ C2(Ω) the following holds • at each local maximum point x0 of u− φ, f(x0) ≤ detD2φ(x0) • at each local minimum point x0 of u−φ, f(x0) ≥ detD2φ(x0), if D2φ(x0) ≥ 0, i.e. D2φ(x0) has positive eigenvalues. As explained in [17], the requirement D2φ(x0) ≥ 0 in the second condition above is natural for the two dimensional case we consider. The space of test functions in the definition above can be restricted to the space of strictly convex quadratic polynomials [15, Remark 1.3.3]. An upper semi-continuous convex function u is said to be a viscosity sub solution of detD2u(x) = f(x) if the first condition holds and a lower semi-continuous convex function is said to be a viscosity super solution when the second holds. A viscosity solution of (1.1) is a continuous function which satisfies the boundary condition and is both a viscosity sub solution and a viscosity super solution. Note that the notion of viscosity solution is a pointwise notion, i.e. conditions will be checked at a point in the domain. For further reference, we recall the comparison principle of sub and super solu- tions, [17, Theorem V. 2]. Theorem 2.7. Let u and v be respectively sub and super solutions of detD2u(x) = f(x) in Ω. Then if supx∈∂Ω max(u(x)− v(x), 0) = M , then u(x)− v(x) ≤M in Ω. EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 17 2.3.1. Equivalence with Aleksandrov solutions. For f > 0, a convex function u ∈ C(Ω) is an Aleksandrov solution of (1.1) if and only if it is a viscosity solution of (1.1), [15, Propositions 1.3.4 and 1.7.1]. The equivalence of viscosity and Aleksan- drov solutions in the degenerate case f ≥ 0 is discussed in [3]. 2.4. The numerical scheme. We consider the following discretization of (1.1): find uh ∈ Ch such that MV [uh](x) = hdf(x), x ∈ Ωh uh(x) = g(x), x ∈ ∂Ωh. (2.4) We establish the stability, unicity and existence of solutions to (2.4). We first recall the Brunn-Minkowski’s inequality [29]. Lemma 2.8. For two nonempty, compact convex sets K and L, their Minkowski sum is defined as K + L = {a+ b, a ∈ K and b ∈ L}. We have |K + L|1/d ≥ |K|1/d + |L|1/d. (2.5) Lemma 2.9. Given x ∈ Ωh the operator vh → (MV [vh](x))1/d is concave on Ch. Proof. We recall that given a set K and λ ∈ R, λK = {λx, x ∈ K}. We observe that for λ > 0, p ∈ ∂V vh(x) if and only if λp ∈ ∂V (λvh)(x). Thus by the positive homogeneity (of degree d) of volume in Rd (MV [λvh](x))1/d = λ(MV [vh](x))1/d. It is therefore enough to prove that for vh, wh ∈ Ch, we have (MV [vh + wh](x))1/d ≥ (MV [vh](x))1/d + (MV [wh](x))1/d. (2.6) Next, we note that ∂V vh(x) + ∂V wh(x) ⊂ ∂V (vh + wh)(x), and thus |∂V (vh + wh)(x)| ≥ |∂V vh(x) + ∂V wh(x)|. We may assume that ∂V vh(x) and ∂V wh(x) are nonempty. Assuming that ∂V vh(x) is compact and convex, (2.6) follows from (2.5). Using the definition and the canonical basis of Rd one shows that ∂V vh(x) is bounded. Thus ∂V vh(x) is compact since it can be shown to be a closed set. The convexity of ∂V vh(x) is a consequence of its definition. This concludes the proof. � Lemma 2.10. Let Cy(x) = ‖y − x‖ denote the cone with vertex y ∈ Ωh. Then Mh[Cy](y) ≥ ωd > 0, where ωd is the volume of the closed unit ball. Proof. We have Cy(y) = 0 and p ∈ ∂V Cy(y) if and only if p · e ≥ −‖e‖∀e ∈ V . Clearly ∂V Cy(y) contains the closed unit ball with volume ωd. This concludes the proof. � 18 G. AWANOU EJDE-2022/CONF/26 2.4.1. Stability. Since f ∈ L1(Ω) ∩ C(Ω) and f ≥ 0, we have∑ x∈Ωh hdf(x) ≤ A, (2.7) with A a number independent of h, for h sufficiently small. For x ∈ Ω we denote by d(x, ∂Ω) the distance of x to ∂Ω. For a subset S of Ω, diam(S) denotes its diameter. Lemma 2.11. Let vh ∈ Ch. Then max x∈Nh vh(x) ≤ max x∈∂Ωh vh(x). Proof. Suppose there is x0 ∈ Ωh such that maxx∈Nh vh(x) = vh(x0) and vh(x0) > maxx∈∂Ωh vh(x). For all e ∈ V , we have vh(x0) ≥ vh(x0 +hex0 e) and vh(x0) ≥ vh(x0−h−ex0 e). This implies that ∆evh(x0) ≤ 0 and hence ∆evh(x0) = 0 since vh is discrete convex. We have vh(x0 + hex0 e)− vh(x0) hex0 = vh(x0)− vh(x0 − h−ex0 e) h−ex0 . Since the left hand side of the above equation is non positive and the right hand side non negative, we conclude that vh(x0) = vh(x0 + hex0 e) = vh(x0 − h−ex0 e), i.e. the maximum is also reached at x0 + hex0 e and x0 − h−ex0 e. Repeating this argument, we may assume that the maximum is reached at an interior point x0 such that x0 +hex0 e ∈ ∂Ωh. Since by assumption vh(x0) > vh(x0 +hex0 e), we obtain ∆evh(x0) < 0, contradicting the assumption vh ∈ Ch. � Lemma 2.12 below is an analogue of [15, Lemma 1.4.1], c.f. [26], and is a discrete version of the Aleksandrov-Bakelman-Pucci’s maximum principle [30, Theorem 8.1], an analogue of which can be found in [19]. Lemma 2.12. Let uh ∈ Ch such that uh ≥ 0 on ∂Ωh. Then for x ∈ Ωh uh(x) ≥ −C(d) [ diam(Ω)d−1d(x, ∂Ω)Mh[uh](Ωh) ]1/d , for a positive constant C(d) which depends only on d. Theorem 2.13. Solutions uh to (2.4) are uniformly bounded. Proof. By Lemma 2.11, we have uh(x) ≤ max x∈∂Ωh g(x). (2.8) By Lemma 2.12, uh(x)− min x∈∂Ωh g(x) ≥ −C(d) [ diam(Ω)d−1d(x, ∂Ω)Mh[uh](Ωh) ]1/d . Since uh solves (2.4), by (2.7) and (2.3) A ≥ ∑ x∈Ωh hdf(x) = ∑ x∈Ωh MV [uh](x) ≥ ∑ x∈Ωh Mh[uh](x) ≥Mh[uh](Ωh). In addition d(x, ∂Ω) ≤ diam(Ω). We conclude that uh(x) ≥ minx∈∂Ωh g(x)−C, for a constant C. Combined with (2.8), we have shown that solutions uh to (2.4) are uniformly bounded. � EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 19 2.4.2. Uniqueness. Theorem 2.14. Under the assumption that f > 0 on Ωh, Problem (2.4) has a unique solution uh. Proof. We consider the convex envelope of the mesh function uh Γ(uh)(x) = sup Laffine {L(x) : L(y) ≤ uh(y) for all y ∈ Nh}, which is a piecewise linear convex function, c.f. for example [2, p. 11]. We note that Γ(uh) depends on the stencil V . This notion of convex envelope generalizes the one used in [2] where we used V = Zd \ {0}. The following result is an analogue of [2, Lemmas 6 and 7] and [2, Theorem 4] where we considered ∂huh. The proofs are identical. If x ∈ Ωh and Γ(uh)(x) 6= uh(x), then ∂V uh(x) = ∅. Moreover, for a subset E ⊂ (conv(Nh))◦, ∂V uh(E) = ∂Γ(uh)(E) up to a set of measure 0 and thus MV [uh](E) = M [Γ(uh)](E). Since g extends to a continuous convex function on Ω, analogous to [2, Lemma 5], Γ(uh) = uh on ∂Ωh if uh solves (2.4). Next, under the assumption that f > 0 on Ωh, ∂V uh(x) 6= ∅ for all x ∈ Ωh, and we conclude that if uh solves (2.4), Γ(uh) solves the Monge-Ampère equation M [Γ(uh)](E) = ∑ x∈E∩Ωh hdf(x), for each Borel set E ⊂ (conv(Nh))◦ with Γ(uh) = g on ∂Ωh and hence Γ(uh) is a prescribed piecewise linear convex function on the boundary of conv(Nh). By Proposition 2.5, the solution is unique, and since Γ(uh) = uh on ∂Ωh, the solution uh is unique. � 2.4.3. Existence. We show that minimizers of a convex functional over a convex set solve (2.4). For vh ∈ Uh and i = 1, . . . , d we consider the first-order difference like operator defined by ∂i−vh(x) := vh(x)− vh(x− h−rix ri)√ h−rix , x ∈ Ωh, and the convex functional Jh(vh) = ∑ x∈Ωh ‖Dhvh(x)‖2, where Dhvh is given by Dhvh(x) = (∂i−vh(x))i=1,...,d. We seek a minimizer of Jh over Sh = {vh ∈ Ch : vh = gh on ∂Ωh, and (MV [vh](x))1/d ≥ f(x)1/d, x ∈ Ωh}. (2.9) The set Sh is a discrete version of S = {v ∈ C(Ω) : v convex , v = g on ∂Ω, and detD2v ≥ f}. It is known, [21], that the solution u of (1.1) is the maximal element of S. This observation may be used to prove the existence of a discrete solution. The proof be- low is motivated by a variational characterization of solutions of (1.1), [21, Section 4], and an observation in [20, p. 86] on discrete Monge-Ampère equations. 20 G. AWANOU EJDE-2022/CONF/26 Lemma 2.15. The set Sh is convex and nonempty. Proof. The convexity of Sh follows from Lemma 2.9. For each y in Ωh, let qy be a cone such that MV [qy](y) ≥ f(y). For example, we may define qy by qy(x) = (f(y) ωd )1/d Cy(x). Put q̂ = ∑ y∈Ωh qy. Since g is bounded on ∂Ω, we can find a number κ such that q̂ − κ ≤ g on ∂Ω. We define wh ∈ Uh by wh(x) = q̂(x)− κ, x ∈ Ωh wh = g on ∂Ωh. We claim that wh ∈ Sh. Let x ∈ Ωh and e ∈ V . Either wh(x+ hexe) = q̂(x+ hexe)− κ or wh(x+ hexe) = g(x+hexe) ≥ q̂(x+hexe)−κ. Similarly wh(x−h−ex e) ≥ q̂(x−h−ex e)−κ. We conclude using the convexity of q̂ that hex + h−ex 2 ∆ewh(x) ≥ q̂(x+ hexe)− κ− wh(x) hex + q̂(x− h−ex e)− κ− wh(x) h−ex = hex + h−ex 2 ∆eq̂(x) ≥ 0. Thus wh ∈ Ch. Next, we prove that ∂V q̂(x) ⊂ ∂V wh(x) for x ∈ Ωh. Since wh = q̂ up to a constant on Ωh, we only need to check that for p ∈ ∂V q̂(x) we have p · (hexe) ≤ wh(x+hexe)−wh(x) when x+hexe ∈ ∂Ωh. Let thus p ∈ ∂V q̂(x) such that x+ hexe ∈ ∂Ωh. We have p · e ≤ q̂(x+ hexe)− q̂(x) = q̂(x+ hexe)− κ− wh(x) ≤ g(x+ hexe)− wh(x) = wh(x+ hexe)− wh(x). We conclude that MV [wh](x) ≥ MV [q̂](x). Therefore by the Brunn-Minkowski inequality (2.5), MV [wh](x)1/d ≥ ∑ y∈Ωh MV [qy](x)1/d ≥ f(x)1/d. This concludes the proof. � We observe that if p ∈ ∂V uh(x), x ∈ Ωh, we have uh(x)− uh(x− h−ex e) h−ex ≤ p · e ≤ uh(x+ hexe)− uh(x) hex . (2.10) Thus MV [uh](x) ≤ d∏ i=1 hex + h−ex 2 ∆riuh(x). (2.11) We define a discrete norm on Uh by ‖vh‖20,h = hd ∑ x∈Ωh vh(x)2, and a semi norm by |vh|21,h = hd ∑ x∈Ωh d∑ i=1 1 h−rix ( ∂i−vh(x) )2 , EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 21 an analogue of a Sobolev semi-norm. Lemma 2.16. We have an analogue of Poincaré’s inequality, C‖vh‖0,h ≤ |vh|1,h, for vh = 0 on ∂Ωh, (2.12) for a constant C > 0 independent of h. Proof. Given x ∈ Ωh and 1 ≤ i ≤ d, let mi x = max{m ∈ N : x−mh−rix ri ∈ Ωh}, and put yix = x−mi xhri. Thus yix−h −ri yix ri ∈ ∂Ωh and by assumption vh(yix−h −ri yix ri) = 0. We have vh(x) = mix−1∑ j=0 vh(x− jhri)− vh(x− (j − 1)hri) + vh(yix) = mix−1∑ j=0 h vh(x− jhri)− vh(x− (j + 1)hri) h + h−riyix vh(yix)− vh(yix − h −ri yix ri) h−riyix . It follows that vh(x)2 ≤ (mix−1∑ j=0 h2 + (h−riyix )2 )(mix−1∑ j=0 (vh(x− jhri)− vh(x− (j + 1)hri)) 2 h2 + (vh(yix)− vh(yix − h −ri yix ri)) 2 (h−riyix )2 ) ≤ mi xh 2 (mix−1∑ j=0 1 h (∂i−vh(x− jhri))2 + 1 h−riyix (∂i−vh(yix))2 ) . Since mi xh and h are bounded by the diameter of Ω, for some constant C > 0 independent of h, ∑ x∈Ωh vh(x)2 ≤ 1 C ∑ x∈Ωh mix−1∑ j=0 1 h (∂i−vh(x− jhri))2 + 1 h−riyix (∂i−vh(yix))2 ≤ 1 C ∑ x∈Ωh d∑ i=1 1 h−rix (∂i−vh(x))2, which concludes the proof. � Lemma 2.17. The functional Jh is coercive on Sh, i.e. Jh(vh)→∞ as ‖vh‖0,h →∞, vh ∈ Sh. Proof. We will assume that h is fixed. We first note that for all x ∈ Ωh and e ∈ V , hex > 0. Let αh = min{hex, x ∈ Ωh, e ∈ V }. Thus for i = 1, . . . , d, 1/h−rix ≥ αh/(h−rix )2 and hdJh(vh) ≥ αh|vh|21,h. Let Φ(p) = ‖p‖2. Using Φ′ to denote the Fréchet derivative of Φ, we have (Φ′(p)− Φ′(q))(p− q) = 2‖p− q‖2. We argue as in [31, p. 550] and put φ(t) = Φ(tDhvh(x) + (1− t)Dhwh(x)). Then Φ(Dhvh(x))− Φ(Dhwh(x)) 22 G. AWANOU EJDE-2022/CONF/26 = φ(1)− φ(0) = ∫ 1 0 φ′(t)dt = ∫ 1 0 Φ′(tDhvh(x) + (1− t)Dhwh(x))(Dhvh(x)−Dhwh(x))dt = ∫ 1 0 ( Φ′(tDhvh(x) + (1− t)Dhwh(x))− Φ′(Dhwh(x)) ) (Dhvh(x)−Dhwh(x)) + Φ′(Dhwh(x))(Dhvh(x)−Dhwh(x))dt ≥ ‖Dhvh(x)−Dhwh(x)‖2 − 2‖Dhwh(x)‖ ‖Dhvh(x)−Dhwh(x)‖. We conclude that hdJh(vh)− hdJh(wh) = hd ∑ x∈Ωh Φ(Dhvh(x))− Φ(Dhwh(x)) ≥ hd ∑ x∈Ωh ‖Dhvh(x)−Dhwh(x)‖2 − 2hd ∑ x∈Ωh ‖Dhwh(x)‖ ‖Dhvh(x)−Dhwh(x)‖. Next ∑ x∈Ωh ‖Dhwh(x)‖ ‖Dhvh(x)−Dhwh(x)‖ ≤ ( ∑ x∈Ωh ‖Dhwh(x)‖2 )1/2( ∑ x∈Ωh ‖Dhvh(x)−Dhwh(x)‖2 )1/2 = Jh(wh)1/2Jh(vh − wh)1/2. Next, if zh = 0 on ∂Ωh, we claim that Jh(zh) ≤ (4d/αh)h−d‖zh‖20,h. Indeed Jh(zh) = ∑ x∈Ωh ‖Dhzh(x)‖2 = ∑ x∈Ωh d∑ i=1 (∂i−zh(x))2 = ∑ x∈Ωh d∑ i=1 (zh(x)− zh(x− h−rix ri)) 2 h−rix ≤ 2 αh ∑ x∈Ωh d∑ i=1 zh(x)2 + zh(x− h−rix ri) 2 ≤ 2d αh ∑ x∈Ωh zh(x)2 + 2 αh d∑ i=1 ∑ x∈Ωh zh(x− h−rix ri) 2, which using zh = 0 on ∂Ωh gives Jh(zh) ≤ 2d αh ∑ x∈Ωh zh(x)2 + 2 αh d∑ i=1 ∑ x∈Ωh zh(x)2 ≤ 4d αh ∑ x∈Ωh zh(x)2 = 4d αh h−d‖zh‖20,h. If vh−wh = 0 on ∂Ωh, we obtain Jh(vh−wh) ≤ (4d/αh)h−d‖vh−wh‖20,h. Therefore, for vh and wh ∈ Sh hdJh(vh)− hdJh(wh) ≥ αh|vh − wh|21,h − 2 ( 4d αh )1/2 Jh(wh)1/2‖vh − wh‖0,h, EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 23 and so using (2.12), hdJh(vh)− hdJh(wh) ≥ Cαh‖vh − wh‖20,h − 2 ( 4d αh )1/2 Jh(wh)1/2‖vh − wh‖0,h, from which the coercivity of Jh on Sh holds. � Theorem 2.18. The functional Jh has a minimizer uh in Sh and uh solves the finite difference equations (2.4). Proof. Since Jh is convex and coercive on Sh and Sh is nonempty, closed and convex, it follows that the functional Jh has a minimizer uh on Sh. We now show that uh solves the finite difference equations (2.4). To this end, it suffices to show that MV [uh] = hdf on Ωh. Let us assume to the contrary that there exists x0 ∈ Ωh such that MV [uh](x0) > hdf(x0) ≥ 0. (2.13) By (2.10), if there were a direction e ∈ V such that ∆euh(x0) = 0, we would have ∂V uh(x0) contained in the hyperplane p · e = (uh(x0 + hexe) − uh(x0))/hex = (uh(x0)−uh(x0−h−ex e))/h−ex , and hence MV [uh](x0) = 0 contradicting (2.13). We conclude that for all e ∈ V ∆euh(x0) > 0. Let ε0 = inf{∆euh(x0) : e ∈ V }. We recall that MV [uh](x) is the volume of a polygon since it is the volume of a domain obtained as an intersection of half-spaces p · (hexe) ≤ uh(x + hexe) − uh(x). Moreover ∂V uh(x) is bounded by (2.11). The vertices of the polygon have coordinates linear combinations of the values uh(y), y ∈ Nh. It is known that the volume of a polygon is a polynomial function, hence a continuous function, of the coordinates of its vertices [1]. Thus the mapping E : R→ R which maps the value of a mesh function vh at x0 to MV [uh](x0) is finite valued and continuous. By (2.13), with r0 = uh(x0), E(r0) > hdf(x0). Therefore there exists ε1 > 0 such that for |r − r0| < ε1, we have E(r) > hdf(x0). Finally, put ε = hex0 h−ex0 min(ε0, ε1). We define wh by wh(x) = uh(x), x 6= x0, wh(x0) = uh(x0) + ε 4 . By construction wh = gh on∂Ωh. For x 6= x0, we have ∆ewh(x) = ∆euh(x),∆ewh(x) = ∆euh(x) + ε 4 2 hex + h−ex 1 hex or ∆ewh(x) = ∆euh(x) + ε 4 2 hex + h−ex 1 h−ex . Moreover ∆ewh(x0) = ∆euh(x0)−ε/(2hex0 h−ex0 ) ≥ ε0−ε/(2hex0 h−ex0 ) ≥ ε/(2hex0 h−ex0 ) > 0 by the definition of ε. We conclude that wh ∈ Ch. Also by construction, MV [wh](x0) = E(r0 + ε/4) > hdf(x0). We claim that for x 6= x0 MV [wh](x) ≥MV [uh](x). Let p ∈ Rd and e ∈ V such that p·(hexe) ≤ uh(x+ hexe)−uh(x). Either uh(x+hexe) = wh(x+hexe) or uh(x+hexe) = wh(x+hexe)−ε/4. This gives p · (hexe) ≤ wh(x + hexe) − wh(x). This proves the claim. We conclude that MV [wh](x) ≥ hdf(x) for all x ∈ Ωh. 24 G. AWANOU EJDE-2022/CONF/26 It remains to show that Jh(wh) < Jh(uh). Let Ωx0 denote the subset of Ωh consisting in x0 and the points x0 + h rj x0rj , j = 1, . . . , d. We have Jh(wh) = ∑ x/∈Ωx0 ‖Dhuh(x)‖2 + ‖Dhwh(x0)‖2 + d∑ j=1 ‖Dhwh(x0 + hrjx0 rj)‖2 = ∑ x/∈Ωx0 ‖Dhuh(x)‖2 + d∑ i=1 1 h−rix0 (wh(x0)− wh(x0 − h−rix0 ri)) 2 + d∑ j=1 d∑ i=1 1 h−ri x0+h rj x0 (wh(x0 + hrjx0 rj)− wh(x0 + hrjx0 rj − h−rix0 ri)) 2. Next, Jh(wh) = ∑ x/∈Ωx0 ‖Dhuh(x)‖2 + d∑ j=1 d∑ i=1 i 6=j 1 h−ri x0+h rj x0 (wh(x0 + hrjx0 rj) − wh(x0 + hrjx0 rj − h−rix0 ri)) 2 + d∑ i=1 1 h−rix0 (wh(x0)− wh(x0 − h−rix0 ri)) 2 + 1 h−ri x0+h ri x0 (wh(x0 + hrix0 ri)− wh(x0))2. We note that h−ri x0+h ri x0 = hrix0 and we have 1 h−rix0 (wh(x0)− wh(x0 − h−rix0 ri)) 2 + 1 hrix0 (wh(x0 + hrix0 ri)− wh(x0))2 = 1 h−rix0 ( uh(x0)− uh(x0 − h−rix0 ri) + ε 4 )2 + 1 hrix0 ( uh(x0 + hrix0 ri)− uh(x0)− ε 4 )2 = 1 h−rix0 (uh(x0)− uh(x0 − h−rix0 ri)) 2 + 1 hrix0 (uh(x0 + hrix0 ri)− uh(x0))2 + ε2 16 ( 1 h−rix0 + 1 hrix0 ) + ε 2h−rix0 (uh(x0)− uh(x0 − h−rix0 ri)) − ε 2hrix0 (uh(x0 + hrix0 ri)− uh(x0)). Thus, since for i 6= j, wh(x0 + hrj)−wh(x0 + hrj − hri) = uh(x0 + hrj)− uh(x0 + hrj − hri), and by our choice of ε, Jh(wh) = Jh(uh) + ε2 16 d∑ i=1 ( 1 h−rix0 + 1 hrix0 ) − ε 2 d∑ i=1 hrix0 + h−rix0 2 ∆riuh(x0) ≤ Jh(uh) + εε0 16 d∑ i=1 hrix0 + h−rix0 − ε 4 d∑ i=1 (hrix0 + h−rix0 )∆riuh(x0) = Jh(uh) + ε 4 d∑ i=1 (hrix0 + h−rix0 ) (ε0 4 −∆riuh(x0) ) < Jh(uh), EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 25 since ∆euh(x0) ≥ ε0 > ε0/4 for all e ∈ V . This contradicts the assumption that uh is a minimizer and concludes the proof. � 3. Convergence analysis In this section, we first address the convergence of the solution uh of (2.4) to the Aleksandrov solution u of (1.1). We require V ⊂ Zd\{0} to converge to Zd\{0}. We thus simply assume that V = Zd \ {0}. We then give a direct proof of convergence to the viscosity solution of (1.1). Finally we make remarks about the case the right hand side of (2.4) approximates a sum of Dirac masses. Definition 3.1. Let uh ∈ Uh for each h > 0. We say that uh converges to a function u uniformly on a compact set K ⊂ Ω if and only if for each sequence hk → 0 and for all ε > 0, there exists h−1 > 0 such that for all hk, 0 < hk < h−1, we have max x∈Nhk∩K |uhk(x)− u(x)| < ε. 3.1. Convergence to the Aleksandrov solution. Theorem 3.2. Let uh solve (2.4). There is a subsequence uhk which converges uniformly on compact subsets to a convex function v ∈ C(Ω) such that detD2v ≤ f(x) in Ω v = g on ∂Ω, Proof. The family uh is a uniformly bounded family of discrete convex functions by Theorem 2.13. Moreover uh = g on ∂Ω and g ∈ C(∂Ω) can be extended to a convex function g̃ ∈ C(Ω). In addition, by (2.3) and (2.7) Mh[uh](Ωh) ≤ ∑ x∈Ωh MV [uh](x) = ∑ x∈Ωh hdf(x) ≤ A. It is proven in [2, Theorem 14] that there is a subsequence uhk which converges uniformly on compact subsets to a convex function v ∈ C(Ω) such that v = g on ∂Ω. It is also proven in [2, Theorem 8] that Mh[uh] defines a Borel measure (as the Monge-Ampère measure of the convex envelope of uh), which converges weakly to M [v]. Since by (2.3), we have Mh[uh](x) ≤ hdf(x), x ∈ Ωh, as an inequality in measures, we obtain detD2v ≤ f(x). � To complete the proof we need additional notions. Given u : Ω → R, the local subdifferential of u is given by ∂lu(x0) = { p ∈ Rd : ∃ a neighborhood Ux0 of x0 such that u(x) ≥ u(x0) + p · (x− x0), for all x ∈ Ux0 } . Clearly for all x0 ∈ Ω we have ∂u(x0) ⊂ ∂lu(x0). Moreover we the following result. Lemma 3.3 ([14, Exercise 1]). If Ω is convex and u is convex on Ω, then ∂u(x) = ∂lu(x) for all x ∈ Ω. We recall that for a family of sets Ak lim sup k Ak = ∩n ∪k≥n Ak. 26 G. AWANOU EJDE-2022/CONF/26 Lemma 3.4. Assume that uh → v uniformly on compact subsets of Ω, with v convex and continuous. Then for K ⊂ Ω compact and any sequence hk → 0 lim sup hk→0 ∂V uhk(K) ⊂ ∂v(K). Proof. Let p ∈ lim sup hk→0 ∂V uhk(K) = ∩n ∪k≥n ∂V uhk(K). Thus for each n, there exists kn and xkn ∈ K∩Zdhkn such that p ∈ ∂V uhkn (xkn). By an abuse notation, let xj denote a subsequence xknj of xkn converging to x0 ∈ K. We have xknj ∈ K ∩ Zdhknj and so with our abuse of notation xj ∈ K ∩ Zdhj . Let Bε(x0) denote the ball of center x0 and radius ε in the maximum norm. We choose ε > 0 such that Bε(x0) ⊂ Ω. Let z ∈ Bε/4(x0) and zhj ∈ Bε/4(x0) ∩ Zdhj such that zhj → z. We have for j sufficiently large ‖xj − x0‖ ≤ ε/8. With e = zhj − xj , xj + e = zhj while xj−e = 2xj−zhj ∈ Bε/4(x0) as ‖2xj−zhj−x0‖ = ‖2(xj−x0)+(x0−zhj )‖ ≤ ε/2. That is xj ± e ∈ Ω ∩ Zdhj . Since p ∈ ∂V uhj (xj) for all j, uhj (zhj ) ≥ uhj (xj) + p · (zhj − xj). (3.1) Next, note that |uhj (xj)− v(x0)| ≤ |uhj (xj)− v(xj)|+ |v(xj)− v(x0)|. By the convergence of xj to x0 and the uniform convergence of uh to v on K, we obtain uhj (xj) → v(x0) as hj → 0. Similarly uhj (z) → v(z) as hj → 0, using uhj (zhj )− v(z) = (uhj (zhj )− v(zhj )) + (v(zhj )− v(z)). Taking pointwise limits in (3.1), we obtain v(z) ≥ v(x0) + p · (z − x0) ∀z ∈ B ε 4 (x0). We conclude that p ∈ ∂lv(K), the image of K by the local subdifferential of v, and thus p ∈ ∂v(K) by Lemma 3.3, since v is convex and Ω convex. � Theorem 3.5. The limit convex function v given by Theorem 3.2 satisfies for K ⊂ Ω compact M [v](K) = ∫ K f(x)dx. Thus for any Borel set B, M [v](B) = ∫ B f(x)dx. Proof. It follows from Lemma 3.4 lim sup hk→0 MV [uhk ](K) ≤M [v](K). (3.2) By Theorem 3.2 M [v](K) ≤ ∫ K f(x)dx. But MV [uh](K) = ∑ x∈K h df(x). We conclude from (3.2) that lim sup hk→0 MV [uhk ](K) = ∫ K f(x)dx ≤M [v](K) ≤ ∫ K f(x)dx, from which the result follows. � Theorem 3.6. The solution uh of (2.4) converges uniformly on compact subsets to the Aleksandrov solution u of (1.1). EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 27 Proof. It follows from Theorems 3.2 and 3.5, that there is a subsequence which converges uniformly on compact subsets to a convex function v ∈ C(Ω) which solves (1.1). By unicity of the solution of the latter, the whole family must converge to u. � 3.2. Convergence to the viscosity solution. Again, we assume that V = Zd \ {0}. For a direct proof of convergence to the viscosity solution of (1.1), we recall the notion of monotonicity and consistency. We note that consistency was not used for the proof of convergence to the Aleksandrov solution. Since we have proven convergence to the Aleksandrov solution, and Aleksandrov solutions are equivalent to viscosity solutions with our assumptions, we obtain convergence to the viscosity solution as well. The purpose of this section is to indicate how one may exploit equicontinuity to give a different proof of convergence to the viscosity solution. The scheme (2.4) is said to be monotone if for zh and wh in Uh, zh(y) ≥ wh(y), y 6= x with zh(x) = wh(x), we have Mh[zh](x) ≥Mh[wh](x). We say that the scheme (2.4) is consistent if for all C2 convex functions φ, a sequence xh → x ∈ Ω lim h→0 1 hd Mh[φ](xh) = detD2φ(x). We could only give a proof which is simple of a weaker form of consistency for the scheme (2.4). Let B(x, r) denote the ball of center x and radius r in the maximum norm and let x′h denote the unique mesh point in B(x, h/2). We say that the scheme is weakly consistent if for all strictly convex quadratic polynomials φ, we have lim h→0 1 hd Mh[φ](x′h) = detD2φ(x). Lemma 3.7. The scheme (2.4) is monotone. Proof. For zh and wh in Uh such that zh(y) ≥ wh(y), y 6= x with zh(x) = wh(x), we have from the definition of discrete normal mapping ∂hwh(x) ⊂ ∂hzh(x). Thus Mh[zh](x) ≥Mh[wh](x), i.e. the scheme (2.4) is monotone. � Lemma 3.8. The scheme (2.4) is weakly consistent. Proof. Let x ∈ Ω and φ a strictly convex quadratic polynomial. Let µ have density detD2φ, i.e. for each Borel set B, µ(B) = ∫ B detD2φ(x)dx. Given a sequence of Borel measures µn which converges weakly to µ, we are interested in the uniform convergence of µn(B) to µ(B) for B in a subset B of Borel sets. Let B consist of balls B(x0, r) of center x0 and radius r ≤ r0 for r0 > 0 fixed. Thus B consists of convex sets in a bounded set. By the Blaschke selection theorem, any sequence in B has a convergent subsequence, hence B is sequentially compact in the Hausdorff metric. By the same argument B ∩ B is compact for any closed ball B. Since detD2φ > 0, µ(∂B(x0, r)) = 0, i.e. B is a µ-continuity class using the terminology of [8]. By [8, Theorem 6 and example 6], B is a µ-uniformity class, i.e. if µn weakly converges to µ, then µn(B(x0, r))→ µ(B(x0, r)) uniformly in r. We recall a form of the Moore-Osgood theorem on exchanging limits. Consider the double sequence an,k with an,k → Bk uniformly in k as n→∞ and for each n, limk→∞ an,k = An. Then the double limits exist with lim n→∞ lim k→∞ an,k = lim k→∞ lim n→∞ an,k. 28 G. AWANOU EJDE-2022/CONF/26 We also recall that every continuity point of detD2φ is a Lebesgue point of detD2φ. That is, as detD2φ ∈ C(Ω) we have for x0 ∈ Ω lim r→0 1 |B(x0, r)| ∫ B(x0,r) detD2φ(x)dx = detD2φ(x0). Let us denote as well by φ the restriction of φ to Nh. By the weak convergence of Mhk [φ] to µ, we have for x ∈ Ω and uniformly in r lim k→∞ Mhk [φ](B(x, r)) = µ(B(x, r)). Therefore, lim r→0 1 |B(x, r)| lim k→∞ Mhk [φ](B(x, r)) = lim r→0 1 |B(x, r)| µ(B(x, r)) = detD2φ(x). By the Moore-Osgood theorem, we obtain lim k→∞ lim r→0 1 |B(x, r)| Mhk [φ](B(x, r)) = detD2φ(x). We now take r = hk/2 so that |B(x, r)| = hdk. Now, there is a unique mesh point x′hk in B(x, hk) and x′hk → x as k → ∞. Therefore Mhk [φ](B(x, hk/2)) = Mhk [φ](x′hk) and we obtain the (weak) consistency of the scheme, lim k→∞ 1 hdk Mhk [φ](x′hk) = detD2φ(x). � By the stability of the scheme (2.4), c.f. Theorem 2.13, the half-relaxed limits u∗(x) = lim sup y→x,h→0 uh(y) = lim δ→0 sup{uh(y) : y ∈ Ωh, |y − x| ≤ δ, 0 < h ≤ δ} u∗(x) = lim inf y→x,h→0 uh(y) = lim δ→0 inf{uh(y) : y ∈ Ωh, |y − x| ≤ δ, 0 < h ≤ δ}, are well defined. Our numerical experiments indicate that (2.4) is consistent. This is taken as an assumption in the following theorem. Rates of convergence of the Oliker-Prussner method, hence interior consistency, were given in [27]. Similar arguments could be followed for the discretization (2.4). But this would make this contribution too long. Theorem 3.9. Let f > 0 and f ∈ C(Ω). Assume that g can be extended to a convex function g̃ ∈ C(Ω). Under the assumption that (2.4) is consistent, the upper half-relaxed limit u∗ is a viscosity sub solution of detD2u(x) = f(x) and the lower half-relaxed limit u∗ is a viscosity super solution of detD2u(x) = f(x) at every point x of Ω. Moreover, solutions uh of (2.4) converge uniformly on compact subsets to the unique viscosity solution of (1.1). Proof. The result follows from the results of [5] and the stability, consistency and monotonicity of the scheme, combined with equicontinuity of the approximations. The part of the proof below which uses the consistency and monotonicity of the scheme follows [9]. The family uh is a family of discrete convex functions which is uniformly bounded and by (2.7) have Monge-Ampère masses uniformly bounded (using the terminology of [2]). Moreover uh = g on ∂Ωh for a convex function g ∈ C(Ω). By [2, Theorem 14], there is a subsequence uhk which converges uniformly on compact subsets to a EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 29 convex function v ∈ C(Ω) which solves v = g on ∂Ω. It follows from the definitions that v = u∗ = u∗ on Ω. At this point, it is not known yet that the limit convex function v is a viscosity solution of (1.1). We show that v = u∗ is a viscosity super solution of detD2u(x) = f(x) at every point x of Ω. Recall that v ∈ C(Ω). Let x0 ∈ Ω and φ be a strictly convex quadratic polynomial such that u∗ − φ has a local minimum at x0 with (u∗ − φ)(x0) = 0. Without loss of generality, we may assume that x0 is a strict local minimum. Let B0 denote a closed ball contained in Ω and containing x0 in its interior. We let xhl be a subsequence in B0 such that xhl → x0 with uhl(xl) → u∗(x0). Let x′l be defined by cl := (uhl − φ)(x′l) = min B0 uhl − φ. Since the sequence x′l is bounded, it converges to some x1 after possibly passing to a subsequence. Since (uhl − φ)(x′l) ≤ (uhl − φ)(xhl) we have (u∗ − φ)(x0) = lim l→∞ (uhl − φ)(xhl) ≥ lim inf l→∞ (uhl − φ)(x′l) ≥ (u∗ − φ)(x1). Since x0 is a strict minimizer of the difference u∗ − φ, we conclude that x0 = x1 and cl → 0 as l→∞. By definition uhl(x) ≥ φ(x) + cl, ∀x ∈ B0 ∩ Ωhl , with equality at x = x′l, and thus, by the monotonicity of the scheme 0 = 1 hdl Mhl [uhl ](x ′ l)− f(x′l) ≥ 1 hdl Mhl [φ+ cl](x ′ l)− f(x′l) = 1 hdl Mhl [φ](x′l)− f(x′l), which gives by the consistency of the scheme detD2φ(x0)− f(x0) ≤ 0. Similarly one shows that if φ is a strictly convex quadratic polynomial such that u∗ − φ has a local maximum at x0 with (u∗ − φ)(x0) = 0, we have detD2φ(x0) − f(x0) ≥ 0. It follows that v = u∗ = u∗ on Ω is a viscosity solution of detD2u = f . By the comparison principle Theorem 2.7, v is equal to the unique viscosity solution of (1.1). Thus all subsequences uhk converge uniformly on compact subsets to the same limit. This concludes the proof. � Several discrete Monge-Ampère equations, e.g. [6, 22], can be written as Mh[uh](x) = hdf(x), x ∈ Ωh, for some operator Mh which satisfies Mh[uh] ≤ CMh[uh]. For f ∈ C(Ω), ∑ x∈Ωh hdf(x)→ ∫ Ω f(x)dx and thus∑ x∈Ωh Mh[uh](x) ≤ C ∑ x∈Ωh Mh[uh](x) = C ∑ x∈Ωh hdf(x) ≤ A, for a constant A independent of h. Thus (2.7) holds for schemes such as the ones in [6, 22] and convergence to the viscosity solution on convex domains not necessarily strictly convex can be proven as for Theorem 3.9. 30 G. AWANOU EJDE-2022/CONF/26 3.3. Remarks on the case of a sum of Dirac masses for the right-hand side. Consider the problem detD2u = N∑ l=1 clδdl in Ω u = g on ∂Ω, (3.3) where dl is a mesh point, cl a real number, δdl the Dirac mass at dl and N is the number of Dirac masses. Here, we assume that the parameter h is chosen so that dl is a mesh point. For example, we may restrict h to take the form 1/2j for a positive integer j when Ω is a cube. The corresponding discrete problem is MV [uh](x) = fh(x), x ∈ Ωh uh(x) = g(x), x ∈ ∂Ωh, (3.4) where fh is a mesh function which equals 0 at all mesh points, except dl where it takes values cl for l = 1, . . . , N . Discrete solutions have Monge-Ampère masses uniformly bounded as ∑ x∈Ωh fh(x) is uniformly bounded. Our convergence analysis to the Aleksandrov solution holds in this case as well. This does not appear to be an effective method in the case of Dirac masses. The method we discussed is a variant of the Oliker-Prussner method [28]. For the latter (3.3) requires the masses cl to be non zero. But with our approximations fh, fh(x) = 0 in parts of the computational domain Ωh. A method which is solely based on the interpretation of f(x) as a continuous function should handle better the case where fh(x) = 0 in parts of the computational domain. The numerical method discussed in [7] can be interpreted as a variant of (3.4) with numerical integration for the computation of the discrete subdifferential at points dl and the use of a different scheme elsewhere. 4. Numerical experiments The computational domain is the unit square [0, 1]2. The initial guess for the iterations was taken as a shifted quadratic x2 + y2 − 2. The discrete nonlinear system was solved with a damped Newton’s method [22]. Let δ, ρ ∈ (0, 1). Given an initial guess u0 h to the nonlinear equations G(uh) = 0, set k = 0. If G(ukh) = 0, stop. Put pk(τ) = ukh − τG′(ukh)−1G(ukh) and let ik be the smallest non-negative integer i such that ‖G(pk(ρi))‖ ≤ (1− δρi)‖G(vkh)‖. We set uk+1 h = pk(ρik). In the experiments, we take δ = ρ = 1. Errors are given in the maximal norm. We used a 1.4 GHz Quad-Core Intel Core i5 MacBook Pro and the implementation was in Matlab. Table 1. Smooth solution u(x, y) = e(x2+y2)/2 with g(x, y) = e(x2+y2)/2 and f(x, y) = (1 + x2 + y2)ex 2+y2 . h 1/24 1/25 1/26 1/27 1/28 1/29 Error 3.51 10−4 8.81 10−5 2.20 10−5 5.51 10−6 1.38 10−6 3.45 10−7 Rate 1.99 1.99 1.99 1.99 2 Time 7.97 10−2 2.01 10−1 1.01 10−0 4.27 10−0 2.02 10+1 9.75 10+1 EJDE-2018/CONF/26 DISCRETE ALEKSANDROV SOLUTIONS 31 Table 2. Non smooth solution u(x, y) = − √ 2− x2 − y2 with g(x, y) = − √ 2− x2 − y2 and f(x, y) = 2/(2− x2 − y2)2. h 1/24 1/25 1/26 1/27 1/28 1/29 Error 6.89 10−4 2.36 10−4 8.21 10−5 2.88 10−5 1.01 10−5 3.58 10−6 Rate 1.55 1.52 1.51 1.50 1.50 Time 7.07 10−2 1.94 10−1 2.17 10−0 1.94 10+1 1.84 10+1 1.91 10+3 For the smooth solution, the number of Newton iterations was about 40, while for the non smooth solution it took hundreds of iterations for fine resolutions. Acknowledgements. The author thanks the anonymous referees for valuable comments. The author was partially supported by NSF grants DMS-1319640 and DMS-1720276. The author would like to thank the Isaac Newton Institute for Math- ematical Sciences, Cambridge, for support and hospitality during the programme “Geometry, compatibility and structure preservation in computational differential equations” where part of this work was undertaken. Part of this work was supported by EPSRC grant no EP/K032208/1. References [1] Eugene L. Allgower, Phillip H. Schmidt; Computing volumes of polyhedra, Math. Comp. 46 (1986), no. 173, 171–174. [2] Gerard Awanou; On the weak convergence of Monge-Ampère measures for discrete convex mesh functions, Acta Appl. Math. 172 (2021), Paper No. 6, 31. [3] Gerard Awanou, Romeo Awi; Convergence of finite difference schemes to the Aleksandrov solution of the Monge-Ampère equation, Acta Applicandae Mathematicae 144 (2016), no. 1, 87–98. [4] Ilya J. Bakelman; Convex analysis and nonlinear geometric elliptic equations, Springer- Verlag, Berlin, 1994, With an obituary for the author by William Rundell, Edited by Steven D. Taliaferro. [5] G. Barles, P. E. Souganidis; Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), no. 3, 271–283. [6] Jean-David Benamou, Francis Collino, Jean-Marie Mirebeau; Monotone and consistent dis- cretization of the Monge-Ampère operator, Math. Comp. 85 (2016), no. 302, 2743–2775. [7] Jean-David Benamou, Brittany D. Froese; Weak Monge-Ampère solutions of the semi- discrete optimal transportation problem, Topological optimization and optimal transport, Radon Ser. Comput. Appl. Math., vol. 17, De Gruyter, Berlin, 2017, pp. 175–203. MR 3729377 [8] Patrick Billingsley, Flemming Topsøe; Uniformity in weak convergence, Z. Wahrschein- lichkeitstheorie und Verw. Gebiete 7 (1967), 1–16. [9] Bruno Bouchard, Romuald Elie, Nizar Touzi; Discrete-time approximation of BSDEs and probabilistic schemes for fully nonlinear PDEs, Advanced financial modelling, Radon Ser. Comput. Appl. Math., vol. 8, Walter de Gruyter, Berlin, 2009, pp. 91–124. [10] Jean-Paul Daniel; Quelques résultats d’approximation et de régularité pour des équations elliptiques et paraboliques non-linéaires, Ph.D. thesis, Paris 6, 2014. [11] Lawrence C. Evans, Ronald F. Gariepy; Measure theory and fine properties of functions, Studies in Advanced Mathematics, CRC Press, Boca Raton, FL, 1992. [12] Xiaobing Feng, Roland Glowinski, Michael Neilan; Recent Developments in Numerical Meth- ods for Fully Nonlinear Second Order Partial Differential Equations, SIAM Rev. 55 (2013), no. 2, 205–267. [13] Xiaobing Feng, Max Jensen; Convergent semi-Lagrangian methods for the Monge-Ampère equation on unstructured grids, SIAM J. Numer. Anal. 55 (2017), no. 2, 691–712. 32 G. AWANOU EJDE-2022/CONF/26 [14] Cristian E. Gutiérrez; KIT Lectures, April 2013. Exercises on the Monge-Ampère equation, https://math.temple.edu/˜gutierre/. [15] Cristian E. Gutiérrez; The Monge-Ampère equation, Progress in Nonlinear Differential Equa- tions and their Applications, 44, Birkhäuser Boston Inc., Boston, MA, 2001. [16] David Hartenstine; The Dirichlet problem for the Monge-Ampère equation in convex (but not strictly convex) domains, Electron. J. Differential Equations (2006), No. 138, 9 pp. (elec- tronic). [17] H. Ishii, P.-L. Lions; Viscosity solutions of fully nonlinear second-order elliptic partial dif- ferential equations, J. Differential Equations 83 (1990), no. 1, 26–78. [18] Max Jensen; Numerical solution of the simple Monge-Ampère equation with non-convex Dirichlet data on non-convex domains, arXiv preprint arXiv:1705.04653 (2017). [19] Hung-Ju Kuo, Neil S. Trudinger; A note on the discrete Aleksandrov-Bakelman maximum principle, Proceedings of 1999 International Conference on Nonlinear Analysis (Taipei), vol. 4, 2000, pp. 55–64. [20] Gregory F. Lawler; Weak convergence of a random walk in a random environment, Comm. Math. Phys. 87 (1982/83), no. 1, 81–87. [21] P.-L. Lions; Two remarks on Monge-Ampère equations, Ann. Mat. Pura Appl. (4) 142 (1985), 263–275 (1986). [22] Jean-Marie Mirebeau; Discretization of the 3D Monge-Ampère operator, between wide sten- cils and power diagrams, ESAIM Math. Model. Numer. Anal. 49 (2015), no. 5, 1511–1523. [23] Michael Neilan; Abner J. Salgado, and Wujun Zhang, Numerical analysis of strongly nonlin- ear PDEs, Acta Numer. 26 (2017), 137–303. [24] Michael Neilan; The Monge-Ampére equation, Geometric partial differential equations. Part I, Handb. Numer. Anal., vol. 21, Elsevier/North-Holland, Amsterdam, [2020] ©2020, pp. 105– 219. [25] R. H. Nochetto, D. Ntogkas, W. Zhang; Two-scale method for the Monge-Ampère equation: convergence to the viscosity solution, Math. Comp. 88 (2019), no. 316, 637–664. [26] Ricardo H. Nochetto, Wujun Zhang; Discrete ABP Estimate and Convergence Rates for Linear Elliptic Equations in Non-divergence Form, Found. Comput. Math. 18 (2018), no. 3, 537–593. [27] Ricardo H. Nochetto, Wujun Zhang; Pointwise rates of convergence for the Oliker-Prussner method for the Monge-Ampère equation, Numer. Math. 141 (2019), no. 1, 253–288. [28] V. I. Oliker, L. D. Prussner; On the numerical solution of the equation (∂2z/∂x2)(∂2z/∂y2)− ((∂2z/∂x∂y))2 = f and its discretizations. I, Numer. Math. 54 (1988), no. 3, 271–293. [29] Rolf Schneider; Convex bodies: the Brunn-Minkowski theory, expanded ed., Encyclopedia of Mathematics and its Applications, vol. 151, Cambridge University Press, Cambridge, 2014. [30] Truyen van Nguyen; On Monge-Ampère type equations arising in optimal transportation problems, Ph.D. Dissertation, Temple University, Temple, USA, 2005. [31] Eberhard Zeidler; Nonlinear functional analysis and its applications. II/B, Springer-Verlag, New York, 1990, Nonlinear monotone operators, Translated from the German by the author and Leo F. Boron. Gerard Awanou Department of Mathematics, Statistics, and Computer Science, M/C 249. University of Illinois at Chicago, Chicago, IL 60607-7045, USA Email address: awanou@uic.edu 1. Introduction 2. Preliminaries 2.1. Aleksandrov solutions 2.2. Discretizations of the normal mapping 2.3. Viscosity solutions of the elliptic Monge-Ampère equation 2.4. The numerical scheme 3. Convergence analysis 3.1. Convergence to the Aleksandrov solution 3.2. Convergence to the viscosity solution 3.3. Remarks on the case of a sum of Dirac masses for the right-hand side 4. Numerical experiments Acknowledgements References