Lagrange interpolation from 1 at these nodes is regular. What does the least interpolant look like?

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

We have

ExpZ = span{e0 ; ex ; ey }

±

∞ ∞

xj yj

= (a + b + c) + bx + cy + b +c | a; b; c ∈ R

j! j!

j=2 j=2

so that

2

PZ = span{1; x; y} = 1:

If the nodes are collinear, say Z = {(0; 0); (1; 0); (2; 0)}, we get

ExpZ = span{e0 ; ex ; ey }

±

∞ j

x

= (a + b + c) + (b + 2c)x + (b + 4c)x2 + (b + 2j c) | a; b; c ∈ R

j!

j=3

so that

PZ = span{1; x; x2 };

which is the correct univariate space for Lagrange interpolation on three nodes on a line.

d

For the general case, we require that the functionals Fq be of the form P(D)(zq ), where P ∈

is a polynomial and zq ∈ Rd . Then the formal power series associated with a functional F is

∞

F(y j ) j

y·z

gF (z) = F(e ):= z:

j!

|j|=0

The power series is called formal, since there is no convergence assumption. For the point evaluation

functional F(f) = f(zq ), we get gFq (z) = ez·zq .

Now we can write down the interpolation space matching the functionals {Fq }

d

Theorem 26. Let F = {F1 ; : : : ; Fm } be functionals deÿned on . Let

GF = span{gF1 ; : : : ; gFm }

and

PF = span{g“ | g ∈ GF }:

Then for any values cq , q = 1; : : : ; m; there is exactly one p ∈ PF with

Fq (P) = cq ; q = 1; : : : ; m:

As an example, let us take our favorite singular Hermite interpolation. The functionals are evalu-

ation of function values and the two ÿrst partial derivatives at z1 and z2 . To simplify computations,

we take Z = {(0; 0); (1; 0)}.

To evaluate the power series, we use

@ xxq +yyq

= xez·zq ;

e

@x

@ xxq +yyq

= yez·zq ;

e

@y

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

so that the power series are

e0 ; xe0 ; ye0 ; ex ; xex ; yex :

Doing the calculation as above, we get

PF = span{1; x; y; x2 ; xy; x3 }:

You can check for yourself that our Hermite interpolation from this space is regular. If we had taken

nodes not lying on the coordinate axes, PF would no longer have a monomial basis.

Now that we have seen that it is relatively easy to construct the least interpolant, let us see what

we are buying. By construction, we can now carry out Lagrange interpolation on any number of

d

nodes without worrying whether the number matches a dim n . Other good properties of the least

Lagrange interpolation on Z are that one can show that one has a ne invariance in the sense that

PaZ+z0 =PZ , for any real a and z0 ∈ R. Also one has transformation rules as for a change of variables:

if A is a nonsingular d — d matrix, then PAZ = PZ · AT .

One of its most important properties is that the least interpolant is degree reducing. From this, it

d d

follows that if Lagrange interpolation on Z is regular for some complete space n , then PZ = n .

Formulating this di erently, if Z ‚ Rd ; m = dim n for some j and the functionals are the point

d

d

evaluation functionals, then PZ = n a.e., since Lagrange interpolation is regular a.e.

This raises the question of the behavior of the spaces PZ when Z changes or what happens to

PZ when two nodes coalesce. If two of the nodes coalesce along a straight line, it can be shown

that the least Lagrange interpolant converges to the Hermite interpolant which replaces one of the

functional evaluations at the coalesced node with the directional derivative in the direction of the

line.

d

But the ÿrst question does raise some computational issues. If m = dim n for some j, then the set

of Z for which PZ = n is open in Rdm . If Z moves to a location in which Lagrange interpolation

d

is singular, PZ must change discontinuously. Thus, around this location, computation of a basis for

PZ is unstable. This is not to say that classical polynomial interpolation is better in this regard.

It is even worse: the interpolant just does not exist for those Z. That this problem can be solved

computationally is show by de Boor and Ron in [9]. They have have also developed a MATLAB

program implementing these ideas.

5. Explicit interpolation schemes

5.1. Introduction

In this section, we will discuss two types of interpolation schemes. The ÿrst is to ÿnd concrete

locations of points for which classical Lagrange interpolation is regular. The second is to construct

Hermite interpolations, including the node sets, guaranteed to be regular. These are usually not of

the classical type, but they have certain advantages. For example, some of them can be computed

in a Newton like way.

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

5.2. Explicit Lagrange interpolation schemes

Chung and Yao, [6], give a quasi-constructive description of locations of nodes in Rd for which

Lagrange interpolation is regular. They satisfy the

Deÿnition 27. A node set Z = {z1 ; : : : ; zm } ‚ Rd with m = dim n for some n is said to satisfy the

d

General Condition if to each node zq , there exist n hyperplanes Hq; 1 ; : : : ; Hq; n such that

(a) zq does not lie on any of these hyperplanes,

(b) all other nodes lie on at least one of them.

A node set satisfying the general condition is said to be a natural lattice. It can easily be shown

d

that Lagrange interpolation from n on a natural lattice is regular since the n functions

n

i=1 Hq; i (z)

q (z):= n

i=1 Hq; i (zq )

are Lagrange fundamental functions. Here Hq; i (z) = 0 are the hyperplanes required by the General

Condition. This is very much in the spirit of the univariate construction in Eq. (14). This idea has

been extended to Hermite interpolation by Busch, see [4].

Finding regular Lagrange interpolations via natural lattices is not really constructive. It is actually

just a su cient condition for regularity. However, it has been the motivation for several explicit

constructions. Let us ÿrst look at triangular arrays

Zn := {j | j ∈ Nd ; |j|6n}:

d

0

d

With a little bit of work, one can convince oneself that each Zn satisÿes the general condition (do

not forget the hyperplanes perpendicular to the direction (1; : : : ; 1)!)

A nicer example in R2 , worked out in great detail by Sauer and Xu, [39], starts with 2r + 1

points equi-distributed on the circumference of the unit disk. We number the points z1 ; : : : ; z2r+1 and

connect zq with zq+r by a straight line. Here, q + r is taken modulo 2r + 1. Let Z (r) be the set of

intersections of these lines within and on the circumference of the circle. Then it can be shown that

Theorem 28. The node set Z (r) described above contains exactly r(2r + 1) = dim 2r’1 points. It

2

is a natural lattice and; consequently; Lagrange interpolation on Z (r) from 2r’1 is regular.

2

Due to the concrete location of the nodes, they lie on r concentric circles, Sauer and Xu are able

to give compact formulas for the fundamental functions and a point-wise bound for the error of the

interpolant. Bos [2] has some similar constructions which we discuss in Section 4.

Now, let us look at a really constructive approach to Lagrange interpolation given by Gasca and

Maeztu [11]. Let there be given n + 1 distinct lines ˜i (z) = 0; i = 0; : : : ; n. To each line ˜i , we

associate lines ˜i; j ; j = 0; : : : ; r(i) each of which intersect ˜i at exactly one point zi; j . In addition,

it is assumed that the node zi; j does not lie on any of the lines ˜0 ; : : : ; ˜i’1 ; 16i6n. Sets of lines

satisfying these conditions are called admissible.

We set

Z = {zi; j |06j6r(i); 06i6n}: (41)

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

Now we must deÿne the space from which we will interpolate. Let

P0; 0 (z) = 1; (42)

P0; j (z) = ˜0; 0 · · · ˜0; j’1 (z); 16j6r(0); (43)

Pi; 0 (z) = ˜0 · · · ˜i’1 (z); 16i6n; (44)

Pi; j (z) = ˜0 · · · ˜i’1 (z)˜i; 0 · · · ˜i; j’1 (z); 16j6r(i); 16i6n: (45)

Then we set

V = span{Pi; j | 06j6r(i); 06i6n}: (46)

Theorem 29. Lagrange interpolation on Z given by (41) from V given by (46) is regular.

How to prove this theorem becomes clear once we recognize that (42) and the following equations

can be given recursively by

Pi; 0 (z) = Pi’1; 0 (z)˜i’1 (z); 16i6n;

Pi; j (z) = Pi; j’1 (z)˜i; j’1 (z); 16j6r(i); 16i6n:

If we order the nodes of Z lexicographically, that is (i; j) ¡ (i ; j ) if i ¡ i or if i = i , then j ¡ j ,

it is easy to see from the above recursive construction that

Pi ; j (zi; j ) = 0 if (i; j) ¡ (i ; j ):

If Z is admissible, Pi; j (zi; j ) = 0. Thus the interpolant can be constructed exactly as in the univariate

Newton construction of Section 2.1.

Many people have considered the special case that the lines ˜i are taken parallel to the x-axis.

Then the lines ˜i; j can be taken parallel to the y-axis.

What does the interpolation space look like? First, we must note that many di erent admissible

choices of lines can lead to the same node set. Thus we can have many di erent spaces for the same

functionals. In one special, but very important case, V is independent of the lines. This is the case

2

when we would like to have V = n for some n. To achieve this, we choose r(i) = n ’ i, 06i6n

2

and the lines so that the admissibility condition is satisÿed. Then dimV = dim n . But, by Theorem

29, all the polynomials in (42) are linearly independent and, from (42), it can be seen that each of

2

them is of degree not exceeding n. Thus V = n as desired, independently of the choice of lines.

Comparing their results with those of Chung and Yao, Gasca and Maeztu have made the conjecture.

Conjecture 30. Let Z be a natural lattice in R2 for some n. Then one of the lines involved in the

deÿnition of the general condition contains exactly n + 1 nodes of Z.

Note that no line can contain more that n + 1 nodes, since then Lagrange interpolation will not

be regular.

If the conjecture were true, then we could remove those n + 1 nodes obtaining a smaller node set

(1) 2

Z , which satisÿes the general condition with respect to n’1 . Continuing in this way, we could

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

conclude that any natural lattice is a special case of the above construction of Gasca and Maeztu

2

for obtaining interpolation spaces with V = n .

Gasca and Maeztu™s construction has a straightforward generalization to Rd , leading to a Newton

formula for Lagrange interpolation in Rd . Their method also includes Hermite interpolation. This

will be presented in the following subsection.

The ÿnal type of construction we mention here can be subsumed under the concept of “Boolean

sum”. A detailed exposition of this class of constructions, which can also be used for trigonometric

polynomials, can be found in a book by Delvos and Shempp [10].

The simplest example of such interpolations is called Biermann interpolation. It is based on

univariate interpolation and the boolean sum of two commuting projectors. Let L and M be two

commuting projectors. Then their boolean sum L • M is given by

L • M = L + M ’ LM:

The projectors we use are those of univariate Lagrange interpolation

n+1

(Ln f)(x) = f(xq ) q; n (x) for f ∈ C(R); (47)

q=1

1

where q; n are the Lagrange fundamental functions for interpolation from n on X = {x1 ; : : : ; x n+1 }.

These projectors are extended to C(R2 ) by just applying them to one of the variables

n+1

for f ∈ C(R2 ):

(Ln f)(x; y) = f(xq ; y) q; n (x) (48)

q=1

By Ms , we denote the same projector, but now applied to the y variable and based on the node set

Y = {y1 ; : : : ; ys+1 }. Then Ln and Ms commute and

n+1 s+1

for f ∈ C(R2 ):

(Ln Ms f)(x; y) = f(xp ; yq ) p; n (x) q; s (y)

p=1 q=1

Choose now increasing integer sequences 16j1 ¡ · · · ¡ jr ; 16l1 ¡ · · · ¡ lr and nodes X = {x1 ; : : : ;

xjr +1 }; Y = {y1 ; : : : ; ylr +1 }. Then the Biermann projector is deÿned by

Br = Lj1 Mlr • Lj2 Mlr’1 • · · · Ljr Ml1 : (49)

The interpolation space is deÿned similarly

V= + + ··· (jr ;l1 ) : (50)

(j1 ;lr ) (j2 ;lr’1 )