                              Revised Version
                                March 1999

Minimally supported error representations and approximation by the constants

Shayne Waldron

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand e–mail: waldron@math.auckland.ac.nz (http:www.math.auckland.ac.nz/˜ waldron)

ABSTRACT

Distribution theory is used to construct minimally supported Peano kernel type representations for linear functionals such as the error in multivariate Hermite interpolation. The simplest case is that of representing the error in approximation to f by the constant polynomial f(a) in terms of integrals of the first order derivatives of f. This is discussed in detail. Here it is shown that suprisingly there exist many representations which are not minimally supported, and involve the integration of first order derivatives over multidimensional regions. The distance of smooth functions from the constants in the uniform norm is estimated using our representations for the errror.

Key Words: minimally supported error representation, distribution theory, intrinsic (geodesic) metric, Friedrichs’ inequality, Poincaré inequality, Sobolev’s inequality

AMS (MOS) Subject Classifications: primary 41A10, 41A44, 41A80, secondary 41A05, 65N30

1. Introduction

The motivation of this paper is the following general problem. Suppose that P is a linear projector onto Π_{k} := Π_{k}(IR^{d}) (the polynomials of degree ≤ k in IR^{d}) such as Lagrange interpolation at some suitable set of points in IR^{d}. Let D^{k+1}f denote the (k+1)th derivative of f, which can be represented by

(D^{α}f)_{|α|=k+1}

the sequence of (k + 1)–order partial derivatives of f. Since the kernel of D^{k+1} is Π_{k}, it is possible to express the error in approximation by P at x ∈ IR^{d} in the form

f(x) − P f(x) = R_{x}(D^{k+1}f),  (1.1)

for sufficiently smooth f, where R_{x} is some linear functional defined on the (k + 1)th derivatives. This can be viewed as a nonconstructive multivariate version of Peano’s kernel theorem. Recently there has been interest in obtaining explicit representations of R_{x}(D^{k+1}f) as a sum of integrals of (k + 1)th derivatives of f over various regions in IR^{d} from which estimates of the error f −P f in terms of some appropriate norm on D^{k+1}f can be obtained, and even more general forms of this problem (see, e.g., de Boor [2], Waldron [12]).

This paper uses distribution theory to analyse representations like (1.1), with particular emphasis on the simplest case when k = 0

P f := f(a), a ∈ IR^{d}.

In Section 2, the ‘support’ of a representation of R_{x}(D^{k+1}f) is defined, and a family of representations which are ‘minimally supported’ is constructed. In Section 3, another family of minimally supported error representations for the case P f := f(a) is given, and these are used to show that there exist representations which involve integrals of first order derivatives over a wide variety of multidimensional regions. This striking example shows that even in the most simple cases when one extends the Peano kernel theory from the univariate to multivariate setting there is a large choice in the derivatives that appear and the regions over which they are integrated. In Section 4, these representations are used to estimate the L_{∞}–distance of smooth functions from the constants, and L_{p}–estimates are discussed.

2. Minimally supported error representations

Some basic results and notation from distribution theory will be used (see, e.g., Barros–Neto [3]). Suppose that the error in approximation to f by P f can be expressed as

f(x) − P f(x) = ∑_{i} R_{i}(D^{k+1}f),  ∀f ∈ C^{k+1}(IR^{d}),  (2.1)

where {R_{i}} is a finite collection of linear functionals for which R_{i} ∘ D^{k+1} is continuous on C^{k+1}(IR^{d}), i.e., in conventional distribution terminology R_{i} ∘ D^{k+1} is a compactly supported distribution of order k + 1, or, for short, R_{i} ∘ D^{k+1} ∈ E′_{k+1}(IR^{d}). The support of R_{i} is defined to be the support of the distribution R_{i} ∘ D^{k+1}, i.e, the compact set

supp R_{i} := supp(R_{i} ∘ D^{k+1}),

and the support of the representation (2.1) is the compact set

K := ⋃_{i} supp R_{i} := ⋃_{i} supp(R_{i} ∘ D^{k+1}).  (2.2)

A representation (2.1) with support K is said to be minimally supported if there is no other representation with support properly contained within K.

Consider first the case

f(x) − f(a) = ∑_{i} R_{i}(Df),  ∀f ∈ C^{1}(IR^{d}).  (2.3)

If a distribution is expressed as a finite sum

λ = ∑_{i} λ_{i}, λ_{i} ∈ D′(IR^{d}),

then it can easily be shown that

supp λ ⊂ ⋃_{i} supp λ_{i}.  (2.4)

In particular, the support of a representation of the form (2.3) must contain {a, x}. In addition, it can be shown that this support must be connected, and so the representation

f(x) − f(a) = ∫_{0}^{1} D_{x−a}f(a + t(x − a)) dt,  (2.5)

involving integration of D_{x−a}f over the line segment joining a and x is minimally supported on this line segment. We now prove a general form of this result. The differential operator induced by q ∈ Π_{k} is written q(D), and the derivative of f in the direction ξ ∈ IR^{d} as D_{ξ}f.

Theorem 2.6 (minimally supported representations). Let λ ∈ D′(IR^{d}) be a distribution of the form

λ(f) := ∑_{j=1}^{m} q_{j}(D)f(a_{j}),  ∀f ∈ C^{k+1}(IR^{d}),  (2.7)

where 0 ≠ q_{j} ∈ Π_{k}, and a_{j} ∈ IR^{d} are distinct points. If λ vanishes on Π_{k}, then there exist a finite number of linear maps R_{i} with R_{i} ∘ D^{k+1} ∈ E′_{k+1}(IR^{d}), such that

λ(f) = ∑_{i} R_{i}(D^{k+1}f),  ∀f ∈ C^{k+1}(IR^{d}).  (2.8)

The support of any representation of the form (2.8), i.e., the compact set

K := ⋃_{i} supp(R_{i} ∘ D^{k+1}),  (2.9)

contains the points {a_{j}}. Suppose in addition that no (notrivial) proper subsum of (2.7) vanishes for all f ∈ Π_{k}. Then the support K is connected, and for any c ∈ IR^{d}, it is possible to choose R_{i} so that K is the union of the line segments from c to the a_{j}, thereby obtaining a minimally supported representation (2.8).

Proof: Properties. If a representation (2.8) exists, then it follows from (2.4) that

supp λ = {a_{j}} ⊂ K.

Suppose that K is not connected, and let K_{1} be the component of K containing a_{1}. Then the condition that no subsum of (2.7) vanishes for all f ∈ Π_{k} implies that there exists a polynomial p ∈ Π_{k} with

∑_{a_{j}∈K_{1}} q_{j}(D)p(a_{j}) ≠ 0.  (2.10)

Let f ∈ D(IR^{d}) be a function which is equal to p on a small neighbourhood of K_{1} and is zero on a small neighbourhood of the other components of K. Then D^{k+1}f = 0 on a neighbourhood of K, which implies

∑_{i} R_{i}(D^{k+1}f) = 0,

whilst

λ(f) = ∑_{a_{j}∈K_{1}} q_{j}(D)f(a_{j}) + ∑_{a_{j}∈K\K_{1}} q_{j}(D)f(a_{j}) = ∑_{a_{j}∈K_{1}} q_{j}(D)p(a_{j}) ≠ 0,

which contradicts (2.8). Hence K must be connected.

Existence. We now construct minimally supported representations (2.8). This is done by using a formula of the form (2.8) for the error at x ∈ IR^{d} in approximation by T_{k,c} (the operator of Taylor interpolation from Π_{k} at c ∈ IR^{d}) to convert (2.7) into such a representation. For q ∈ Π_{ℓ}^{0}(IR^{d}), 0 ≤ ℓ ≤ k (the homogeneous polynomials of degree ℓ)

q(D)(T_{k,c}f) = T_{k−l,c}(q(D)f),

and so by the univariate integral remainder theorem for Taylor interpolation

q(D)(f − T_{k,c}f)(x) = \frac{1}{k!} ∫_{0}^{1}(1 − t)^{k}(D_{x−c}^{k+1−ℓ}q(D)f)(c + t(x − c)) dt =: R(D^{k+1}f).

(2.11)

It is easily verified that R ∘ D^{k+1} ∈ E′_{k+1}(IR^{d}), and for q ≠ 0 the support of R is the line segment from x to c. Express each q_{j} as a sum of its homogeneous terms, i.e.,

q_{j} = ∑_{ℓ=0}^{k} q_{j}^{ℓ},  q_{j}^{ℓ} ∈ Π_{ℓ}^{0}(IR^{d}).  (2.12)

Since λ ∈ E′_{k+1}(IR^{d}) and vanishes on Π_{k}, (2.7) can be expanded using (2.11) and (2.12) as follows

\begin{aligned}λ(f) & = λ(f − T_{k,c}f) = ∑_{j=1}^{m} ∑_{ℓ=0}^{k} q_{j}^{ℓ}(D)(f − T_{k,c}f)(a_{j}) \\ & = \frac{1}{k!} ∑_{j=1}^{m} ∑_{ℓ=0}^{k} ∫_{0}^{1}(1 − t)^{k}(D_{a_{j}−c}^{k+1−ℓ}q_{j}^{ℓ}(D)f)(c + t(a_{j} − c)) dt, \end{aligned}  (2.13)

which is a representation of the form (2.8). The support of the representation (2.13) is the union of the line segments from c to the a_{j}. No proper subset of this support which contains {a_{j}} is connected, and so (2.13) is a minimally supported representation.

Theorem 2.6 is a multivariate extension of the Peano kernel theorem for functionals of the form (2.7). Similar extensions for more general linear functionals can be obtained along the same lines. This result applies to a number of linear functionals of practical interest, such as the pointwise error in multivariate Hermite interpolation from Π_{k}(IR^{d}). Here is a typical example.

Suppose that

λ(f) := f(x) − L_{Θ}f(x) = f(x) − ∑_{v∈Θ} ℓ_{v}(x)f(v),  x ∉ Θ  (2.14)

is the error in linear interpolation (interpolation by linear polynomials) at the points Θ ⊂ IR^{d}, where ℓ_{v} are the Lagrange polynomials (which are the barycentric coordinates). This satisfies the conditions of Theorem 2.6 with Π_{k} = Π_{1}. Taking c = x in the expansion (2.13) gives the multipoint Taylor formula of Ciarlet and Wagschal [4:Th.2], while the choice c = w ∈ Θ gives (in the notation used in [12])

f(x) − L_{Θ}f(x) = ∫_{[w,w,x]} D_{x−w}^{2}f − ∑_{{v∈Θ \atop v≠w}} ℓ_{v}(x) ∫_{[w,w,v]} D_{v−w}^{2}f,  (2.15)

which is a new formula. There also exist representations of (2.14) which are not minimally supported, see, e.g., Gregory [9] or Waldron [13]. Simpler examples of representations which are not minimally supported are examined in the next section.

c = x u  v w  c = w x  c  x

Fig. 2.1. The support K of minimally supported error formulæ for linear interpolation at the vertices of a triangle (shaded) given by (2.13). First the multipoint Taylor formula, followed by formula (2.15), and an example where c ∉ {Θ, x}.

3. Error representations for approximation by the constants

In this section we consider error representations of the form (2.3) for approximation by the constant P f := f(a), i.e., the linear functional

λ(f) := f(x) − f(a), x ≠ a.

First we give a family of minimally supported representations for λ which contains those given by (the proof of) Theorem 2.6 as particular cases. These representations are then “averaged” to obtain ones which are supported on a variety of multidimensional regions. This example illustrates a basic difficulty in developing a constructive and useful multivariate Peano kernel theory, namely deciding

• Which (k + 1)–order derivatives should appear in (2.1)?

• What regions should they be integrated over?

when it is known that many such formulæ exist.

A path in IR^{d} is a continuous, piecewise differentiable map γ : [0, 1] → IR^{d}. Let T denote the unit tangent vector along the curve γ, i.e.,

T := \frac{Dγ}{∥Dγ∥},

length(γ) the length of γ, and ds the arc length element. A restatement of the fundamental theorem of calculus shows that there is a representation (2.3) which is supported on

K = γ^{∗} := γ([0, 1]),

where γ is any path from a to x, i.e., γ(0) = a, γ(1) = x. Here ∇f is the gradient of f.

Lemma 3.1. Let γ : [0, 1] → IR^{d} be a path from a to x, then

λ(f) := f(x) − f(a) = ∫_{γ} D_{T}f ds,  ∀f ∈ C^{1}(γ^{∗}),  (3.2)

and in particular,

|f(x) − f(a)| ≤ (max_{γ^{∗}} ∥∇f∥) length(γ).  (3.3)

Proof: Let g := f ∘ γ, then by the fundamental theorem of calculus

f(x) − f(a) = g(1) − g(0) = ∫_{0}^{1} Dg = ∫_{0}^{1}(D_{T}f ∘ γ)∥Dγ∥ = ∫_{γ} D_{T}f ds,

and hence

|f(x) − f(a)| ≤ ∫_{γ} |D_{T}f| ds ≤ ∫_{γ} ∥∇f∥ ds ≤ (max_{γ^{∗}} ∥∇f∥) length(γ).

Thus, if γ has no self intersections, then Theorem 2.6 implies that (3.2) provides a minimally supported error representation. A number of these representations are well– known, and have been used in numerical analysis. For example, if γ is the line segment from a to x, then (3.2) is the univariate Taylor error formula (2.5) for approximation by a constant, while if γ is the path in IR^{2} consisting of the line segment from (a, b) to (x, b) followed the line segment from (x, b) to (x, y), then (3.2) becomes

f(x, y) − f(a, b) = ∫_{a}^{x} D_{1}f(s, b) ds + ∫_{b}^{y} D_{2}f(x, t) dt.  (3.4)

The formula (3.4) is an example of the Taylor formula given by Sard [11:p163] for certain spaces, denoted by B_{p,q}, of functions defined on some rectangle I in IR^{2}. This example is for the space B_{0,1} = B_{0,1}(I; a, b), where (a, b) ∈ I. If γ^{∗} is the union of the line segments from c to a and x, then (3.2) is the representation (2.13).

a  x  a  x  a  x  a  x

Fig. 3.1. The support K = γ^{∗} of some error representations given by (3.2). The first is (2.5) the ‘univariate Taylor formula for approximation by a constant’, and the second is (3.4), which was used by Sard. All but the last (which has a self intersection) are minimal supports.

Given the error formulæ (3.2) of Lemma 3.1, it is not difficult to imagine taking an average (or even weighted average) of some family of them to obtain an error representation (2.3) which is supported on some multidimensional region. We illustrate this idea in the bivariate case with the construction of a representation for the error f(x) − f(a) in terms of Df which is supported on the rectangle aligned in the coordinate directions with opposite vertices given by a and x. To the author at least, the existence of such a formula is suprising. In principle, an error representation supported on any compact path–connected set containing a and x could be obtained in this way.

For simplicity, suppose that a = (0, 0) and (x, y) is in the first quadrant. Let γ_{λ} be the path given by the line segments from (0, 0) to ξ_{λ} := ((1 − λ)x, λy) and ξ_{λ} to (x, y). Taking the average over λ_{1} ≤ λ ≤ λ_{2} of the corresponding representation (3.2) gives

f(x, y) − f(0, 0) = \frac{1}{λ_{2} − λ_{1}} ∫_{λ_{1}}^{λ_{2}} ∫_{γ_{λ}} D_{T}f ds dλ,  (3.5)

which is supported on Q the quadrilateral with vertices (0, 0), ξ_{λ_{1}}, (x, y), ξ_{λ_{2}} (ordered in the positive angular direction).

(0, 0) γ_{1} γ_{\frac{1}{2}} γ_{\frac{1}{4}} γ_{0} (x, y)  ξ_{λ_{2}}  ξ_{λ_{1}}  T_{1}  T_{2}

Fig. 4.1. The family of curves γ_{λ} (λ = 0, 1/4, 1/2, 1), followed by the support of the formula (3.5) for 0 < λ_{1} < λ_{2} < 1/2, and the support Q = T_{1} ⋃ T_{2} of the formula obtained by taking λ_{1} = 0, λ_{2} = 1.

If λ_{1} = 0, λ_{2} = 1, then Q is the rectangle with vertices (0, 0), (x, 0), (x, y), (0, y). For this case we now compute the weight functions w_{1}, w_{2} that occur when (3.5) is rewritten in the form

f(x, y) − f(0, 0) = ∫_{Q} w_{1} D_{1}f + ∫_{Q} w_{2} D_{2}f.  (3.6)

Since

f(x, y) − f(0, 0) = {f(x, y) − f(ξ_{λ})} + {f(ξ_{λ}) − f(0, 0)},

by using (2.5), (3.5) can be rewritten as

f(x, y) − f(0, 0) = ∫_{0}^{1} ∫_{0}^{1}((1 − λ)xD_{1}f(t(1 − λ)x, tλy) + λyD_{2}f(t(1 − λ)x, tλy)) dt dλ
+ ∫_{0}^{1} ∫_{0}^{1}(λxD_{1}f((1 − λ)x + tλx, λy + t(1 − λ)y)
+ (1 − λ)yD_{2}f((1 − λ)x + tλx, λy + t(1 − λ)y)) dt dλ.
(3.7)

The first of these iterated integrals is of Df over the triangle T_{1} with vertices (0, 0), (x, 0), (0, y). In this integral make the change of variables:

u = t(1 − λ)x, v = tλy,

to obtain

∫_{T_{1}} \frac{xyu}{(yu + xv)^{2}} D_{1}f(u, v) + \frac{xyv}{(yu + xv)^{2}} D_{2}f(u, v) du dv.

Using a symmetry argument, this can be used to express the second iterated integral in (3.7) as an integral over T_{2} the triangle with vertices (x, 0), (x, y), (0, y). In this way, we obtain that the weight functions w_{1}, w_{2} occuring in (3.6) are given by

w_{1}(u, v) = xy \{ \begin{matrix}\frac{u}{(yu+xv)^{2}} , & (u, v) ∈ T_{1} \\ \frac{x−u}{(y(x−u)+x(v−y))^{2}} , & (u, v) ∈ T_{2} \end{matrix}

and

w_{2}(u, v) = xy \{ \begin{matrix}\frac{v}{(yu+xv)^{2}} , & (u, v) ∈ T_{1} \\ \frac{y−v}{(y(x−u)+x(v−y))^{2}} , & (u, v) ∈ T_{2}. \end{matrix}

These integrable functions w_{i} : Q → IR are supported on Q and continuous at every point except (0, 0) and (x, y), near which they are unbounded.

4. The distance of smooth functions from the constants

In this section we use the (minimally supported) error formulæ of Section 3 to obtain estimates of the L_{∞}(Ω)–distance of smooth functions from Π_{0} (the constants). In contrast to previous results, these estimates do not require special conditions on the domain Ω, such as being convex or starshaped.

Specifically, we are interested in the best constant C_{Ω} in the estimate

dist_{L_{∞}(Ω)}(f, Π_{0}) ≤ C_{Ω} ∥Df∥_{L_{∞}(Ω)},  (4.1)

for all sufficiently smooth f, such as f from W_{1}^{∞}(Ω), C^{1}(Ω), or C^{1}(Ω̄). This turns out to be an involved question, with C_{Ω} depending not only on the geometry of the domain Ω, but also, in some cases, on the definition of sufficiently smooth used. We will deal primarily with the most technical and interesting case when f ∈ W_{1}^{∞}(Ω).

Suppose that Ω ⊂ IR^{d} is a domain, i.e., is open and path–connected. Our estimates of C_{Ω} in (4.1) will be described in terms of d_{Ω} the intrisic (or geodesic) metric on Ω,

d_{Ω}(a, x) := the infimum of the lengths of the paths from a to x that lie in Ω.

If the line segment from a to x lies in Ω̄, then d_{Ω}(a, x) = ∥x − a∥, otherwise d_{Ω}(a, x) > ∥x − a∥. We define an “intrinsic” radius of Ω about a, which measures the length of the longest path needed to connect a with a point in Ω, as follows

r(a, Ω) := sup_{x∈Ω} d_{Ω}(a, x)  (4.2)

(which may be infinite, even when Ω is bounded), and let

r(Ω) := inf_{a∈Ω} r(a, Ω) = inf_{x∈Ω} sup_{y∈Ω} d_{Ω}(x, y).  (4.3)

It follows from the triangle inequality that

r(Ω) ≤ sup_{x,y∈Ω} d_{Ω}(x, y) ≤ 2r(Ω).  (4.4)

Let diam Ω be the (Euclidean) diameter of Ω. It can easily be shown that

\frac{1}{2} diam Ω ≤ r(Ω) ≤ r(a, Ω),  (4.5)

and that if Ω is starshaped with respect to a point a, then

r(Ω) ≤ r(a, Ω) ≤ diam Ω.  (4.6)

2r(Ω) 2r(Ω) x d_{Ω}(a, x) a

Fig 4.2 The distance d_{Ω}(a, x) for a domain Ω (shaded), followed by the distance 2r(Ω) for a convex and nonconvex bounded domain Ω.

For any domain Ω, the Sobolev space W_{∞}^{1}(Ω) consists of the bounded locally Lipschitz functions on Ω, i.e., those bounded functions f satisfying an inequality

|f(x) − f(y)| ≤ M ∥x − y∥,  M < ∞,  (4.7)

for all points x, y for which [x, y] the line segment from x to y is contained in Ω. It is easily shown that the seminorm on W_{∞}^{1}(Ω) defined by

∥Df∥_{L_{∞}(Ω)} := the L_{∞}(Ω)–norm of ∥∇f∥  (4.8)

coincides with the smallest constant M in the inequality (4.7), i.e.,

M := sup_{{[x,y]⊂Ω \atop x≠y}} \frac{|f(x) − f(y)|}{∥x − y∥}.  (4.9)

We are now able to give the main result of this section.

Theorem 4.10 (approximation by constants). Suppose that Ω ⊂ IR^{d} is open and path–connected. Then there exists a finite constant C_{Ω} for which

dist_{L_{∞}(Ω)}(f, Π_{0}) := inf_{c∈Π_{0}} ∥f − c∥_{L_{∞}(Ω)} ≤ C_{Ω} ∥Df∥_{L_{∞}(Ω)},  ∀f ∈ W_{∞}^{1}(Ω), (4.11)

if and only if

sup_{x,y∈Ω} d_{Ω}(x, y) < ∞.  (4.12)

The best such constant satisfies

\frac{1}{4} diam Ω ≤ \frac{1}{2}r(Ω) ≤ \frac{1}{2}r(a, Ω) ≤ C_{Ω} ≤ r(Ω),  ∀a ∈ Ω.  (4.13)

For d > 1, the quotient C_{Ω}/ diam Ω can be arbitrarily large for a domain satisfying (4.12). However, for Ω convex

C_{Ω} = \frac{1}{2} diam Ω,  (4.14)

and for Ω starshaped

\frac{1}{4} diam Ω ≤ C_{Ω} ≤ diam Ω.  (4.15)

Proof: First, we prove the lower bound on C_{Ω}, and the necessity of the condition (4.12). Fix a ∈ Ω. Let

f := d_{Ω}(a, ·),  (4.16)

which is bounded if and only if r(a, Ω) < ∞, and (by the triangle inequality) satisfies

M := sup_{{[x,y]⊂Ω \atop x≠y}} \frac{|f(x) − f(y)|}{∥x − y∥} = 1.  (4.17)

Thus, if (4.12) holds, then f ∈ W_{∞}^{1}(Ω) and satisfies

inf_{Ω} f = f(a) = 0,  sup_{Ω} f = r(a, Ω) < ∞,  ∥Df∥_{L_{∞}(Ω)} = 1,

so that

\frac{dist_{L_{∞}(Ω)}(f, Π_{0})}{∥Df∥_{L_{∞}(Ω)}} = \frac{1}{2}r(a, Ω) ≤ C_{Ω},

which together with (4.5) gives the lower bounds of (4.13). Suppose that (4.12) does not hold, i.e.,

sup_{x,y∈Ω} d_{Ω}(x, y) = ∞,  (4.18)

then f may be unbounded, and so not belong to W_{∞}^{1}(Ω). In this case, we slightly modify f so that it belongs to W_{∞}^{1}(Ω), and thereby show that no finite constant can exist in (4.11). By (4.18), we can choose a, x ∈ Ω for which

d_{Ω}(a, x) ≥ N,

for any N > 0. Let f be defined by

f(y) := min{d_{Ω}(a, y), N}.

This f satisfies (4.17), and

inf_{Ω} f = f(a) = 0,  sup_{Ω} f = N,  ∥Df∥_{L_{∞}(Ω)} = 1,

so it belongs to W_{∞}^{1}(Ω), and we obtain

\frac{dist_{L_{∞}(Ω)}(f, Π_{0})}{∥Df∥_{L_{∞}(Ω)}} = \frac{1}{2}N ≤ C_{Ω}.

Hence, when (4.12) fails there exists no finite constant in (4.11).

Next, we prove the upper bound on C_{Ω} by using (3.3) for f ∈ W_{∞}^{1}(Ω). Suppose that (4.12) holds, and so, by (4.4), r(Ω) < ∞. For a, x ∈ Ω, let γ be a path in Ω from a to x. Since f ∘ γ is a Lipschitz function, (3.2) holds, and from it we obtain that

|f(x) − f(a)| ≤ ∫_{γ} |D_{T}f| ds ≤ ∫_{γ} ∥Df∥_{L_{∞}(γ^{∗})} ds ≤ ∥Df∥_{L_{∞}(Ω)} length(γ).  (4.19)

Taking the infimum of the righthand side of (4.19) over all possible γ then gives

|f(x) − f(a)| ≤ ∥Df∥_{L_{∞}(Ω)} d_{Ω}(a, x),

so that

∥f − f(a)∥_{L_{∞}(Ω)} ≤ ∥Df∥_{L_{∞}(Ω)} r(a, Ω).  (4.20)

Hence by (4.20)

dist_{L_{∞}(Ω)}(f, Π_{0}) ≤ inf_{a∈Ω} ∥f − f(a)∥_{L_{∞}(Ω)} ≤ ∥Df∥_{L_{∞}(Ω)} r(Ω),

giving the upper bound C_{Ω} ≤ r(Ω).

The remaining estimates of C_{Ω} follow from (4.5) and (4.6). For example, if Ω is convex, then

C_{Ω} ≤ r(Ω) = \frac{1}{2} diam Ω,

while choosing a ∈ Ω with sup_{x∈Ω} ∥x − a∥ = diam Ω − ε, ε > 0, gives

\frac{1}{2}(diam Ω − ε) = \frac{1}{2}r(a, Ω) ≤ C_{Ω}.

Finally, we show for d > 1 that C_{Ω}/ diam Ω can be arbitrarily large. Let γ be some path of length L (which can be as large as desired) contained in some ball of diameter 1, e.g., a suitably tight spiral. For ε > 0, let Ω be a domain obtained from γ by taking the union over a ∈ γ^{∗} of open balls of centre a and radius < ε chosen so that

L − ε < sup_{x,y∈Ω} d_{Ω}(x, y) < L + ε.

For this domain, it follows from (4.13) and (4.4) that

\frac{C_{Ω}}{diam Ω} ≥ \frac{r(Ω)/2}{diam Ω} ≥ \frac{sup_{x,y∈Ω} d_{Ω}(x, y)/4}{diam Ω} ≥ \frac{(L − ε)/4}{1 + 2ε},

which for suitably large L and small ε can be as large as desired.

The best constant C_{Ω} in (4.1) also depends on the definition of sufficiently smooth used, as we now show by example.

Let Ω := (0, 1) × (−δ, δ) ⊂ IR^{2}, for small δ > 0. For f from W_{∞}^{1}(Ω) and C^{1}(Ω̄) the best constant C_{Ω} is the same, and close to 1/2 (approximate f by f(1/2, 0) to estimate C_{Ω} from above, and use f(x) := x to get the lower bound). Now make a slit along (δ, 1) × {0} to obtain Ω^{∗} := Ω \ (δ, 1) × {0}. This effectively gives a strip of length 2 instead of 1 as previously. For f from W_{∞}^{1}(Ω) the approximation f(δ/2, 0) is nearly optimal, and multiplies the previous constant by almost 2, i.e., C_{Ω^{∗}} ≈ 2C_{Ω}. But for f from C^{1}(Ω̄^{∗}) = C^{1}(Ω̄) the best constant remains the same, i.e., C_{Ω^{∗}} = C_{Ω}.

Remarks on L_{p}–estimates

From the beginnings of the theory of Sobolev spaces it has been known that for a suitably regular domain Ω there exists a finite constant C_{p,Ω} for which

dist_{L_{p}(Ω)}(f, Π_{0}) := inf_{c∈Π_{0}} ∥f − c∥_{L_{p}(Ω)} ≤ C_{p,Ω} ∥Df∥_{L_{p}(Ω)},  ∀f ∈ W_{p}^{1}(Ω),  (4.21)

where ∥Df∥_{L_{p}(Ω)} is some seminorm measuring the L_{p}(Ω)–size of Df. The argument for this, which is by contradiction (see Morrey [10:Th.3.6.11]) , does not give any information about how the best such constant C_{p,Ω} depends on the geometry of the domain Ω (or on p). From now on, let

∥Df∥_{L_{p}(Ω)} := the L_{p}(Ω)–norm of ∥∇f∥.

There have been many constructive estimates of C_{p,Ω} (and similar constants), see, e.g., Dupont and Scott [7], or Dahmen, DeVore and Scherer [5]. For the specific case (4.21), the best of these is the following. Suppose that p > d and Ω is starshaped with respect to a. By a slight refinement of the estimate of Arcangeli and Gout [1:Th.1-1] one obtains

dist_{L_{p}(Ω)}(f, Π_{0}) ≤ ∥f − f(a)∥_{L_{p}(Ω)} ≤ \frac{r(a, Ω)}{1 − d/p} ∥Df∥_{L_{p}(Ω)},  ∀f ∈ W_{p}^{1}(Ω), (4.22)

and Dechevski and Quak [6:p491] give the bound

dist_{L_{p}(Ω)}(f, Π_{0}) ≤ ∥f − f(a)∥_{L_{p}(Ω)} ≤ \frac{diam Ω}{1 − d/p} ∑_{i=1}^{d} ∥D_{i}f∥_{L_{p}(Ω)},  ∀f ∈ W_{p}^{1}(Ω). (4.23)

From (4.13) it is seen when p = ∞ the dependence of the best constant C_{p,Ω} on Ω is in terms of the equivalent quantities

r(Ω) := inf_{a∈Ω} sup_{x∈Ω} d_{Ω}(a, x), d(Ω) := sup_{x,y∈Ω} d_{Ω}(x, y),

rather than on diam Ω. Presumably this behaviour also holds to some extent for other values of p (particularly large p). One might conjecture that for 1 ≤ p ≤ ∞, there exist constants A_{n,p} and B_{n,p} (depending only on n and p), for which

A_{n,p} r(Ω) ≤ C_{Ω} ≤ B_{n,p} r(Ω),

for all sufficiently regular domains Ω. It is not at all obvious how the proof of Theorem 4.10 could be modified to obtain such a result. However, for f := d_{Ω}(a, ·) one does have

∥Df∥_{L_{p}(Ω)} = (measure of Ω)^{1/p},

and so, for the lower bound at least, there is some hope of obtaining at least a partial result.

Inequalities of the form (4.21) are closely related to several classical Sobolev inequalities from the theory of partial differential equations. These include Friedrichs’ inequality

∥f − f_{Ω}∥_{L_{p}(Ω)} ≤ C ∥Df∥_{L_{p}(Ω)}, ∀f ∈ W_{p}^{1}(Ω),

where f_{Ω} is the constant function given by

f_{Ω} := \frac{1}{meas Ω} ∫_{Ω} f,

(it can easily be shown that ∥f−f_{Ω}∥_{L_{p}(Ω)} ≤ 2 dist_{L_{p}(Ω)}(f, Π_{0})), and the Poincaré inequality

∥f∥_{L_{p}(Ω)} ≤ C ∥Df∥_{L_{p}(Ω)}, ∀f ∈ C_{0}^{∞}(Ω).

Most of the work on these involves determining conditions on the domain Ω that are necessary and sufficient for these inequalities to exist for an appropriately defined Sobolev space, see, e.g., Edmonds and Opic [8] where weighted Sobolev spaces are considered.

Acknowledgement

I would like to thank Pavel Shvartsman and Jean–Pierre Rosay for some helpful and interesting discussions related to Section 4.

References

[1] Arcangeli, R. and J. L. Gout(1976): Sur l’evaluation de l’erreur d’interpolation de Lagrange dans un ouvert de IR^{n}. Rev. Française Automat. Informat. Rech. Opér., Anal. Numer. 10(3), 5–27

[2] Boor, C. de(1997): The error in polynomial tensor-product, and in Chung-Yao, interpolation. In: A. Le Méhauté, C. Rabut, and L. L. Schumaker, eds, Surface Fitting and Multiresolution Methods, 35–50. Vanderbilt University Press, Nashville TN

[3] Barros–Neto, J.(1973): An introduction to the theory of distributions. Marcel Dekker, New York

[4] Ciarlet, P. and C. Wagschal(1971): Multipoint Taylor formulas and applications to the finite element method. Numer. Math. 17, 84–100

[5] Dahmen, W., R. DeVore, and K. Scherer(1980): Multidimensional spline approximations. SIAM J. Numer. Anal. 17, 380–402

[6] Dechevski, L. T. and E. Quak(1990): On the Bramble-Hilbert lemma. Numer. Func. Anal. Optim. 11 (5&6), 485–495

[7] Dupont, T. and R. Scott(1980): Polynomial approximation of functions in Sobolev spaces. Math. Comp. 34(150), 441–463

[8] Edmonds, D. E. and B. Opic(1993): Weighted Poincaré and Friedrichs inequalities. J. London Math. Soc. 47, 79–96

[9] Gregory, J. A.(1975): Error bounds for linear interpolation on triangles. In: J. Whiteman, ed, Mathematics of Finite Elements and Applications, 163–170. Academic Press, London

[10] Morrey, C. B.(1966): Multiple integrals in the calculus of variations. Springer-verlag, Berlin

[11] Sard, A.(1963): Linear approximation. Math. Survey 9, AMS, Providence

[12] Waldron, S.(1998): Multipoint Taylor formulæ. Numer. Math. 80(3), 461–494

[13] Waldron, S.(1998): The error in linear interpolation at vertices of a simplex. SIAM J. Numer. Anal. 35(3), 1191–1200