f (x) ’ u j (x) f (x j ) ¤ (1 + C1 ) (C2 h)m+1

—)

L∞(

±!

|±|=m+1

j=1

¤ Ch m+1 | f |C m+1 ( ,

—)

with h = h X, .

Let us point out that the result is indeed local. It always gives the approximation order

that can be achieved by polynomial reproduction. Hence, if f is less smooth in a subregion

of , say it possesses only ¤ m continuous derivatives there, then the approximant still

gives order ’ 1 in that region and this is the best we can hope for.

3.2 Norming sets

After having learnt about the bene¬ts of a local polynomial reproduction, we now want

to prove its existence. The case m = 0 of constant polynomials is easy to handle. If one

chooses for x ∈ an index j such that x ’ x j 2 is minimal, the functions can be de¬ned

pointwise by u j (x) = 1 and u k (x) = 0 for k = j. These functions obviously satisfy the

conditions of De¬nition 3.1 with arbitrary h 0 and C1 = C2 = 1.

It remains to prove existence in case of polynomials of degree m ≥ 1. This will be done

in a very elegant way, which allows us to state all the involved constants explicitly. The

drawback of this approach is that it is nonconstructive: it will give us no hint how the

functions u j might look.

3.2 Norming sets 27

Let V be a ¬nite-dimensional vector space with norm · V and let Z ⊆ V — be a ¬nite

set consisting of N functionals. Here, V — denotes the dual space of V consisting of all linear

and continuous functionals de¬ned on V .

De¬nition 3.3 We will say that Z is a norming set for V if the mapping T : V ’ T (V ) ⊆

R N de¬ned by T (v) = (z(v))z∈Z is injective. We will call T the sampling operator.

If Z is a norming set for V then the inverse of the sampling operator exists on its range,

’1

T : T (V ) ’ V . Let R N have the norm · R N , and let · R N — be the dual norm on

—

R N = R N . Equip T (V ) with the induced norm. Finally, let T ’1 be the norm de¬ned as

T ’1 x V v

T ’1 =

V

= sup .

sup

v∈V \{0} T v

x RN RN

x∈T (V )\{0}

This norm will be called the norming constant of the norming set.

We are mainly interested in using the ∞ -norm on R N , so that the dual norm is given by

the 1 -norm.

The term norming set comes from the fact that Z allows us to equip V with an equiva-

lent norm via the operator T . To see this, ¬rst note that obviously T v R N ¤ T v V .

Conversely, since T is injective we have v V = T ’1 (T v) V ¤ T ’1 T v R N . Hence,

· V and T (·) R N are equivalent norms on V .

It is clear that we need at least N ≥ dim V functionals to make the operator T injective.

It is also obvious that we can get along with exactly N = dim V functionals. But what we

have in mind is that a certain family of functionals is given, for example point-evaluation

functionals. Then the natural question is how many of these functionals are necessary not

only to make T injective but also to control the norm of T and its inverse. In case of point-

evaluation functionals we might also ask for the locus of the points. These questions will

be addressed in the next section. We now come to the main result on norming sets.

Theorem 3.4 Suppose V is a ¬nite-dimensional normed linear space and Z = {z 1 , . . . , z N }

is a norming set for V , T being the corresponding sampling operator. For every ψ ∈ V —

there exists a vector u ∈ R N depending only on ψ such that, for every v ∈ V ,

N

ψ(v) = u j z j (v)

j=1

and

T ’1 .

¤ψ

u RN — V—

Proof We de¬ne the linear functional ψ on T (V ) by ψ(x) = ψ(T ’1 x). It has a norm that is

bounded by ψ ¤ ψ V — T ’1 . By the Hahn“Banach theorem, ψ has a norm-preserving

extension ψext to R N . On R N all linear functionals can be represented by the inner product

28 Local polynomial reproduction

with a ¬xed vector. Hence, there exists u ∈ R N with

N

ψext (x) = u jxj

j=1

T ’1 . Finally, we ¬nd for an arbitrary v ∈ V , by setting x = T v,

¤ψ

and u RN — V—

N N

ψ(v) = ψ(T ’1 x) = ψ(x) = ψext (x) = u jxj = u j z j (v),

j=1 j=1

which ¬nishes the proof.

It is important to notice that there are two different ingredients in this result. On the one

hand we have the functionals in Z , and they determine the norming set. On the other hand

there is the functional ψ. But the existence of the vector u does not depend on ψ, it only

depends on Z . Of course, the actual vector u will depend on the speci¬c ψ but not the

general result on its existence. Hence, if we know that Z is a norming set, we can represent

every functional ψ in this way.

3.3 Existence for regions with cone condition

To use norming sets in the context of local polynomial reproduction, we choose V =

πm (Rd )| and Z = {δx1 , . . . , δx N }. Here δx denotes the point-evaluation functional de¬ned

by δx ( f ) = f (x). A ¬rst consequence of this choice is

Proposition 3.5 The functionals Z = {δx1 , . . . , δx N } form a norming set for πm (Rd ) if and

only if X is πm (Rd )-unisolvent.

As mentioned earlier, we equip R N with the ∞ -norm. If we additionally choose ψ to

be δx , Theorem 3.4 gives us a vector u(x) ∈ R N that recovers polynomials in the sense of

De¬nition 3.1 and has a bounded 1 -norm. Hence, two of the three properties of a local

polynomial reproduction are satis¬ed, provided that Z = {δx1 , . . . , δx N } is a norming set

for the polynomial space. The third property will follow by a local argument. But before

that we give conditions on the set of data sites X such that Z forms a norming set. This

is hopeless in the case of a general domain . Hence, we restrict ourselves to the case of

domains satisfying an interior cone condition.

De¬nition 3.6 A set ⊆ Rd is said to satisfy an interior cone condition if there exists an

angle θ ∈ (0, π/2) and a radius r > 0 such that for every x ∈ a unit vector ξ (x) exists

such that the cone

C(x, ξ (x), θ, r ) := {x + »y : y ∈ Rd , y = 1, y T ξ (x) ≥ cos θ, » ∈ [0, r ]} (3.1)

2

is contained in .

We will often make use of the following elementary geometric fact (see Figure 3.1).

3.3 Existence for regions with cone condition 29

q

y

sin