2020/10/21 by Hecht, Michael, Gonciarz, Krzysztof, Michelfeit, Jannik +2
#41A05 #41A10 #41A50 #41A63 #FOS: Mathematics #Numerical Analysis (math.NA) #Primary 65D15 #Secondary 41A25
paper · doi:10.48550/arxiv.2010.10824
We extend Newton and Lagrange interpolation to arbitrary dimensions. The core contribution that enables this is a generalized notion of non-tensorial unisolvent nodes, i.e., nodes on which the multivariate polynomial interpolant of a function is unique. By validation, we reach the optimal exponential Trefethen rates for a class of analytic functions, we term Trefethen functions. The number of interpolation nodes required for computing the optimal interpolant depends sub-exponentially on the dimension, hence resisting the curse of dimensionality. Based on these results, we propose an algorithm to efficiently and numerically stably solve arbitrary-dimensional interpolation problems, with at most quadratic runtime and linear memory requirement.