<<

. 39
( 83 .)



>>



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

<<

. 39
( 83 .)



>>