Numer Algor DOI 10.1007/s11075-006-9062-2 ORIGINAL PAPER
Multivariate polynomial interpolation: conjectures concerning GC-sets Carl de Boor
Received: 13 November 2006 / Accepted: 19 December 2006 © Springer Science + Business Media B.V. 2007
Abstract GC-sets are subsets T of Rd of the appropriate cardinality dim n for which, for each τ ∈ T, there are n hyperplanes whose union contains all of T except for τ , thus making interpolation to arbitrary data on T by polynomials of degree ≤ n uniquely possible. The existing bivariate theory of such sets is extended to the general multivariate case and the concept of a maximal hyperplane for T is highlighted, in hopes of getting more insight into existing conjectures for the bivariate case. Keywords Gasca–Maetzu conjecture · Geometric characterization · Completely factorizable · Lagrange form · Maximal polynomial Mathematics Subject Classifications (2000) 41A05 · 41A10 · 41A63 · 65D05
1 Introduction As already simple bivariate examples involving two, three, or four points make clear, those interested in multivariate polynomial interpolation must contend with the following Basic problem. Given a finite set T of data sites τ in Rd , how to choose a space F of polynomials so that, for every choice of data values a = (a(τ ) : τ ∈ T) ∈ FT
C. de Boor (B) POB 1076, Eastsound WA 98245, USA e-mail:
[email protected] http://www.cs.wisc.edu/∼deboor
Numer Algor
(with F either R or C), there is exactly one element f ∈ F that matches this information, i.e., satisfies f (τ ) = a(τ ),
τ ∈ T.
I will call such F correct for T. Others have used “unisolvent” or “poised” or “regular” instead of “correct”. While there is some work on this problem (see, e.g., [2–4]), most of the work to date on multivariate polynomial interpolation has gone into the somewhat different problem of finding sets that are correct of degree n, or n-correct, for short, i.e., sets T ⊂ Rd correct for ⎫ ⎧ ⎬ ⎨ ()α c(α) : c(α) ∈ F , F := ⎭ ⎩ |α|≤n
with ()α : Rd → F : x → xα := x(1)α(1) · · · x(d)α(d) a nonstandard but handy notation for the monomial with exponent α ∈ Zd+ and |α| := α(1) + · · · + α(d) its (total) degree. In effect, most of the work has focused, not on interpolation per se but, rather, on interpolation as a means for constructing approximations from ≤n (Rd ) under the assumption that there is some leeway in the choice of interpolation sites. At its most intricate, this line of research looks for good interpolation sites, i.e., for sites for which the resulting linear projector has small norm, with [6] a particularly striking example. The aim of this note is much less ambitious. It is to generalize (in a reasonable way, I hope) what is known in the bivariate case about a particular kind of n-correct T to the general multivariate case, in hopes of shedding some light on a conjecture made by Gasca and Maeztu nearly 25 years ago and still essentially unsettled.
2 Basic linear algebra I find it most convenient to start a discussion of interpolation with its inverse, i.e., with the linear map δT : f → f
T
:= ( f (τ ) : τ ∈ T) ∈ FT
of restriction to, or evaluation at, the data sites. In terms of this map, (T, F) is correct iff δT maps F 1-1 onto FT . Hence, if (T, F) is correct, then the inverse of δT F exists and is necessarily a column map, i.e., of the form (δT F )−1 a =: τ a(τ ) =: [τ : τ ∈ T] a, a ∈ FT , τ ∈T
and with τ (σ ) = δτ σ for all τ, σ ∈ T, i.e., [τ : τ ∈ T] is the Lagrange basis for F with respect to T.
Numer Algor
3 Basic facts about n-correct sets From now on, assume that T ⊂ Rd is n-correct, hence τ p(τ ) p= τ ∈T
is the Lagrange form for p ∈