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) ²を使用できます。おそらく、一連のセンサーからポイントと距離を取得します。その場合、使用する適切なエラー関数は、距離の測定にどれだけの不確実性があるかを反映しています。

適切な誤差関数を選択したら、それを最適化する方法を見つける必要があります。これを行う最も簡単な方法は、誤差関数の勾配を計算し、それを使用してパス検索アルゴリズムを最低点までたどることです。エラー関数の動作が適切であれば、それほど高速ではありませんが、これは機能するはずです。野心がある場合は、多変量ニュートン ラフソン法を使用してその点を見つけることができます。これにより、エラー関数についてより多くの仮定が作成され、多くの作業が必要になりますが、はるかに高速に収束します。

Answer 2

この問題は通常、誤差の二乗を最小化する「最小二乗」を解くことにより、線形代数でアプローチされます。

これは、GPS 受信機が「最適な」座標を見つける方法です。彼らは、すべての異なる衛星への「ノイズの多い」距離のセットを取得し、「ノイズの多い」距離からの最小の二乗誤差を持つ単一のポイントを満たす新しい距離のセットを見つけます。

これらの型の問題を解決するための関数を備えた線形代数ライブラリが多数あります (最も優勢なのは linpack です)。