Theorem 4. Let A ‚ Nd . Let Aq ‚ A; q = 1; : : : ; m; V = A ; Vq = Aq ; q = 1; : : : ; m. Then Abel“

0

Goncharov interpolation (29) is regular for any node set Z if and only if A is the disjoint sum of

the Aq ; q = 1; : : : ; m.

d

This theorem implies Theorem 2. For example, for Hermite interpolation of type total degree, n =

d

A with A = {j | j ∈ N0 ; |j|6n} while the derivatives to be interpolated derive from the polynomial

spaces Vq = Aq with Aq = {j | j ∈ Nd ; |j|6kq }. The same holds for Hermite interpolation of type

0

coordinate degree. It also includes a similar theorem for multivariate Birkho interpolation.

In view of the these results, Jia and Sharma formulated the conjecture

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

Conjecture 5. Let V and {Vq }m be scale-invariant subspaces of d

such that

q=1

m

Vq ‚ V:

q=1

Then Abel-Goncharov interpolation (29) is regular if and only if (30) holds.

3.3. A.e. regular Hermite interpolation of type total degree in R2

From the previous section, we have seen that multivariate Hermite interpolation can, except for

some very special cases, be at most regular for almost all choices of nodes. We denote this as

being regular a.e. Not too much is known about even a.e. regular Hermite interpolation of type total

degree. Gevorkian et al. [16] have proven

Theorem 6. Bivariate Hermite interpolation of type total degree (8) is regular a.e. if there are at

most 9 nodes with kq ¿1.

Sauer and Xu [38] have proven

Theorem 7. Multivariate Hermite interpolation of type total degree (8) in Rd with at most d + 1

nodes having kq ¿1 is regular a.e. if and only if

kq + kr ¡ n

for 16q; r6m; q = r.

The authors of Theorem 6 have also considered Hermite interpolation of type total degree from

the point of view of algebraic geometry. These results will be discussed in Section 6. A conjecture

due to them and Paskov [18,34], simultaneously does ÿt in here. Let us use the stenographic notation

N = {n; s1 ; : : : ; sm } to stand for Hermite interpolation of type total degree on m nodes interpolating

derivatives of order up to kq = sq ’ 1 at zq by bivariate polynomials of degree n. We are using

the standard notation of algebraic geometry here, working with orders of singularities sq . Also, we

will not be much concerned about the node set Z, since we are only interested in regularity a.e.

In addition, we allow an sq to be 0. This just means that there is no interpolation condition at that

node. We also do not demand that the condition (7) requiring that the number of degrees of freedom

in the interpolation space equals the number of functionals to be interpolated, holds.

With this freedom, we do not have interpolations n the strict sense of Equation 2 any more, so

let us just call them singularity schemes. We introduce addition among singularity schemes just by

vector addition. If N = {n; s1 ; : : : ; sm } and R = {r; t1 ; : : : ; tm }, then

N + R = {n + r; s1 + t1 ; : : : ; sm + t1 }: (31)

We can add singularity schemes of di erent lengths by introducing zeros in the shorter of them.

2

The relevance of this addition is that if Q1 ∈ n satisÿes the homogeneous interpolation conditions

2

of N and if Q2 ∈ r satisÿes the homogeneous interpolation conditions of R, where N and R

2

are of the same length and refer to the same nodes, then Q1 Q2 ∈ n+r satisÿes the homogeneous

interpolation conditions of N + R,

The conjecture is

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

Conjecture 8. Let N correspond to a Hermite interpolation of type total degree (that is condition

(7) holds). Then N is singular if and only if there are schemes Ri = {ri ; ti; 1 ; : : : ; ti; m }; =1; : : : ; p

satisfying

m

ri + 2 ti; q + 2

¿ ; i = 1; : : : ; p;

2 2

q=1

such that

p

N= Mi :

i=1

The su ciency part of this theorem is easy to see. There are always nonzero polynomials Qi

satisfying the homogeneous interpolation conditions of Ri , i = 1; : : : ; p, since each of them can be

found by solving a linear system of homogeneous equations with less equations than unknowns.

p 2

By the above remark, i=1 Qi ∈ n is a nonzero polynomial satisfying the homogeneous conditions

for N.

We have already seen an example of this. It is our favorite singular Hermite interpolation: the

interpolation of ÿrst derivatives at two nodes in R2 by polynomials from 2 . In the notation used

2

here, this is the singularity scheme N = {2; 2; 2}. It can be decomposed as N = R + S, with

R = S = {1; 1; 1}. More singular Hermite interpolations constructed using this idea can be found in

[34; 28 Chapter 4].

There are essentially no other results for the a.e. regularity of general Hermite interpolation of

total degree. More is known for uniform Hermite interpolation of total degree. The results which

follow can be found in [38,28].

The simplest case of uniform Hermite interpolation is, of course, Lagrange interpolation in which

2

partial derivatives of order zero are interpolated at each node. The number of nodes in dim n for

some n and it is regular a.e.

The next case is when all partial derivatives up to ÿrst order are interpolated at each node.

Condition (7) is then

n+2 1+2

=m = 3m: (32)

2 2

This equation has a solution for n and m if and only if n = 1; 2 mod 3.

Theorem 9. For all n with n = 1; 2 mod 3; bivariate uniform Hermite interpolation of type total

degree interpolating partial derivatives of order up to one is regular a.e.; except for the two cases

with n = 2 (then m = 2) and n = 4 (then m = 5). The two exceptional cases are singular.

Note that our favorite singular Hermite interpolation is included. The smallest non-Taylor a.e.

regular case is for n = 5. The interpolation is then on 7 nodes.

The method of the proof of this and the following two theorems is to show that the Vandermonde

determinant does not vanish identically by showing that one of its partial derivatives is a nonzero

constant. The technique used to show this is the “coalescence” of nodes and, roughly speaking, tries

to reduce the number of nodes of the interpolation until a Taylor interpolation is obtained.

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

If all partial derivatives up to second order are interpolated at each node, condition (7) becomes

n+2 2+2

=m = 6m: (33)

2 2

This equation has a solution for n and m if and only if n = 2; 7; 10; 11 mod 12.

Theorem 10. For all n with n = 2; 7; 10; 11 mod 12; bivariate uniform Hermite interpolation of type

total degree interpolating partial derivatives of order up to two is regular a.e.

The smallest non-Taylor a.e. regular case is for n = 7. The interpolation is then on 12 nodes.

For third derivatives, we must have n = 3; 14; 18; 19 mod 20.

Theorem 11. For all n with n=3; 14; 18; 19 mod 20; bivariate uniform Hermite interpolation of type

total degree interpolating partial derivatives of order up to three is regular a.e.

The smallest non-Taylor a.e. regular case is for n = 14. The interpolation is then also on 12 nodes.

For related results from algebraic geometry, see Section 6.

3.4. A.e. regular bivariate Hermite interpolation of type coordinate degree in R2

No theorems about the a.e. regularity of general Hermite interpolation of type coordinate degree

in Rd , as deÿned in (26), are known except for the relatively simple one given at the end of this

subsection. But there are a few things known of the uniform case. If we want to interpolate all

2

partial derivatives of order up to k1 in x and to k2 in y from (n1 ;n2 ) , then

(n1 + 1)(n2 + 1) = m(k1 + 1)(k2 + 1) (34)

must hold. The proofs of the the following theorems, all of which can be found in [28], are based

on the same techniques as for the theorems on a.e. regularity of uniform Hermite interpolation of

type total degree in the previous subsection.

Theorem 12. If (34) is satisÿed; and either k1 +1 divides n1 +1 or k2 +1 divides n2 +1; then bivariate

uniform Hermite interpolation of type coordinate degree interpolating all partial derivatives of

2

order up to k1 in x and to k2 in y from (n1 ;n2 ) is a.e. regular.

This is more general than tensor product interpolation, since there one would have that both k1 + 1

divides n1 + 1 and k2 + 1 divides n2 + 1. If n1 = n2 = n and k1 = k2 = k, which is a kind of (uniform)2

Hermite interpolation, then (34) forces k to divide n and we have

Corollary 13. Bivariate uniform Hermite interpolation of type coordinate degree interpolating all

2

partial derivatives of order up to k in x and in y from (n1 ;n2 ) is a.e. regular.

This corollary also holds in Rd , but theorems like Theorem 12 in Rd require much more restrictive

assumptions.

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

As for uniform Hermite interpolation of type total degree, interpolations involving only lower

order derivatives can be taken care of completely.

Theorem 14. For all combinations; except two; of k1 ; k2 with 06k1 ; k2 62 and n1 ; n2 with

06k1 6n1 ; 06k2 6n2 satisfying (34); uniform bivariate Hermite interpolation of type coordinate

2

degree interpolating all partial derivatives of order up to k1 in x and to k2 in y from (n1 ;n2 ) is

2

a.e. regular. The two exceptional cases are k1 = 1 and k2 = 2 from (2; 3) and the corresponding

interpolation with x and y interchanged. These are singular.

This theorem includes cases Theorem 12 does not cover. For example, interpolating partial deriva-

2

tives of ÿrst order in x and second order in y at each of eight nodes from (8; 3) is regular a.e. But

Theorem 12 does not apply since neither 2 divides 9 nor does 3 divide 4.

We conclude this subsection with a theorem on non-uniform interpolation.

Theorem 15. A bivariate Hermite interpolation of type coordinate degree interpolating all partial

2

derivatives of order up to kq; 1 in x and to kq; 2 in y at zq ; q = 1; : : : ; m from (n1 ;n2 ) is a.e. regular

if the rectangle (0; n1 + 1) — (n2 + 1) is the disjoint union of the translates of the rectangles

(0; kq; 1 + 1) — (kq; 2 + 1) q = 1; : : : ; m.

This theorem does not hold in Rd for d¿3.

3.5. Singular Hermite interpolations in Rd

The general trend of the results of this subsection will be that a Hermite interpolation in Rd will

be singular if the number of nodes is small, typically m6d + 1. Of course, Taylor interpolations are

excepted. Also Lagrange interpolation by linear polynomials (m = d + 1) is excluded. The theorems

can all be found in [28,38].

Theorem 16. Hermite interpolation of type total degree in Rd ; d¿2; is singular if the number of

nodes satisÿes 26m6d + 1 except for the case of Lagrange interpolation which is a.e. regular.

Implicitly, condition (7) is assumed to be satisÿed.

The theorem includes our favorite singular Hermite interpolation. It is proved showing that the

interpolation restricted to a certain hyperplane is not solvable.

One application of this theorem is a negative result related to the construction of ÿnite elements.

The statement is that there is no ÿnite element interpolating all derivatives up to a given order (which

may depend on the vertex) at each of the vertices of a tetrahedron in Rd , d¿2, which interpolates

d

from a complete space, say n . The existence of such an element would have been desirable as it

would have combined the highest degree approximation, n + 1, and global continuity available for a

given amount of computational e ort.

For interpolation of type coordinate degree, we have

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

Theorem 17. Bivariate uniform Hermite interpolation of type coordinate degree interpolating all

2

partial derivatives of order k1 in x and to k2 in y at either two or three nodes from (n1 ;n2 ) is

singular unless either p1 + 1 divides n1 + 1 or p2 + 1 divides n2 + 1.

The exceptional cases are regular by Theorem 12.

Singular uniform Hermite interpolation schemes on more than d + 1 nodes in Rd are hard to ÿnd.

Here are some for uniform Hermite interpolation of type total degree due to Sauer and Xu [38].

Theorem 18. Uniform Hermite interpolation of type total degree interpolating all partial deriva-

tives of order up to k at each of m nodes in Rd by polynomials from n is singular if

d

(n + 1) · · · (n + d)

m¡ :

((n ’ 1)=2 + 1) · · · ((n ’ 1)=2 + d)

In R2 , the smallest example is covered by this theorem is the interpolation of all partial derivatives

of up to ÿrst order at each of 5 nodes by quartic polynomials.

3.6. Conclusions

We have seen that Hermite interpolation of either total or coordinate degree type is regular if

m = 1, is singular if there are not too many nodes and, for uniform Hermite interpolation of type

coordinate degree, there are no other exceptions if we are interpolating derivatives of order up to

one, two or three. Really general theorems for a.e. regularity of interpolations with arbitrarily high

derivatives are not known. The same holds for the results obtained by the methods of algebraic

geometry, as we will see in Section 6.

In this section, we have assiduously ignored one of the essential components of interpolation.

Most of the theorems of this section concerned a.e. regularity. To use these interpolations, one must

ÿnd concrete node sets for which the interpolations are regular. Only for Lagrange interpolation are

any systematic results are known. Otherwise, nothing is known. For this reason, special constructions

of interpolations which include the node sets, such as those in Sections 5 and 6, are of importance,

d

even if the interpolation spaces are not complete spaces n .

4. Alternatives to classical multivariate Hermite interpolation

4.1. Lifting schemes

Our extension of univariate to “classical” multivariate Hermite interpolation, namely to multivariate

Hermite interpolation of type total degree, has one glaring defect. It is not regular for any choice of

nodes. It is in fact possible to get rid of this unfavorable property, but alas, at a price. The method

to be introduced here, called “lifting”, yields a multivariate interpolation which is formulated exactly

as in the univariate case. In our context, it was introduced by Goodman [19] motivated by the ÿrst

special cases, those of Kergin [25], Hakopian [21] and of Cavaretta et al. [5]. For a more complete

survey, see the book [1] of Bojanov, Hakopian and Sahakian, or the thesis of Waldron [43] and the

references therein.