math - 找到一个最适合 n 个球体交集的点

Question

我有一系列有距离的点。我希望找到一个最能满足条件的点

for (point_i, distance_i) in pointArray:
  abs(point - point_i) = distance_i

我认为这可以通过某种回归或最小二乘来解决，但我在问题表述上遇到了麻烦。

如果有人可以提供帮助，将不胜感激

Answer 1

您需要定义“最佳”以获得可回答的问题。

您可能想要做的是定义某种误差函数，以确定偏离给定点的程度，然后尝试最小化误差的总和。要使用的错误函数取决于您的实际问题。例如，也许您想使用 (length(point - point_i) - distance) ²。那将是最小二乘。但也许您并不太关心距离偏离的绝对量，只关心它们的距离与您期望的距离之间的比率。所以你可以使用 (length(point - point_i)/distance - 1) ²。也许您可以从一堆传感器中获得点和距离。在这种情况下，要使用的适当误差函数反映了距离测量中有多少不确定性。

一旦你选择了合适的误差函数，你就需要找到一种优化它的方法。最简单的方法是计算误差函数的梯度，并使用它跟随寻路算法到达最低点。如果你的错误函数表现良好，这应该可以工作，虽然不是那么快。如果您有野心，您可以使用多元 Newton-Raphson 方法来找到这一点。这会对您的误差函数做出更多假设，并且会做很多工作，但收敛速度会更快。

Answer 2

这个问题通常用线性代数来解决，通过求解“最小二乘”，最小化误差的平方。

这就是 gps 接收器如何找到“最合适”的坐标来提供您的坐标。他们将一组“嘈杂”距离带到所有不同的卫星，并找到一组新的距离，这些距离与“嘈杂”距离中具有最小平方误差的单个点相交。

那里有许多线性代数库（最主要的是 linpack），它们应该具有解决这些类型问题的功能。