. 40
( 83 .)


polynomial Pj ∈ which interpolates the ÿrst j values, We take
Qj+1 (z) = (z ’ zq ):

Then Rj+1 (z) = cj+1 Qj+1 (z)=Qj+1 (zj+1 ) vanishes at the ÿrst j nodes while taking the value cj+1 at
zj+1 . Let Pj+1 = Pj + Rj+1 . Then Pj+1 ∈ j interpolates the ÿrst j + 1 values.
The formula for the Newton interpolant to a continuous function f is
P(f)(x) = f[z1 ; : : : ; zq ] (z ’ zr ); (15)
q=1 r=1

where the divided di erence f[zr ; : : : ; zq ]; r6q, is deÿned by
f[zr ] = f(xr ); (16)
f[zr ; : : : ; zq’1 ] ’ f[zr+1 ; : : : ; zq ]
f[zr ; : : : ; zq ] = : (17)
zr ’ zq
The Newton form of the interpolant is particularly suitable for obtaining error estimates.
We have gone through these well-known univariate methods in such detail because, as we will
see, many multivariate proofs and constructions are based on these principles, although the details
may be much more involved.

2.2. Multivariate Lagrange interpolation

I claim that univariate and multivariate Lagrange interpolation are two very di erent animals. To
see what I mean, let us look at the ÿrst nontrivial bivariate Lagrange interpolation: the interpolation
of two values at two nodes z1 , z2 in R2 . But which space of polynomials should we use? The space
of linear polynomials 1 is spanned by 1, x and y and thus has dimension 3, while the space of
constants, 0 , has dimension only one! Our interpolation falls into the gap. There is no “natural”
space of polynomials which ÿts our problem, or at least no obvious natural space.
Now let us try Lagrange interpolation on three nodes Z = {z1 ; z2 ; z3 }. We choose V = 1 , so that
(2) is satisÿed. Choosing the monomial basis for 1 , the Vandermonde determinant of the interpola-
tion is
D(Z) = (x2 ’ x1 )(y3 ’ y1 ) ’ (x3 ’ x1 )(y2 ’ y1 );
where zq = (xq ; yq ). If the three nodes are the vertices of a non-degenerate triangle, then D(Z) = 0.
But if the nodes are collinear, say z1 = (0; 0); z2 = (1; 0) and z3 = (2; 0), one can check that D(Z)
vanishes and the interpolation is singular.
Thus, we have seen two di erences between univariate and multivariate Langrange interpolation.
In the multivariate case, it is not clear which interpolation spaces we should choose and, even when
there is an easy choice, the interpolation is regular for some knot sets and singular for others. We
can be more precise about the latter statement.

Theorem 1. Let Z = {zq }m ‚ Rd and n ∈ Z0 such that m = dim n . Then Lagrange interpolation
is regular for almost all choices of Z in the Lebesgue measure of Rmd .
R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 173

In fact, the Vandermonde determinant D(Z) of the system of equations for the coe cients of the
interpolant is a polynomial in the coordinates of the nodes and therefore either vanishes identically
or is nonzero almost everywhere.
The most general statement one can make about Z for which Lagrange interpolation is regular
is that Z does not lie on an algebraic curve of degree not exceeding n. However, this statement is
almost a tautology and is not constructive.
Many people have worked on ÿnding explicit formulas for arrays for which Lagrange interpolation
is regular. Some of them are quite ingenious and beautiful, but all of them are only necessary
conditions for regularity. We will see some of them in Section 5.

2.3. Multivariate Hermite interpolation

Everything we have said about Lagrange interpolation also holds for multivariate Hermite in-
terpolation including Theorem 1. However, yet another complication rears its head. Consider the
simplest non-trivial bivariate Hermite interpolation. This is interpolating function values and both
ÿrst derivatives at each of two nodes z1 and z2 in R2 . We interpolate using quadratic polynomials,
i.e., polynomials from 2 . Note that the condition (2) is satisÿed. There are 6 functionals to be
interpolated and dim 2 = 6. We will show that this interpolation is singular for all choices of nodes
z1 ; z2 . We will be seeing this example quite often. For this reason, I call it my favorite singular
Hermite interpolation.
A common method used to demonstrate the singularity of this interpolation is based on the obser-
vation that an interpolation satisfying the condition (2) is singular if and only if there is a nonzero
polynomial which satisÿes the homogeneous interpolation conditions. That is, there is a P ∈ V sat-
isfying (9) with all cq = 0.
Now returning to our Hermite interpolation, let ˜(z) = 0 be the equation of the straight line joining
z1 and z2 . ˜ is a linear polynomial, i.e., in 1 . So ˜2 ∈ 2 . We see that ˜2 and both of its ÿrst
2 2

derivatives vanish at both z1 and z2 . Thus the interpolation is singular.
Sitting back and sifting through the rubble, we are forced to distinguish between three possibilities:
(a) the interpolation is regular for any choice of node set,
(b) the interpolation is regular for almost any choice of node set, but not for all,
(c) the interpolation is singular for any choice of node set.
In the situation where the functionals to be interpolated depends on the choice of the nodes, as for
Lagrange or Hermite interpolation, we will say that the interpolation is regular if (a) holds, that it
is a.e. regular if (b) holds, and that it is singular if (c) holds.
We have just shown that both (b) and (c) occur. What about (a)? In the next section, we will
show that for Hermite interpolation, (a) can occur if and only if the interpolation is on one node
(m = 1). This is called Taylor interpolation. In that section we also run through the known cases of
almost everywhere regular and of singular Hermite interpolations.
In Section 4, we will look at two alternatives to “classical” Hermite interpolation. The ÿrst one
“lifts” univariate Hermite interpolation to higher dimensions. The second, called the “least interpo-
lation”, constructs the polynomial space to match the functionals and can be used in a much more
general context.
The above proof of singularity brings us quite close to a classical question of algebraic geometry.
174 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201

Given the functionals (6) of Hermite interpolation, what is the lowest degree of a nonzero polynomial
Q satisfying the homogeneous equation? One then says that Q has singularities of order kq + 1 at
zq . If (7) is satisÿed, then the interpolation is singular if and only the lowest degree is the n of (7).
But one can still formulate the question even if (7) does not hold. This question is considered in
Section 6.

3. Multivariate Hermite interpolation

3.1. Types of Hermite interpolation

Although we only discussed classical Hermite interpolation in the introduction, a type which we
will denote by total degree from now on, there are other types. They can be subsumed in the
following deÿnition of Hermite interpolation from [38], which replaces derivatives in the coordinate
directions by directional derivatives.
Let z ∈ Rd and m ∈ N0 . Given an index set
1 1 m m
E = (1| 1 ; : : : ; r1 | : : : | 1 ; : : : ; rm ); (18)
d d

where = 1 or 1, and a diagram Tz = Tz; E deÿned by
1 1 m m
Tz = (z|y1 ; : : : ; yrd | : : : |y1 ; : : : ; yrm ); (19)

where yik ∈ Rd and yik = 0 if ik = 0, one says that E is of tree structure if for each ik = 1; k ¿ 1,
k’1 k’1
there exists a unique j = j(i) such that j = 1. j is called the predecessor of ik . Moreover, the
edges of the tree connect only at a vertex and its predecessor. Note that this deÿnition of a tree is
more restrictive than the usual deÿnition of a tree in graph theory.
The trees used here will be speciÿed by their maximal chains. A sequence =(i1 ; : : : ; ik ) is called a
chain in the tree structure E, if i11 =· · ·= ikk =1, where for each j; 16j6k ’1; ik is the predecessor
of i+1 . It is called a maximal chain if its last vertex ikk is not the predecessor of another element
in E.
Let be a chain of Tz , ( ∈ Tz ). Deÿne
y = yi11 · · · yikk ; ( )=k (20)
and the di erential operator
Dy ( ) = Dyi1 · · · Dyik : (21)
1 k

The chain and the diagram Tz deÿne a product of directional derivatives.
To deÿne Hermite interpolation at a point z, we choose a tree Tz with the additional property that
every vertex of Tz is connected to the root z by exactly one chain. Then Hermite interpolation at
the point z is deÿned to be the interpolation of all of the functionals
Dyi1 · · · Dyik f(z) (22)
1 k

associated to the vertices of the tree via the unique chain connecting that vertex to the root. One of
the important characteristics of this deÿnition is that there are no gaps in the chains of increasing
orders of derivatives. Hermite interpolation at nodes z1 ; : : : ; zm would be interpolating the functionals
R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201 175

of Eq. (22) for trees Tz1 ; : : : ; Tzm by polynomials from n . It is assumed that the number of functionals
interpolated equals the dimension of the interpolating space.
By restricting the directions yj to the coordinate directions and choosing the tree appropriately,
one may obtain Hermite interpolation of total degree.
Another special case is denoted by Hermite interpolation of coordinate degree. To motivate this
second type, let us look at Lagrange interpolation on a node set which forms a rectangular grid in
R2 . Let x1 ¡ x2 ¡ · · · ¡ x n1 +1 and y1 ¡ y2 ¡ · · · ¡ yn2 +1 be points in R. It seems natural to measure
the values of a function on the rectangular grid
Z = {(xi ; yj ) | 16i6n1 + 1; 16j6n2 + 1}: (23)
Now let us interpolate these values. Which space of polynomials ÿts this grid? Surely not some n !
Instead, we introduce the space of polynomials (n1 ;:::;nd ) of coordinate degree (n1 ; : : : ; nd ).
It is convenient to ÿrst introduce more general polynomial spaces of which the space of poly-
nomials of total degree will be a special case. Let A ‚ Nd . Then the polynomial space A is
deÿned by
± 
 
aj z j
= : (24)
 

d d
For example, we recover the space in the form = with
n n

A = {j ∈ Nd | |j|6n}:
Now the space of polynomials of coordinate degree (n1 ; : : : ; nd ) is with
(n1 ;:::;nd )

A = {j ∈ Nd | 06ji 6ni ; i = 1; : : : ; d}: (25)
For Lagrange interpolation on the grid (23), at least, (n1 ;:::;nd ) is the right space. Lagrange interpo-
lation on the grid (23) with polynomials from (n1 ;:::;nd ) is regular.
This motivates the deÿnition of Hermite interpolation of coordinate degree: Let a positive integer
m; d-tuples of non-negative integers (n1 ; : : : ; nd ); kq = (kq; 1 ; : : : ; kq; d ) for q = 1; : : : ; m, a node set
Z = {z1 ; : : : ; zm }; zq ∈ Rd and a set of values cq; be given. Find a P ∈ (n1 ;:::;nd ) with

D P(zq ) = cq; 06 i 6kq; i ; 16i6d; 16q6m: (26)
The numbers n and kq are assumed to satisfy
d m d
(ni + 1) = (kq; i + 1): (27)
i=1 q=1 i=1

If we interpolate the same derivatives at each node, then we have uniform Hermite interpolation of
type either total or coordinate degree. Of course, (7) and (27) are to be satisÿed with all kq equal.

3.2. Everywhere regular schemes

In this subsection, we will consider those interpolation schemes which are regular for any location
of the nodes. For Hermite interpolation of type either total or coordinate degree, this is only the
case if there is only one node in the interpolation, Z = {z}. Such interpolations are called Taylor
176 R.A. Lorentz / Journal of Computational and Applied Mathematics 122 (2000) 167“201

interpolations. Then there is a one-to-one correspondence between the partial derivatives to be in-
d d
terpolated (at z) and the monomial basis of n , respectively (n1 ;:::;nd ) : D ” z . The Vandermonde
matrix based on the monomial basis of the polynomial space, say in the lexicographical ordering,
with the derivatives taken in the same order is an upper triangular matrix with the non-zero diagonal
entries !. So the determinant never vanishes. We have proved that Taylor interpolation is regular
for any choice of the node.
It is, in fact, the only such multivariate Hermite interpolation, see [28].

Theorem 2. In Rd ; d¿2; the only Hermite interpolation of type total or coordinate degree; which
is regular for all choices of the nodes; is Taylor interpolation.

This theorem is also true for more general polynomial spaces. The most general form I know is by
Jia and Sharma, [24]. To formulate it, we need some terminology. Let V ‚ d be a ÿnite-dimensional
space of polynomials. V is said to be scale invariant if P(az) ∈ V for any a ∈ R and any P ∈ V .
Also, for any polynomial P = j aj z j , the di erential operator P(D) is deÿned by

aj D j f:
P(D)f = (28)

Now let Z be a node set. To each zq ∈ Z, let there be associated a ÿnite-dimensional space of
polynomials Vq ‚ d . We choose any bases Pq; 1 ; : : : ; Pq; r(q) of Vq ; q = 1; : : : ; m (then r(q) = dim Vq ),
values cq; i and a set A ∈ Nd . The Abel-Goncharov interpolation problem is to ÿnd a polynomial
Q ∈ A (recall deÿnition (24)) satisfying
Pq; i (D)Q(zq ) = cq; i ; 16i6r(q); q = 1; : : : ; m: (29)
The choice of the bases does not a ect the regularity of the interpolation.

Theorem 3. Using the above notation; let V; Vq ; q = 1; : : : ; m, be scale invariant. Then Abel-
Goncharov interpolation (29) is regular for any node set if
V= Vq : (30)


. 40
( 83 .)