2018/12/11 by Hecht, Michael, Hoffmann, Karl B., Cheeseman, Bevan L. +1
#26C99 #41A10 #65D05 #65F05 #65F99 #65L20 #FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1812.04256
For m,n ∈ ℕ, m≥ 1 and a given function f : ℝm\longrightarrow ℝ, the polynomial interpolation problem (PIP) is to determine a unisolvent node set Pm,n ⊆ ℝm of N(m,n):=|Pm,n|=\binomm+nn points and the uniquely defined polynomial Qm,n,f∈ Πm,n in m variables of degree deg(Qm,n,f)≤ n ∈ ℕ that fits f on Pm,n, i.e., Qm,n,f(p) = f(p), ∀ p ∈ Pm,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 Qm,n,f in O(N(m,n)2) time using O(mN(m,n)) 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 ∈ Hk(Ω,ℝ) \subsetneq C0(Ω,ℝ), Ω=[-1,1]m of regularity k >m/2 can be uniformly approximated, i.e., limn→ ∞|| f -Qm,n,f ||C0(Ω)= 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.