Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Newtonsches Näherungsverfahren

Newtonsches Näherungsverfahren

Universität / Fachhochschule

Differentiation

Gewöhnliche Differentialgleichungen

Tags: Differentiation, Gewöhnliche Differentialgleichungen, GPS, iteration, Newtonsches Näherungsverfahren

chaostilo aktiv_icon

19:28 Uhr, 25.05.2009

Hallo,

ich steh vor einem für mich recht großen Problem:

Ich soll am Do. einen Vortrag über GPS halten. Die Entfernungsermittlung basiert auf einer Zeitdifferenzmessung

(s = v \cdot t -

wobei

t

eigentlich

δ t

ist, also die Zeitdifferenz zwischen dem Absenden des Signals und dem Empfang des Signals).

Um damit 3 Koordinaten zu erhalten benötigt man 3 Satelliten. Wenn die Entfernung zu jedem einzelnen Satelliten bekannt ist, kann man sich nur auf einer Kugeloberfläche die den Radius des Abstandes zum Satelliten hat befinden

\to 3

Satellitenentfernungen ergeben damit 3 Kugeloberflächen und somit nur noch 2 mögliche Schnittpunkte, von denen einer verworfen werden kann, weil er im Weltall liegt.

Weiterhin hat der Empfänger keine Ahnung, zu welcher Zeit der das Signal empfangen hat (da für eine ausreichend exakte Zeit eine Atomuhr notwendig wäre, die in einfachen Geräten einfach nicht eingebaut werden kann. Also benötigt man noch einen vierten Satelliten um ddie Zeit bestimmen zu können.

Daher läuft das ganze auf ein Gleichungssystem mit 4 Gleichungen und 4 Unbekannten hinaus. Das ganze sieht dann so aus:

Gleichung

1 : {(x 0 - x 1)}^{2} + {(y 0 - y 1)}^{2} + {(z 0 - z 1)}^{2} = {(v \cdot (t 0 - t 1))}^{2}

Gleichung

2 : {(x 0 - x 2)}^{2} + {(y 0 - y 2)}^{2} + {(z 0 - z 2)}^{2} = {(v \cdot (t 0 - t 2))}^{2}

Gleichung

3 : {(x 0 - x 3)}^{2} + {(y 0 - y 3)}^{2} + {(z 0 - z 3)}^{2} = {(v \cdot (t 0 - t 3))}^{2}

Gleichung

4 : {(x 0 - x 4)}^{2} + {(y 0 - y 4)}^{2} + {(z 0 - z 4)}^{2} = {(v \cdot (t 0 - t 4))}^{2}

die Unbekannten sind:

x 0; y 0; z 0

und

t 0

also die Koordinaten des Empfängers und die Empfangsuhrzeit

Die Koordinaten der einzelnen Satelliten

(x 1

bis

x 4; y 1

bis

y 4; z 1

bis

z 4)

und die Zeiten an denen das Signal von den einzelnen Satelliten abgeschickt wurde

(t 1

bis

t 4)

sind bekannt.

Dieses Gleichungssystem wird dann iterativ durch das Newtonsche Näherungsverfahren gelöst. Wobei

i

d

. R. als Startwert ein ungefährer Wert für

t 0

verwendet wird.

Ich weiß nicht, ob man das ganze durch Umstellen und Einsetzen lösen könnte (hab es mal spaßenshalber mit einem 1 dimensionalen System gemacht, da geht es). Jedoch ist dieses Gleichungssystem in der Realität nicht eindeutig lösbar, da durch die Atmosphäre weitere Differenzen in den Signallaufzeiten der einzelnen Satellitensignale und noch diverse andere Fehler auftreten. Daher das Näherungsverfahren. Die tatsächliche Berechnung, die der GPS-Empfänger ausführt ist in Wirklichkeit noch wesentlich komplexer (da auch die Störfaktoren wie Atmosphäre, Ungenauigkeit der Satellitenbahnen etc. berücksichtigt und teilweise korrigiert werden), aber ich will in dem Vortrag ja auch nur mal kurz anreißen, wie das Prinzip funktioniert.

Ich hab hier zwar schon einen dicken Schinken "Mathe für Fachhochschulen" rumliegen, aber vermutlich würde ich hier eher "Mathe für Elite-Universitäten" benötigen :-). Dort wird nicht annähernd auf die Anwendung dieses Verfahrens zum Lösen kompletter Gleichungssysteme eingegangen. Da ich nun auch nicht gerade Spitzenkenntnisse in Mathematik habe, hoffe ich, daß hier jemand das ganze verstanden hat und mir helfen kann.

Ich glaube die Beschränkung auf ein zweidimensionales Problem wäre erstmal einfacher zu erklären und würde mir auch sehr viel weiterhelfen.

Besten Dank im Voraus.

MfG

Tilo

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

el holgazán aktiv_icon

21:06 Uhr, 25.05.2009

In Ordnung, machen wir das ganze mal 2 Dimensional.

Die Satelliten senden uns folgende Daten:

\vec{r 1} = (2, 4), t 1 = 2

\vec{r 2} = (- 6, 2), t 2 = 1

und

\vec{r 3} = (4, - 2), t 3 = 3

Wir setzen ausserdem

v = 1

Also haben wir

(x - 2)^{2} + (y - 4)^{2} - (t - 2)^{2} = 0

(x + 6)^{2} + (y - 2)^{2} - (t - 1)^{2} = 0

(x + 4)^{2} + (y + 2)^{2} - (t - 3)^{2} = 0

Wir suchen also eigentlich Nullstellen der obigen 3-Variablen-Funktion. Wir nennen diese Funktion

f (x, y, t)

- sie gibt jeweils einen 3-er Vektor aus.

Was wir nun als erstes machen müssen ist obige Funktion ableiten (bestimmten der Jakobi-Matrix). Und zwar leiten wir erst die erste Gleichung nach x, dann nach y und dann nach t ab. Dann die zweite Gleichung nach x u.s.w. Die jeweiligen Ergebnisse schreiben wir in die Matrix:

J (x, y, t) = (\begin{array}{l} 2 (x - 2) & 2 (y - 4) & - 2 (t - 2) \\ 2 (x + 6) & 2 (y - 2) & - 2 (t - 1) \\ 2 (x + 4) & 2 (y + 2) & - 2 (t - 3) \end{array})

Diese Matrix entspricht nun unserer Ableitung. Wenn wir

r_{n}

kennen, dann können wir den nächsten Datenpunkt

r_{n + 1}

wie folgt bestimmen:

r_{n + 1} = r_{n} - J (r_{n})^{- 1} \cdot f (r_{n})

Hierbei steht

J^{- 1}

für die Inverse Matrix von J. Da dies aufwändig ist wird normalerweise numerisch nicht die Inverse Matrix berechnet, sondern das lineare Gleichungsystem gelöst:

J (r_{n}) \cdot (r_{n + 1} - r_{n}) = - f (r_{n})

Diese Gleichung hat die Form

A x = b

ist also wirklich eine lineare Gleichung. Für uns heisst das, wir müssen unsere Startwerte in f und J einsetzen, und dann obiges Gleichungssystem nach

(r_{n + 1} - r_{n}) = Δ r

auflösen.

Unsere Startwerte sind

\vec{r} = (x, y) = (3, 1)

t = 0

Das setzen wir erst in f ein:

f (r_{0}) = (\begin{array}{l} (x - 2)^{2} + (y - 4)^{2} - (t - 2)^{2} \\ (x + 6)^{2} + (y - 2)^{2} - (t - 1)^{2} \\ (x + 4)^{2} + (y + 2)^{2} - (t - 3)^{2} \end{array}) = (\begin{array}{l} (3 - 2)^{2} + (1 - 4)^{2} - (0 - 2)^{2} \\ (3 + 6)^{2} + (1 - 2)^{2} - (0 - 1)^{2} \\ (3 + 4)^{2} + (1 + 2)^{2} - (0 - 3)^{2} \end{array}) =

= (\begin{array}{l} 1 + 9 - 4 \\ 81 + 1 - 1 \\ 49 + 9 - 9 \end{array}) = (\begin{array}{l} 6 \\ 81 \\ 49 \end{array})

Einsetzen in J bringt:

J (r_{0}) = (\begin{array}{l} 2 & - 6 & 4 \\ 18 & - 2 & 2 \\ 14 & 6 & 6 \end{array})

Also müssen wir nun das Gleichungssysem Lösen:

(\begin{array}{l} 2 & - 6 & 4 \\ 18 & - 2 & 2 \\ 14 & 6 & 6 \end{array}) \cdot (\begin{array}{l} Δ x \\ Δ y \\ Δ z \end{array}) = - (\begin{array}{l} 6 \\ 81 \\ 49 \end{array})

Die Lösung hierzu lautet:

{Δ x \to - \frac{565}{122}, Δ y \to \frac{89}{122}, Δ z \to \frac{233}{122}}

Also ist unser

r_{1}

r_{1} = r_{0} + Δ r = (3 - \frac{565}{122}, 1 + \frac{89}{122}, \frac{233}{122})

Weitere Iterationen führen auf:

r_{2} = (- 13.8861, 23.1757, - 53.2375)

r_{3} = (- 7.78165, 12.4929, - 25.7674)

r_{4} = (- 4.77485, 7.23098, - 12.2368)

r_{5} = (- 3.35774, 4.75105, - 5.85984)

r_{6} = (- 2.79135, 3.75987, - 3.31108)

r_{7} = (- 2.6584, 3.52719, - 2.71279)

r_{8} = (- 2.65016, 3.51279, - 2.67573)

r_{9} = (- 2.65013, 3.51273, - 2.67559)

Wie du siehst bekommen wir so unseren Punkt heraus.

Anzumerken ist übrigens, dass man für die Berechnung der Position auch die Spezielle Relativitätstheorie berücksichtigen muss - ein sehr eindrücklicher Beweis für die Richtigkeit derselben.

Mit Mathematica geht das ganze übrigens so:
J[{x_, y_, t_}] := {{2 (x - 2), 2 (y - 4), -2 (t - 2)}, {2 (x + 6),
2 (y - 2), -2 (t - 1)}, {2 (x + 4), 2 (y + 2), -2 (t - 3)}}

f[{x_, y_, t_}] := {(x - 2)^2 + (y - 4)^2 - (t - 2)^2, (x + 6)^2 + (y -
2)^2 - (t - 1)^2, (x + 4)^2 + (y + 2)^2 - (t - 3)^2}

r = {3, 1, 0}

Zeitschritt:

r = r + {x, y, t} /. N[Solve[J[r].{x, y, t} == -f[r], {x, y, t}][[1]]]

chaostilo aktiv_icon

23:20 Uhr, 25.05.2009

Leider doch noch nicht alles klar,

ich hab das gerade erstmal versuch in einem KOS einzutragen...bei der iterativen Lösung sollten doch eigentlich die gesuchten Koordinaten des Empfängers und die gesuchte Zeit raus kommen...

$Δ$ x, $Δ$ y verstehe ich als die gesuchten Empfängerkoordinaten und $Δ$ z als die gesuchte Zeit...

Damit hab ich im KOS leider nicht so viel Erfolg...die Koordinaten kann ich zwar eintragen, jedoch ergibt $Δ$ z als Zeit keinen Sinn, da die Empfänngerzeit ja größer sein muss, als die Zeit, zu der das Signal ausgesendet wurde...

Und dann noch eine Frage: wo ist die Geschwindigkeit hin?

(weil v=1 betrug einfach nicht mehr mitgeschleppt)...?

Hoffentlich blamier ich mich hier nicht mit dieser Frage :)...

Danke nochmal.

el holgazán aktiv_icon

13:03 Uhr, 26.05.2009

Hallo :-)

Nein nicht ganz.

Δ x = x_{1} - x_{0}

Das heisst um den nächsten Schritt zu erhalten muss man rechnen:

x_{1} = x_{0} + Δ x_{0}

Wenn du also

Δ x

bestimmt hast, musst du das noch mit der alten Lösung addieren.

Dass die Zeit in ersten oder zweiten Schritt keinen Sinn macht macht nicht unbedingt etwas - es kann sein, dass sich die Lösung erst nach ein paar Schritten auf die richtige Lösung zubewegt (siehe mein Beispiel).

Was auch sein kann ist, dass du den falschen Punkt findest - es gibt ja zwei Lösungen zum Problem. Wenn du nun mit Anfangsbedingungen starest kann es sein, dass du die falsche Lösung erhälst. In diesem Falle versuche es nochmal neu mit anderen Anfangsbedingungen.

Ich habe bei meinem Beispiel v=1 gesetzt und es somit einfach weggelassen. Natürlich kannst du für v auch etwas anderes einsetzen; v wird wohl deine Übertragungsgeschwindigkeit sein, also so etwas wie Lichtgeschwindigkeit c, was ja einfach eine Konstante ist.

Es kann auch sein dass die obigen Werte die ich benutzt haben überhaupt keinen Sinn machen. Das Beispiel soll nur zeigen wie das Prinzip funktioniert - die effektiven Lösungen können völliger Schwachsinn sein.

chaostilo aktiv_icon

19:03 Uhr, 26.05.2009

k

. dann ist jetzt alles klar,

ich probier dasmorgen nochmal mit einem anderen Beispiel, was ich vorher mal in einem KOS erstelle (um zu wissen, daß es tatsächlich dafür eine Lösung gibt), aber das sollte dann ja auch alles funktionieren.

Vielen herzlichen Dank nochmal für die kompetente HIlfe und einen schönen Tag noch.

MfG

Tilo

chaostilo aktiv_icon

01:36 Uhr, 31.05.2009

Also ich hab Dein ganzes Beispiel mal mit Matlab durchgerechnet.

In Deinem Beispiel ist ein Vorzeichenfehler drin, da ansonsten Deine Jacobi-Matrix nicht stimmt

(x 3 = - 4)

. Ansonsten war alles richtig und hat mir echt wahnsinnig weitergeholfen.

Da Dein Beispiel vollkommen aus der Luft gegriffen war, hab ich mir noch mal ein Beispiel ausgedacht, was wirklich funktioniert, damit ich in einem Koordinatensystem noch mal prüfen konnte, ob die Ergebnisse auch stimmen.

Nun zu meinem Beispiel und der Berechnung mit Matlab:

Die Koordinaten der Sender:

x 1 = 11; y 1 = 7;

Sendezeitpunkt:

3 s

x 2 = 20; y 2 = 11;

Sendezeitpunkt:

2 s

x 3 = 14; y 3 = 18;

Sendezeitpunkt:

1 s

Der Empfänger, der alle Signale zeitgleich zum Zeitpunkt

t = 8 s

empfängt befindet sich an folgenden Koordinaten:

x = 14; y = 11

Als Geschwindigkeit habe ich

v = 1 \frac{m}{s}

angenommen, dennoch schleppe ich die Geschwindigkeit in den Matrizen noch mit. Weiterhin habe ich mich mehr an der Grundformel von Newton orientiert: xn=xn-1-(f(x)/f’(x)), sodaß bei meinem kleinen Prog am Ende gleich die Koordinaten ausgegeben werden.

Bei dem Matlab-Prog hab ich versucht Deine Indizes weitestgehend beizubehalten, sodaß man das alles relativ leicht verstehen sollte.

Nun zum Matlab-Programm-Quellcode:

%näherungsweise gesuchte Koordinaten des Empfängers und die gesuchte Empfangszeit, das sind die willkürlich festgelegten Startwerte für die Berechnung%

x = - 7;

y = 2;

t = 1;

v = 1; % \in \frac{m}{s} -

bei GPS

\to

Lichtgeschwindigkeit, hier entsprechend dem Beispiel wesentlich kleiner%

%Koordinaten der Sender in diesem zweidimensionalen Beispiel%

x 1 = 11;

y 1 = 7;

t 1 = 3;

x 2 = 20;

y 2 = 11;

t 2 = 2;

x 3 = 14;

y 3 = 18;

t 3 = 1;

i = 0;

%Zählvariable für die nachfolgende Schleife zur iterativen Berechnung%

while

i < 50

% Gleichungssystem zur Ermittlung der Empfängerposition%

f 1 = {(x - x 1)}^{2} + {(y - y 1)}^{2} - {(v \cdot (t - t 1))}^{2};

f 2 = {(x - x 2)}^{2} + {(y - y 2)}^{2} - {(v \cdot (t - t 2))}^{2};

f 3 = {(x - x 3)}^{2} + {(y - y 3)}^{2} - {(v \cdot (t - t 3))}^{2};

frn=

[

f1;

f 2; f 3];

%Erzeugung einer Matrix aus den Gleichungen mit einer Spalte und drei Zeilen%

fx1abl=2*(x-x1);
fy1abl=2*(y-y1);
ft1abl=-2*(v*(t-t1));

fx2abl=2*(x-x2);
fy2abl=2*(y-y2);
ft2abl=-2*(v*(t-t2));

fx3abl=2*(x-x3);
fy3abl=2*(y-y3);
ft3abl=-2*(v*(t-t3));

J=

[

fx1abl fy1abl ft1abl; fx2abl fy2abl ft2abl; fx3abl fy3abl ft3abl]; %Erzeugung einer Matrix aus den abgeleiteten Gleichungen mit 3 Spalten und 3 Zeilen%

rn=

[

x;y;t]; %Erzeugen einer Matrix mit den Startwerten%
werte=rn' %zu Ausgabezwecken erfolgt die Ausgabe als transponierte Matrix, hat keinen Einfluß auf Berechnung%
rn1=rn-inv(J)*frn; %Startwert-inverse Jacobimatrix*Matrix aus den nicht abgelittenen Gleichungen%
x=rn1(1); %x-Wert wird neu belegt%
y=rn1(2); %y-Wert wird neu belegt%
t=rn1(3); %t-Wert wird neu belegt%

i = i + 1;

end

und hier die Ergebnisse:

1. Iteration:x=-7;

y = 2; t = 1

2. Iteration:x=11.6584;

y = - 0.7079; t = 75.9059

3. Iteration:x=12.9239;

y = 5.6197; t = 39.2058

4. Iteration:x=13.5485;

y = 8.7423; t = 21.0945

5. Iteration:x=13.8450;

y = 10.2250; t = 12.4951

6. Iteration:x=13.9667;

y = 10.8337; t = 8.9647

7. Iteration:x=13.9977;

y = 10.9884; t = 8.0670

8. Iteration:x=14.0000;

y = 10.9999; t = 8.0004

9. Iteration:x=14.0000;

y = 11.0000; t = 8.0000

10

. Iteration:x=14.0000;

y = 11.0000; t = 8.0000

11

. Iteration:x=14.0000;

y = 11.0000; t = 8.0000

Man sieht, daß trotz der sehr schlechten Startwerte bereits nach der 9. Iteration das genaue Ergebnis ermittelt wurde. Respekt vor Newton, der das ganze noch ohne Computer rausgefunden hat und das alles von Hand rechnen musste...nicht schlecht :-)...

So, damit ist die Sache dann ja jetzt endlich mal komplett dokumentiert. Ich hatte vorher vergeblich in diversen Foren nach einem Beitrag gesucht, in dem das mal vollständig und beispielhaft erklärt wird. Leider erfolglos. Ich hoffe, daß einige davon noch profitieren können.

Dann nochmal vielen Dank für die kompetente Hilfe.

MfG

Tilo

616523

614786

	Status: nicht eingeloggt	Noch nicht registriert?