标题： 向下闭合空间中的多元牛顿插值对于Bos--Levenberg--Trefethen函数达到最优几何逼近速率 显示英文标题

标题： Multivariate Newton Interpolation in Downward Closed Spaces Reaches the Optimal Geometric Approximation Rates for Bos--Levenberg--Trefethen Functions

摘要： 我们将一元牛顿插值算法推广到任意空间维度，并适用于任何向下的闭合多项式空间，同时保持其平方运行时间和线性存储成本。 这种推广支持任何提供的非张量型单义插值节点的选择，这些节点的数量与所选向下闭合空间的维数一致。 具体来说，我们证明了通过选择勒让德有序的切比雪夫-洛巴托节点或勒让德节点，一类解析函数（称为博斯-列文伯格-特雷费森函数）的最佳几何逼近速率得以实现，并且可以扩展到插值函数的导数上。 特别是，选择欧几里得度会导致向下闭合空间的维数仅以次指数方式随空间维数增长，同时提供接近甚至匹配张量子最大度情况的逼近速率，从而缓解了维度灾难问题。 多个数值实验展示了由此产生的多元牛顿插值相对于最先进的替代方法的性能，并验证了我们的理论结果。 显示英文摘要

摘要： We extend the univariate Newton interpolation algorithm to arbitrary spatial dimensions and for any choice of downward-closed polynomial space, while preserving its quadratic runtime and linear storage cost. The generalisation supports any choice of the provided notion of non-tensorial unisolvent interpolation nodes, whose number coincides with the dimension of the chosen-downward closed space. Specifically, we prove that by selecting Leja-ordered Chebyshev-Lobatto or Leja nodes, the optimal geometric approximation rates for a class of analytic functions -- termed Bos--Levenberg--Trefethen functions -- are achieved and extend to the derivatives of the interpolants. In particular, choosing Euclidean degree results in downward-closed spaces whose dimension only grows sub-exponentially with spatial dimension, while delivering approximation rates close to, or even matching those of the tensorial maximum-degree case, mitigating the curse of dimensionality. Several numerical experiments demonstrate the performance of the resulting multivariate Newton interpolation compared to state-of-the-art alternatives and validate our theoretical results.