Нахождение точки, которая наилучшим образом соответствует пересечению n сфер

Question

У меня есть массив точек с расстояниями.Я хочу найти точку, которая наилучшим образом удовлетворяет условию, что

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

Я думаю, что это можно решить с помощью некоторой регрессии или метода наименьших квадратов, но у меня возникли проблемы с формулировкой задачи.

Если бы кто-нибудь мог помочь, это было бы очень признательно

Answer 1

Чтобы ответить на вопрос, нужно определить «лучший».

То, что вы, вероятно, хотите сделать, - это определить какую-то функцию ошибки для определения того, насколько важно отклонение от заданной точки, а затем попытаться минимизировать сумму ошибок. Используемая функция ошибки зависит от вашей реальной проблемы. Например, возможно, вы хотите использовать (длина (точка - точка_i) - расстояние) ² . Это было бы наименьших квадратов. Но, возможно, вас не волнует абсолютная величина расстояния, просто соотношение между тем, как далеко они находятся, и как далеко вы их ожидаете. Поэтому вы можете использовать (длина (точка - точка_i) / расстояние - 1) ² . Возможно, вы получаете точки и расстояния от группы датчиков. В этом случае соответствующая используемая функция ошибок отражает степень неопределенности при измерении расстояния.

Как только вы выбрали подходящую функцию ошибки, вам нужно найти способ ее оптимизации. Самый простой способ сделать это - вычислить градиент для вашей функции ошибки и использовать его, чтобы следовать алгоритму поиска пути до самой низкой точки. Если ваша функция ошибок хорошо себя ведет, это должно работать, хотя и не так быстро. Если вы амбициозны, вы можете использовать многомерный метод Ньютона-Рафсона, чтобы найти эту точку. Это делает больше предположений о вашей функции ошибок, и будет много работы, но будет сходиться намного быстрее.

Answer 2

Эта проблема обычно решается с помощью линейной алгебры, решая для «наименьших квадратов», который минимизирует квадрат ошибки.

Это - то, как приемники gps находят «лучшее соответствие», чтобы дать ваши координаты,Они принимают набор «шумных» расстояний до всех разных спутников и находят новый набор расстояний, которые соответствуют одной точке, которая имеет наименьшую квадратичную ошибку от «шумных» расстояний.

Тамсуществует множество библиотек линейной алгебры (наиболее преобладающим из которых является linpack), которые должны иметь функции для решения проблем этих типов.