这可能是一个微不足道的问题，如果是这样，我深表歉意。考虑以下简单问题：我们有一个二维的规则网格点（比如$X = [0,5000] \times [0,5000]$) 以 1 为单位均匀间隔（例如，$(0,0), (0,1), (1,0) \in X$并且存在一个函数$f(x,y)$我们的目标是近似$X$. 让我们假设它是好的和平滑的，至少$C^2$. 假设我们在一个统一的子网格上有数据样本（比如在一个方向上每 100 个点我们有一个样本值$f(x_i,y_i)$）。我们都知道存在许多不同的方法来逼近这样的函数。我很好奇的是关于哪些方法可以为我提供对不在子网格上的新给定点的最快评估的建议（例如，在某个点$(50,25)$）。

选项 1：多元多项式插值。

我们可以选择某个固定次数的多元多项式基（假设是 3 阶）所以，$p(x,y) = c_0 + c_1 x + c_2y + c_3 x^2 + c_4 xy + c_5 y^2 + c_6 x^3 + c_7 x^2 y + c_8 xy^2 + c_n y^3$.

这种方法有很多优点：存储空间小（我们只需要存储系数，相对于网格中的点数来说这是一个非常小的数字）并且对新点的评估相对较快（我们有几个乘法，加上一些加法）。

但是，我们还必须拟合这个多项式。这需要我们解决最小二乘问题，其中我们将有一个矩阵$N \times d$其中 d 是系数的数量和$N$是样本点的数量。我相信我最好的选择是 SVD 解决方案（可能使用 Armadillo 或 Eigen）。这肯定是整个考验中最慢的部分，因此前期成本很高。

下一个缺点是诸如龙格现象之类的问题。由于某些区域的精度差等问题，我通常对拟合多元多项式非常谨慎。此外，基的选择显着影响系统的可解性。如果这是一维的，如果可能的话，我会做切比雪夫多项式。在 2D 中是否有更好的基础来解决这样的问题？

选项 2：方形网格上的分段多项式

我是这个选项的粉丝。我可以在实际子区域（比如 100 x 100 单位）上使用线性或二次元素。缺点是我需要存储$N$已知函数样本。所以这需要更多的存储空间，因此复制和移动这些信息比移动例如多项式系数（这是一个固定的微小数字）更重要。评估应该很快。我需要知道单元格顶点的值，并给定一个新点 (x,y)，我需要计算它所在的方形单元格。我假设我可以通过除法来做到这一点$x$和$y$跨步（比如 100）并将其铺平以找出新点所在的单元格的左下角。我在这里看到的巨大优势是我没有解决大型系统来获取近似函数的系数。

我真正看到的唯一缺点是我的网格间距变化的情况（比如 100 x 100 个单元格，然后是 50 x 50 个单元格）。给定一个新点来评估 (x,y) 处的函数值，我需要高效快速地计算 (x,y) 所在的单元格，然后在该单元格中快速进行分段多项式评估。也许我很笨，但是当单元格的大小不同时，快速计算一个点所在的单元格的有效方法是什么？

3：径向基函数方法

这需要解决大型系统和大量系数，所以我在这里没有看到优势。如果我有不规则的采样点，我会考虑这个。

总结：速度对我来说至关重要；我将有很多传入点和函数值的评估在这些所需的点，我还需要尽快设置近似函数（例如求解多项式或 RBF 系数）。建议会很棒。谢谢！

编辑：我的问题不清楚。我的目标是使用某种方法（多项式、分段多边形等）实时（或尽可能接近）拟合传入的数据集（如上所述），然后这些方法将随后实时接收许多评估请求. 我将收到不止一个数据集，每秒可能很多（几十个？几百个？）。因此，构建插值/拟合方案和后续评估的前期成本都需要很快。我肯定需要尽可能多地并行化。