Matheproblem

[Jim P. (jim)]

Hallo,

ich habe ein Problem, für welches sicher schon eine Lösung existiert.
Also, ich habe eine Punktwolke. Als Messwerte (die alle auch einen 
Messfehler haben) habe ich die Abstände/Laufzeiten zwischen jeweils 2 
Punkten. Ziel ist es, unter Zuhilfenahme der Abstandsinformationen eine 
Karte der Punkte zu erstellen.

Idee: Konstruktion mit Zirkel / Kreisschnittpunkten. - Hierbei würde 
aber (dadurch, dass die Messabweichungen sich addieren) das Problem 
auftreten, dass, wenn ich ueber 2 verschiedene Wege die Position eines 
Punktes ermitteln will, eine großer Fehler entsteht.

Idee: Gleichungssystem - dieses wäre überbestimmt und durch die Fehler 
nicht lösbar...

Idee: Algorithmus: - Ich nehme mir einen Anfangspunkt und einen der mit 
ihm verbunden ist, sowie alle Informationen über Abstände zu anderen 
Punkten die vorhanden sind. Daraus ergeben sich dann Kreise.... dann 
muesste man die Toleranzen mit einbeziehen mhm...

Frage: Gibt es einen solchen Algorithmus oder ein Programm, welches ein 
solches Problem lösen kann? Habt Ihr da Ideen / Erfahrungen?

Vielen Dank erstmal!

[Florian R. (Firma: TU Wien) (frist)]

Hallo Jim

> Idee: Gleichungssystem - dieses wäre überbestimmt und durch die Fehler
> nicht lösbar...

Das stimmt so nicht. Es gibt (i.A. wegen der Fehler) keine exakte 
Lösung, aber eine (unter bestimmten Gesichtspunkten) optimale Lösung 
gibt es schon. Und die kann man auch ausrechnen, wie bei einem 
"normalen" Gleichungssystem. Sollte sich das Problem auf ein 
überbestimmtes lineares Gleichungssystem abbilden lassen könnte man das 
z.B. über die Penrose Pseudoinverse machen:

  http://de.wikipedia.org/wiki/Pseudoinverse


Grüße
Flo

[Winfried J. (Firma: Nisch-Aufzüge) (winne)]

Hallo,
das Problem hast du bei der Navigation (Koppeln)auch. Grundlage ist das 
Fehlerfortpflanzungsgesetz. Deine Kreise werden dort, in der Navigation, 
Fehlerkreis genannt.

Reduziert wird der Fehlerkreis durch Redundanz. Das bedeutet für einen 
Punkt (Standort) werden mehrer Messungen gemacht und dann wird zwischen 
den Schnittpunkten der Fehlerkreise interpoliert. Dadurch wird der 
Fehler gegenüber den Einzelmessungen verringert.

Das Prinzip spielt auch in der Satellitennavigation eine Rolle. Siehe 
dort.

Namaste

[Jim P. (jim)]

Danke für Eure schnellen Antworten!

Flo: Das könnte der richtige Weg sein. Das Verfahren mit der 
Pseudoinverse werde ich versuchen zu verstehen.

Winfried: Ich glaube, du hast mich mißverstanden. Ich habe nicht fuer 
einen Punkt verschiedene Messwerte, und muss mitteln. Ich habe nur die 
Abstände von Punkten, die jeweils eine eigene "richtige" Position auf 
der Landkarte haben. Diese Abstände haben ne Messunsicherheit...

Angenommen ich hätte auf nem Fußballfeld 10 kleine Roboter stehen. Jeder 
misst per Ultraschall den Abstand zu seinen Nachbarn. Die Werte funken 
die an mich und ich will nun (aus den fehlerbehafteten Daten) eine 
Landkarte erstellen mit den genauen Positionen der einzelnen Roboter. 
Wenn die Messfehler klein sind oder gar nicht da wären, könnte ich die 
Karte konstruieren. Aber mit Fehlern würden diese sich ja addieren und 
die "Bereiche", in denen sich ein Roboter befinden koennte immer 
groesser.

weiterknobel

Man muesste zuerst irgendwie eine optimale Lösung für die Berichtigung 
der Abstände finden.

[P. M. (o-o)]

Man sollte noch darauf hinweisen, dass dieses System nicht zwingend 
eindeutig lösbar ist: Wenn man von drei Punkten den gegenseitigen 
Abstand hat, so sind immer noch spiegel- und rotationssymmetrische 
Varianten möglich. Ein vierter Punkt kann zwar bei drei bekannten 
Punkten richtig eingeordnet werden. Allerdings muss man zuerst eine 
korrekte Hypothese über die Lage der Punkte betreffend den 
Spiegelsymmentrien haben.