插值建议（线性，三次样条？）

Question

我需要找到一个未定义函数与阈值相交的好近似点。我正在遍历我的空间，每当我发现两个连续步骤在阈值的不同侧时，我会在它们之间添加一个点：

_{(来源: ning.com)}

我的第一种方法是只选择中间点，但这显然是一个糟糕的解决方案:

_{(来源: ning.com)}

我现在使用线性插值，这可以得到一个合理的结果，但基础函数实际上几乎永远不会是线性的。因此，只有当我的步长足够小时，这才能很好地工作:

_{(来源: ning.com)}

对于基础函数进行取样可能会非常昂贵，但是添加一两个额外的样本以获得更好的近似值是我想尝试的。这里是否可以使用三次插值？像这样：

_{(来源: ning.com)}

或者还有更好的方法吗？

非常感谢， David Rutten

PS: 我是用C#编写的，但这是一个与语言无关的问题。

- David Rutten

---

你用什么软件制作这些图片的？ - Don

@Don，XaraX。同时将其用于我所有的图标。 - David Rutten

Answer 1

魔术词汇是“根求解器”；数学根是函数等于零的值。通过添加/减去阈值，您可以使用根查找器。

如果您知道正在插值的功能，则可以设置非常快速的根查找器。如您所述("未定义"), 如果您不知道，则最好的方法是"Brent's method"，这是"割线法"和"二分法"的组合，或仅使用"割线法"。维基百科上有关于此方法的条目。

与您的观点相反，使用更复杂的函数并不是一个好主意。主要的性能障碍是随着更多点/获取导数或更复杂的插值函数而增加的函数评估。

如果您接近极大值/极小值/拐点，则牛顿-拉夫逊方法是非常糟糕的，因为接近零的导数会将您远离该点，并且存在其他问题。在了解自己在做什么之前，请勿使用它。

- Thorsten S.

---

@Thorsten，谢谢。我会研究根解算器。据我回忆，我们在应用程序的其他地方已经使用了Brent逻辑，所以我应该能够向办公室的C++专家寻求信息。 - David Rutten

Answer 2

我的数学非常生疏，但您可能会发现牛顿-拉夫逊法可以给您提供良好的结果。通常情况下，只要迭代开始“足够接近”所需的根，它就可以非常快速地收敛到准确的解。

- Rich Seller

---

牛顿法需要多次对函数进行采样，这是他无法承受的。 - Ron Warholic

然而，如果初始猜测不太准确，则它会二次收敛，因此一两次迭代可能就足够了。OP说这是可以接受的。 - Rich Seller

这看起来非常有趣和棘手。我需要一段时间来消化那个维基百科页面。感谢提供链接。 - David Rutten

牛顿法要求您知道正在采样的函数的导数。现在我了解到，在这种情况下，您确实知道导数...所以我认为这将非常有效。它并不太难理解，只需要看看图片 :) - Thomas

@David 不用谢，如果我没记错的话，理论很复杂，但实际应用很简单。 - Rich Seller

我认为我可以很容易地得到导数。这种方法似乎足够通用，值得进行一些严肃的投资。 - David Rutten

Answer 3

您的最后一张图片只显示了三个点，这只足以定义二次多项式，而不是三次的。对于三次插值，您需要四个点。可以用不同的方法拟合三次多项式，以下是两种方法。

最简单的方法是让（唯一的）多项式通过所有四个点。

另一种方法是使用切线。同样，我们需要四个点。让左边的两个点定义一个斜率。让多项式穿过第二个点（通常不穿过第一个点），并在该点匹配计算出的斜率。右侧的第四个和第三个点也是如此。

顺便说一句，任何高阶多项式可能都不是一个好主意，因为它们往往在即使有一点输入噪声的情况下也变得非常不稳定。

如果您提供关于问题域的更多细节，我可能能够给出更具体的答案。例如，您的数据点来自哪里，您通常可以期望什么样的曲线，并且如果需要，您可以返回并进行更多采样吗？如果需要，我还可以提供方程和伪代码。

- Thomas

---

@Thomas：我可以在每个位置随意采样。我画的确实是二次的而不是三次的，我比我想象中还要困惑 :) 这些值来自于一个分布在二维空间中的一组电荷点。本质上，它是N个双曲线的总和。 - David Rutten

你是在尝试用等电线或其他方式绘制2D图像吗？N有多大？ - Thomas

是的，我是。N 的取值范围在 1 到约 1000 之间。 - David Rutten

根据每个电荷的影响范围和所需的精度，您可能可以使用“喷溅”技术。建立一个大的二维数组，包含所有点（像素）的场强度，然后逐个添加电荷，而不是迭代整个数组，而只是在电荷影响大于某个epsilon的（圆形）区域内进行。 - Thomas

我已经在空间中使用盒式跳跃的方式，所以我认为我已经将评估数量降至最低。但对于实时界面来说速度仍然太慢了（在大型数据集上只有10帧每秒）。 - David Rutten

似乎对于GPU来说是个不错的工作。 - Thomas