论文标题
Unislovent节点中的多元插值 - 举起维度的诅咒
Multivariate Interpolation in Unisolvent Nodes -- Lifting the Curse of Dimensionality
论文作者
论文摘要
我们将牛顿和拉格朗日插值扩展到任意维度。实现这是非感官Unisolvent节点的广义概念的核心贡献，即函数的多元多项式插值剂是唯一的节点。通过验证，我们达到了一类分析功能的最佳指数式三分率，我们称为Treefethen功能。计算最佳插值所需的插值节点的数量取决于尺寸，因此抵抗了维度的诅咒。基于这些结果，我们提出了一种算法，以有效且数值稳定地解决任意维插值问题，最多最多具有二次运行时和线性内存要求。
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.
