. 43
( 83 .)


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
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
= (a + b + c) + (b + 2c)x + (b + 4c)x2 + (b + 2j c) | a; b; c ∈ R
 

so that
PZ = span{1; x; x2 };
which is the correct univariate space for Lagrange interpolation on three nodes on a line.
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
gF (z) = F(e ):= z:

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 }

Theorem 26. Let F = {F1 ; : : : ; Fm } be functionals deÿned on . Let
GF = span{gF1 ; : : : ; gFm }
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 ;
@ xxq +yyq
= yez·zq ;
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
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
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
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

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

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
that Lagrange interpolation from n on a natural lattice is regular since the n functions
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}:
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

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

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
when we would like to have V = n for some n. To achieve this, we choose r(i) = n ’ i, 06i6n
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
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
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
(Ln f)(x) = f(xq ) q; n (x) for f ∈ C(R); (47)

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
for f ∈ C(R2 ):
(Ln f)(x; y) = f(xq ; y) q; n (x) (48)

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 )


. 43
( 83 .)