Multivariate Newton Interpolation

Authors Michael Hecht, K. B. Hoffmann, Bevan L. Cheeseman, Ivo F. Sbalzarini

Publication date 11 December 2018

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical linear algebra (65F99) Numerical interpolation (65D05) Approximation by polynomials (41A10) Stability and convergence of numerical methods for ordinary differential equations (65L20) Polynomials, rational functions in real analysis (26C99)

Abstract: For

m, n i n m a t h b b N

,

m g e q 1

and a given function

f : m a t h b b R^{m} l o n g r i g h t a r r o w m a t h b b R

, the polynomial interpolation problem (PIP) is to determine a unisolvent node set

P_{m, n} s u b s e t e q m a t h b b R^{m}

of

points and the uniquely defined polynomial

Q_{m, n, f} i n P i_{m, n}

in

m

variables of degree

m a t h r m d e g (Q_{m, n, f}) l e q n i n m a t h b b N

that fits

f

on

P_{m, n}

, i.e.,

Q_{m, n, f} (p) = f (p)

,

f o r a l l, p i n P_{m, n}

. For

m = 1

the solution to the PIP is well known. In higher dimensions, however, no closed framework was available. We here present a generalization of the classic Newton interpolation from one-dimensional to arbitrary-dimensional spaces. Further we formulate an algorithm, termed PIP-SOLVER, based on a multivariate divided difference scheme that computes the solution

Q_{m, n, f}

in

time using

memory. Further, we introduce unisolvent Newton-Chebyshev nodes and show that these nodes avoid Runge's phenomenon in the sense that arbitrary periodic Sobolev functions

f i n H^{k} (O m e g a, m a t h b b R) s u b s e t n e q C^{0} (O m e g a, m a t h b b R)

,

O m e g a = [- 1, 1]^{m}

of regularity

k > m / 2

can be uniformly approximated, i.e.,

l i m_{n i g h t a r r o w i n f t y} | |, f - Q_{m, n, f}, | |_{C^{0} (O m e g a)} = 0

. Numerical experiments demonstrate the computational performance and approximation accuracy of the PIP-SOLVER in practice. We expect the presented results to be relevant for many applications, including numerical solvers, quadrature, non-linear optimization, polynomial regression, adaptive sampling, Bayesian inference, and spectral analysis.

This page was built for publication: Multivariate Newton Interpolation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311002)