Now it is clear how a possible generalization can be made. We start with a function : —

’ R for ⊆ Rd and form the space F ( ) in the same way as we formed Fφ [a, b]. We

only have to replace φ(| · ’ x j |) by (·, x j ) and the annihilation conditions as appropriate.

Of course this can only work for ™s that allow us to equip F ( ) with an inner product

(·, ·) . But we can turn things upside down and use this property as a de¬nition for . In any

case, if gives rise to an inner product on F ( ) we can form the closure F ( ) of F ( )

with respect to this inner product. It will turn out that the new space can be interpreted as

a space of functions again and that the interpolants are minimal semi-norm interpolants

again.

1.5 Approximation and approximation orders

So far, we have only dealt with the concept of interpolation. But especially if the number

of points is large and the data values contain noise it might be reasonable not to interpolate

the given values exactly but to ¬nd a smooth function that only nearly ¬ts the values. The

14 Applications and motivations

standard method in this case is to compute a least squares solution. To this end, one chooses

a ¬nite-dimensional space S ⊆ C(Rd ) and determines the function s ∈ S that minimizes

N

[s(x j ) ’ f j ]2 .

j=1

This approach has the disadvantage of being global in the sense that every data point has

some in¬‚uence on the solution function in any point. It would be more interesting to allow

only the nearest neighbors of the evaluation point x to in¬‚uence the approximate value s(x).

A method that realizes this idea is the moving least squares method. It is a variation on the

classical least squares technique. Here, the dimension of the space S is supposed to be small.

After ¬xing a weight function w : Rd — Rd ’ R one determines for every evaluation point

x the solution s — of

N

[s(x j ) ’ f j ]2 w(x, x j ) : s ∈ S .

min

j=1

The approximate value is then given by s — (x). If the weight function is of the form w(x, x j ) =

w0 (x ’ x j ) with a compactly supported function w0 having a support centered around zero

this method uses only the data sites in a neighborhood of x to compute the approximate

value. Thus, in this sense it is a local method, though for every evaluation point x a small

linear system has to be solved. Nonetheless, this method turns out to be highly ef¬cient.

After having discussed the concepts involved in reconstructing a function from discrete

values we have to investigate the bene¬ts of the methods. In general, this is done by analyzing

the approximation properties of the approximation process.

Suppose that X ⊆ ⊆ Rd , where is a bounded set. Suppose further that the data values

{ f j } come from an unknown function f ∈ C( ), i.e. f (x j ) = f j , 1 ¤ j ¤ N . Then we are

interested in how well the approximant or interpolant s f,X approximates the function f on

when the sets of data sites X become denser in . This obviously needs a measure of how

dense X is in . For example, in case of splines it is usual to de¬ne h X = max(x j+1 ’ x j )

as such a measure.

In case of natural cubic splines it is well known that there exists a constant c > 0 such

that for all functions f ∈ H 2 [a, b] the error can be bounded as follows:

3/2

f ’ s f,X ¤ ch X L 2 [a,b] .

f

L ∞ ([a,b])

The d-variate generalization is given by

De¬nition 1.4 The ¬ll distance of a set of points X = {x1 , . . . , x N } ⊆ for a bounded

domain is de¬ned to be

x ’ xj 2.

h X, := sup min

1¤ j¤N

x∈

The ¬ll distance can be interpreted in various geometrical ways. For example, for any

point x ∈ there exists a data site x j within a distance at most h X, . Another possible

1.6 Notation 15

interpretation is the following. The ¬ll distance h X, denotes the radius of the largest ball

which is completely contained in and which does not contain a data site. In this sense

h X, describes the largest data-site-free hole in .

De¬nition 1.5 An approximation process ( f, X ) ’ s f,X has L ∞ convergence order k for

the function space F if there exists a constant c > 0 such that for all f ∈ F,

f ’ s f,X ¤ ch k F.

f

L∞( ) X,

The process possesses a spectral convergence order if there exists a constant c > 0 and a

constant » ∈ (0, 1) such that, for all f ∈ F,

f ’ s f,X ¤ c»1/h X, F.

f

L∞( )

1.6 Notation

It is time to ¬x certain items of notations that will be used throughout this book, though

in fact some of them have already been employed. In many cases the symbols will be

introduced where needed but some are important throughout, so that we want to collect

them here.

Our main goal is to work with real-valued functions but sometimes it is necessary to

employ complex-valued ones also. In this sense, the following function spaces contain

real-valued functions if it is not stated otherwise.

We continue to denote the space of d-variate polynomials of absolute degree at most

m by πm (Rd ). The function space C k ( ) is the set of k times continuously differentiable

functions on , where we assume ⊆ Rd to be open if k ≥ 1. The intersection of all these

spaces is denoted by C ∞ ( ). The Lebesgue spaces are as usual denoted by L p ( ), 1 ¤ p ¤

∞, where ⊆ Rd should be measurable, i.e. they consist of all measurable functions f

p

having a ¬nite L p -norm. The L p -norm · L p ( ) is given by f L p ( ) := | f (x)| p d x for

1 ¤ p < ∞ and by f L ∞ ( ) := ess supx∈ | f (x)|. The latter means the following. Every

function f ∈ L ∞ ( ) is essentially bounded on , i.e. there exists a constant K > 0 such

that | f (x)| ¤ K almost everywhere on . The greatest lower bound of such constants K

gives the norm. The space L loc ( ) consists of all measurable functions f that are locally

p

in L p , meaning their restriction f |K belongs to L p (K ) for every compact set K ⊆ . If

is an interval [a, b] we will write L p [a, b] and C k [a, b] for L p ([a, b]) and C k ([a, b]),

respectively, and similarly for open and semi-open intervals.

If dealing with several points in Rd one runs automatically into problems with indices.

Throughout this book we will use the following notation. For a point x ∈ Rd its components

will be given as x1 , . . . , xd , whereas x1 , . . . , x N will denote N points in Rd . The components

of x j are thus denoted x j,k , 1 ¤ k ¤ d. We will use similar notation for y and z. These are

the main critical cases and we will comply strictly with this usage. In the case of other letters

we might sometimes relax the notation when there is no possibility of misunderstanding.

16 Applications and motivations

p

As usual we denote by x p the discrete p-norm x p = d |x j | p for 1 ¤ p < ∞ and

j=1

x ∞ = max |x j |.

For a multi-index ± ∈ Nd we denote its components by as usual ± = (±1 , . . . , ±d )T . The

0

length of ± is given by |±| = ±1 + · · · + ±d = ± 1 and the factorial ±! by ±1 ! · · · ±d !. For

two multi-indices ±, β, the inequality ± ¤ β is meant component-wise and

± ±!

=

β β!(± ’ β)!

is again de¬ned component-wise. If |±| ¤ k, x ∈ Rd , and f ∈ C k ( ) are given, we denote

the ±th derivative of f and the ±th power of x by

‚ |±|

x ± := x±1 · · · x±d .

D ± f := f and

‚x±1 · · · x±d d

1

d

1

Finally, there is a concept that will accompany us throughout this book. We will often

meet multivariate functions that are constant on spheres around zero, i.e. they are radial.

Hence, such a function depends only on the norm of its argument. We will always use

to denote the multivariate function and a small letter φ to denote the

a capital letter