Multivariate Hermite interpolation by algebraic polynomials:

A survey

R.A. Lorentz

SCAI - Institute for Algorithms and Scientiÿc Computing, GMD - German National Research Center for Information

Technology, Schlo Birlinghoven, D - 53754 Sankt Augustin, Germany

Received 10 June 1999; received in revised form 15 February 2000

Abstract

This is a survey of that theory of multivariate Lagrange and Hermite interpolation by algebraic polynomials, which

has been developed in the past 20 years. Its purpose is not to be encyclopedic, but to present the basic concepts and

techniques which have been developed in that period of time and to illustrate them with examples. It takes “classical”

Hermite interpolation as a starting point, but then successively broadens the assumptions so that, ÿnally, interpolation of

arbitrary functionals and the theory of singularities from algebraic geometry is discussed. c 2000 Elsevier Science B.V.

All rights reserved.

Keywords: Multivariate Hermite interpolation; Algebraic polynomials; Lagrange; Least interpolation; Lifting schemes

1. Introduction

1.1. Motivation

This is a survey of interpolation by multivariate algebraic polynomials covering roughly the last

20 years.

Why should one study multivariate polynomials? Firstly of all, they are a building block of

surprisingly many numerical methods, most often locally. For example, ÿnite elements and splines,

both univariate and multivariate, are piecewise polynomials. Secondly, theorems on the quality of

approximation of functions or on the quality of a numerical scheme almost invariably reduce to local

interpolation by polynomials, even when the approximating functions, respectively the basis of the

numerical scheme is of another type. Take any modern textbook on numerical analysis. Except for

the part on linear algebra, polynomials are probably mentioned on every third or fourth page. Finally,

despite their fundamental importance for numerical methods, the theory of multivariate polynomial

0377-0427/00/$ - see front matter c 2000 Elsevier Science B.V. All rights reserved.

PII: S 0 3 7 7 - 0 4 2 7 ( 0 0 ) 0 0 3 6 7 - 8

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

interpolation is underdeveloped and there is hardly any awareness of the issues involved. Indeed,

there is hardly any awareness that basic questions are still unresolved.

The three reasons just given to motivate the study of polynomial interpolation are practically

oriented. But there is another reason to study polynomials: they are beautiful! Why is number

theory so appealing? Because it is beautiful. The objects studied, integers, are the simplest in all of

mathematics. I see polynomials as the next step up in the scale of complexity. They are also simple

and, again, they are beautiful!

This survey neither intends to be encyclopedic in that all of the newest results are mentioned

nor does it intend to be historic, in that it reports on the ÿrst occurence of any particular idea.

Instead, the main constructions and the basic ideas behind them will be presented. In addition, many

examples will be given. It is my hope that the reader will then understand what has been done

and be in a position to apply the methods. No proofs will be given, but often the ideas behind the

proofs. In addition, the references are mainly chosen according to how well they explain an idea or

survey a group of ideas and as to how useful their list of references is.

Most of the results obtained in multivariate interpolation have been obtained in the 30 years

surveyed here. The past 10 years have seen a new wave of constructive methods which show how

to construct the interpolants and which have been used to ÿnd new interpolation schemes. These

results are surveyed in detail by Gasca and Sauer in [15], which is also a survey of multivariate

interpolation in the same time period. For this reason, these techniques will not be discussed in very

much detail here. Rather links to [15] will be made wherever appropriate.

1.2. Interpolation

What is interpolation? In the most general case we will be considering here, we are given a normed

linear space Y , a ÿnite linear subspace V of Y , a ÿnite set of bounded functionals F = {Fq }m and

q=1

real numbers {cq }m . The interpolation problem is to ÿnd a P ∈ V such that

q=1

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

We will often abbreviate this formulation by saying that we interpolate the functionals F from V .

The interpolating element is called the interpolant.

The interpolation problem is called regular if the above equation has a unique solution for each

choice of values {cq }m . Otherwise, the interpolation is singular. In order that an interpolation be

q=1

regular, it is necessary that

dim V = m = the number of functionals: (2)

Often the values are given by applying the functionals to an element f of Y :

cq = Fq f; q = 1; : : : ; m: (3)

If so, the interpolation problem can be formulated in a somewhat di erent way, which we will have

cause to use later. Let G = span{Fq }m . Then G is an m-dimensional subspace of Y — , the dual of

q=1

Y . The interpolation problem (3) is equivalent to: given f ∈ Y , ÿnd a P ∈ V such that

FP = Ff for any F ∈ G: (4)

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

An example of all of the above is what I call “classical” Hermite interpolation. To describe it,

we ÿrst need some polynomial spaces:

±

d

aj z j | j ∈ Nd ; z ∈ Rd ; aj ∈ R :

= (5)

n 0

|j|6n

Here and in the following, we use multivariate notation: z = (x1 ; : : : ; xd ); j = (j1 ; : : : ; jd ); z j =

xij1 x22 · · · xdd for z ∈ Rd and j ∈ Nd . Moreover |j| = j1 + · · · + jd . The above space is called the

j j

0

space of polynomials of total degree n and will be our interpolation space V .

The functionals we interpolate are partial derivatives: given a set of distinct points {zq }m in Rd

q=1

and nonnegative integers k1 ; : : : ; km , our functionals are

Fq; f = D f(zq ); 06| |6kq ; 16q6m; (6)

where

@| |

D= :

@x11 · · · xdd

Since

d+n

d

dim =

d

n

and the number of partial derivatives (including the function value) to be interpolated at zq is

d + kp

;

d

we also require that

m

d+n d + kp

= : (7)

d d

q=1

“Classical” Hermite interpolation, or Hermite interpolation of total degree is thus the problem of

d

ÿnding a P ∈ n satisfying

D P(zq ) = cq; ; 06| |6kq ; 16q6m; (8)

d

for some given values cq . If all the kq = 0, then we have Lagrange interpolation: ÿnd P ∈ such

n

that

P(zq ) = cq ; 16q6m: (9)

d

Here, of course, m = dim n .

What determines which kind of of multivariate interpolation is the “right” or “most natural” one?

The simplest answer is to just look at the univariate case and ÿnd the most natural generalization.

That is how one arrives at the multivariate interpolation just described. But, as we shall see, there

are other perfectly good multivariate interpolations. For, while in the univariate case, the polynomial

1

interpolation space, namely n , is canonical, in the multivariate case, we have many polynomial

spaces of the same dimension. The derivatives we have chosen are in the direction of the coordinate

axes. See Section 3 for Hermite interpolations involving directional derivatives. Moreover, we will

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

see (in Section 4) that interpolating not point values of functions or their derivatives, but mean

values of them over line segments, triangles, etc., leads to interpolation schemes retaining many of

the properties of univariate interpolation.

Other criteria for the choice of the interpolation derive from the use to which the interpolant

is to be put. If, for example, the interpolant interpolates the values resulting from the application

of the functionals to a function, as in (3), then one would like to know how well the interpolant

approximates the function (in the norm of Y ). and tailor the interpolation accordingly. For exactly

this reason, there is a host of papers concerned with developing Newton like interpolations. Since

this aspect of polynomial interpolation will not be emphasized here, the reader can ÿnd them in the

survey paper by Gasca and Sauer [15], and in the papers by Sauer and Xu [37,38].

Often such interpolations allow more precise statements about the error of approximation. In

addition, these methods are numerically quite stable.

For ÿnite elements, other properties play an important role. Two of them are that the dimension

of interpolation space, V , be as small as possible to attain the desired global continuity and that the

d

interpolation spaces be a nely invariant. Consequently, V may not be a full space n for some n,

d d

d, but may lie between two such spaces n ( V ( n+1 . Many examples of such interpolations can

be found in [7].

As a last application which would require special properties from the interpolant, let me mention

cubature formulas. As in the univariate case, one method for constructing cubature formulas is to base

them on Lagrange interpolation at the zeros of orthogonal polynomials. Here the nodes are prescribed

and a polynomial space must be constructed so that interpolation at these nodes is regular. Again,

d

these spaces will, in general, not coincide with a n .

Of course, many nonpolynomial multivariate interpolation methods have benn developed. See [40]

for a survey on scattered data interpolation.

2. The issues involved

2.1. Univariate interpolation

Let us ÿrst look at univariate interpolation, since everything works well there. Given m distinct

points {zq }m in R1 and m real values {cq }m , there is one and only one polynomial P ∈ m’1 with

1

q=1 q=1

P(zq ) = cq ; q = 1; : : : ; m; (10)

i.e., the univariate Lagrange interpolation problem is regular for any set of nodes. The same is true

of univariate Hermite interpolation: Given a nodal set Z = {zq }m , integers kq and values cq; for

q=1

1

06 6kq and q = 1; : : : ; m, there is one and only one polynomial P ∈ n , where

m

n= (kq + 1) ’ 1; (11)

q=1

such that

D P(zq ) = cq; 06 6kq ; q = 1; : : : ; m; (12)

i.e., the univariate Hermite interpolation problem is regular for any nodal set and for any choice

of derivatives to be interpolated. A word of caution here. There is another type of univariate in-

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

terpolation, called Birkho interpolation, which interpolates derivatives but di ers from Hermite

interpolation in that gaps in the derivatives are allowed. In this theory, for example, one could

interpolate f(zq ) and f (zq ) but not f (zq ). Such interpolations are not necessarily regular. See [27]

for the univariate theory and [28] for the multivariate theory of Birkho interpolation.

How does one prove regularity? There are several ways. One method is constructive in that one

1

ÿnds a basis q , q = 1; : : : ; m of n (or of V in general) dual to the functionals we are interpolating

in the sense that Fq r = qr . The elements of such a basis are sometimes called the fundamental

functions of the interpolation. The Lagrange interpolant, for example, could then be written as

m

P(z) = f(zq ) q (z); (13)

q=1

if the data to be interpolated are given by cq = f(zq ). The fundamental functions then satisfy

r (zq ) = qr . For Lagrange interpolation, it is easy to ÿnd the dual basis

16r6m; r=q (z ’ zr )

q (z) = : (14)

(zq ’ zr )

16r6m; r=q

It is also not hard to ÿnd the dual basis for univariate Hermite interpolation.

1

Another, but nonconstructive approach to proving regularity starts by choosing a basis for n (or

of V in general). Then Eq. (10) or (12) (or (1) in general) become a linear system of equations for

the coe cients of the representation of the interpolant in the chosen basis. We will call the matrix

M of this linear system the Vandermonde matrix and the determinant D of M the Vandermonde

determinant. We sometimes write M (F; V ) or M (Z) to make the dependency of M or D on the

functionals and on the details of the interpolation more explicit.

The method is based on the fact that our interpolation is regular if and only if D = 0. The

interpolation is singular if D = 0. For Lagrange interpolation, we have the famous formula for

the (original) Vandermonde determinant

D(Z) = (zq ’ zr )

16q¡r6m

if the monomial basis {x }m=1 is taken for m’1 . We can immediately read o of this formula that

1

Lagrange interpolation is regular if and only if the nodes zq are distinct. A similar formula can be

found for the Vandermonde determinant of Hermite interpolation.

A third method, another constructive method, is known as the Newton method. The idea is to

start by interpolating one functional, then increase the number of functionals interpolated stepwise

(either one at a time, or in packets) until the required set of functionals is interpolated. At each step,

one adds a polynomial to the previous interpolant, which interpolates zero values for the functionals

already interpolated. In this way, the work done in the previous steps is not spoiled.

Let us carry this out for Lagrange interpolation of the function values cq at the nodes zq ;

q = 1; : : : ; m. We take P1 (z) ≡ c1 . Then P1 interpolates the ÿrst functional (functional evaluation

1

at z1 ) and P1 ∈ 0 . Let Q2 (z) = z ’ z1 . Then Q2 (z1 ) = 0 and R2 (z) = c2 Q2 (z)=Q2 (z2 ) vanishes at z1

and takes the value c2 at z2 . So P2 = P1 + R2 interpolates the ÿrst two functionals. After ÿnding a

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