Here the sum of two subspaces U and V is deÿned by U + V = {u + v | u ∈ U; v ∈ V }.

Theorem 31. Lagrange interpolation from V given in (50) on the node set

Z = {(xi ; yj ) | 16i6jm + 1; 16j6lr+1’m + 1; 16m6r}

is regular. The interpolation is given explicitly by

(Br f)(x; y) = f(xi ; yj )

where Br is the Biermann projector (49).

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

The interpolation space has a monomial basis, so if we write V = A, then A resembles (optically)

the node set. Both have the same cardinality

r

(km + 1)(lr+1’m ’ lr’m ):

m=1

The special case that km = lm = m ’ 1 for m = 1; : : : ; r + 1 turns out to be the Lagrange interpolation

2

from r on the triangular array given in Section 2.2. The Biermann projector is deÿned similarly

in higher dimensional euclidean spaces.

One of the nice features of these kinds of interpolations is that the error of interpolation can be

expressed as a product of the univariate errors.

5.3. Explicit Hermite interpolation schemes

Gasca and Maeztus technique for Lagrange interpolation given in the previous subsection can be

used to obtain Hermite interpolation simply by dropping the assumption the lines need be distinct,

and that the intersection zi; j of ˜i and ˜i; j not lie on any of the lines “preceding” it in the sense

mentioned in the previous subsection. The deÿnition of the interpolating space remains the same as

before (42), (46), but with the lines repeated according to their multiplicities. But the functionals to

be interpolated change. This is to be Hermite interpolation after all. To describe them, we use the

notation previously introduced. Let ti be lines orthogonal to ˜i and ti; j be lines orthogonal to ˜i; j .

We deÿne the numbers

±

0 if j = 0;

ai = the number of lines among (51)

{˜0 ; : : : ; ˜i’1 } coincident with ˜i if 16i6n;

±

0 if i = 1;

the number of lines among

bi = (52)

{˜0 ; : : : ; ˜i’1 } that contain zi; j if 16i6n;

±

0 if j = 0;

the number of lines among

ci; j = (53)

{˜i; 0 ; : : : ; ˜i; j’1 } that contain zi; j if 16j6r(i):

The functionals to be interpolated are

b +ci; j

Di; j f = Dtaii Dti;ij f(zi; j ); 16i6n; 16j6r(i); (54)

where, as before, Dt f is the directional derivative of f in the direction t.

Theorem 32. The interpolation of the functionals (54) from the space spanned by the polynomials

(42) is regular.

For another approach which yields regular interpolation schemes similar in avor to those just

d

discussed, see Gevorkian et al. [17]. There V = n and they obtain their interpolation conditions by

projections onto the intersection of families of hyperplanes.

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

If we start with a Hermite interpolation, then it seems clear that one obtains another by subjecting

all components, the node set and the interpolation space to an a ne transformation. This was carried

out systematically by Gasca and Muhlbach in [12“14]. There starting with a node set lying on a

Cartesian grid, they apply projectivities to obtain new schemes. For these new schemes, one can

ÿnd Newton-type interpolation formulas and formulas for the error of interpolation resembling the

univariate ones. These projectivities allow mapping “ÿnite” points to “inÿnity” and thus one can

obtain nodes lying on pencils of rays. This extends an approach used by Lee and Philips [26].

5.4. Node sets on algebraic varieties

The interpolation schemes presented in the previous subsections were very much concerned with

lines and hyperplanes. In this subsection, we look at Lagrange interpolation on node sets restricted

to algebraic varieties. The presentation is taken from Bos [2]. By algebraic variety or algebraic

manifold, we mean sets of the form

W = {z ∈ Rd | P(z) = 0; P ∈ P}; (55)

d

. Given a point set E ‚ Rd , the ideal IE associated

where P is a collection of polynomials from

with E is

d

IE = {P ∈ | P(z) = 0; z ∈ E}: (56)

If E is a variety, then we say that IE is the ideal of the variety. An ideal is called principal if there

is a Q ∈ d such that

d

I = {PQ | P ∈ }: (57)

Finally, given a point set E ‚ Rd ,

Nnd (E) = dim( d

n |E ):

Much of the following is based on the

Lemma 33. Let W be an algebraic variety whose ideal IW is principal being represented by the

polynomial Q. Then

n+d n ’ deg Q + d

Nnd (W ) = ’ :

d d

d

In the following, we ÿx n, d and want to interpolate from n .

Let W1 ; : : : ; WN be algebraic varieties whose ideals are principal and are represented by the poly-

nomials Q1 ; : : : ; QN having degrees n1 ; : : : ; nN . Assume that these polynomials are pairwise relatively

prime and, in addition,

n1 + · · · + nN ’1 ¡ n; (58)

n1 + · · · + nN ¿n : (59)

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

Set si = n ’ n1 ’ · · · ’ ni’1 and let Zi be an arbitrary set of Nsd points on Wi , i = 1; : : : ; N such that

i

all of these points are distinct. If n1 + · · · + nN ¿ n, set

N

Z= Zi (60)

i=1

and if n1 + · · · + nN = n, put

N

Z= Zi ∪ {a}; (61)

i=1

d

where a does not lie on any of the Wi . With this choice, there are always a total of dim n nodes

in Z.

The reason for choosing the nodes this way is that the regularity of Lagrange interpolation on Z

can be decomposed to the Lagrange regularity on each of the varieties.

d

Theorem 34. Let Z; Zi ; i = 1; : : : ; N; be chosen as above. If Lagrange interpolation from si |Wi on

d

Zi is regular for i = 1; : : : ; N; then Lagrange interpolation from n on Z is regular.

This theorem is proved by repeated application of Lemma 33.

For a simple example of this technique, we consider varieties which are concentric circles in R2 .

Take distinct radii Ri ; i = 1; : : : ; N; and

Wi = {(x; y) | x2 + y2 = R2 }:

i

Then each IWi is a principal ideal with Pi = x2 + y2 ’ R2 , so ni = 2. We ÿx n and want to interpolate

i

2

from n . By (58) and (59), we must choose N = [(n + 1)=2], where [a] is the integer part of a.

Then n1 + · · · + nN ¿ n if n is odd and n1 + · · · + nN = n if n is even. It follows that si = n ’ 2(i ’ 1)

and that, by Lemma 33, that

si + 2 si ’ 2 + 2

Nsd (Wi ) = ’ = 2si + 1:

2 2

i

But Lagrange interpolation by algebraic polynomials of degree si on 2si +1 nodes on a circle centered

at the origin is the same as interpolation by trigonometric polynomials of the same degree, which

is regular. So taking an additional point (0; 0) in n is even, Theorem 34 allows us to conclude that

d

Lagrange interpolation from n on a node set consisting of 2n ’ 4i + 5; i = 1; : : : ; N nodes lying

respectively on N = [(n + 1)=2] concentric circles, is regular.

The Lagrange interpolation by Sauer and Xu mentioned in Section 5.2 is also has its nodes lying

2

on concentric circles. In that construction, there are r(r + 1) nodes when interpolating from 2r’1 .

These nodes are distributed over r circles, with r + 1 nodes on each of them. In the example of Bos,

the number of nodes on the circles di ers from circle to circle, but their location on the circles can be

chosen at will. Another di erence is that the circles given by Sauer and Xu have the predetermined

radii

cos j =(2j + 1)

Rj = ; j = 1; : : : ; r:

cos r =(2j + 1)

Despite the resemblance, it does not seem that there is any connection between these schemes.

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

As we have seen in this and the previous section, the study of polynomial ideals is quite useful

for multivariate interpolation. More about them can be found in Moller [32,33], Xu [45] and the

references given in Section 4.

6. Related topics

6.1. Introduction

In this section, we will look at the theory of singularities, i.e., at the investigation of the set of

polynomials having zeros of given multiplicities. The last subject will be the results of Vassiliev on

the minimal dimension an interpolation space must have in order to be able to solve a Lagrange

interpolation for any choice of nodes.

6.2. Singularities

In concordance with the notation generally used, we will speak of singularities of a given order

of a function. A function f deÿned on Rd has a singularity of order s at z if

D f(z) = 0 for | | ¡ s:

On the other hand, we consider polynomials in euclidian and not in projective spaces, so that some

of our notation does di er for example from the survey paper of Miranda [31], from which some

of this material was taken. Let Z = {z1 ; : : : ; zm } be a set of nodes in Rd and {s1 ; : : : ; sm } ‚ Nd . Then

L(d) (’ m sq zq ) stands for the subspace of n of polynomials having a singularity of order sq at

d

n q=1

zq for q = 1; : : : ; m. L(d) (’ m sq zq ) could consist of just the zero polynomial or be very large,

n q=1

since there is no connection between the number of singularities and the degree of the polynomials.

The virtual dimension (d) of L(d) (’ m sq zq ) is

n n q=1

«

m m

d+n sq ’ 1

’ sq zq =

(d)

’ :

d d

n

q=1 q=1

d

Intuitively, if we take and subject it to the

n

m

sq ’ 1

d

q=1

conditions that the polynomials have the given singularities on Z, then we expect to reduce its

d

dimension by exactly this number, unless this number is larger than the dimension of n , in which

case, we expect to get dimension 0. Thus, we deÿne the expected dimension e(d) by

n

±

« «

m m

e(d) ’ sq zq = max 0; ’ sq zq :

(d)

n n

q=1 q=1

What does this mean for an interpolation scheme? There

m

d+n sq ’ 1

= ; (62)

d d

q=1

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

so that the expected dimension is always 0. If the true dimension is not 0, then there is a polynomial

d

in n which satisÿes the homogeneous interpolation conditions. Thus the interpolation is singular.

As we have seen from Theorem 2, for each Hermite interpolation (except the Taylor interpolation)

there are always node sets Z for which the dimension of L(d) (’ m sq zq ) is nonzero, i.e., for

n q=1

which the interpolation is singular. This is nothing special. On the other hand, it is a rather special

situation if the dimension of L(d) (’ m sq zq ) is always larger than the expected dimension. Thus

n q=1

we say that the system of homogeneous equations described by (n; s1 ; : : : ; sm ), whose solution yields

L(d) (’ m sq zq ) if solved for the node set Z, is special if

n q=1

« «

m m

inf dimL(d) ’ sq zq ¿ e(d) ’ sq zq : (63)

n n

Z

q=1 q=1

An example is the system (2; 2; 2), which is our favorite singular Hermite interpolation. It is special.

We have

«

2

inf dimL(2) ’ 2zq = 1

2