Let us ÿrst formulate it for Lagrange interpolation: given m nodes z1 ; : : : ; zm in Rd and values

d

c1 ; : : : ; cm , there is a polynomial P ∈ m’1 which interpolates the values

P(zq ) = cq ; q = 1; : : : ; m: (35)

d

So what is the problem? The problem is that dim m’1 is much larger than m, so that Eq. (35)

does not determine P uniquely. As we will see, there are many di erent ways to add additional

interpolation conditions in order to make the interpolant unique.

But wait. Let us be more cautious. If the nodes can be chosen arbitrarily, can we be sure that

d

there is at least one P in m’1 satisfying (35). Severi, [41], has already answered this question for

us in the context of Hermite interpolation.

We will say that a Hermite interpolation (of type total degree) is solvable with polynomials from

d m

n if given m, orders {kq }q=1 and values cq; for 06| |6kq , q = 1; : : : ; m, there is, for any node set

Z = {zq }m , a P ∈ n with

d

q=1

D P(zq ) = cq; 06| |6kq ; q = 1; : : : ; m: (36)

Theorem 19. Let m and nonnegative integers {kq }m be given. A necessary and su cient condition

q=1

d

that Hermite interpolation of type total degree be solvable with polynomials from n is that

m

n + 1¿ (kq + 1):

q=1

d

Thus, we see that Lagrange interpolation on m nodes is solvable from m’1 . Note also that the

condition is the same for any dimension d. Actually, the case of Lagrange interpolation can be done

d

directly. One can construct a Lagrange interpolating function from m’1 for a node by taking the

product of m ’ 1 hyperplanes passing through the other nodes but not through the given nodes.

= {‚1 ; : : : ; ‚m } ∈ Rd be a set of points with some of the

We start with some deÿnitions, Let

nodes possibly repeated. Here and in the following, denotes a point set with some of the points

possibly repeated, while Z is our old notation of a point set with no points repeated. Given an

integrable function f on Rd and a point set , its divided di erence I (f) of order m ’ 1 is deÿned

to be

1 1

I (f) = ··· f(‚1 + s1 (‚2 ’ ‚1 ) + · · · + sm’1 (‚m ’ ‚m’1 )) dsm’1 · · · ds1 : (37)

0 0

This is a direct generalization of the univariate divided di erence (Eq. (16)) and leads to error

estimates via remainder formulas (see [15, Section 2]).

For z ∈ Rd and f a continuously di erentiable function on Rd , the directional derivative, Dz f, of

f in the direction z is denoted by

Dz f = z · f:

To each ∈ Rd , we associate the functional — on Rd deÿned by — z = · z (the Euclidian scalar

product).

A plane wave, or ridge function, h in Rd is the composition of a functional and a univariate

function g : R ’ R

—

)(z) = g( — z) for z ∈ Rd :

h(z) = (g —¦ (38)

R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 183

Let C s (Rd ) be the space of s times continuously di erentiable functions on Rd .

Now the main deÿnition

Deÿnition 20. Let s ∈ N0 be given and L associate with each ÿnite set ‚ R of points (possibly

repeated) a continuous linear map L

L : C s (R) ’ C s (R):

A continuous linear map

L : C s (Rd ) ’ C s (Rd )

‚ Rd if it satisÿes

is the lift of L to

— —

L (g —¦ ) = (L g) (39)

—

∈ Rd and any g ∈ C s (Rd ). Here —

= { — ‚1 ; : : : ; —

‚ Rd .

for any ‚m } ‚ R for

Since it is by no means clear that each map L has a lift, for example the univariate ÿnite di erence

of point in Rd . A lift, if it

map has no lift, we say that L is liftable if it has a lift to each set

exists, is unique.

The maps we want to lift are Lagrange and Hermite maps. Given a node set Z = {z1 ; : : : ; zm } ‚ R

1

and g ∈ C(R), the Lagrange map LZ g delivers the interpolant to g from m’1 . More generally, the

Hermite map H based on the univariate Hermite interpolation given by (11) and (12) associates

with each g ∈ C n (R), the Hermite interpolant from n to the values cq; = D g(zq ). Here, Z is

d

and kq are their multiplicities. g was required to be in C n (R) with

the set of distinct points in

n = m (kq + 1) ’ 1 since potentially all the points in could coincide. Note also that the Hermite

q=1

map becomes the Lagrange map when all the points of are distinct.

The lift L of say the Lagrange map would necessarily associate to each node set Z ‚ Rd and

function f ∈ C(R) a multivariate polynomial from m’1 . In fact, let f ∈ C(Rd ). Then f can be

d

approximated arbitrarily well by linear combinations of plane waves. Since, by deÿnition, L is

continuous, L (f) can be approximated arbitrarily well by linear combinations of functions of the

form (L — g) —¦ — . But each (L — g) is a univariate polynomial (in m’1 ) and, consequently, so is

1

L (f) as their limit.

For the same reason, a lift H of the Hermite map would also map C s (Rd ) to n . d

Before we formulate the general theorem on lifting Hermite maps, let us describe their precursors.

Kergin (see [25]) ÿrst constructed a lift of the Hermite map but without using the concept of lifting.

Theorem 21. Given a set of not necessarily distinct points = {‚1 ; : : : ; ‚n+1 } from Rd ; there exists

a unique linear map H : C n (Rd ) ’ n such that for each f ∈ C n (Rd ); each Q ∈ k ; 06k6n

d d

and each J ‚{1; : : : ; n + 1}; there is a z ∈ span{‚q }q ∈ J such that

Q(D)(L (f) ’ f)(z) = 0:

Choosing J = {q} in this theorem shows that H (f)(‚q ) = f(‚q ), so that H indeed interpolates

function values. Similarly, if ‚q is repeated kq times, then all partial derivatives of f up to order kq

are interpolated at ‚q .

184 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201

Micchelli, respectively, Micchelli and Milman [29,30] showed how to construct the Kergin inter-

polant by showing that it interpolates the functionals

f(‚1 ); I{‚1 ;‚2 } (@f=@xi ); i = i; : : : ; d;

···; I{‚1 ;:::;‚n+1 } (D f) | | = n:

This is not such a nice representation of the functionals since, ÿrst of all, it is not clear from the

formula that the interpolant is independent of the order in which the points ‚q are arranged and,

secondly, it assumes an order of di erentiability of f which is not really necessary. In fact, as was

remarked in the original papers, it is independent of the choice of the nodes and, if the nodes are

in general position, then Kergin™s interpolant has a continuous extension from C n (Rd ) to C d’1 (Rd ).

To elucidate this, let us look Lagrange interpolation at three noncollinear nodes {‚1 ; ‚2 ; ‚3 } in R2 .

2

The Kergin interpolant is from 2 whose dimension is 6. According to the representation given

above, the functionals to be interpolated are f(‚1 ), the average values of @f=@x and @f=@y along

the line joining z1 with z2 , and the average values of @2 f=@x2 , @2 f=@x@y and @2 f=@y2 over the

triangle formed by the nodes. In [28], it was shown that one obtains the same interpolation if one

interpolates the functionals f(zq ), q = 1; 2; 3 and the average values of @f=@ni over the ith side of

the triangle, i = 1; 2; 3. Here, ni is the normal to the ith side. This representation is symmetric in the

nodes and one sees that only f ∈ C 1 (R2 ) is required instead of C 2 (R2 ). Waldron [44] gives explicit

formulas for the general case.

Interpolating average values of functions or their derivatives is not as exotic as it may seem. For

example, a well-known ÿnite element, the Wilson brick (see [7]), interpolates average values of

second derivatives.

Another generalization of univariate Hermite interpolation to Rd was given by Hakopian [21].

Let ‚ Rd have m¿d + 1 nodes in general position, meaning that any d + 1 of them form a

nondegenerate tetrahedron. Then the problem of interpolating the functionals

for all ˜ ‚ with | ˜ | = d

I˜

for f ∈ C(Rd ) with polynomials from d

is regular. Here | | is the cardinality of . Note that

m’d

there are exactly

m

d

d

interpolation conditions, which is also the dimension of m’d .

Take three noncollinear nodes z1 ; z2 ; z3 in R2 . Hakopians™ interpolant interpolates the average value

of a function over the three sides of the triangle formed by the nodes.

Goodman [19] showed that these two types of interpolations are the end points of a whole scale

of univariate Hermite interpolations, which are all liftable.

Let f ∈ C(R) and let D’r f be any function with D r (D’r ) = f. Then the generalized Hermite

map H (r) associated with r and the set ‚ R, with | | = n + 1, is the map

H (r) : C n’r (R) ’ 1

n’r

given by

H (r) f = Dr H D’r f:

R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 185

Theorem 22. For any r; n with 06r6n; H (r) ; with | | = n + 1; is liftable to H(r) : C n’r (Rd ) ’

d

n’r . The functionals interpolated are

I ˜ (P˜ (D)f) (40)

for all ˜ ‚ with | ˜ |¿r +1 and where {P˜ } is a basis for the homogeneous d-variate polynomials

of degree | ˜ | ’ r ’ 1.

If r = 0, we obtain the Kergin map. If r = d ’ 1, n¿d ’ 1 and the points of are in general

position, we get the Hakopian map.

4.2. The least interpolant

Would it not be nice if given any functionals Fq , q = 1; : : : ; m, we could ÿnd a polynomial space

V such that the equations

Fq P = cq ; q = 1; : : : ; m

have a unique solution P ∈ V for any cq ? Note that the point of view has changed here. Given the

functionals, we do not know which interpolation space to use, we derive it.

Well, if one is not too choosy, such a space almost always exists. All one needs is that the func-

tionals be linearly independent in the space of all polynomials. Then a simple elimination argument

shows that there are polynomials Qr (dual polynomials) so that Fq Qr = q; r . The linear span of these

polynomials forms a possible space V .

The above construction is clearly not unique. One can require the interpolation space to have

desirable properties. It turns out that the condition that the degree of the interpolant be as low as

possible is a key concept, connecting the quest for good interpolation spaces with, among other things,

Grobner bases of polynomial ideals. This connection will be explained for Lagrange interpolation.

Let Z = {z1 ; · · · ; zm } be a set of nodes in Rd and V a space of polynomials from which Lagrange

interpolation is regular. V is called degree reducing (the interpolant from V is degree reducing) if

for any polynomial P, its interpolant Q satisÿes deg Q6 deg P.

A set of polynomials {P | ∈ I ‚ Nd } is called a Newton basis with respect to Z if Z can be

indexed as {z | ∈ I } so that for any , ÿ ∈ I with | |6|ÿ|, one has P (zÿ ) = ; ÿ and for any n,

there is a decomposition

d d

= span{P | | |6n} • {Q ∈ | Q(zq ) = 0; q = 1; : : : ; m}:

n n

Sauer [35] shows that

Theorem 23. A space of polynomials V has a Newton basis with respect to Z if and only if it is

degree reducing for Z.

d

Even degree reducing spaces are not unique except when V = n for some n. These ideas can

be generalized to Hermite interpolation and to orderings of d which are compatible with addition,

see [15,35, Section 3].

be a total ordering of Nd

A closely related subject is that of Grobner bases and H-bases. Let

which has 0 as its minimal element and is compatible with addition (in Nd ). We will use it to order

186 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201

the terms of a polynomial for which reason we call it a term order. Let I be an ideal of polynomials.

A ÿnite set P is called a Grobner basis for I if any polynomial Q ∈ I can be written as

Q= QP P;

P∈P

where the (term order) degree of any summand does not exceed the degree of Q. If the term order

degree is replaced by total degree, then we have an H-basis.

Now suppose I is the ideal associated with the node set Z, i.e., I ={P | P(zq )=0; q =1; : : : ; m} and

P a Grobner or an H-basis for I . Given a set of values to interpolate, let Q be any polynomial which

interpolates them. We really want an interpolant of lowest possible degree (in our chosen ordering),

so if the degree of Q is too high, we can eliminate the term of highest degree with some polynomial

multiple of one of the basis polynomials. Continuing, we reduce Q as much as possible, arriving

at a “minimal degree interpolant” with respect to the order used. This also works the other way

around. One orders monomials according to some term order. Then one uses Gaussian elimination

to ÿnd an interpolant. During the elimination, one encounters zero columns. The linear combinations

producing these columns are just the coe cients of a Grobner or an H-basis polynomial. We again

refer to the survey paper [15] for the precise formulations of the above sketchy ideas. Other sources

are Sauer [35,36], Buchberger [3], and Groebner [20].

The least interpolant of de Boor and Ron [8], which we will deÿne now, is such a degree reducing

interpolant. It uses an ordering of degrees “in blocks” of total degree.

Deÿnition 24. Let g be a real-analytic function on Rd (or at least analytic at z = 0)

∞

aj z j :

g(z) =

|j|=0

Let j0 be the smallest value of |j| for which some aj = 0. Then the least term of g“ of g is

aj z j :

g“ =

j=j0

Note that g“ is a homogeneous polynomial of degree j0 .

Theorem 25. Given a node set Z ‚ Rd ; let

ExpZ = span{ez·zq | q = 1; : : : ; m}

and

PZ = span{g“ | g ∈ ExpZ }:

Then Lagrange interpolation from PZ to values at Z is regular.

The map L : C(Rd ) ’ PZ with Lf being the interpolant to the values of f on Z is called the

least Lagrange interpolant. Note that dim PZ = dim ExpZ .

Let us now look at some examples in R2 . First, let Z = {(0; 0); (1; 0); (0; 1)}. We know that