Multivariate polynomial interpolation
Here is a summary of my on-going investigations into the error in multivariate
interpolation. This page is organised to more generally serve those interested
in multivariate polynomial interpolation (error formulae and computations),
and contributions are most welcome.
I am interested in bounding the p-norm of the error in a multivariate
polynomial interpolation scheme by norms of derivatives which kill the
interpolating space (and require the function interpolated to be no smoother
than is necessary). These are the estimates that
numerical analysts use to show that a numerical scheme based on
multivariate polynomial interpolation has the highest order of accuracy that
its polynomial reproduction allows.
Because of this interest (especially in the area of finite elements),
there is a large literature dealing with these questions, particularly for
linear interpolation on a triangle.
The basic idea behind all of the constructive work to date, is to find a
pointwise error formulae that involve integrals of the desired derivatives.
Even in the simplest of cases, linear interpolation on a triangle, there are
many possible ways to do this
(see The error in linear interpolation at the vertices of a simplex, Waldron 1994).
Good examples of such pointwise error formulae include
my work dealing with the error in
Kergin and Hakopian interpolation,
Sauer and Xu's error formula, de Boor's multivariate divided difference,
and the references therein.
Kergin and Hakopian interpolation
are `lifted' versions of Hermite interpolation.
Given a pointwise error formulae involving the desired derivatives,
it is generally not clear how to obtain L_p-error bounds (for finite p) from it.
In many cases L_p-error bounds can be obtained by using a
multivariate form of Hardy's inequality,
while for others there is currently no method for obtaining such bounds (and
this appears to be a fundamental limitation these formulae).
There are a number of methods that are used for obtaining pointwise error
formulae for multivariate polynomial interpolation schemes including
- The error is written in a form which involves the function values
(and derivatives) that are matched by the interpolation, then
to introduce the desired derivatives. The key tool here is the fundamental
theorem of calculus in two of its guises: the integration by parts formula
and the recurrence relation for simplex splines.
- A version of the multipoint Taylor formula
This formula is well-known in finite elements, but has
received little attention from approximation theorists.
- A Newton form for the interpolation polynomial is used to
give an error formula in a similar way to the classical univariate setting.
Or, to quote Thomas Sauer, ``the crucial idea is to find a RECURSIVE way of
building up the interpolation polynomial, or the remainder term, and to this
you apply the fundamental theorem of calculus''.
Some well-known work that uses `differencing' to find error formulae
- Linear approximation, A. Sard, AMS monograph (1963)
- Error bounds for linear interpolation on a triangle, J. A. Gregory,
In: Mathematics of finite elements and applications (J. Whiteman, ed.) (1975)
Some well-known work on the multipoint Taylor formula
- General Lagrange and Hermite interpolation in R^n with applications to
finite element methods, P. G. Ciarlet and P. A. Raviart, Arch. Rational Mech.
Anal. 46 (1972), pp 177-199
- Sur l'evaluation de l'erreur d'interpolation de Lagrange dans un ouvert
de R^n, R. Arcangeli and J. L. Gout, Rev. Francaise Automat. Informat. Rech.
Oper., Anal. Numer. 10(3) (1976), pp 5-27
Some recent work that uses a `Newton form' to find error formulae
On multivariate Lagrange interpolation,
T. Sauer and Y. Xu, Math. Comp. 64 (1995) pp 1147--1170
A case study in multivariate Lagrange interpolation,
T. Sauer, preprint (1994)
Computational aspects of multivariate Lagrange interpolation,
T. Sauer and Y. Xu, Advances in Comp. Math. 3 (1995) pp 219--237
On multivariate Hermite interpolation,
T. Sauer and Y. Xu, Advances in Comp. Math. 4 (1995) pp 207--259
A multivariate divided difference ,
C. de Boor,
(Approximation Theory VIII, Vol. 1: Approximation and Interpolation),
Charles K. Chui and Larry L. Schumaker (eds.),
World Scientific (Singapore) (1995) pp 87--96
Some more recent papers dealing with
multivariate polynomial interpolation
The least solution for the polynomial interpolation problem, C. de Boor
and A. Ron, Math. Z. 210 (1992) pp 347-378
On multivariate polynomial interpolation, C. de Boor and A. Ron, Const.
Approx. 6 (1990), pp 287-302
On the error in multivariate polynomial interpolation, C. de Boor,
Applied Numerical Mathematics 10 (1992), pp 297-305
Polynomial interpolation in several variables ,
C. de Boor,
(Proceedings of the Conference honoring Samuel D. Conte), R. DeMillo and
J.R. Rice (eds.), Plenum Press (New York) (199x)
Sharp error estimates for interpolatory approximation on convex
A. Guessab and G. Schmeisser
(SIAM Journal on Numerical Analysis 2005)
- The finite element method for elliptic problems, P. G. Ciarlet (1978)
- Spline functions and multivariate interpolations, B. D. Bojanov, H. A.
Hakopian and A. A. Sahakian (1993)
Some work in progress and people involved
- Junbin Gao
(using the least solution to the polynomial interpolation
problem to construct
nonconforming finite elements)
- Mariano Gasca with Muehlbach (
for interpolation to data points from a lower set)
- David Handscomb (using the variational calculus to get sharp L_2-bounds
error in linear interpolation on a triangle)
- Guenter Muehlbach (joint work with Gasca)
- Thomas Sauer (computational aspects of multivariate Lagrange
- Shayne Waldron (integral
error formulae for linear interpolation on a triangle)
- Yuan Xu (multivariate Lagrange interpolation)
- Hovik Gevorgian, Hakop Hakopian, Artur Sahakian (describing positions
of points for which Lagrange and Hermite interpolation is correct).
Due to oversight, the crucial role that univariate splines play in describing
the error in Hermite interpolation has only recently been exploited to obtain
L_p-error bounds. To find out about recent advances see
Project Hermite .
This document is maintained by
Last Modified: .