polynomial Pj ∈ which interpolates the ÿrst j values, We take

j’1

j

Qj+1 (z) = (z ’ zq ):

q=1

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

1

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

q’1

m

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

2

of linear polynomials 1 is spanned by 1, x and y and thus has dimension 3, while the space of

2

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.

2

Now let us try Lagrange interpolation on three nodes Z = {z1 ; z2 ; z3 }. We choose V = 1 , so that

2

(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

d

q=1

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,

2

i.e., polynomials from 2 . Note that the condition (2) is satisÿed. There are 6 functionals to be

2

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

k

where = 1 or 1, and a diagram Tz = Tz; E deÿned by

i

1 1 m m

Tz = (z|y1 ; : : : ; yrd | : : : |y1 ; : : : ; yrm ); (19)

d

1

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

k+1

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

d

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.

k

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)

2

Now let us interpolate these values. Which space of polynomials ÿts this grid? Surely not some n !

d

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

0

deÿned by

±

aj z j

= : (24)

A

j∈A

d d

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

A

n n

A = {j ∈ Nd | |j|6n}:

0

d

Now the space of polynomials of coordinate degree (n1 ; : : : ; nd ) is with

A

(n1 ;:::;nd )

A = {j ∈ Nd | 06ji 6ni ; i = 1; : : : ; d}: (25)

0

d

For Lagrange interpolation on the grid (23), at least, (n1 ;:::;nd ) is the right space. Lagrange interpo-

d

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

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)

j

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

0

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

m

V= Vq : (30)

q=1