Multivariate Newton Interpolation

arXiv1812.04256MaRDI QIDQ6311002FDOQ6311002

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

Publication date: 11 December 2018

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.

Mathematics Subject Classification ID

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)

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)