. 42
( 83 .)


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

Let us ÿrst formulate it for Lagrange interpolation: given m nodes z1 ; : : : ; zm in Rd and values
c1 ; : : : ; cm , there is a polynomial P ∈ m’1 which interpolates the values
P(zq ) = cq ; q = 1; : : : ; m: (35)
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
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 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
that Hermite interpolation of type total degree be solvable with polynomials from n is that
n + 1¿ (kq + 1):

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
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
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
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

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
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

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

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 .
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

for f ∈ C(Rd ) with polynomials from d
is regular. Here | | is the cardinality of . Note that
there are exactly
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

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 ) ’
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.
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;

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) =

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“ =

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}
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


. 42
( 83 .)