当我只有一组点时，我将如何实现根查找？

Question

我有一些代码输出两个数组，其中包含x值和y值。我现在需要根-找到使用这些点，但这是可能的，而不知道函数？例如，如何实现使用的二分法只一组(x, y)对(没有函数f(x))？我在网上找到的所有例子都显示了一个预定义的多项式函数所使用的二分法。我需要先找到一个近似函数才能使用二分法吗？

Answer 1

我想在根上你指的是y=0.0的点

找出两个后续点，(x0,y0),(x1,y1)，y0*y1<=0.0，这意味着它们是过零的，所以根就在它们之间，所以在这里取n点，形成多项式(插值或贝塞尔或其他什么)，然后使用二分法或任何其他方法。

首先，您可以使用线性插值，因此只需解决以下问题：

x(t) = x0 + (x1-x0).t // parametric line x
y(t) = y0 + (y1-y0).t // parametric line y
y(t) = 0.0 // root y
x(t) = ?   // root x
---------------------
0.0 = y0 + (y1-y0).t
t = -y0/(y1-y0)
---------------------
x(t) = x0 + (x1-x0).t 
x(t) = x0 + -y0/((y1-y0).(x1-x0)) // this is your approximate root

你可能想看看：

• How approximation search works
• How can I produce multi point interpolation?

还可以处理y0或y1为零的特殊情况。这意味着它们是根，您不需要插值。如果它们都是零，那么它们之间就有无穷多的根。