Diplomarbeit - uni-weimar.de · Lineare Systeme dieser Art können z.B. direkt mit dem Gauß-Jordan-Algorithmus gelöst werden. Die Lösung eines nichtlinearen Gleichungssystems dieser

Diplomarbeit

Anwendung der Differentiations-Arithmetik für Aufgaben derAusgleichungsrechnung

Jens KerstenMatrikel-Nr.: 211111

Studiengang: Vermessungswesen

Vergeben von: Prof. Dr.-Ing. Lothar GründigBetreut durch: Dipl.-Ing. Christian ClemenEingereicht am: 12.02.2008

Inhaltsverzeichnis

Inhaltsverzeichnis I

Ehrenwörtliche Erklärung IV

1 Einführung 1

2 Grundlagen und Verfahren zur Lösung von Minimierungsaufgaben 22.1 Taylorapproximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Newton-Raphson-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.4 Halley-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.5 Minimierung einer nichtlinearen skalaren Funktion . . . . . . . . . . . . . . . . 5

2.5.1 Eigenschaften der gesuchten Minima . . . . . . . . . . . . . . . . . . . . 62.6 Zusammenhang zwischen Nullstellen- und Minimierungsaufgaben . . . . . . . . 72.7 Zwischenfazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.8 Lösung der Minimierungsaufgabe . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.8.1 Newton-Raphson-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . 82.8.2 Gauß-Newton-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.8.3 Vergleich der Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Automatisches Differenzieren 133.1 Motivation und Entwicklungsverlauf . . . . . . . . . . . . . . . . . . . . . . . . 133.2 Mathematische Grundlagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.3 Anwendung von AD in Computerprogrammen . . . . . . . . . . . . . . . . . . . 163.4 Die Forward-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.5 Die Backward-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.6 Implementierung von AD in FADBAD++ . . . . . . . . . . . . . . . . . . . . . 203.7 Vergleich der beiden Methoden . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

4 Implementierung des Newton-Raphson-Verfahrens 244.1 Anpassung des Berechnungsablaufs . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Spezialisierung von Funktionen der Klassentemplates . . . . . . . . . . . . . . . 264.3 Forward-Forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.4 Forward-Backward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294.5 Backward-Forward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.6 Backward-Backward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.7 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

5 Implementierung des Halley-Verfahrens 345.1 Nutzung der STL-Containerklasse map für Ableitungen dritter Ordnung . . . . 35

I

Inhaltsverzeichnis

5.2 Bestimmung partieller Ableitungen dritter Ordnung mit FADBAD++ . . . . . 365.3 Die Methode solveSNE() und Tensoren dritter Stufe . . . . . . . . . . . . . . . 38

5.3.1 Supersymmetrische Tensoren . . . . . . . . . . . . . . . . . . . . . . . . 385.3.2 Die Methode solveSNE() . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

6 Modifikation von FADBAD++ für Sparse-Vektoren 426.1 Der Operator * . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436.2 Die Funktion atan() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.3 Ergebnisse der Modifikation und Fazit . . . . . . . . . . . . . . . . . . . . . . . 44

7 Numerische Ergebnisse der implementierten Verfahren 467.1 Laufzeituntersuchung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467.2 Konvergenzverhalten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497.3 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

8 Robuste Parameterschätzung mit dem Newton-Raphson-Verfahren 558.1 Homogenisierung des Gauß-Markov-Modells . . . . . . . . . . . . . . . . . . . . 558.2 Allgemeines Konzept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568.3 M-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

8.3.1 Huber-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578.3.2 modifizierter Huber-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . 578.3.3 Hampel-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588.3.4 Biweight-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598.3.5 Fair-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598.3.6 Talwar-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608.3.7 Welsch-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618.3.8 Lp-Norm-Schätzer: Sonderfall p = 1.5 . . . . . . . . . . . . . . . . . . . 618.3.9 Lp-Norm-Schätzer: Sonderfall p = 2 . . . . . . . . . . . . . . . . . . . . 628.3.10 Krarup-Schätzer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

8.4 M-Schätzung mit dem Newton-Raphson-Verfahren . . . . . . . . . . . . . . . . 638.5 Untersuchung robuster Schätzer am Beispiel linearer und nichtlinearer Ausglei-

chungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648.5.1 Neupunktbestimmung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648.5.2 Ausgleichende Gerade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708.5.3 Ausgleichender Kreis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 758.5.4 Fazit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

8.6 Implementierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

9 Schlussbetrachtung und Ausblick 84

10 Anhang 8610.1 Generische Programmierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8610.2 Entwurfsmuster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

10.2.1 Besucher-Muster . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8810.2.2 Schablonenmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

10.3 Implementierung verschiedener Ausgleichungsansätze . . . . . . . . . . . . . . . 8910.4 Der bisherige Einsatz von AD in GENERAL . . . . . . . . . . . . . . . . . . . . 93

II

Inhaltsverzeichnis

10.5 Erweiterung von FADBAD++ durch die Funktion fabs() . . . . . . . . . . . . . 9410.6 Entwicklungsumgebung und Rechnermerkmale . . . . . . . . . . . . . . . . . . 95

11 Literaturverzeichnis 96

Inhalt der beiliegenden CD

Die CD enthält den gesamten in dieser Arbeit erweiterten C++-Quellcode des Ausgleichungs-Frameworks sowie eine digitale Version dieser Arbeit (pdf-Format). Sämtliche Plots von Funk-tionen und Daten wurden mit dem kostenlos erhältlichen Programm gnuplot 4.2 erstellt. Fürjeden Plot wurde eine Script-Datei (Endung .plt), in der alle Befehle für das Plotten einesGraphen gespeichert werden, erstellt. Diese Dateien können mit jedem beliebigen Texteditorgeöffnet und bearbeitet werden. Das Programm gnuplot und alle in dieser Arbeit erstelltenPlot-Dateien befinden sich ebenfalls auf der CD. Diese hat die folgende Ordnerstruktur:

Ordner Inhaltgnuplot gnuplot Version 4.2Grafiken_gnuplot In weiteren Unterordnern sind die Script-Dateien der Plots und die

Ergebnisdateien im png-Format enthalten.Implementierung Quellcode

III

Ehrenwörtliche Erklärung

„Ich versichere hiermit ehrenwörtlich durch meine Unterschrift, dass ich die vorstehende Di-plomarbeit selbständig und ohne Benutzung anderer als der angegebenen Hilfsmittel angefer-tigt habe. Alle Stellen, die wörtlich oder sinngemäß aus veröffentlichten oder unveröffentlichtenSchriften oder dem Internet entnommen worden sind, sind als solche kenntlich gemacht. Keineweiteren Personen waren an der geistigen Herstellung der vorliegenden Arbeit beteiligt. DieArbeit hat noch nicht in gleicher oder ähnlicher Form oder auszugsweise im Rahmen eineranderen Prüfung dieser oder einer anderen Prüfungsinstanz vorgelegen.“

........................................... ...........................................Ort, Datum Unterschrift

IV

1 Einführung

Das Fachgebiet für Geodäsie und Ausgleichungsrechnung an der TU-Berlin entwickelt einegeodätische Software zur Erfassung dreidimensionaler Gebäudegeometrien. Im Gegensatz zuanderer Bau- und Architektursoftware werden hier Methoden der Ausgleichungsrechnung ver-wendet.

Neu an dem Ansatz ist, dass jeder empirische Beobachtungswert als statistische Größebetrachtet wird, wodurch aus den redundant gespeicherten Messwerten statistisch gesicherteAussagen bezüglich Qualität und Zuverlässigkeit getroffen werden können.

Das zu diesem Zweck in C++ erarbeitete generische Ausgleichungs-Framework (GENERAL)ist dabei so allgemein wie möglich formuliert, so dass sich eine Anwendung dieser Bibliotheknicht auf das angesprochene Gebäude-Informationssystem (GebIS) beschränkt, sondern aufbeliebige Ausgleichungsprobleme anwenden lässt. Ein Nutzer dieses Frameworks muss ledig-lich den Typ der Unbekannten und Beobachtungen sowie den funktionalen Zusammenhangangeben. Je nach Art des funktionalen Zusammenhangs kann dann zwischen den Ansätzenvermittelnde Ausgleichung mit Unbekannten (Gauß-Helmert-Modell), bedingte Ausgleichungund vermittelnde Ausgleichung (Gauß-Markov-Modell) gewählt werden. Zusätzliche Bedin-gungen zwischen den Unbekannten können ebenfalls eingeführt werden.

Im Zuge der Anwendung des Gauß-Newton-Verfahrens für die Parameterschätzung wird fürdie Linearisierung der meist nichtlinearen Beobachtungsgleichungen das automatische Diffe-renzieren (AD) angewendet. Die Bibliothek FADBAD++ [13] nutzt dabei die Operatorüber-ladung in C++, wodurch gleichzeitig mit der Berechnung eines Funktionswertes die exaktenpartiellen Ableitungen (auch höherer Ordnung) einer Funktion berechnet werden können, oh-ne die analytischen Formeln dieser Ableitungen zu kennen.

In der vorliegenden Arbeit wird die Anwendung des automatischen Differenzierens bei derLösung von Ausgleichungsproblemen im Gauß-Markov-Modell untersucht. In diesem Kontextwird das Newton-Raphson- und das Halley-Verfahren vorgestellt und deren Implementierun-gen erläutert. Das Halley-Verfahren stellt eine Erweiterung des Newton-Raphson-Verfahrensdar, in der nicht nur partielle Ableitungen zweiter, sondern auch dritter Ordnung in jedemIterationsschritt neu bestimmt werden müssen.

In die Untersuchungen werden neben der Methode der kleinsten Quadrate auch alternativeSchätzverfahren einbezogen. So wird in Abschnitt 8 die Klasse der M-Schätzer vorgestellt unddie Anwendung des Newton-Verfahrens anhand von Beispielen untersucht.

Obwohl das automatische Differenzieren in der Mathematik und in anderen Disziplinenweit verbreitet ist, wird es in der Geodäsie kaum angewendet. Die beiden vorliegenden Metho-den des automatischen Differenzierens werden deshalb anhand von Beispielen erläutert undKombinationen der Methoden für höhere partielle Ableitungen getestet. Dabei wird besondersdetailliert auf die Anwendung der Bibliothek FADBAD++ eingegangen, da dies insbesonderefür höhere Ableitungen teilweise sehr komplex und selbst in der Dokumentation der Bibliotheknur sehr knapp beschrieben ist.

1

2 Grundlagen und Verfahren zur Lösungvon Minimierungsaufgaben

Die auf dem Aufgabenfeld der Geodäsie gesuchten physikalischen Parameter können meistnicht direkt gemessen werden. Jedoch können Beobachtungen über funktionale Beziehungen(2.1) mit den Parametern in Verbindung gebracht werden.

l = f (x,k) (2.1)

Dabei hängen die Funktionen f nicht zwingend nur von den Parametern x und den fehlerfrei-en Konstanten k ab (Gauß-Markov-Modell), sondern mitunter auch von den Beobachtungenl selbst(Gauß-Helmert-Modell). Jedes Ausgleichungsproblem lässt sich jedoch in das Gauß-Markov-Modell überführen [5], so dass sich die Untersuchungen in dieser Arbeit auf diesesmathematische Modell beschränken.

Da die wahren Werte l unbekannt sind, werden an deren Stelle die tatsächlichen Beobach-tungen l verwendet. Die Beobachtungen l sind Schätzwerte für die wahren Werte l und unter-liegen zufälligen Messfehlern, wodurch die Konsistenz des Gleichungssystems (2.1) nicht mehrgewährleistet ist. Um die Konsistenz des Gleichungssystems nach diesem Schritt zu erhalten,werden kleine Verbesserungen v eingeführt. Damit ergibt sich für das allgemeine funktionaleModell

l + v = f (x,k). (2.2)

Um die Schätzwerte x der Parameter zu bestimmen, können verschiedene Forderungen an-gesetzt werden. So soll bei der Methode der kleinsten Quadrate (L2-Norm) die gewichteteQuadratsumme der Verbesserungen minimiert werden:

Ω = vTPv→ min. (2.3)

Dieser Ansatz liefert die bestmöglichste und wahrscheinlichste Schätzung, da die Minimie-rung der Verbesserungsquadratsumme gleichbedeutend mit einer Maximierung der Maximum-Likelihood-Funktion ist. (Siehe dazu z.B. [5] Seite 101f .)

Zielfunktion (2.3) zeigt, dass sich ein Ausgleichungsproblem als Minimierungs- bzw. Op-timierungsproblem formulieren lässt. So wird bei der L1-Norm die Summe der Beträge derVerbesserungen, und bei der L∞-Norm der Betrag der größten Verbesserung minimiert. Beinichtlinearen funktionalen Zusammenhängen ergibt sich, unabhängig vom Lösungsansatz, stetsein Iteratives Verfahren, für welches Näherungswerte benötigt werden.

In diesem Abschnitt werden zunächst zwei Verfahren zur Bestimmung von Nullstellen nicht-linearer Funktionen und deren mehrdimensionale Erweiterung vorgestellt. Auf dieser Grund-lage wird der Zusammenhang zwischen der Bestimmung von Nullstellen eines nichtlinearenGleichungssystems und der Bestimmung von Minimia einer Zielfunktion dargelegt und in die-sem Kontext das Gauß-Newton-Verfahren und das Newton-Raphson-Verfahren erklärt undverglichen.

2

2 Grundlagen und Verfahren zur Lösung von Minimierungsaufgaben

Grundlegendes Werkzeug für die Herleitung von Lösungsalgorithmen ist die bekannte Tay-lorapproximation.

2.1 Taylorapproximation

Mit einem Taylorpolynom der Form

Tx0,n(x) =f (k)(x0)

k!(x− x0)

k , k = 1, ...n (2.4)

wird eine Funktion f an der Stelle x0 approximiert. Voraussetzung dafür ist die n-malige stetigeDifferenzierbarkeit der Funktion. Ist diese Voraussetzung erfüllt, so kann man eine Konvergenzdes Taylorpolynoms gegen die Funktion in der gewählten Umgebung von x0 erwarten:

f(x) = limn→∞

Tx0,n(x). (2.5)

Für die meisten Anwendungen wird die Taylorreihe Tx0,1(x) verwendet, da hier lediglich Ab-leitungen erster Ordnung auftreten. In diesem Fall spricht man von einer Linearisierung vonf an der Stelle x.

Ist eine Funktion f von mehreren Variablen abhängig (also f : Rn → R), so ergibt sich füreine Approximation zweiter Ordnung (n = 2):

Tx0,2(x) = f(x0) +∇f(x0)T (x− x0) +12

(x− x0)T ∇2f(x0) (x− x0) , (2.6)

wobei f von x = (x1, ..., xn)T abhängt, ∇f(x0) der Gradient und ∇2f(x0) die Hesse-Matrixvon f an der Stelle x0 ist. Der Aufwand einer Approximation steigt hier für höhere Ordnungenim Gegensatz zum eindimensionalen Fall stark an. Je Erhöhung der Ordnung k müssen nk

zusätzliche partielle Ableitungen bestimmt werden.

2.2 Newton-Verfahren

Mit dem von Isaac Newton (1643 - 1727) entwickelten Verfahren können Nullstellen von Funk-tionen f : R→ R bestimmt werden. Ist die Funktion f in x0 stetig differenzierbar, kann diesemittels Taylorapproximation linearisiert werden:

f(x) = f(x0) + f ′(x0) · (x− x0) . (2.7)

Da an der gesuchten Nullstelle f(x) = 0 gilt, ergibt sich die Iterationsvorschrift

xk+1 = xk −f(xk)f ′(xk)

. (2.8)

Für die Lösung der Aufgabe wird ein Startwert x0 benötigt. Liegt dieser im Konvergenzbe-reich der gesuchten Nullstelle, so weist das Verfahren eine quadratische Konvergenz gegendie Nullstelle auf. Da es bei schlechten Näherungswerten zu Divergenz, Oszillation oder zuKonvergenz gegen eine nicht gewünschte Nullstelle kommen kann, spricht man von lokalerKonvergenz. Abgebrochen wird die Iteration, sobald f(xk) < ε oder |xk+1 − xk| < ε, wobei εein geeignet gewählter Schrankenwert ist.

3


2.3 Newton-Raphson-Verfahren

Hierbei handelt es sich um eine Erweiterung des Newton-Verfahrens für mehrdimensionaleFunktionen bzw. Gleichungssysteme F(x) : Rn → Rn mit so vielen Gleichungen wie Unbe-kannte. Lineare Systeme dieser Art können z.B. direkt mit dem Gauß-Jordan-Algorithmusgelöst werden. Die Lösung eines nichtlinearen Gleichungssystems dieser Art ist meist nichtgeschlossen möglich und erfolgt deshalb iterativ. Es ist also die Nullstellenaufgabe

F(x) = 0 (2.9)

zu lösen. Dabei ist F = (f1, ..., fn)T ein Vektor mit n Funktionen, welche von n Unbekanntenx = (x1, ..., xn)T abhängen. Eine Iterationsvorschrift ergibt sich aus der Anwendung der Tay-lorapproximation auf alle Gleichungen des Systems. Durch den Abbruch der Approximationnach dem Glied erster Ordnung ergibt sich, analog zum eindimensionalen Fall, eine lineare Er-satzaufgabe des ursprünglichen Problems. Durch die Forderung F(x) = 0 erhält man folgendeIterationsvorschrift1:

xk+1 = xk − F′(xk)−1F(xk), (2.10)

wobei F(xk) der Vektor mit den an der Stelle xk ausgewerteten Funktionen fi und F′(xk) dieJakobimatrix mit den Ableitungen ∂fi/∂xj , mit i, j = 1, ..., n, darstellt. Als Abbruchkriteriumkann z.B. die euklidische Norm ‖F(x)‖ < ε oder die Maximumnorm ‖F(x)‖∞ < ε gewähltwerden.

Voraussetzung für die Lösbarkeit des Nullstellenproblems ist die Regularität der Jakobima-trix F′(xk), was der Forderung nach linearer Unabhängigkeit der Spalten- bzw. Zeilenvektorendieser quadratischen Matrix entspricht. Auch hier ist zu beachten, dass alle Aussagen überdie Lösbarkeit des Nullstellenproblems von lokalem Charakter sind, so dass unterschiedlicheStartwerte x0 unter Umständen gegen verschiedene Lösungen konvergieren können.

Für Startwerte aus einer geeignet kleinen Umgebung der gesuchten Lösung (reguläre Null-stelle) weist das Newton-Raphson-Verfahren, entsprechend dem eindimensionalen Fall, einelokale quadratische Konvergenz auf.

2.4 Halley-Verfahren

Dieses nach Edmond Halley (1656 - 1742) benannte Verfahren zur Bestimmung von Nullstel-len von nichtlinearen Gleichungen und Gleichungssystemen ergibt sich aus der quadratischenApproximation des Gleichungssystems F(x)

F(x) = F(x0) + F′(x0)T (x− x0) +12

(x− x0)T F′′(x0) (x− x0) , (2.11)

wobei F(x), x und x0 Vektoren, F′(x0) die Jakobi-Matrix und F′′(x0) ein Tensor dritterStufe im Entwicklungspunkt x0 ist. Voraussetzung für diese quadratische Approximation istdie zweimal stetige Differenzierbarkeit von F in x0.

1Hinweis zur Notation: Die ersten partiellen Ableitungen stehen hier in einer Matrix. Um den Unterschiedzum Gradienten ∇f zu verdeutlichen, wird hier die Schreibweise F′ verwendet.

4


Mit der Eigenschaft F(x) = 0 an der gesuchten Nullstelle ergibt sich die Iterationsvorschrift

xk+1 = xk −F(xk)

F′(xk) + 12F′′(xk)(xk+1 − xk)

, (2.12)

welche jedoch nicht geschlossen ausgewertet werden kann, da der Term der Iterierten abhängigvon xk+1 ist. Nimmt man jedoch für (xk+1 − xk) das Ergebnis aus der Newton-Raphson-Iteration F′(xk)−1F(xk), so ergibt sich folgende Iterationsvorschrift [12]:

1) Newton-Schritt: F′(xk)xa = −F(xk)

2) Halley-Korrektur:[F′(xk) + 1

2F′′(xk)xa

]xb = −1

2F′′(xk)xaxa

3) Aufdatierung: xk+1 = xk + xa + xb

Dieses Vorgehen verdeutlicht, dass es sich hier um eine Erweiterung des Newton-Raphson-Verfahrens handelt. Durch die Lösung des Systems in Schritt 2 wird die Newton-Lösung ausSchritt 1 korrigiert, wodurch, äquivalent zu der Anwendung einer Approximation zweitenGrades, bei hinreichend guten Startwerten eine kubische Konvergenz zu erwarten ist.

Das Halley-Verfahren kann unter anderem auch durch die Anwendung des Newton-Verfahrensauf die Approximation f(x) = f(x)√

|f ′(x)|hergeleitet werden.

2.5 Minimierung einer nichtlinearen skalaren Funktion

Nach der Behandlung von Nullstellen nichtlinearer Gleichungen soll nun die Minimierungsauf-gabe

min f(x) : x ∈ Rn (2.13)

betrachtet werden, wobei f : Rn → R eine skalare Funktion ohne Nebenbedingungen, und Rn

der Raum aller n-dimensionalen reellen Vektoren x = (x1, ..., xn)T ist. Gesucht wird demnachdie globale Minimumstelle x von f auf Rn, so dass

f(x) ≥ f(x) ∀ x ∈ Rn (2.14)

gilt. Bei der Behandlung von Minimierungsproblemen kommt dem Begriff Konvexität einezentrale Bedeutung zu. Anschaulich gesehen ist eine Teilmenge D0 ⊂ Rn konvex, wenn dieVerbindungsgerade zwischen zwei Punkten x, y ∈ D0 ebenfalls komplett Teil der Menge D0

ist, also [x, y] ∈ D0 ∀ x, y ∈ D0 gilt.

5


Satz 1

Die Funktion f : Rn → R sei auf der konvexen Menge D0 differenzierbar. Dann ist f genaudann konvex auf D0, wenn

f(y) ≥ f(x) +∇f(x)T(y − x) ∀ x,y ∈ D0 (2.15)

gilt, und f ist genau dann gleichmäßig konvex auf D0, wenn

f(y) ≥ f(x) +∇f(x)T(y − x) +m

2‖y − x‖2 ∀ x,y ∈ D0 (2.16)

mit einem m > 0 gilt ([10] Seite 38).

Die rechte Seite in (2.15) entspricht der linear approximierten Funktion f . Geometrischbedeutet Konvexität somit, dass auf einem definierten Intervall die Tangentialebene in einemPunkt x komplett „unter“ der durch die Funktion f beschrieben Fläche liegt.

2.5.1 Eigenschaften der gesuchten Minima

Meist ist keine Information über die Eigenschaften der zu minimierenden Funktion vorhanden,so dass lediglich in der Umgebung der Startwerte geprüft werden kann, ob es sich bei derermittelten Lösung tatsächlich um ein Minimum handelt. Dieser Umstand führt dazu, dassoft keine gesicherte Aussage getroffen werden kann, ob das gefundene Minimum global ist. Esgilt bekanntlich, dass jedes globale Minimum auch ein lokales Minimum ist. Diese Aussage istjedoch nicht umkehrbar. Die folgende Aussage ist eine notwendige Bedingung für das Vorliegeneiner Nullstelle ([10], Seite 65).

Aussage 1

Es sei x ∈ Rn eine lokale Minimumstelle der Funktion f : Rn → R, und sei f in x differen-zierbar. Dann gilt

∇f(x) = 0. (2.17)

Voraussetzung für die Lösbarkeit einer Minimierungsaufgabe sind gewisse Definitheitsbe-dingungen an die Hesse-Matrix der zu minimierenden Funktion ([10], Seite 66):

Aussage 2

Die Funktion f : Rn → R sei im Punkt x ∈ Rn zweimal differenzierbar.

(i) Falls x lokale Minimumstelle von f ist, so gilt ∇f(x) = 0, und die Hesse-Matrix ∇2f(x)ist positiv semidefinit.

(ii) Gilt ∇f(x) = 0 und ist ∇2f(x) positiv definit, so ist x lokale Minimumstelle von f .

(iii) Gilt ∇f(x) = 0 und ist ∇2f(x) negativ definit bzw. indefinit, so ist x keine lokale Mini-mumstelle von f , sondern eine lokale Maximumstelle bzw. ein Sattelpunkt von f .

(i) stellt eine notwendige, und (ii) eine hinreichende Bedingung für das Vorliegen einerMinimumstelle in einem stationären Punkt x dar.

6


2.6 Zusammenhang zwischen Nullstellen- undMinimierungsaufgaben

Nachdem die Minimalstellen von Funktionen charakterisiert wurden, soll nun dargelegt wer-den, wie und unter welchen Voraussetzungen ein überbestimmtes Gleichungssystem in eineMinimierungsaufgabe umformuliert werden kann, und welche Vorteile diese Transformationmit sich bringt. Nach Aussage 1 ist jede Lösung der Minimierungsaufgabe

min f(x) : x ∈ Rn (2.18)

notwendig auch Lösung der Nullstellenaufgabe

∇f(x) = 0. (2.19)

Die Nullstellenaufgabe (2.19) kann als Ersatzproblem der ursprünglichen Minimierungsaufga-be (2.18) gesehen werden.

Umgekehrt lässt sich eine Nullstellenaufgabe F(x) als Minimierungsaufgabe formulieren,wenn ein f(x) existiert, so dass F(x) := ∇f(x) gilt. Dabei ist jedoch zu beachten, dass dieHesse-Matrix der Zielfunktion f(x) symmetrisch und positiv semidefinit sein muss (Aussage2). Sind diese Voraussetzungen erfüllt, so ist die Zielfunktion in der Umgebung von x konvexund die Minima von f(x) entsprechen den Nullstellen von F(x). Ist die Konvexitätsforderungnicht erfüllt, können bei dieser Transformation unter Umständen Lösungen verloren gehen.

Um die Behandlung überbestimmter Systeme zu ermöglichen, erfolgt die „Konstruktion“einer Zielfunktion, so dass sie der oben angesprochenen Definitheitsvoraussetzung genügt. AmAnfang dieses Abschnitts wird gesagt, dass sich ein Ausgleichungsproblem

l + v = f (x,k) (2.20)

durch die Minimierung einer Norm als Minimierungsaufgabe, wie z.B. im Falle der L2-Norm

Ω = vTPv→ min (2.21)

formulieren lässt. Dadurch ist die Zielfunktion Ω so beschaffen, dass die Nullstellen von (2.20)unter den Minima von (2.21) zu finden sind. Diese Herangehensweise erweist sich auch dannals sinnvoll, wenn die Gleichungen (2.20) keine Nullstellen besitzen, da in diesem Fall die besteLösung im Sinne der gewählten Norm gefunden wird ([10], Seite 71).

In diesem Zusammenhang hat die L2-Norm eine entscheidende Bedeutung, da bei einer An-wendung auf linearisierte Beobachtungsgleichungen (Gauß-Newton-Verfahren) die oben an-gesprochene Definitheitsbedingung in jedem Fall erfüllt ist und somit immer eine Lösunggefunden werden kann ([10] Seite 272f). Unabhängig von den hier behandelten Verfahren istdabei allerdings zu beachten, dass bei nicht Einhalten der Konvexitätsbedingung unter Um-ständen eine falsche Lösung berechnet wird, da in diesem Fall das globale Minimum bei derTransformation in ein Minimierungsproblem verloren gehen kann.

2.7 Zwischenfazit

Bevor auf die Lösung von Minimierungsaufgaben eingegangen wird, sollen die bis jetzt gewon-nenen Erkenntnisse zusammengetragen werden.

7


• Für die Lösung nichtlinearer Gleichungssysteme wird stets ein Ersatzproblem formuliert,welches iterativ gelöst werden kann.

• Bei den hier vorgestellten und gängigen Verfahren zur Bestimmung von Nullstellen han-delt es sich um lokale Verfahren.

• Je nach Approximationsgrad des ursprünglichen Problems ändert sich auch die lokaleKonvergenzrate der resultierenden Iterationsvorschrift.

• Bei einem nichtlinearen Gleichungssystem F(x) : Rn → Rn ist der Aufwand für dieBerechnung der partiellen Ableitungen insbesondere bei der Verwendung des Halley-Verfahrens sehr hoch, da hier die Taylorapproximation erst nach dem Term zweiterOrdnung abgebrochen wird. Symmetrieeigenschaften der Ableitungen wurden dabei bisjetzt außer Acht gelassen.

• Ein überbestimmtes Gleichungssystem kann durch das Ansetzen einer Ausgleichungsfor-derung [7] in eine Minimierungsaufgabe umformuliert werden. Ist die Hesse-Matrix derZielfunktion positiv semidefinit, so ist die Zielfunktion in x konvex und es geht keineLösung durch die Transformation des Problems verloren.

2.8 Lösung der Minimierungsaufgabe

Wie oben festgestellt, kann ein überbestimmtes Gleichungssystem z.B. durch das Ansetzen dereuklidischen Norm (Methode der kleinsten Quadrate) als Minimierungsaufgabe formuliert wer-den. Im Hinblick auf die Anwendng des automatischen Differenzierens ist eine Lösung dieserAufgabe mit dem Newton-Raphson-Verfahren sehr interessant, denn hier werden die partiellenAbleitungen unabhängig von der Problemstellung mit dem gleichen minimalen Programmier-aufwand bereitgestellt und der Lösungsalgorithmus ändert sich durch die Linearisierung nachder Formulierung der Normalgleichungen für alternative resp. robuste Zielfunktionen nicht.Aus diesem Grund wird nun das Newton-Raphson-Verfahren vorgestellt und mit dem Gauß-Newton-Verfahren verglichen. Alle Ausführungen beschränken sich dabei zunächst auf dieMethode der kleinsten Quadrate.

2.8.1 Newton-Raphson-Verfahren

Für ein überbestimmtes Gleichungssystem wird im ersten Schritt die gewünschte ZielfunktionΩ(x) aus den ursprünglichen Verbesserungsgleichungen formuliert. Für die Schätzwerte x,welche die stationären Punkte dieser Funktion darstellen, muss nach Aussage 1 die Forderung

∇Ω (x) =∂Ω∂xi

= 0, i = 1, . . . , u (2.22)

erfüllt werden. u entspricht dabei der Anzahl der gesuchten Parameter.Die sogenannten Normalgleichungen in∇Ω (x) werden nun mittels Taylorapproximation ersterOrdnung linearisiert.

∇Ω(x) = ∇Ω(x) +∇2Ω(x) · (x− x) (2.23)

Wie oben angesprochen, ergibt sich durch diese Vorgehensweise ein von der Zielfunktion un-abhängiger Algorithmus, wonach die Implementierung unterschiedlicher Schätzfunktionen in

8


Computerprogrammen erheblich vereinfacht wird. Für die Berechnung der Ableitungen ersterund zweiter Ordnung kann das automatische Differenzieren angewendet werden. Die analy-tischen Formeln der Ableitungen müssen deshalb nicht für jede Aufgabenstellung hergeleitetund implementiert werden.

Aus Forderung (2.22) folgt für die gesuchten differenziellen Zuschläge ∆x zu den Nähe-rungswerten:

(x− x) = ∆x = (−∇2Ω(x))−1 · ∇Ω(x). (2.24)

Dabei enthält der Vektor ∇Ω(x) die ersten partiellen Ableitungen (Gradient) und die symme-trische Matrix ∇2Ω die zweiten partiellen Ableitungen (Hesse-Matrix) der Zielfunktion Ω(x)nach den Unbekannten an der Stelle x. Im Falle der Methode der kleinsten Quadrate kann dieexakte Lösung bei linearen Beobachtungsgleichungen aufgrund der quadratischen Konvergenzdes Verfahrens in einem Iterationsschritt exakt berechnet werden.

2.8.2 Gauß-Newton-Verfahren

Das Gauß-Newton-Verfahren ist das wohl bekannteste und am meisten eingesetzte Verfah-ren zur Schätzung von Parametern. Hier werden die Verbesserungsgleichungen f(x,k) vor derBildung der Normalgleichungen mittels Taylorapproximation erster Ordnung an der Stelleder Näherungswerte x0 linearisiert und das resultierende lineare Problem dann im Sinne derMethode der kleinsten Quadrate exakt gelöst. Durch diese Vorgehensweise ist der Algorith-mus auf die euklidische Norm begrenzt. Legt man die Zielfunktion (2.21) zugrunde, ergebensich die hinlänglich bekannten Gebrauchsformeln für eine vermittelnde Ausgleichung. Für dieVerbesserungen im linearisierten Modell gilt

v = Ax− l. (2.25)

Um die Minimierungsaufgabe zu lösen, muss die erste Ableitung der Zielfunktion Ω verschwin-den.

Ω = vTPv =(xTAT − lT

)P (Ax− l) (2.26)

∂Ω∂x

= 0 (2.27)

Aus dieser Forderung ergibt sich für die gesuchten Parameter x der vertraute Ausdruck

x =(ATPA

)−1ATPl. (2.28)

Durch das in jedem Fall positiv semidefinite Produkt N = ATPA wird problemunabhängigKonvexität erzwungen. Dadurch kann das Gleichungssystem (2.28) in jedem Iterationsschritteindeutig gelöst werden. Es besteht jedoch die Gefahr, dass bei ungünstigen Näherungswertenein nicht gewünschtes Minimum gefunden wird.

2.8.3 Vergleich der Verfahren

Bislang wird die Parameterschätzung in GENERAL nach dem Gauß-Newton-Verfahren durch-geführt. Ebenso wie auch beim Newton-Raphson-Verfahren, handelt es sich um ein lokales Ver-fahren. Die Frage wann Näherungswerte „ausreichend gut“ sind und ob es zu Konvergenz gegen

9


die gewünschte Lösung kommt, kann jedoch bei beiden Verfahren nicht einfach beantwortetwerden. Das folgende Beispiel ([10], Seite 279) verdeutlicht, dass Konvergenz nicht zwingendabhängig von den Näherungswerten sein muss. Auch wenn die Zielfunktion nur ein Minimumbesitzt, und somit dieses auch dem globalen Minimum entspricht, kann unter Umständen keineLösung gefunden werden. Die Beobachtungsgleichungen des Beispiels lauten:

l1 + v1 = 2 + 0, 5x2 (2.29)l2 + v2 = x, (2.30)

mit den Beobachtungen

l1 = 0 und l2 = 0.

Die Ergebnisse der Berechnungen mit dem Gauß-Newton-Verfahren für unterschiedlicheStartwerte x0 sind in Tabelle 2.1 dargestellt.

Iteration 100,0000 1,0000 0,1000 0,0001 ←Startwerte x0

1 49,9750 -0,7500 -0,1975 -0,00022 24,9370 0,8250 0,3765 0,00043 12,3690 -0,8147 -0,6362 -0,00084 5,9835 0,8169 0,8141 0,00165 2,5853 -0,8164 -0,8170 -0,00326 0,4515 0,8165 0,8164 0,00647 -0,7119 -0,8165 -0,8165 -0,01288 0,8252 0,8165 0,8165 0,02569 -0,8147 -0,8165 -0,8165 -0,051110 0,8169 0,8165 0,8165 0,102011 -0,8164 -0,8165 -0,8165 -0,201312 0,8165 0,8165 0,8165 0,383013 -0,8165 -0,8165 -0,8165 -0,643514 0,8165 0,8165 0,8165 0,815915 -0,8165 -0,8165 -0,8165 -0,816616 0,8165 0,8165 0,8165 0,816517 -0,8165 -0,8165 -0,8165 -0,8165

Tabelle 2.1: Ergebnisse des Gauß-Newton-Verfahrens für vier verschiedene Startwerte.

Durch Betrachtung des Graphen (Abbildung 2.1) der Zielfunktion∑ (v2i

)=

(2 + 0, 5 · x2

)2 + x2 (2.31)

lässt sich eine anschauliche Erklärung finden, warum es zur Oszillation kommt. Das einzigeMinimum Pmin dieser biquadratischen Funktion liegt bei x = 0. Durch die Linearisierungder Verbesserungsgleichungen wird jedoch die ursprüngliche Funktion durch die Tangente amEntwicklungspunkt P0 der Taylorreihe (hier x = 0.5) ersetzt und laut Forderung (2.3) derkürzeste Abstand vT vmin zum Beobachtungspunkt (hier (0, 0)) berechnet. Die Quadratsum-me der Verbesserungen eines Iterationsschrittes vT vmin ist somit bei der Methode der kleinstenQuadrate geometrisch gesehen stets ein Lot auf die Tangente der ursprünglichen Zielfunktion.Die Übertragung des Punktes P1 der Tangente zurück auf die ursprüngliche Zielfunktion istdas Ergebnis dieses Iterationsschritts (P2). Wie in Abbildung 2.1 ersichtlich, nähert man sich

10


0

1

2

3

4

5

6

7

−1.5 −1 −0.5 0 0.5 1 1.5

vT v

x

vT v

Tangente

Beobachtungspunkt

vT vmin

P0P2

P1

Pmin6

•

•

•

•

•

Abbildung 2.1: Iterationsschritt

aufgrund der offensichtlich zu großen Schrittweite dem gesuchten Minimum nicht. Unabhän-gig vom Näherungswert alterniert die differentielle Änderung des Parameters x nach einigenSchritten mit ∆x = ±0, 8165 um das gesuchte Minimum.

Für das Newton-Raphson-Verfahren können im Grunde ähnliche Aussagen bezüglich derEigenschaften getroffen werden wie beim Gauß-Newton-Verfahren. Eine universelle Aussageüber die Richtigkeit der gefundenen Lösung eines beliebigen Ausgleichungsproblems lässt sichdemnach auch bei diesem Verfahren nicht treffen. Das oben untersuchte Beispiel aus [10] kannjedoch mit diesem Verfahren korrekt gelöst werden. Dieses Beispiel zeigt, dass das Newton-

Iteration 100,0000 1,0000 0,1000 0,0001 ←Startwerte x0

1 66,6533 0,2222 0,0003 0,00002 44,4156 0,0036 0,00003 29,5804 0,00004 19,67535 13,04946 8,59867 5,58148 3,49659 2,003310 0,891311 0,168912 0,001613 0,0000

Tabelle 2.2: Ergebnis des Newton-Raphson-Verfahrens für vier verschiedene Startwerte.

11


Raphson-Verfahren bezüglich der Methode der kleinsten Quadrate eine Alternative zum Gauß-Newton-Verfahren darstellen kann. Zusammenfassend können folgende Aussagen bezüglich derbeiden hier vorgestellten Verfahren zur Lösung eines Minimierungsproblems getroffen werden:

• In beiden Verfahren sind „ausreichend gute“ Näherungswerte erforderlich. Die Qualitätentscheidet darüber, ob die richtige Lösung gefunden werden kann. Deshalb spricht manvon lokalen Verfahren.

• Das Newton-Raphson-Verfahren weist, sobald die Startwerte im Konvergenzbereich derLösung liegen, eine quadratische Konvergenz auf, wohingegen beim Gauß-Newton-Verfahrenim Allgemeinen mit linearer Konvergenz zu rechnen ist [6]. In beiden Fällen wird beilinearen Ausgleichungsproblemen mit der Methode der kleinsten Quadrate die exakteLösung in einem Iterationsschritt bestimmt.

• Während die Anwendung robuster Schätzer mit dem Gauß-Newton-Verfahren lediglichdurch eine entsprechende Anpassung der Gewichte der Beobachtung erfolgen kann, istder Algorithmus des Newton-Raphson-Verfahrens, durch die Formulierung des Ersatz-problems nach der Bildung der Normalgleichungen, unabhängig von der Wahl der Ziel-funktion.

• Mit dem Newton-Raphson-Verfahren wird eine Bestimmung der zweiten partiellen Ablei-tungen der Zielfunktion nach den zu schätzenden Parametern in jedem Iterationsschritterforderlich.

Die hier angeführten Kriterien zeigen, dass der Ansatz nach Newton-Raphson durchausvorteilhafter sein kann, als das Gauß-Newton-Verfahren. Verwendet man nun das automatischeDifferenzieren für die Berechnung des Gradienten und der Hesse-Matrix, sind für die eigentlicheBerechnung der Parameter weniger Rechenoperationen mit Matrizen als bei Gauß-Newtonnötig.

Bevor beschrieben wird, wie der Einsatz des Newton-Raphson-Verfahrens mit Hilfe derAnwendung des automatischen Differenzierens in Bezug auf das Framework GENERAL um-gesetzt werden kann, soll im folgenden Abschnitt näher auf das automatische Differenzierenund die zu Grunde liegende Differentiations-Arithmetik eingegangen werden.

12

3 Automatisches Differenzieren

In diesem Kapitel wird das automatische Differenzieren (AD) und die zu Grunde liegendeDifferentiations-Arithmetik vorgestellt. Nach einer kurzen Einführung werden die mathema-tischen Grundlagen und die programmiertechnische Umsetzung am Beispiel der BibliothekFADBAD++ erläutert. In den Abschnitten 3.4 und 3.5 werden dann die Ansätze Forward-und Backward-Methode anhand eines konkreten Beispiels dargestellt.

3.1 Motivation und Entwicklungsverlauf

Sowohl in der Schule, als auch verstärkt im Studium, lernt man den Gebrauch von allgemeinenAbleitungsregeln. Dabei wird z.B. der Wert der Ableitung einer Funktion f(x) entweder nu-merisch mittels Differenzenquotient oder analytisch mit den bekannten Ableitungsregeln füreinzelne Grundrechenoperationen berechnet. Die Gebrauchsformeln für die Ableitungen wer-den aus dem Differenzenquotienten abgeleitet. Ein simples Beispiel ist die Funktion f(x) = x2.Der Differenzenquotient

f ′ (x) = lim∆x→0

f (x + ∆x)− f (x)∆x

(3.1)

liefert eine Approximation der Ableitung an der Stelle x. Mit f(x) = x2 ergibt sich

f ′ (x) = lim∆x→0

(x + ∆x)2 − (x)2

∆x

= lim∆x→0

x2 + 2x∆x + ∆x2 − x2

∆x(3.2)

= lim∆x→0

2x + ∆x

f ′ (x) = 2x.

Für komplizierte automatisierte Berechnungen ist es von Vorteil auf die fehleranfällige undmühsame Bestimmung und Implementierung der analytischen Ableitungen zu verzichten. Dienumerische Berechnung von Ableitungen nach (3.1) führt allerdings zu einem Ergebnis, wel-ches mit Approximationsfehlern behaftet ist: Zum einen ist die Rechengenauigkeit begrenzt(Rundungsfehler) und zum anderen wird, bezogen auf eine Funktion f(x), nicht exakt die Tan-gente an der gewünschten Stelle, sondern eine Sekante durch diese und den Punkt (x + ∆x)berechnet (Verfahrensfehler). Der Wert ∆x muss vom Anwender je nach Verlauf der Funktionsinnvoll angegeben werden, denn das Ergebnis der Approximation hängt stark von dieser Wahlab.

Unter Verwendung der Differentiations-Arithmetik besteht die Möglichkeit simultan zu ei-ner beliebig komplizierten Berechnung in einem Computerprogramm zusätzlich die exaktenlediglich mit Rundungsfehlern behafteten Werte von gewünschten Ableitungen - auch höhe-rer Ordnung - zu bestimmen. Dabei ist kein Vorwissen über die zu differenzierende Funktion

13


nötig. Der Anwender hat lediglich anzugeben, welche Parameter abhängig und welche unab-hängig sind, bzw. welche Funktion nach welchen Parametern abgeleitet werden soll. Wie inden folgenden Abschnitten gezeigt wird, ist diese Aufgabe nicht immer leicht zu lösen. Die Be-zeichnung automatisch könnte deshalb missverstanden werden, denn vollkommen automatischist AD demnach nicht. In der Literatur ist AD deshalb auch bekannt unter rechnergestütztesoder algorithmisches Differenzieren.

Die Entwicklung von AD begann mit dem verstärkten Einsatz von Computern am Anfangder 60er Jahre. Die zugrunde liegenden mathematischen Ideen wurden jedoch schon viel frühervon verschiedenen Personen zu unterschiedlichen Zeiten unabhängig voneinander entwickelt.Ziel war es - und ist es noch heute - exakte Werte der Ableitungen von sehr komplexenFunktionen und Modellen (z.B. Atmosphären- und Ozeansimulationen) zu berechnen. Diezunächst recht einfache Forward-Methode fand aus unerfindlichen Gründen nur wenig Akzep-tanz. Hauptsächlich das Mathematics Research Center (MRC) der Universität von Wisconsin-Madison verwendete AD für verschiedene Projekte. 1982 hat AD im Zuge von neu entwickeltenProgrammiertechniken und der effizienteren Backward-Methode die Aufmerksamkeit stärkerauf sich lenken können. Es folgte eine geradezu explosionsartige Entwicklung von Techniken,Applikationen und Tools, welche AD verwendeten. [8] gibt einen guten Überblick, auf welchenGebieten AD heute eingesetzt wird. Dabei ist FADBAD++ natürlich nicht die einzige Bi-bliothek die eine Anwendung der Differenziations-Arithmetik unterstützt. Das Dokument [14]stellt einige der gängigen Bibliotheken für die Anwendung von AD in Computerprogrammenvor und Vergleicht diese in Hinblick auf Anwendungsmöglichkeiten, Dokumentation und An-wenderfreundlichkeit. Wie schon erwähnt, wird in dieser Arbeit die Bibliothek FADBAD++verwendet. Aufgrund der sehr kurz gehaltenen Dokumentation der Bibliothek, liegt in Kapitel4 der Schwerpunkt bei der Anwendung.

3.2 Mathematische Grundlagen

Mit der Verwendung der Differentiations-Arithmetik [9] ist es möglich, sowohl den Wert einerFunktion f(x), als auch die dazugehörige Ableitung f ′(x) in einer Variable zu vereinen. Dazuwerden, ähnlich wie bei den komplexen Zahlen, geordnete Paare von Zahlen verwendet.

U =(u, u′

), V =

(v, v′

), U, V ∈ R2 (3.3)

Sind für diese Arithmetik die Grundrechenoperationen und Elementarfunktionen definiert, sokann neben der Berechnung eines Wertes simultan die Berechnung der Ableitung(en) ausge-führt werden. Es können z.B. folgende Regeln aufgestellt werden:

1. Addition: U + V = (u, u′) + (v, v′) = (u + v, u′ + v′)

2. Subtraktion: U − V = (u, u′)− (v, v′) = (u− v, u′ − v′)

3. Multiplikation: U · V = (u, u′) · (v, v′) = (u · v, u · v′ + u′ · v)

4. Division: U · V = (u,u′)(v,v′) =

(uv , u·v′−u′·v

v2

), v 6= 0

Diese Regeln können durch das Einführen einer „infinitesimalen Einheit“ d hergeleitet werden,für die d2 = 0, mit U = u + u′d gilt.

14


Für eine Multiplikation ergibt sich damit:

U · V =(u + u′d

)·(v + v′d

)= uv + uv′d + u′d · v + d2 · u′v′ = uv +

(uv′ + u′v

)d (3.4)

Die erste Komponente uv entspricht dabei den Regeln der reellen Arithmetik und die zweiteKomponente entspricht den dazu korrespondierenden Ableitungsregeln.

Ein Zahlenpaar U = (u, u′) im R2 wird Element der Menge D genannt, wobei das reelleZahlensystem R in D enthalten ist: c = (c, 0), c ∈ R. Eine Funktion f : R→ R kann mitder differenziellen Arithmetik, analog zu den komplexe Zahlen, zu einer Funktion f : D→ Derweitert werden. Dazu wird jeder Wert x durch X = (x, 1), und jede Konstante c mit C =(c, 0) ersetzt. Dies entspricht den allgemeinen Regeln

dx

dx= 1,

dc

dx= 0 (3.5)

der Differenzierung von unabhängigen Variablen und Konstanten.Als Beispiel sei die Funktion

f(x) =x2 + 2x− 3

x + 2=

(x− 1) · (x + 3)x + 2

(3.6)

angeführt [9]. Der Ausdruck für die Ableitung lautet

f ′(x) = 1 +3

(x + 2)2(3.7)

und für x = 3 ergibt sich

f(3) =125

, f ′(3) = 1 +325

=2825

. (3.8)

Wird in die Funktion nun X = (3, 1) und für die Konstanten C = (c, 0) eingesetzt, erhält man

f((3, 1)) =((3, 1)− (1, 0)) · ((3, 1) + (3, 0))

((3, 1) + (2, 0))=

12, 85, 1

=(

125

,2825

). (3.9)

Die Ableitung ist direkt mit der Berechnung des Funktionswertes und der differenziellen Arith-metik berechnet worden. Eine spezielle Formel für f ′(x) wurde dabei nicht benötigt.

Der Schlüssel für die Verwendung von AD für beliebig komplexe Funktionen in Computer-programmen liegt bei der Anwendung der Kettenregel, nach der für eine Verkettung

f(x) = u(v(x)) (3.10)

die Ableitung durch das Produkt der äußeren Ableitung u′ und der inneren Ableitung v′

gebildet wird:

f ′(x) = u′(v(x)) · v′(x). (3.11)

In Computerprogrammen kann diese Regel sehr gut implementiert werden, da sie rein mecha-nisch einsetzbar ist.

15


3.3 Anwendung von AD in Computerprogrammen

Eine Funktion beliebiger Komplexität wird in einem Computerprogramm in eine Sequenz vonelementaren Operationen fii=1,...n zerlegt, wobei fi jeweils lediglich abhängig ist von denZwischenergebnissen τ1, . . . , τi−1 und τi = fi τ1, . . . , τi−1. Dabei können auch if-Anweisungen,do-Loops und Funktionsaufrufe etc. im Programm vorkommen. Einige der Zwischenergebnis-se τi werden korrespondierend zu den Variablen des Programms an verschiedenen Stellen imSpeicher abgelegt und überschreiben dabei einen alten Wert der gleichen Variable oder es wirdfreigegebener Speicherplatz verwendet. Andere Variablen müssen für die Verfügbarkeit in meh-reren Operationen in einem temporären Register gespeichert werden, bevor der Speicherplatzfreigegeben werden kann. Eine Funktion y = f(x1, x2) der Form

y =[sin

(x1

x2

)+

x1

x2− ex2

]·[x1

x2− ex2

](3.12)

mit den Startwerten τ−1 = x1 = 1, 5 und τ0 = x2 = 0, 5 wird für die Berechnung desFunktionswertes y in die folgende Sequenz zerlegt [2]:

τ−1 = x1 = 1, 5000τ0 = x2 = 0, 5000τ1 = τ−1/τ0 = 1, 5000/0, 5000 = 3, 0000τ2 = sin(τ1) = sin(3, 0000) = 0, 1411τ3 = eτ0 = e0,5000 = 1, 6487τ4 = τ1 − τ3 = 3, 0000− 1, 6487 = 1, 3513τ5 = τ2 + τ4 = 0, 1411 + 1, 3513 = 1, 4924τ6 = τ5 · τ4 = 1, 4924 · 1, 3513 = 2, 0167y = τ6 = 2, 0167

Tabelle 3.1: Code-Liste für f(x1, x2).

Die Berechnung kann graphisch mit einem Berechnungsdiagramm (computational graph)dargestellt werden. Eine wichtige Regel dabei ist, dass keine mathematische Variable mehr alseinmal deklariert wird. Mit der Initialisierung der Variablen x1 und x2 beginnt die Berechnung.Jede Variable ergibt sich unter Anwendung von Elementaroperationen auf vorher definierteVariablen. Damit ist eine Form erreicht, die zwar nicht auf den ersten Blick mit Ausdruck

Abbildung 3.1: Berechnungsdiagramm zur Beispielfunktion.

(3.12) korrespondiert, jedoch eine effiziente Berechnung gewährleistet und den Einsatz derKettenregel sehr begünstigt.

16


Die Kettenregel wurde von den Entwicklern von AD nach den folgenden zwei Ansätzenimplementiert:

1. Es werden für jede Variable im Laufe der Berechnungskette simultan die partiellen Ab-leitungen nach den gewünschten Variablen mitgeführt (Forward-Methode).

2. Es wird zunächst der Funktionswert berechnet und dabei der Berechnungsablauf gespei-chert. Anschließend kann ausgehend vom Ende der Berechnungen das aufgezeichneteBerechnungsdiagramm von hinten abgearbeitet werden (Backward-Methode).

Im Folgenden werden diese beiden Ansätze anhand der obigen Beispielfunktion vorgestelltund deren Vor- und Nachteile diskutiert. Für die Umsetzung in Programmen verwendetFADBAD++ die Operatorüberladung.

Exkurs: Operatorüberladung

Definiert man einen neuen Datentyp (z.B. geordnete Paare von Zahlen), so sind Operatorenwie z.B. + und ∗, aber auch andere Elementarfunktionen wie sin(), für diesen Typ nicht de-finiert und eine Anwendung schlägt fehl. In der Computersprache C++ hat man deshalb dieMöglichkeit der Operatorüberladung, wodurch die Funktionsweise bzw. Bedeutung der Opera-toren nach der jeweils geltenden Arithmetik angepasst werden kann. FADBAD++ verwendetgenau diesen „Trick“, damit der Programmierer seine implementierten Funktionen unabhängigvom Datentyp verwenden kann. Für Datentypen von FADBAD++ wird dann die differentielleArithmetik verwendet.

3.4 Die Forward-Methode

Zur Erläuterung dieser Methode soll die Ableitung von y nach x1, also ∂y/∂x1, bestimmtwerden. Eine Möglichkeit der Lösung besteht darin, für jeden Wert τi der Sequenz in Tabelle3.1 auch den Wert der Ableitung nach x1, also τi = ∂τi/∂x1 mitzuführen. Damit ist x1 dieeinzige unabhängige Variable und y eine abhängige Variable.

Beginnend mit den initialen Werten x1 = τ−1 = 1, 0 und x2 = τ0 = 0, 0, erhält man durchdie mechanische Anwendung der Kettenregel auf jede Zeile der Code-Liste zu jedem τi denkorrespondierenden Wert τi = ∂τi/∂x1. Beispielhaft ergibt sich für τ1 = τ−1/τ0

τ1 =(

∂τ1

∂τ−1

)· τ−1 +

(∂τ1

∂τ0

)· τ0

=1τ0· τ−1 −

(τ−1

τ0

)· 1τ0· τ0 (3.13)

= (τ−1 − τ1 · τ0) /τ0

= (1, 0000− 3, 0000 · 0, 0000)/0, 5000 = 2, 0000,

und für τ2 = sin(τ1)

τ2 =(

∂τ2

∂τ1

)· τ1 = cos(τ1) · τ1 = −0, 9900 · 2, 0000 = −1, 9800. (3.14)

17


Die durch ein kleines Vielfaches der ursprünglichen Rechenoperationen erweiterte Abfolgevon Berechnungen ist in Tabelle 3.2 dargestellt. Dabei sind die Zwischenergebnisse τi und diedazu gehörige partielle Ableitung τi jeweils paarweise grau oder weiß hinterlegt.

τ−1 = x1 = 1, 5000τ−1 = x1 = 1, 0000τ0 = x2 = 0, 5000τ0 = x2 = 0, 0000τ1 = τ−1/τ0 = 1, 5000/0, 5000 = 3, 0000τ1 = (τ−1 − τ1 · τ0) /τ0 = 1, 0000/0, 5000 = 2, 0000τ2 = sin(τ1) = sin(3, 0000) = 0, 1411τ2 = cos (τ1) · τ1 = −0, 9900 · 2, 0000 = −1, 9800τ3 = eτ0 = e0,5000 = 1, 6487τ3 = τ3 · τ0 = 1, 6487 · 0, 0000 = 0, 0000τ4 = τ1 − τ3 = 3, 0000− 1, 6487 = 1, 3513τ4 = τ1 − τ3 = 2, 0000− 0, 0000 = 2, 0000τ5 = τ2 + τ4 = 0, 1411 + 1, 3513 = 1, 4924τ5 = τ2 + τ4 = −1, 9800 + 2, 0000 = 0, 0200τ6 = τ5 · τ4 = 1, 4924 · 1, 3513 = 2, 0167τ6 = τ5 · τ4 + τ4 · τ5 = 0, 0200 · 1, 3513 + 2, 0000 · 1, 4924 = 3, 0118y = τ6 = 2, 0167y = τ6 = 3, 0118

Tabelle 3.2: Code-Liste für die Forward-Methode [2].

Die Vorgehensweise wird Forward genannt, da die Ableitungen τi für jeden Berechnungs-schritt mitgeführt werden. Das Problem ein Programm so zu transformieren, dass die zusätz-lich benötigten Variablen und Berechnungsvorschriften zur Verfügung gestellt werden, wird inFADBAD++ mit der oben erklärten, systematisch angewendeten Operatorüberladung gelöst.

Um die Ableitung ∂y/∂x2 zu berechnen, muss die Berechnung einfach mit den Initialwertenx2 = 1, 0000 und x1 = 0, 0000 durchgeführt werden. Natürlich können auch alle Ableitungensimultan bestimmt werden.

3.5 Die Backward-Methode

Wurden im ersten Ansatz Inputvariablen ausgewählt und für jede Zwischenvariable die Ab-leitung nach diesen bestimmt, so werden hier Outputvariablen gewählt und die Ableitungendieser nach den Zwischenwerten berechnet, um an das gewünschte Ziel zu gelangen. Die einzigeOutputvariable in dem Beispiel ist y. Für jede Variable τi existiert eine Ableitung τi = ∂y/∂τi,welche auch als adjungierte Variable bezeichnet wird. Um diesen entscheidenden Unterschiedzur Forward-Methode zu kennzeichnen, wird für die partiellen Ableitungen statt τi nun dieNotation τi verwendet.

Die adjungierten Variablen können wieder mit der Kettenregel und Operatorüberladungautomatisch bestimmt werden. Dazu muss der Berechnungsgraph rückwärts durchschrittenwerden. Der Startwert für die einzige Outputvariable lautet für das Beispiel y = 1, 0000. τ1

beeinflusst y durch τ4 = τ1 − τ3 und durch τ2 = sin(τ1), also muss gelten:

τ1 = τ4 + τ2 · cos(τ1) = 2, 8437 + 1, 3513 · (−0, 9900) = 1, 5059. (3.15)

18


Aus praktischen Gründen wird dieser Ausdruck in zwei Teile geteilt:

τ1 = τ4 = 2, 8437 (3.16)τ1 = τ1 + τ2 · cos(τ1) = 2, 8437 + 1, 3513 · (−0, 9900) = 1, 5059

Damit ist es möglich, Teile des Ausdrucks für τ1 der jeweilig korresponierenden Zeile im Be-rechnungsablauf, welche abhängig von τ1 ist, zuzuordnen. Tabelle 3.3 gibt die Reihenfolge imReverse- oder Backward-Modus wieder. Dabei sind die adjungierten Variablen unter den Zei-len angeordnet, aus denen sie erzeugt wurden.

τ−1 = x1 = 1, 5000τ0 = x2 = 0, 5000

τ1 = τ−1/τ0 = 1, 5000/0, 5000 = 3, 0000τ2 = sin(τ1) = sin(3, 0000) = 0, 1411

τ3 = eτ0 = e0,5000 = 1, 6487τ4 = τ1 − τ3 = 3, 0000− 1, 6487 = 1, 3513

τ5 = τ2 + τ4 = 0, 1411 + 1, 3513 = 1, 4924τ6 = τ5 · τ4 = 1, 4924 · 1, 3513 = 2, 0167

y = τ6 = 2, 0167τ6 = y = 1, 0000

τ5 = τ6 · τ4 = 1, 0000 · 1, 3513 = 1, 3513τ4 = τ6 · τ5 = 1, 0000 · 1, 4924 = 1, 4924

τ4 = τ4 + τ5 = 1, 4924 + 1, 3513 = 2, 8437τ2 = τ5 = 1, 3513

τ3 = −τ4 = −2, 8437τ1 = τ4 = 2, 8437

τ0 = τ3 · τ3 = −2, 8437 · 1, 6487 = −4, 6884τ1 = τ1τ2 · cos(τ1) = 2, 8437 + 1, 3513 · (−0, 9900) = 1, 5059

τ0 = τ0 − τ1 · τ1/τ0 = −4, 6884− 1, 5059 · 3, 0000/0, 5000 = −13, 7239τ−1 = τ1/τ0 = 1, 5059/0, 5000 = 3, 0118

x2 = τ0 = −13, 7239x1 = τ−1 = 3, 0118

Tabelle 3.3: Code-Liste für die Backward-Methode [2].

Das Ergebnis stimmt mit dem aus der Forward-Methode exakt überein. Allerdings wurdenhier Ableitungen für beide Inputvariablen x1 und x2 berechnet.

19


3.6 Implementierung von AD in FADBAD++

Der Datentyp für den Forward-Modus wird folgendermaßen deklariert:

1 template <class T>2 class FTypeName3 4 public:5 T v; // Realteil6 T *g; // Array mit Infinitesimalteilen7 int gsize; // Größe dieses Feldes8 void diff(int idx, int n); // setzen nach was differenziert werden soll9 T& x(); // gibt den Realteil aus

10 T& d(int i); // gibt die gewünschte Ableitung aus11

12 ... // weitere Methoden13 ;

Diese Klassenschablone wird vom Programmierer mit dem gewünschten Datentyp speziali-siert. In der Regel erfolgt dies mit dem Datentyp double. Für das Newton-Raphson-Verfahrenwerden jedoch auch Ableitungen zweiter Ordnung benötigt. Dafür wird die Klassenschabloneauf Typebene mit dem Datentyp der ersten Ableitung spezialisiert.

1 // Die Grundtypen:2 typedef FTypeName<double> FDouble;3 typedef BTypeName<double> BDouble;4

5 // Kombinationen:6

7 // Forward-Forward:8 typedef FTypeName<FDouble> FF;9 // Forward-Backward:

10 typedef FTypeName<BDouble> FB;11 // Backward-Backward:12 typedef BTypeName<BDouble> BB;13 // Backward-Forward:14 typedef BTypeName<FDouble> BF;

Für eine Ableitungsordnung p ergeben sich 2p Kombinationen von Datentypen. InFADBAD++ werden auf diese Weise Ableitungen bis zur sechsten Ordnung unterstützt.

Eine Variable vom Typ FF besteht entsprechend der Differentiations-Arithmetik aus einemRealteil v und einem Array mit den partiellen Ableitungen erster Ordnung. Diese partiellenAbleitungen sind wiederum Variablen vom Typ FDouble. Der Realteil einer partiellen Ablei-tung erster Ordnung v beinhaltet also den Wert der Ableitung und der Infinitesimalteil istwiederum ein Vektor mit den Ableitungen zweiter Ordnung vom Typ double.

20


Die oben angesprochene Operatorüberladung sorgt dafür, dass der Compiler bei der Ver-wendung der Rechenoperatoren auf Variablen der definierten Datentypen die Differentiations-Arithmetik verwendet. Der Operator / für die Division ist dementsprechend wie folgt überla-den:

1 template <class T>2 FTypeName<T> operator/ (const FTypeName<T>& a, const FTypeName<T>& b)3 4 // Division der Realteile5 FTypeName<T> c(a.v/b.v);6

7 // Allokieren des Gradienten8 c.touchg(a.gsize);9

10 // Anwendung der Quotientenregel11 for (int i=0;i<a.gsize;i++) c.g[i]=(a.g[i]-c.v*b.g[i])/b.v;12

13 // Rückgabe14 return c;15

3.7 Vergleich der beiden Methoden

Für den Programmierer stellt sich die Frage, welche der beiden Methoden und, bezogen aufhöhere Ableitungen, welche Kombination der Methoden die effizientere ist. Obwohl diese sichin der Vorgehensweise stark unterscheiden, hat man in FADBAD++ versucht die Anwendungso einheitlich wie möglich zu gestalten. Dennoch sind im Falle eines Methodenwechsels unterUmständen erhebliche Veränderungen im Quellcode erforderlich.

Anwendung

Im Forward-Modus muss vor der eigentlichen Berechnung festgelegt werden, nach welchenVariablen abgeleitet werden soll. Dazu steht die Funktion diff(int id,int n) zur Verfügung.Um die Variable y, definiert durch Formel (3.12) nach x1 und x2 abzuleiten, wird folgenderQuellcode nötig:

1 // Deklaration der Variablen2 FDouble x1,x2,y;3

4 // Kennzeichne die unabhängigen Variablen:5 x1.diff(0,2) // Differenziere das Ergebnis nach x1..6 x2.diff(1,2) //..und x27

8 // Berechnung9 y = ....

10

11 // Ausgabe (keine Berechnung!)12 std::cout<<y.x()<<endl; //der Funktionswert

21


13 std::cout<<y.d(0).x()<<endl; //Wert der Ableitung nach x114 std::cout<<y.d(1).x()<<endl; //Wert der Ableitung nach x2

Die Funktion diff(int id,int n) wird also auf die Inputvariablen x1 und x2 angewendet,woraufhin sich nach der Berechnung des Funktionswertes y (durch den selben Code wie mitder reellen Arithmetik!) die partiellen Ableitungen in der Ergebnisvariable befinden.

Im Backward-Modus verhält es sich, entsprechend der Vorgehensweise, genau entgegenge-setzt: nach der Berechnung des Funktionswertes und der Aufzeichnung des Berechnungsgra-phen durch Operatorüberladung, erfolgt der Aufruf der Methode diff(int id,int n) bei derErgebnisvariable. Die partiellen Ableitungen sind nach diesem Aufruf in den Inputvariablenzu finden.

1 // Deklaration der Variablen2 BDouble x1,x2,y;3

4 // Berechnung und Aufzeichnen des Berechnungsablaufes5 y = ....6

7 // Markiere die Abhängige Variable (gehe Berechnungsgraph zurück)8 y.diff(0,1);9

10 // Ausgabe (keine Berechnung!)11 std::cout<<y.x()<<endl; //der Funktionswert12 std::cout<<x1.d(0).x()<<endl; //Wert der Ableitung nach x113 std::cout<<x2.d(0).x()<<endl; //Wert der Ableitung nach x2

Ist die Ableitung nach einem Parameter (z.B. x2) nicht gewünscht, so muss dies mit x2=x2.x()oder x2=0 signalisiert werden. Diese Markierung ist für den Backward-Modus von entschei-dender Bedeutung. Für eine erfolgreiche Berechnung ist es essenziell wichtig, dass auch alleabhängigen Variablen explizit als unabhängig zu markieren sind, wenn man sie nicht ablei-ten möchte. Auf den ersten Blick scheint das eine einfache Vorgabe zu sein, kann jedoch beikomplizierten Berechnungen und vor allem bei höheren Ableitungen schwierig werden.

Effizienz

Im Forward-Modus wird lediglich während den Berechnungen zusätzlicher Speicherplatz fürtemporäre Variablen benötigt. Die Ableitungen werden in Vektoren bzw. Arrays gespeichert.Hat man eine Funktion welche von 10 Variablen abhängt, so wird für die partiellen Ableitungenerster Ordnung ein Array mit 10 Elementen alloziert. Möchte man nun auch die zweiten par-tiellen Ableitungen bestimmen, so besteht jeder dieser 10 Variablen des Arrays aus dem Wertder ersten Ableitung und einem entsprechenden Array mit den zweiten Ableitungen. Somitwerden weitere 10 Arrays mit je 10 Elementen benötigt. Für Ableitungen dritter Ordnung wer-den dementsprechend 100 weitere Arrays benötigt. Allerdings sind die Arrays, insbesondere fürhöhere Ableitungen, sehr dünn besetzt (sparse), so dass eine Modifikation von FADBAD++mit Sparse-Vektoren viel Speicherplatz sparen kann. In Abschnitt 6 wird diese Modifikationbeschrieben.

Im Backward-Modus muss der gesamte Ablauf der Berechnungen für längere Zeit gespeichertwerden, um diesen rückwärts durchlaufen zu können. Der Ablauf wird mittels Operatorüberla-dung während der Berechnung „aufgezeichnet“ (in [11] Forward-Sweep genannt). Insbesondere

22


bei der Verwendung von Schleifen im Berechnungsablauf ist nicht immer abschätzbar, wieviele Daten in diesem Vorgang gespeichert werden.

Generell lässt sich sagen, dass für eine Berechnung der Ableitungen von wenigen abhängigenVariablen nach vielen Inputvariablen die Backward-Methode schneller ist [11]. Übertragen aufdas Laufzeitverhalten des Newton-Raphson-Verfahrens bedeutet diese Aussage, dass für dieersten partiellen Ableitungen immer der Backward-Modus zu verwenden ist, da es hier injedem Fall nur eine Funktion gibt, welche von mehreren Parametern abhängt.

Sollen eine große Menge an abhängigen Variablen nach einigen wenigen unabhängigen Varia-blen abgeleitet werden, ist die Forward-Methode zu bevorzugen [11]. Beim Newton-Raphson-Verfahren treten im Zuge der Bestimmung der zweiten partiellen Ableitungen in jedem Fallebenso viele Funktionen (erste Ableitungen) wie Parameter auf, was bedeutet, dass das Ver-hältnis von abhängigen und unabhängigen Variablen immer gleich (1 : 1) ist. Welche Methodein diesem Fall vorzuziehen ist, kann an dieser Stelle vom Autor noch nicht beantwortet werden.In den folgenden Abschnitten werden die hier formulierten Aussagen anhand von Beispielenuntersucht.

23

4 Implementierung desNewton-Raphson-Verfahrens

Die Grundzüge des Berechnungsablaufs der Verfahren Gauß-Newton und Newton-Raphson äh-neln sich sehr, so dass die bestehende Struktur des Frameworks erweitert werden konnte, ohnegrundlegende Veränderungen am bestehenden Code vornehmen zu müssen1. Unter kleinenVeränderungen ist es möglich, die Template-Methode compute() der Basisklasse Adjustmentebenfalls für den neuen Berechnungsablauf zu verwenden.

Da partielle Ableitungen bis zur zweiten Ordnung benötigt werden, erhält man bei denzwei Methoden für die Bestimmung der Ableitungen die vier Datentypen FF, FB, BF undBB (F=Forward, B=Backward). Einige Methoden sind datentypunabhängig (Methoden derKlassen Adjustment_GMM_AD und Builder_HG), wodurch sich folgende Struktur ergibt:

#setSLEMatrices()#setSNE()

Adjustment

#SetDiff()

Adjustment_GMM_AD

+declareArrays(in nBeob_ : int, in nPara_ : int)+Build_HG()

Builder_HG

Abbildung 4.1: Neu implementierte Klassen für das Newton-Raphson-Verfahren

Um das Newton-Raphson-Verfahren z.B. mit dem Typ BB zu verwenden, ist vom Anwen-dungsprogrammierer mit

Adjustment_GMM_NR<BB> agl;

ein Objekt (hier: agl) der Template-Klasse Adjustment_GMM_NR zu instanziieren. Alle weiterenSchritte sind identisch mit denen, die für die schon bestehenden Ausgleichungsansätze gelten.

1Detaillierte Angaben zur Ausgangsstruktur sind in Abschnitt 10 zu finden.

24

4 Implementierung des Newton-Raphson-Verfahrens

Die von den Datentypen unabhängigen Methoden sind in den Klassen Adjustment_GMM_ADund Builder_HG deklariert und in den dazugehörigen cpp-Dateien implementiert. Die KlasseBuilder_HG sorgt für die Bereitstellung der Matrizen. In den Template-KlassenAdjustment_GMM_NR und Builder_NR sind die Funktionen deklariert, deren Verhalten abhän-gig vom Datentyp variiert. Eine Spezialisierung des Verhaltens der Funktion SetDiff() wirdmit den Deklarationen

1 template <>2 void Adjustment_GMM_NR<FF>::SetDiff();3 template <>4 void Adjustment_GMM_NR<FB>::SetDiff();5 template <>6 void Adjustment_GMM_NR<BF>::SetDiff();7 template <>8 void Adjustment_GMM_NR<BB>::SetDiff();

ermöglicht. In der Klasse Builder_NR ist äquivalent eine Spezialisierung der MethodeBuild_HG() erforderlich. Die Implementierung der einzelnen Spezialisierungen erfolgt, im Ge-gensatz zu Template-Methoden, ebenfalls in der entsprechenden cpp-Datei. Dieses Vorgehenbewirkt, dass das Programm nicht kompiliert werden kann, wenn für T ein unbekannter Typeingesetzt wird.

4.1 Anpassung des Berechnungsablaufs

Es folgt eine Zusammenstellung der Veränderungen, die getätigt wurden, um die Template-Methode compute() für das Newton-Raphson-Verfahren verwenden zu können. ZusätzlicheMatrizendeklarationen werden nicht nötig, da die Hesse-Matrix der NormalgleichungsmatrixN und der Gradient dem Vektor der rechten Seite rhs entspricht. In beiden Fällen handelt essich um Membervariablen der Klasse Adjustment.

Die Methoden setSLEMatrices() und setSNE() übernehmen die Belegung der Matrizenund die Erstellung des Normalgleichungssystems. Beide Methoden sind in Adjustment alspure virtual deklariert und müssen deshalb von Adjustment_GMM_AD überschrieben werden.

Ein Test auf Linearisierungsfehler folgt nach der Berechnung des Gradienten der Zielfunk-tion. Für den Gradienten gilt bei einem Minimum ∇f(x) ≈ 0. Als Abbruchkriterium wurdedie Maximumnorm ‖∇f(x)‖∞ < ε gewählt. Ist das Abbruchkriterium erfüllt, kann mit breakaus der Iterationsschleife gesprungen werden.

Damit am Ende eines Iterationsschrittes nicht noch einmal ein Test auf Linearisierung durch-geführt wird, wurde die Einschubmethode testLinearization() überschrieben. Diese Me-thode hat keine Funktionalität - verhindert jedoch, dass der für die anderen Ausgleichungengeltende Code ausgeführt wird.

Die Berechnung der Verbesserungen erfolgt beim Newton-Raphson-Verfahren ebenfalls ananderer Stelle des bisherigen Berechnungsablaufes, wodurch auch hier eine Einschubmethode(calculate_v()) ohne Code in Adjustment_GMM_AD deklariert wurde. Die Verbesserungen

25


können erst nach der Aufdatierung der Unbekannten durch die Funktion (calculate_v_ad())berechnet werden, wodurch im Umkehrschluss eine Einschubmethode mit gleichem Namenohne auszuführenden Code in der Klasse Adjustment deklariert wurde.

Die Berechnung der Kofaktorenmatrix der Unbekannten Qxx war bisher für alle Ansätzegleich (calculate_Qxx()), musste aber für das neue Verfahren in Adjustment_GMM_AD über-schrieben werden. Bei der Berechnung wird der Zusammenhang

Qxx = 2 ·H−1 (4.1)

ausgenutzt.

Die folgenden vier Abschnitte befassen sich eingehend mit der Anwendung der BibliothekFADBAD++. Für jeden der vier Datentypen wird anhand der FunktionenBuilder_NR::Build_HG() und Adjustment_GMM_NR::SetDiff() erklärt, wie und an welcherStelle die abhängigen und unabhängigen Variablen, zwecks Ableitung der Zielfunktion nachdiesen, gekennzeichnet werden müssen und wo die partiellen Ableitungen nach Ausführungder erforderlichen Schritte zu finden sind. Prinzipiell ist anzumerken, dass die Anwendungdes Forward-Modus leichter zu handhaben ist. Für den Backward-Modus ist es von großerBedeutung, dass alle Variablen, nach denen keine Ableitung gewünscht ist und welche nichtabgeleitet werden sollen, explizit auf Null gesetzt werden müssen.

4.2 Spezialisierung von Funktionen der Klassentemplates

In der Methode SetDiff() wird die für den Forward-Modus erforderliche Markierung derunabhängigen Variablen, nach denen eine Ableitung benötigt wird, vor der Berechnung derZielfunktion (hier: vT Pv) vorgenommen. Des weiteren sorgt diese Methode für die Bereit-stellung der Variablen (Unbekannte, Beobachtungen und Konstanten) für die Berechnung derZielfunktion.

1 template <>2 void Adjustment_GMM_NR<AD_TYP>::SetDiff()3 4 // bool-Vektor löschen5 m_HGBuilder.fix.clear();6

7 // Array mit allen Unbekannten zusammenstellen.8 unsigned int u=collector.unknowns_.size();9

10 // Schleife über alle Unbekannten:..11 for(unsigned int i=0;i<u;i++)12 13 // ..hole den aktuellen Wert der Unbekannten.14 m_HGBuilder.ArrayUnknowns_[i]=collector.unknowns_[i]->getValuePlusDelta();15

16 // Falls die Unbekannte nicht durch eine Bedingung festgehalten wird:..17 if ( !collector.unknowns_[i]->isFixed() )

26


18 19 // ..hier die unabhängigen Variablen markieren..20 ....21

22 // ..und merken, dass Wert nicht festgehalten wird23 m_HGBuilder.fix.push_back(false);24 25 // Sonst: Merken, dass die Unbekannte fest26 else m_HGBuilder.fix.push_back(true);27 28

29 // Array mit allen Beobachtungen zusammenstellen30 get_Observations();31

Der Typ AD_TYP in Zeile 2 ist an dieser Stelle lediglich ein Platzhalter für die vier Speziali-sierungstypen. Die Membervariable ArrayUnknowns_in Zeile 14 ist ein Array von eben diesemTyp. In Zeile 20 werden abhängig vom Datentyp die unabhängigen Variablen markiert. DieserTeil der Funktion ist demnach Datentypabhängig.

Die Membervariable m_HGBuilder ist ein Objekt der Klasse Builder_NR<AD_TYP>. Um eini-ge Methoden und Variablen dieser Klasse hier ansprechen zu können, mussten diese als publicdeklariert werden. Dazu gehört z.B. der Vektor fix<bool>, welcher sich merkt, welche der Un-bekannten durch eine Bedingung festgehalten (true) bzw. nicht festgehalten werden (false).Mit den Informationen aus diesem Vektor wird in der Methode Build_HG() für den Backward-Modus dafür gesorgt, dass wirklich nur die Ableitungen nach den unbekannten Parameternbestimmt werden.

Die Methode Build_HG() übernimmt die Berechnung der Zielfunktion, das Markieren derVariablen für den Backward-Modus und die Übergabe der Werte der Ableitungen an dieArrays, welche in der Ausgleichung für das Lösen des Gleichungssystems benötigt werden.Damit ergibt sich folgende allgemeine Struktur.

1 template <>2 void Builder_NR<AD_TYP>::Build_HG()3 4

5 // Berechnung der Zielfunktion6 calc_vtPv();7

8 // Markierung der Variablen für den Backward-Modus9 ...

10

11 // Hesse-Matrix (pN) und Gradient (rhs) erstellen12 ...13

In den folgenden Ausführungen werden lediglich die variierenden Teile der Methoden be-trachtet, was in SetDiff() der Zeile 20 und in Build_HG() den Zeilen 9 bis 12 entspricht.

27


4.3 Forward-Forward

Der Typ FF (definiert durch typedef FTypeName<FTypeName<double> > FF) ist am einfachs-ten zu handhaben. Für alle Variablen nach denen eine Ableitung gewünscht ist, wird eineentsprechende Markierung dieser in SetDiff() nötig.

1 template <>2 void Adjustment_GMM_NR<FF>::SetDiff()3 4 for(unsigned int i=0;i<u;i++)5 6 // Unbekannte markieren7 m_HGBuilder.ArrayUnknowns_[i].diff(i,u);8 m_HGBuilder.ArrayUnknowns_[i].x().diff(i,u);9

10

In Build_HG() sind die partiellen Ableitungen nach Berechnung der Zielfunktion in derVariable für diese enthalten.

1 template <>2 void Builder_NR<FF>::Build_HG()3 4 // Zielfunktion berechnen5 calc_vtPv();6

7 // Hesse-Matrix (pN) und Gradient (rhs) belegen8 for ( unsigned int i = 0; i < u; i++ )9

10 // erste Ableitungen11 (*prhs_)(i,0) = -vtPv.d(i).x();12

13 for ( unsigned int j = 0; j < u; j++ )14 15 // zweite Ableitungen16 (*pN_)(i,j) = vtPv.d(i).d(j);17 18 19

28


4.4 Forward-Backward

In der Methode SetDiff() werden wieder die unabhängigen Variablen für die Forward-Methode markiert - aufgrund des Datentyps FB jedoch nur für die Ableitungen erster Ordnung.

1 template <>2 void Adjustment_GMM_NR<FB>::SetDiff()3 4 for(unsigned int i=0;i<u;i++)5 6 // Unbekannte markieren7 m_HGBuilder.ArrayUnknowns_[i].diff(i,u);8 9

Aus der Verwendung der Backward-Methode für die zweiten Ableitungen, ergibt sich fol-gende Spezialisierung für Build_HG():

1 template <>2 void Builder_NR<FB>::Build_HG()3 4 // Zielfunktion berechnen5 calc_vtPv();6

7 // alle Beobachtungen unabhängig machen8 // -> keine Ableitung nach diesen ist benötigt9 for ( unsigned int i = 0; i < n; i++ )ArrayObservations_[i]=0;

10

11 // festgehaltene Unbekannte ebenfalls =0 setzen12 for ( unsigned int i = 0; i < u; i++ ) if(fix[i]) ArrayUnknowns_[i].x()=0;13

14 // die ersten Ableitungen markieren15 for ( unsigned int i = 0; i < u; i++ ) if(!fix[i]) vtPv.d(i).diff(i,u);16

17 // wichtig! Funktionswert muss ebenfalls =0 gesetzt werden!18 vtPv.x() = 0;19

20 // Hesse-Matrix (pN) und Gradient (rhs) belegen21 for ( unsigned int i = 0; i < u; i++ )22 23 (*prhs_)(i,0) = -vtPv.d(i).x();24

25 for ( unsigned int j = 0; j < u; j++ )26 27 (*pN_)(i,j) = ArrayUnknowns_[i].x().d(j);28 29 30

29


In Zeile 9 und 12 werden alle Werte, nach der die Zielfunktion nicht abgeleitet werden sollzu Null gesetzt. Für den Fall, dass die Werte später noch verfügbar sein sollen, kann dieseMarkierung auch mit

ArrayObservations_[i]=ArrayObservations_[i].x();

vorgenommen werden. Die Werte der ersten Ableitungen befinden sich, durch die Anwendungder Forward-Methode, in der Variable vtPv, und können durch vtPv.d(i).x() angesprochenwerden. Nach der Berechnung sind genau diese ersten Ableitungen mit vtPv.d(i).diff(i,u)(Zeile 15) für die zweiten Ableitungen mittels Backward-Methode zu markieren. Da alle Va-riablen von denen keine Ableitung gewünscht ist als solche zu kennzeichnen sind, muss auchdie Variable vtPv zu Null gesetzt werden (Zeile 18). Erst jetzt sind alle partiellen Ableitungenzweiter Ordnung verfügbar. Sie sind in den Variablen der unabhängigen Eingangswerte derBerechnung zu finden und können mit ArrayUnknowns_[i].x().d(j) angesprochen werden(Zeile 27).

4.5 Backward-Forward

Für SetDiff() ergibt sich beim Datentyp BF folgende Markierung für die Ableitung zweiterOrdnung.

1 template <>2 void Adjustment_GMM_NR<BF>::SetDiff()3 4 for(unsigned int i=0;i<u;i++)5 6 m_HGBuilder.ArrayUnknowns_[i].x().diff(i,u);7 8

In Build_HG() ist jetzt lediglich mit vtPv.diff(0,1) festzulegen, dass dieser Wert abge-leitet werden soll.

1 template <>2 void Builder_NR<BF>::Build_HG()3 4 calc_vtPv();5

6 // alle Beobachtungen unabhängig machen7 // -> keine Ableitung nach diesen ist benötigt8 for ( unsigned int i = 0; i < n; i++ )ArrayObservations_[i]=0;9

10 // festgehaltene Unbekannte ebenfalls =0 setzen11 for ( unsigned int i = 0; i < u; i++ ) if(fix[i]) ArrayUnknowns_[i].x()=0;12

13 // Kennzeichen, dass abhängige Variable abgeleitet werden soll14 vtPv.diff(0,1);15

30


16 // Hesse-Matrix (pN) und Gradient (rhs) belegen17 for ( unsigned int i = 0; i < u; i++ )18 19 (*prhs_)(i,0) = -ArrayUnknowns_[i].d(0).x();20

21 for ( unsigned int j = 0; j < u; j++ )22 23 (*pN_)(i,j) = ArrayUnknowns_[i].d(0).d(j);24 25 26

Auch hier werden die Variablen nach denen keine Ableitung gewünscht wird, entsprechendmarkiert. Die partiellen Ableitungen sind jetzt ausschließlich in den Eingangswerten der Be-rechnungen ArrayUnknowns_[i] enthalten, und werden durch Zeile 19 und 23 angesprochen.

4.6 Backward-Backward

Beim Typ BB ist vor der Berechnung der Zielfunktion keine Markierung zum Differenzierenerforderlich. Somit wird in SetDiff() lediglich für die Bereitstellung der Variablen gesorgt.In Build_HG() sind nach der Funktionswertberechnung die folgenden Schritte nötig:

1 template <>2 void Builder_NR<BB>::Build_HG()3 4 calc_vtPv();5

6 // alle Beobachtungen unabhängig machen7 // -> keine Ableitung nach diesen ist benötigt8 for ( unsigned int i = 0; i < n; i++ )ArrayObservations_[i]=0;9

10

11 // Die festgehaltenen Unbekannten =0 setzen12 for ( unsigned int i = 0; i < u; i++ )13 14 if(fix[i])15 16 ArrayUnknowns_[i]=0; //erste Ordnung17 ArrayUnknowns_[i].x()=0; //zweite Ordnung18 19 20 // Kennzeichen, dass abhängige Variable abgeleitet werden soll.21 vtPv.diff(0,1);22

23 // Die Ableitungen erster Ordnung sind nun in den Unbekannten enthalten24 // -> Kennzeichnung für die Ableitung zweiter Ordnung25 for ( unsigned int i = 0; i < u; i++ )

31


26 27 if(!fix[i]) ArrayUnknowns_[i].d(0).diff(i,u);28 29 // wichtig! Funktionswert muss ebenfalls =0 gesetzt werden!30 vtPv.x() = 0;31

32 // Hesse-Matrix (pN) und Gradient (rhs) belegen33 for ( unsigned int i = 0; i < u; i++ )34 35 (*prhs_)(i,0) = -ArrayUnknowns_[i].d(0).x();36 for ( unsigned int j = 0; j < u; j++ )37 38 (*pN_)(i,j) = ArrayUnknowns_[i].x().d(j);39 40 41

Die partiellen Ableitungen sind wieder in den Eingangswerten der BerechnungenArrayUnknowns_[i] enthalten, und werden durch Zeile 35 und 38 angesprochen.

4.7 Zusammenfassung

Aus Zwecken der Übersicht werden nun die Markierungen der Variablen und der Zugriff aufdie Werte der Ableitungen tabellarisch für die vier Datentypen zusammengefasst (Tabelle 4.1).Für jeden Datentyp ist die Abfolge der erforderlichen Operationen von oben nach unten zulesen. In den Arrays Unkn und Obs befinden sich die Eingangswerte für die Berechnungen,wobei lediglich Ableitungen nach den Variablen in Unkn von Interesse sind. Der Ergebniswertder Berechnungen ist vtPv. Die Typen der Variablen bzw. Arrays entsprechen der jeweilsangewendeten Ableitungsmethode bzw. der Kombination dieser (linke Spalte). Für die Indicesi, j und l gilt: i, j = 0, ..., (u− 1), und l = 0, ..., (n− 1), mit u =Anzahl der Unbekannten undn =Anzahl der Beobachtungen. Die hellgrau hinterlegten Felder beinhalten die Markierungder Variablen und den Zugriff auf die Ableitungen. Mit 1) und 2) ist jeweils die Ordnung derAbleitung gemeint.

32


Datentyp Adjustment_GMM_NR::SetDiff() Builder_NR::Build_HG() Zugrif auf Ableitungen

1) Unkn[i].diff(i,u)2) Unkn[i].x().diff(i,u)

FF Berechnung von vtPv

1) vtPv.d(i).x()2) vtPv.d(i).d(j)

1) Unkn[i].diff(i,u)Berechnung von vtPv

a) Obs[l]=0b) vtPv.x()=0

falls festgehalten:FB c) Unkn[i]=0

2) vtPv.d(i).diff(i,u)1) vtPv.d(i).x()2) Unkn[i].x().d(j)

2) Unkn[i].x().diff(i,u)Berechnung von vtPv

a) Obs[l]=0BF falls festgehalten:

b) Unkn[i]=01) vtPv.diff(0,1)

1) Unkn[i].d(0).x()2) Unkn[i].d(0).d(j)

Berechnung von vtPv

a) Obs[l]=0falls festgehalten:b) Unkn[i]=0

BB c) Unkn[i].x()=01) vtPv.diff(0,1)2) Unkn[i].d(0).diff(i,u)

1) Unkn[i].d(0).x()2) Unkn[i].x().d(j)

Tabelle 4.1: Verwendung von FADBAD++ für Ableitungen zweiter Ordnung.

33

5 Implementierung des Halley-Verfahrens

Die Klassenstruktur für das Halley-Verfahren konnte ebenfalls in die bestehende Klassenstruk-tur integriert werden. Die einzigen Unterschiede zum Newton-Raphson-Verfahren resultierenaus der Tatsache, dass nun auch partielle Ableitungen dritter Ordnung benötigt werden, unddass die Lösung eines Iterationsschritts nicht mehr mit der Methode Adjustment::solveSNE()berechnet werden kann, da hier eine Korrektur des Newton-Schritts, unter Verwendung derdritten Ableitungen, vorgenommen wird.


Adjustment

#SetDiff()

Adjustment_GMM_AD

+declareArrays(in nBeob_ : int, in nPara_ : int)+Build_HG()

Builder_HG

Abbildung 5.1: Neu implementierte Klassen für das Halley-Verfahren

Aus diesem Grund wurde in der Klasse Adjustment_GMM_Halley die Methode solveSNE()überschrieben.

34


Um das Halley-Verfahren z.B. mit dem Typ BBB zu verwenden, ist vom Anwendungspro-grammierer mit

Adjustment_GMM_H<BBB> agl;

äquivalent zum Newton-Raphson-Verfahren ein Objekt (hier: agl) der Template-KlasseAdjustment_GMM_H zu instanziieren. Tests mit dem Newton-Raphson-Verfahren haben dieVorbetrachtungen in Abschnitt 3.7 bestätigt, womit die Laufzeit für die Bereitstellung derAbleitungen mit den Typen FF und FB im Vergleich zu den Typen BB und BF extrem langsamist, so dass für das Halley-Verfahren die Ableitungen lediglich mit den Kombinationen BBB,BBF, BFF und BFB bestimmt werden.

5.1 Nutzung der STL-Containerklasse map für Ableitungendritter Ordnung

Die partiellen Ableitungen zweiter Ordnung werden in Sparse-Matrizen (Typ SMatrix ) derBibliothek boost abgelegt. Bei der Speicherung der Ableitungen dritter Ordnung sollte manbedenken, dass z.B. bei der Verwendung des Typs multi_array<double,3> der Bibliothekboost bei 50 Unbekannten Speicher für ein Array mit 125000 double Werten alloziert werdenmuss. Um den Speicherplatz so gering wie möglich zu halten, werden mehrere maps (Standard-Bibliothek STL) mit dem Ausdruck

map<int, map<int, map<int, double> > > tensor;

ineinander verschachtelt. Ist eine Ableitung ungleich Null, so wird dieser Wert mit den dreidazugehörigen Indizes der Variable tensor zugeordnet. Eine Testberechnung für ein zwei-dimensionales Lagenetz ergab, dass bei 16 Unbekannten lediglich 96 partielle Ableitungendritter Ordnung gespeichert wurden. Dies entspricht der Belegung eines Tensors dritter Stufeentsprechender Größe (16× 16× 16 Elemente) von 2, 3%.

Bei einer map handelt es sich um einen assoziativen Container, in dem man Werte mit einemeindeutigen Schlüsselwert (hier vom Typ int) ablegen und effizient abfragen kann. Die map-Klasse ist eine Template-Klasse, und somit unabhängig von den Typen die als Element oderSchlüsselwert verwendet werden. Dadurch ist es möglich, für die Ableitungen dritter Ordnungeine Variable vom Typ map<int,map<int,map<int,double>> > zu deklarieren. Der Zugriffauf die Elemente erfolgt über die eindeutigen Schlüsselwerte entweder mit Iteratoren oder mitdem Operator []. Werte vom Typ double können mit der Struktur

typedef pair<int,double> paar;

in den Container eingefügt werden. Ein Element mit den Indices i, j und k wird mit

double wert = 3,14159;tensor[i][j].insert(paar(k,wert));

eingefügt, und mit tensor[i][j][k] abgefragt. Ist unter den angegebenen Schlüsselwertenkein Wert abgelegt, wird bei dem Typ double eine Null zurückgegeben.

35


5.2 Bestimmung partieller Ableitungen dritter Ordnung mitFADBAD++

An dieser Stelle wird auf die Angabe von Quellcode verzichtet und ein tabellarischer Überblicküber die Anwendung von FADBAD++ gegeben. Es gelten dabei die gleichen Bezeichnungenwie in Abschnitt 4.7. Für den Index k gilt k = 0, ..., (u−1), mit u = Anzahl der Unbekannten.Die zugrunde liegenden Kombinationen der Methoden Forward und Backward sind BBB, BBF,BFF und BFB.

Datentyp Adjustment_GMM_H::SetDiff() Builder_H::Build_HG() Zugrif auf Ableitungen

3) Unkn[i].x().x().diff(i,u)

Berechnung von vtPv

a) Obs[l]=0

b) vtPv.x()=0

falls festgehalten:

c) Unkn[i]=0

d) Unkn[i].x()=0

BBF 1) vtPv.diff(0,1)

2) Unkn[i].d(0).diff(i,u)

1) Unkn[i].d(0).x().x()

2) Unkn[i].x().d(j).x()

3) Unkn[i].x().d(j).d(k)

2) Unkn[i].x().diff(i,u)

3) Unkn[i].x().x().diff(i,u)

Berechnung von vtPv

a) vtPv.x()=0

BFF b) Obs[l]=0

falls festgehalten:

c) Unkn[i]=0

1) vtPv.diff(0,1)

1) Unkn[i].d(0).x().x()

2) Unkn[i].d(0).d(j).x()

3) Unkn[i].d(0).d(j).d(k)

Tabelle 5.1: Verwendung von FADBAD++ für Ableitungen dritter Ordnung (Teil I)

36


Datentyp Adjustment_GMM_H::SetDiff() Builder_H::Build_HG() Zugrif auf Ableitungen

Berechnung von vtPv

a) vtPv.x()=0

b) Obs[l]=0

falls festgehalten:

c) Unkn[i]=0

1) vtPv.diff(0,1)

falls nicht festgehalten:

2) Unkn[i].d(0).diff(i,u)

sonst:

BBB d) Unkn[i].d(0)=0

Indices v = u2, w = 0, ..., (v − 1)


3) Unkn[i].x().d(j).diff(w,v)

sonst:

e) Unkn[i].x().d(j)=0

1) Unkn[i].d(0).x().x()

f) Unkn[i].d(0).x()=0

2) Unkn[i].x().d(j).x()

3) Unkn[i].x().x().d(w)

2) Unkn[i].x().diff(i,u)

Berechnung von vtPv

a) vtPv.x()=0

b) Obs[l]=0

falls festgehalten:

c) Unkn[i]=0

1) vtPv.diff(0,1)

BFB Indices v = u2, w = 0, ..., (v − 1)


3) Unkn[i].d(0).d(j).diff(w,v)

sonst:

d) Unkns[i].d(0).d(j)=0

1) Unkn[i].d(0).x().x()

e) Unkn[i].d(0).x()=0

2) Unkn[i].d(0).d(j).x()

3) Unkn[i].x().x().d(w)

Tabelle 5.2: Verwendung von FADBAD++ für Ableitungen dritter Ordnung (Teil II)

37


Vor allem bei den Kombinationen BBB und BFB sind die erforderlichen Schritte teilweiseschwer nachzuvollziehen und vom Autor nicht logisch erklärbar. So müssen die Werte derersten Ableitung nach dem Zugriff auf diese auf Null gesetzt werden, um an die Ableitungenhöherer Ordnung zu gelangen (BBB: Schritt f; BFB: Schritt e). Spezialisierungen werden, wiebei Newton-Raphson, für die Funktionen SetDiff() und Build_HG() benötigt. Die Strukturder Funktionen bleibt dabei so, wie sie in Abschnitt 4.2 beschrieben wurde.

5.3 Die Methode solveSNE() und Tensoren dritter Stufe

Durch die erweiterte Iterationsvorschrift des Halley-Verfahrens wird das Überschreiben derMethode Adjustment::solveSNE() erforderlich. Da ein Aufruf dieser Methode in der Template-Methode compute() erfolgt, ist ein Überschreiben in der Template-Klasse Adjustment_GMM_H<T>nicht möglich, da in compute() der Typ für die Ableitungskombination nicht bekannt ist. Ausdiesem Grund wurde die Klasse Adjustment_GMM_Halley mit einer entsprechenden Funktionimplementiert. Eine Korrektur xb des Newton-Schritts unter Verwendung der dritten Ablei-tungen wird durch die Lösung des Gleichungssystems[

F′(xk) +12F′′(xk)xa

]xb = −1

2F′′(xk)xaxa (5.1)

bestimmt, wobei xa die Lösung des Newton-Schritts ist. Die Symmetrieeigenschaften des Ten-sors F′′(xk) können für die Berechnung des Produkts F′′(xk)x1 genutzt werden.

5.3.1 Supersymmetrische Tensoren

Satz 2

Sei f : Rn → R eine dreimal stetig differenzierbare Funktion. Für ein gegebenes x ∈ Rn seiferner

gi =∂f(x)∂xi

, Hij =∂2f(x)∂xi∂xj

, Tijk =∂3f(x)

∂xi∂xj∂xk, (5.2)

mit g ∈ Rn, H ∈ Rn×n und T ∈ Rn×n×n.H ist eine symmetrische Matrix

Hij = Hji, mit i 6= j. (5.3)

Man sagt, dass ein n× n× n-Tensor supersymmetrisch ist, wenn

Tijk = Tikj = Tjik = Tjki = Tkij = Tkji, i 6= j, j 6= k, i 6= k (5.4)Tiik = Tiki = Tkii, i 6= k. (5.5)

38


Für einen voll besetzten Tensor mit dieser Eigenschaft müssen lediglich 16n (n + 1) (n + 2)

statt n3 Elemente gespeichert werden [12]. Die daraus resultierende Form des Arrays ohneredundant gespeicherte Werte ist in Abbildung 5.2 dargestellt.

Methods for Solving Nonlinear EquationsLocal Methods for Unconstrained Optimization

The General Sparsity of the Third DerivativeHow to Utilize Sparsity in the Problem

Numerical Results

BasicsComputations with the Tensor

Super-Symmetric Tensor

For a super-symmetric tensor we only store 16n(n + 1)(n + 2) elements Tijk for

1 ≤ k ≤ j ≤ i ≤ n. (n = 9).

Trond Steihaug Newton and Halley are one step apart

Abbildung 5.2: Symmetrischer Tensor für n = 9

Bei einer Ausgleichung eines zweidimensionalen Richtungs- und Streckennetzes (TestBed:TestNetz2D_Simulation) mit 4 × 4 Punkten werden ohne Ausnutzung der Symmetrie 2588partielle Ableitungen in der Variable tensor abgelegt. Beachtet man die Symmetrie, so sindlediglich 719 Werte in dem Container enthalten und man kann, neben der Ersparnis vonSpeicherplatz, mit einer geringfügigen Laufzeitverbesserung rechnen, da nun Doppel- bzw.Dreifachschleifen nicht voll durchlaufen werden müssen.

39


5.3.2 Die Methode solveSNE()

Für das Halley-Verfahren ergibt sich der folgende (hier vereinfachte) Ablauf:

1 void Adjustment_GMM_Halley::solveSNE()2 3 // Newton-Schritt:4 loesung = pcg_solve(N,rhs,singular);5

6 // Halley-Schritt:7

8 // N merken:9 SMatrix H = N;

10

11 // Hilfsvariable12 double h;13

14

15 // Produkt F’’(x)*x berechnen16 ...17

18 // rechte Seite:19 rhs = sparse_prod(H-N,loesung,rhs,true);20

21 // Lösungsvektor:22 matrix l;23

24 l = pcg_solve(N,rhs,singular);25

26 // Korrektur der Lösung aus Newton-Schritt27 loesung = loesung+l;28

Entsprechend der Speicherung der Werte ist nun auch die Symmetrie bei der Berechnungdes Terms

NH = N + F′′(xk)x1 (5.6)

(Zeile 16) zu berücksichtigen. In Zeile 19 wird die rechte Seite des zweiten Gleichungssystemsberechnet. Da in Zeile 9 die ursprüngliche Matrix N in der Hilfsmatrix H gespeichet wird,kann −F′′(xk)x1 (rechte Seite des Gleichungssystems der Halley-Korrektur) einfach aus

−F′′(xk)x1 = H−NH (5.7)

bestimmt werden.

40


Entsprechend dem Vorschlag in [12] erfolgt die Berechnung von (5.6) wie folgt:1 void Adjustment_GMM_Halley::solveSNE()2 3 ...4 // N+F’’(x)*x5 for ( int i = 0; i < u; i++ )6 7 for ( int j = 0; j < i; j++ )8 9 for ( int k = 0; k < j; k++ )

10 11 // falls Ableitung existiert12 if (tensor[i][j][k])13 14 h = tensor[i][j][k];15

16 N(i,j)+=loesung(k,0)*h; N(i,k)+=loesung(j,0)*h;17 N(j,k)+=loesung(i,0)*h;18

19 //wegen Symmetrie20 N(j,i)+=loesung(k,0)*h; N(k,i)+=loesung(j,0)*h;21 N(k,j)+=loesung(i,0)*h;22 23 24 if (tensor[i][j][j])25 26 h = tensor[i][j][j];27

28 N(i,j)+=loesung(j,0)*h; N(j,j)+=loesung(i,0)*h;29 N(j,i)+=loesung(j,0)*h; //wegen Symmetrie30 31 32 for ( int k = 0; k < i; k++ )33 34 if (tensor[i][i][k])35 36 h = tensor[i][i][k];37

38 N(i,i)+=loesung(k,0)*h; N(i,k)+=loesung(i,0)*h;39 N(k,i)+=loesung(i,0)*h; // wegen Symmetrie40 41 42 if (tensor[i][i][i])43 44 N(i,i)+=loesung(i,0)*tensor[i][i][i];45 46 47 ...48

In den Zeilen 19 − 21, 29 und 39 wird verhindert, dass lediglich die obere DreiecksmatrixNH berechnet wird. Wie an den Zeilen 5, 7, 9 und 32 zu erkennen ist, wird tatsächlich nurauf den in Abbildung 5.2 dargestellten Teil des Tensors zugegriffen.

41

6 Modifikation von FADBAD++ fürSparse-Vektoren

Vor allem bei der Einführung von zusätzlichen Bedingungen zwischen den Unbekannten, z.B.zwecks Datumsfestlegung, ist zu erwarten, dass nicht alle partiellen Ableitungen der Zielfunk-tion existieren und die Arrays, in denen diese gespeichert sind, dünn besetzt sind. Für höherepartielle Ableitungen verstärkt sich dieser Umstand, da diese für viele Funktionen nach einigenoder sogar allen Parametern verschwinden. Steht im Gradient der Zielfunktion für eine Va-riable x eine Null, so sind ausgehend von dieser alle partiellen Ableitungen höherer Ordnungebenfalls Null. Deshalb soll hier geprüft werden, wie sich die Speicherung der partiellen Ablei-tungen in Sparse-Vektoren resp. in einer map (siehe Abschnitt 5.1) auf die Laufzeit auswirkt.Aufgrund der komplexen Struktur des Backward-Modus in FADBAD++ ist diese Modifika-tion lediglich für den Forward-Modus vorgenommen worden. Die Operatorüberladungen fürdie Grundrechenoperationen sind in der Datei fadiff.h zu finden. Ebenfalls in dieser Dateibefindet sich die Klassenschablone FTypeName für Variablen, bei denen der Forward-Modusangewendet werden soll. Hier ist als Membervariable neben dem Realteil v auch der Infinite-simalteil g als Array deklariert.

public:T v;T *g;

Mit der Typdefinition

typedef typename std::map<unsigned int,T> S_GRADIENT;

kann der neue Infinitesimalteil in FTypeName mit

S_GRADIENT gradient;

deklariert werden und mit den Iteratortypen

typedef typename std::map<unsigned int,T>::iterator S_GRADIENT_ITERATOR;typedef typename std::map<unsigned int,T>::const_iterator S_CONST_ITERATOR;typedef typename std::map<unsigned int,T>::value_type S_VALUE_TYPE;

wird der Zugriff auf den Vektor bzw. den Container gradient ermöglicht. Die Memberfunktio-nen von FTypeName müssen wegen dieser Änderung dementsprechend angepasst werden. DieMethode touchg(int n) z.B., welche für die Reservierung des Arrays für die partiellen Ab-leitungen zuständig ist, verzichtet nun auf die Allozierung eines Arrays mit n Elementen undmerkt sich lediglich die Anzahl der partiellen Ableitungen n. Als Beispiel für die Verwendungdes neuen Gradienten in den Operatordefinitionen sollen im Folgenden die Operatoren ∗ undarctan() dienen.

42

6 Modifikation von FADBAD++ für Sparse-Vektoren

6.1 Der Operator *

Der *-Operator ist mit folgender Definition von FADBAD++ überladen:

1 template <class T>2 INLINE2 FTypeName<T> operator* (const FTypeName<T>& a, const FTypeName<T>& b)3 4 // Realteil von c = Multiplikation der Realteile von a und b5 FTypeName<T> c(a.v*b.v);6 // Abbruch falls Größe der Infinitesimalteile unterschiedlich7 USER_ASSERT(a.gsize==b.gsize,"derivative vectors not of same size in operator*");8

9 // Array der Größe des Infinitesimalteils reservieren10 c.touchg(a.gsize);11

12 // Produktregel anwenden13 for (int i=0;i<a.gsize;i++) c.g[i]=a.g[i]*b.v+b.g[i]*a.v;14 return c;15

Zeile 13 wird nun durch den folgenden Code ersetzt:

1 FTypeName<T>::S_GRADIENT_ITERATOR it_c;2 FTypeName<T>::S_GRADIENT_ITERATOR it_end_c=c.gradient.end();3 FTypeName<T>::S_GRADIENT_ITERATOR it_begin_c=c.gradient.begin();4

5 FTypeName<T>::S_CONST_ITERATOR it_b=b.gradient.begin();6 FTypeName<T>::S_CONST_ITERATOR it_end_b=b.gradient.end();7 FTypeName<T>::S_CONST_ITERATOR it_begin_b=b.gradient.begin();8

9 FTypeName<T>::S_CONST_ITERATOR it_a=a.gradient.begin();10 FTypeName<T>::S_CONST_ITERATOR it_end_a=a.gradient.end();11 FTypeName<T>::S_CONST_ITERATOR it_begin_a=a.gradient.begin();12

13 for(;it_a!=it_end_a;it_a++)14 15 c.gradient.insert(FTypeName<T>::TYPE_SPARSE_GRADIENT_VALUE_TYPE...16 ...(it_a->first,it_a->second*b.v));17 18

19 for(;it_b!=it_end_b;it_b++)20 21 // Ist dieses Feld schon in c belegt?22 it_c=c.gradient.find(it_b->first);23

24 // Falls nein:25 If(it_c==it_end_c)26 c.gradient.insert(FTypeName<T>::S_VALUE_TYPE(it_b->first,it_b->second*a.v));27

28 // Falls ja:29 else it_c->second=it_c->second+it_b->second*a.v;30

In Zeile 1− 11 werden die Iteratoren für die Variablen a, b und c deklariert und Zeiger aufden Anfang und das Ende eines jeden Vektors gesetzt. Einer der beiden Eingangsgradienten,

43


in diesem Fall der Gradient von a, wird nun in den Zeilen 13− 17 in die Ausgangsvariable cübertragen. Da nicht existierende Ableitungen nicht abgespeichert werden, muss in Zeile 22geprüft werden, ob eine Ableitung mit dem entsprechenden Schlüsselwert des Vektors von bauch in dem von a bzw. c zu finden ist. Falls das nicht der Fall ist, so fällt der entsprechende Teilder Produktregel weg (Zeile 26). Ansonsten wird der komplette Ausdruck für die Produktregelbenötigt (Zeile 29).

6.2 Die Funktion atan()

In dieser Funktion ist eine Anpassung mit wesentlich weniger Aufwand verbunden:

1 template <class T>2 INLINE2 FTypeName<T> atan (const FTypeName<T>& a)3 4 FTypeName<T> c(atan(a.v));5 c.touchg(a.gsize);6

7 T tmp(FADBAD_ONE/(FADBAD_ONE+_sqr(a.v)));8

9 // alt:10 // for (int i=0;i<a.gsize;i++) c.g[i]=a.g[i]*tmp;11

12 // neu:13 c.gradient.insert(a.gradient.begin(),a.gradient.end());14

15 FTypeName<T>::S_GRADIENT_ITERATOR it = c.gradient.begin();16 FTypeName<T>::S_GRADIENT_ITERATOR it_end = c.gradient.end();17

18 for(;it!=it_end;it++) it->second=it->second*tmp;19

20 return c;21

Statt Zeile 10 wird nun der Code von Zeile 13− 18 ausgeführt.

6.3 Ergebnisse der Modifikation und Fazit

Am Beispiel eines 2D-Punktnetzes mit 11 × 11 Punkten für das Newton-Raphson-Verfahrenund eines 2D-Punktnetzes mit 4 × 4 Punkten für das Halley-Verfahren wurde getestet, obmit der modifizierten Bibliothek neben der Reduktion des verwendeten Speichers auch eineLaufzeitverbesserung erzielt werden konnte. Alle Tests in dieser Arbeit wurden mit einemLaptop mit den folgenden Merkmalen durchgeführt:

• Intel Pentium M, Prozessor: 1, 5 GHz

• 512 MB −RAM

44


In der ersten Zeile (SLE) der Tabellen 6.1 und 6.2 ist die Zeit in Sekunden für die Bereitstel-lung der partiellen Ableitungen für alle Kombinationen in der Funktion setSLEMatrices()aufgeführt. Die zweite Zeile gibt Auskunft über die Dauer des gesamten Ausgleichungsprozes-ses. Die dunkelgrau hinterlegten Felder markieren die langsamsten, die hellgrau hinterlegtenFelder die schnellsten Laufzeiten.

alte Bibliothek neue Bibliothek

NR<FF> NR<FB> NR<BB> NR<BF> NR<FF> NR<FB> NR<BB> NR<BF>

SLE [s] 87, 6 - 0, 4 0, 4 20, 3 1, 2 0, 4 1, 7

insgesamt [s] 365 - 3, 6 3, 6 89, 9 6, 8 3, 6 8, 4

Tabelle 6.1: Test der Newton-Raphson-Methode, 11× 11 Punkte, 3 Iterationen

Die Bestimmung der Ableitungen mit dem Typ FB dauert länger als mit FF, so dass der Testan dieser Stelle abgebrochen wurde. Für den Typ FF verbessert sich die Laufzeit mit der mo-difizierten Bibliothek enorm, ist aber, verglichen mit den anderen Typen, nicht zu empfehlen.Als beste Kombination erweist sich in diesem Beispiel der Typ BB, für welchen die Laufzeitnatürlich für beide Bibliotheken gleich ist. Nicht den Erwartungen entsprechend verhält sichdie Laufzeit für den Typ BF, denn mit der neuen Bibliothek verschlechtert sich diese enorm.

Für das Halley-Verfahren konnte bei gleicher Beispielberechnung keine größere Netzgrößeals 4 × 4 Punkte gewählt werden, da für die Ableitungen mit dem Typ BBB der Speicherbe-darf für die Aufzeichnung des Berechnungsgraphen zu groß wird und das Programm mit derMeldung, dass nicht genügend virtueller Speicher verfügbar ist, abgebrochen wird.


H<BBB> H<BBF> H<BFF> H<BFB> H<BBB> H<BBF> H<BFF> H<BFB>

SLE [s] 2, 2 0, 2 0, 2 1, 8 2, 2 0, 7 0, 2 0, 3

insgesamt [s] 6, 4 0, 5 0, 7 5, 6 6, 4 2, 4 0, 7 0, 8

Tabelle 6.2: Test der Halley-Methode, 4× 4 Punkte, 2 Iterationen

Für den Typ BBB verändert sich mit der neuen Bibliothek nichts, jedoch ist hier der Speicher-bedarf zwecks Aufzeichnung des Berechnungsgraphen so hoch, dass diese Kombination fürviele Unbekannte nicht funktioniert. Auch hier entspricht die Tatsache, dass für den Typ BBFdie alte Bibliothek schneller ist, nicht den Erwartungen. Für den Typ BFB verbessert sich dieLaufzeit mit der modifizierten Bibliothek enorm. Im folgenden Abschnitt wird diese Beispiel-berechnung weiter untersucht.

45

7 Numerische Ergebnisse derimplementierten Verfahren

Anhand von konkreten und in der Geodäsie häufig auftretenden Beispielberechnungen werdennun die drei Verfahren Gauß-Newton, Newton-Raphson und Halley bezüglich Laufzeit undKonvergenzverhalten untersucht. Dabei wird sowohl die Kombination der Methoden von AD,als auch die modifizierte Bibliothek FADBAD++ behandelt.

7.1 Laufzeituntersuchung

Testbeispiel ist ein simuliertes kombiniertes zweidimensionales Richtungs- und Streckennetz.Die Punkte sind in quadratischer Form angeordnet, wobei vier Punkte ein Quadrat mit einerSeitenlänge von je 10 m bilden. Die Anzahl der Punkte in Y- und X- Richtung ist derartveränderbar, dass immer ein Netz in Form eines Quadrates entsteht. Zwecks Datumsfestlegungwerden die Eckpunkte des Netzes durch Bedingungen festgehalten. Auf jedem Standpunkt (allePunkte die nicht Element einer Außenseite des Netzes sind) werden acht Richtungs- und achtStreckenbeobachtungen zu den benachbarten Punkten simuliert. Dabei ergaben sich folgendeKonfigurationen:

Netzgröße # Beobachtungen # Unbekannte # Restriktionen Redundanz

3× 3 16 19 8 5

4× 4 64 36 8 36

5× 5 144 59 8 93

6× 6 256 88 8 176

7× 7 400 123 8 285

8× 8 576 164 8 420

9× 9 784 211 8 581

11× 11 1296 323 8 981

13× 13 1936 459 8 1485

15× 15 2704 619 8 2093

Es folgen zwei Diagramme, in denen die Laufzeiten für die Bestimmung der benötigtenAbleitungen in einen Iterationsschritt bezüglich der Ausgleichungsverfahren dargestellt sind.Dabei wird zwischen der ursprünglichen und der modifizierten Bibliothek FADBAD++ un-terschieden.

46

7 Numerische Ergebnisse der implementierten Verfahren

Laufzeit für die Bestimmung der Ableitungen (ursprüngliche FADBAD++)

0

2

4

6

8

10

12

2x2 3x3 4x4 5x5 6x6 7x7 8x8 9x9 10x10 11x11 12x12 13x13 14x14 15x15Netzgröße (Punktanzahl)

Lauf

zeit

in s

Gauß-NewtonNewton-Raphson<BB>Newton-Raphson<BF>Newton-Raphson<FB>Newton-Raphson<FF>Halley<BBB>Halley<BBF>Halley<BFB>Halley<BFF>

Abbildung 7.1: Laufzeiten mit ursprünglicher FADBAD++

Laufzeit für die Bestimmung der Ableitungen (modifizierte FADBAD++)

0

2

4

6

8

10

12

2x2 3x3 4x4 5x5 6x6 7x7 8x8 9x9 10x10 11x11 12x12 13x13 14x14 15x15Netzgröße (Punktanzahl)

Lauf

zeit

in s

Gauß-NewtonNewton-Raphson<BB>Newton-Raphson<BF>Newton-Raphson<FB>Newton-Raphson<FF>Halley<BBB>Halley<BBF>Halley<BFB>Halley<BFF>

Abbildung 7.2: Laufzeiten mit modifizierter FADBAD++

47


Das plötzliche Ende des Verlaufs einer Kurve, wie es z.B. in Abbildung 7.2 für den TypBFF der Fall ist, signalisiert, dass mit einer größeren Netzgröße ein Programmabsturz wegenfehlendem virtuellem Speicher für die Aufzeichnung des Berechnungsgraphen herbeigeführtwurde. Abbildung 7.1 verdeutlicht, dass die Laufzeit bei den Kombinationen FB und FF fürdas Newton Raphson-Verfahren, sowie für alle Kombinationen (BBB, BBF, BFB und BFF) desHalley-Verfahrens auch bei relativ kleinen Netzgrößen sehr hoch ist. Bezüglich des Newton-Raphson-Verfahrens ist die Bestimmung der Ableitungen mit der Kombination BB am schnells-ten, dicht gefolgt von der Kombination BF. Damit wird die Vorüberlegung bezüglich der erstenpartiellen Ableitungen aus Abschnitt 3.7 bestätigt. Bei einem Verhältnis von 1 : 1 zwischenden ersten partiellen Ableitungen und den Parametern nach denen diese Abgeleitet werdensollen, ist ebenfalls die Backward-Methode zu empfehlen. Aufgrund der Tatsache, dass beimGauß-Newton-Verfahren für die A-Matrix lediglich partielle Ableitungen erster Ordnung derBeobachtungsgleichungen benötigt werden, ist dieses Verfahren etwas schneller als die Kombi-nationen BB und BF. Mit wachsender Netzgröße ist auch mit wachsenden Laufzeitdifferenzenzu rechnen.

Mit der Modifizierung der Bibliothek FADBAD++ für Sparse-Vektoren hat sich die Laufzeitfür einige Kombinationen verbessert, jedoch sind auch Verschlechterungen zu beobachten. Beider auch hier schnellsten Kombination BB ändert sich nichts, da die Modifikation lediglich fürden Forward-Modus vorgenommen wurde. Für die Kombination FB hat sich die Laufzeit extremverbessert. Auch für die langsamste Kombination FF ist eine Verbesserung der Laufzeit zubeobachten. Gegen den Erwartungen ist das Gauß-Newton-Verfahren durch die Modifikation,wenn auch nur im 1/100 s-Bereich, langsamer geworden. Es stellt auch mit „verbesserter“Bibliothek das schnellste Verfahren bei großen Gleichungssystemen dar. Auch die KombinationBF ist unerwartet langsamer geworden.

Zusammenfassend können bezogen auf das vorliegende Rechenbeispiel die folgenden Aussa-gen getroffen werden:

• Bei der Bestimmung von Ableitungen zweiter Ordnung ist die modifizierte Bibliotheknur schneller, wenn ausschließlich der Forward-Modus verwendet wird (FF), und wennder Forward-Modus vor dem Backward-Modus eingesetzt wird (FB).

• Für den Typ BF ist die neue Bibliothek erheblich langsamer.

• Bei der Bestimmung von Ableitungen dritter Ordnung ist die modifizierte Bibliotheklediglich für die Typen BFB und BFF schneller bzw. gleich schnell.

• Entsprechend der Kombination BF, ist die neue Bibliothek für den Typ BBF ebenfallserheblich langsamer.

Neben einer Verringerung des Speicherbedarfs für den Forward-Modus hat die Modifikationvon FADBAD++ bezüglich der schnellsten Kombinationen der Ableitungsmethoden (BB, BF,BBF und BFF) leider keine Laufzeitverringerung erzielt, sondern ist für die Kombinationen BFund BBF sogar langsamer als die ursprüngliche Version. Das Halley-Verfahren zeigt sich abeiner Netzgröße von 3 × 3 = 9 Netzpunkten als nicht praktikabel. Es ist zwar eine schnellereKonvergenz zu beobachten, jedoch ist bei einer Zielfunktion, welche von mehr als ca. 35 Pa-rametern abhängig ist, für diesen funktionalen Zusammenhang die Bestimmung der partiellenAbleitungen zu aufwendig und es kann aufgrund des extrem hohen Bedarfs an Speicherplatzneben sehr langen Laufzeiten sogar zu Programmabstürzen kommen. Bezüglich der Bereit-stellung der Matrizen für das Newton-Verfahren ist mit den Kombinationen BB und BF der

48


ursprünglichen Bibliothek eine relativ effiziente Alternative zum Gauß-Newton-Verfahren ge-geben. Das Gauß-Newton-Verfahren ist jedoch dadurch, dass hier lediglich Ableitungen ersterOrdnung bestimmt werden, in allen Fällen am schnellsten.

In Tabelle 7.1 sind sowohl die Laufzeiten für die Bestimmung der partiellen Ableitungen(SLE), als auch die Laufzeiten einer kompletten Ausgleichung für die Verfahren Gauß-Newtonund Newton-Raphson aufgeführt.


GN NR<FF> NR<FB> NR<BB> NR<BF> GN NR<FF> NR<FB> NR<BB> NR<BF>

SLE [s] 0, 002 870 >FF 1, 3 1, 5 0, 005 140 5 1, 3 6

∆x 1, 8 1, 7 1, 7

insges. [s] 15, 1 3523 >FF 20, 2 21, 6 15, 4 593 36 20, 2 46, 5

Tabelle 7.1: Laufzeitvergleich GN vs. NR, 15× 15 Punkte, 3 Iterationen

Für beide Verfahren werden gleich viele Iterationsschritte benötigt. Zu beachten ist, dassbeim Newton-Raphson-Verfahren nach einem Iterationsschritt der Gradient für die Kontrolledes Abbruchkriteriums erneut berechnet werden muss. Der Vorteil, dass die Normalgleichungs-matrix N und die rechte Seite des Gleichungssystems bei Newton-Raphson nicht mit mehrerenMatrizenmultiplikationen berechnet werden müssen, führt zu keiner nennenswerten Laufzeit-verbesserung. Ein Vorteil bezüglich des Speicherbedarfs bei Newton-Raphson ist, dass die un-ter Umständen sehr große Ableitungsmatrix A nicht in den Iterationsschritten selbst benötigtwird. Für die Berechnung der Kofaktorenmatrix der Verbesserungen Qvv muss diese allerdingsdennoch bereitgestellt werden. Im Hinblick auf die Laufzeit ist das Gauß-Newton-Verfahrenden neu implementierten Verfahren vorzuziehen. Hier besteht, durch die Verwendung der Gra-dienten der Beobachtungsgleichungen für die Berechnung der einzelnen Elemente der MatrixN, zusätzlich die Möglichkeit ein Mitführen der Ableitungsmatrix A in jedem Iterationsschrittebenfalls zu vermeiden. Diese Vorgehensweise ist noch nicht im Framework implementiert.

7.2 Konvergenzverhalten

Die Betrachtung des Konvergenzverhaltens erfolgt am konstruierten Beispiel eines Bogen-schnitts. In die Berechnung fließen als Beobachtungen vier Strecken vom Neupunkt zu viergegebenen Festpunkten ein. Damit ergibt sich ein Ausgleichungsproblem mit der Redundanzvon r = 2. Um eine Vorstellung darüber zu erhalten, ob und nach wie vielen Iterationsschrit-ten in Abhängigkeit von den Näherungswerten eine Lösung mit den verschiedenen Verfahrengefunden werden kann, wurden ca. 25000 Ausgleichungen mit jedem Verfahren durchgeführt.Die Näherungswerte wurden dabei in einem Raster mit einem Punktabstand von 50 m in Y -und X-Richtung über das Messgebiet verteilt. Insgesamt wird ein Gebiet untersucht, welcheseine Ausdehnung von ca. 8000 × 8000 m hat. Als einheitliches Abbruchkriterium wurde dieMaximumnormm ‖∆x‖∞ < 1 · 10−5 m gewählt. Kartiert man nun die Anzahl der benötigtenIterationen in Abhängigkeit von den Startkoordinaten, so ergibt sich für das Gauß-Newton-Verfahren Abbildung 7.3.

49


Abbildung 7.3: Konvergenzverhalten des Gauß-Newton-Verfahrens.

Zwecks einheitlicher Darstellung für die drei Verfahren sind hier Iterationen im Intervalli = [1, 15] dargestellt. Da die maximale Anzahl der benötigten Iterationen lediglich i = 6beträgt, wurde in 7.3 eine logarithmische Skala gewählt.

Die Punkte P1,..,4 sind in etwa quadratisch angeordnet und der Neupunkt befindet sich inder Mitte dieses Quadrates. Statt der Punkte selbst sind die beobachteten Strecken zwischendiesen eingezeichnet. Zunächst fällt auf, dass bei diesem Beispiel unabhängig von den Start-werten immer die korrekte Lösung gefunden wird (dazu später mehr). Untersuchungen in derunmittelbaren Umgebung der Lösung haben ergeben, dass für Startwerte in einem radialenBereich von ca. 0.5 m um die gesuchte Lösung das Abbruchkriterium nach zwei Iterations-schritten erfüllt ist. Befinden sich die Startwerte in einem radialen Bereich von ca. 150 m umdie gesuchte Lösung, werden drei Iterationen benötigt. Bei Ausdehnung dieses Bereichs aufca. 2000 m um den gesuchten Punkt werden vier Iterationen benötigt. Darüber hinaus werdenlaut Abbildung 7.3 maximal fünf bis sechs Iterationen erforderlich, um das Abbruchkriteri-um zu erfüllen. Diese Aussagen sind jedoch sicherlich nicht auf andere, z.B. kompliziertereAufgabenstellungen, bei denen die Zielfunktion von weitaus mehr Parametern abhängt, über-tragbar. Hier kann es abhängig von den Startwerten durchaus zu Divergenz, Oszillation oderzu Konvergenz gegen eine andere Lösung (lokales Minimum) kommen.

50


Das entsprechende Diagramm für das Newton-Raphson-Verfahren ist in Abbildung 7.4 dar-gestellt.

Abbildung 7.4: Konvergenzverhalten des Newton-Raphson-Verfahrens.

Aufgrund der recht symmetrischen Anordnung der Punkte ergibt sich offenbar auch ein sym-metrisches Muster der Bereiche gleicher Konvergenz. Auch hier führt jeder Satz von Startwer-ten zum richtigen Ergebnis. Verglichen mit dem Gauß-Newton-Verfahren ist der Radius desBereichs um die Lösung, in dem die gesuchten Parameter in zwei Iterationsschritten gefundenwerden, mit ca. 0.3 m etwa 20 cm kleiner als beim Gauß-Newton-Verfahren. Auch die Berei-che in denen nach drei bzw. vier Iterationen des Abbruchkriterium erfüllt wird ist mit einemRadius von ca. 50 m bzw. 500 m um die Lösung kleiner als beim Gauß-Newton-Verfahren.Bei Startwerten in der Umbebung der Festpunkte ist teilweise mit sehr vielen Iterationen zurechnen.

Mit der Anwendung des Halley-Verfahrens (Abbildung 7.5) erweitert sich der Bereich derNäherungskoordinaten, in dem lediglich zwei Iterationen für die Parameterschätzung benötigtwerden, auf ein Gebiet mit einem Radius von ca. 4.2 m um die tatsächliche Lösung. BeiStartwerten ab einem Radius von ca. 1500 m um den gesuchten Neupunkt ist mit weitausmehr Iterationen zu rechnen als bei den vorher betrachteten Verfahren. In den dunklerenRegionen werden teilweise mehr als 15 Iterationen benötigt.

51


Abbildung 7.5: Konvergenzverhalten des Halley-Verfahrens.

Durch die Untersuchung der Eigenwerte der Hesse-Matrix konnte festgestellt werden, dassfür Näherungswerte in einigen Bereichen des untersuchten Gebiets, die Zielfunktion vT Pvnicht konvex ist. Diese Feststellung wird durch die Betrachtung der Zielfunktion bestätigt.Die zwei zu schätzenden Parameter spannen einen zweidimensionalen Raum auf und durchdie Funktion vT Pv ist die dritte Dimension gegeben. In Abbildung 7.6 ist zu erkennen, dass dieZielfunktion lediglich ein Minimum und eine recht einfache Struktur besitzt. Deshalb konnte inden Berechnungen für jeden Satz von Näherungswerten die korrekte Lösung gefunden werden.In den Bereichen der Festpunkte P1,..,4 „wölbt“ sich die Funktion in positiver Z-Richtung nachoben. In diesen Regionen ist offensichtlich, dass Satz 1 in Abschnitt 2.5 nicht mehr erfülltsein kann und somit die Funktion nicht konvex ist. In einem solchen Fall ist laut Abschnitt2.6 nicht gewährleistet, dass in den Lösungen des Minimierungsproblems tatsächlich auch dieLösungen des ursprünglichen Problems enthalten sind. Vermutlich aufgrund des Vorliegensvon nur einem Minimum ist die Lösung jedoch nicht verloren gegangen.

52


Abbildung 7.6: Zielfunktion vT Pv für das Beispiel Bogenschnitt.

7.3 Fazit

Zusammenfassend können aufgrund der Laufzeituntersuchung in Abschnitt 7.1 folgende Aus-sagen getroffen werden:

• Durch die Implementierung der Verfahren Newton-Raphson und Halley konnte keineLaufzeitverbesserung im Vergleich zum Gauß-Newton-Verfahren erzielt werden.

• Die Bereitstellung der Ableitungen beim Newton-Raphson-Verfahren ist mit der Anwen-dung der Backward-Methode für die Ableitungen erster und zweiter Ordnung für die hiervorgestellten Testberechnungen am schnellsten.

• Die Modifikation der Bibliothek FADBAD++ ist für einige Kombinationen der Bestim-mung der Ableitungen von Vorteil, hat aber für die ursprünglich schnellsten Verfah-ren (NR<BF> und GN) eine Laufzeitverschlechterung zur Folge. Für die Berechnung mitNR<BB>, welche in den Testberechnungen stets die schnellsten Ergebnisse lieferte, ändertsich durch die Modifikation nichts.

53


Nach Abschnitt 7.2 lassen sich folgende Aussagen bezüglich des Konvergenzverhaltens derbetrachteten Verfahren treffen:

• Bezüglich des Beispiels Bogenschnitt fällt auf, dass das Gauß-Newton-Verfahren nachmaximal sechs Iterationsschritten, unabhängig von den Startwerten in dem festgelegtenIntervall, das definierte Abbruchkriterium erfüllt.

• Im Vergleich zu Gauß-Newton wurde mit dem Newton-Raphson-Verfahren insgesamteine langsamere Konvergenz erreicht. Mit dem Halley-Verfahren konnte zwar der Bereichfür eine schnellere Konvergenz in der näheren Umgebung der Lösung vergrößert werden,jedoch sind weitaus mehr Iterationen für Startwerte in den nicht konvexen Regionen derZielfunktion und in deren Umgebung erforderlich.

Es konnte anschaulich gezeigt werden, dass die Konvexität der Zielfunktion nicht für alle Start-werte gewährleistet ist. Dies korrespondiert mit der Forderung, dass bei einer Ausgleichungdurch ein lokal konvergentes und iteratives Verfahren stets gute Näherungswerte angesetztwerden sollten, da sonst die Gefahr besteht, nicht das globale bzw. kein Minimum zu fin-den. Abbildung 7.7 zeigt, bei welchen Startwerten man mit dem Newton-Raphson-Verfahrenzwangsläufig eine nicht konvexe Zielfunktion erhält. Dabei können die Startwerte entwederdirekt am Beginn der Berechnung in den nicht konvexen Bereichen liegen (Umgebung derFestpunkte), oder die iterierten Parameter „durchqueren“ im Laufe der Berechnung einen die-ser Bereiche.

Abbildung 7.7: Startwerte, welche bei Newton-Raphson zu einer nicht konvexen Zielfunktionführen. rot=konvex, gelb=nicht konvex

54

8 Robuste Parameterschätzung mit demNewton-Raphson-Verfahren

Mit dem Newton-Raphson-Verfahren ist, unter Verwendung des automatischen Differenzierensmit den Kombinationen BB und BF für die partiellen Ableitungen, ein relativ effizienter Ansatzfür die Lösung einer Minimierungsaufgabe im Gauß-Markov-Modell gegeben. Dabei wurde indieser Arbeit bislang lediglich die Methode der kleinsten Quadrate betrachtet. Da hier fürdie Lösung eines Minimierungsproblems erst nach der Formulierung der Normalgleichungenmittels Taylorapproximation linearisiert wird, gilt es die berechtigte Frage zu beantworten, obmit diesem Verfahren auch für andere Zielfunktionen eine Lösung gefunden werden kann.

In diesem Abschnitt wird die Klasse der M-Schätzer vorgestellt und anhand von Beispielenbelegt, dass das Newton-Raphson-Verfahren unter gewissen Voraussetzungen bezüglich derGüte der Näherungswerte ein alternativer Ansatz für die oft in der Literatur vorgeschlage-nen Regewichtung darstellt. Bei einer Regewichtung erfolgt die Parameterschätzung mit demGauß-Newton-Verfahren, wobei die Gewichte der Beobachtungen entsprechend der angesetz-ten Zielfunktion in jedem Iterationsschritt angepasst werden.

Bevor das allgemeine Konzept der M-Schätzer näher betrachtet wird, soll zunächst auf diezuvor nötige Homogenisierung des Gauß-Markov-Modells zwecks einheitlicher Darstellung derVerbesserungen eingegangen werden.

8.1 Homogenisierung des Gauß-Markov-Modells

Als Grundlage für die robuste Parameterschätzung ist eine einheitlich skalierte Darstellungder Verbesserungen erforderlich. Anders als beim Gauß-Newton-Verfahren wird hier jedochvon nichtlinearen Beobachtungsgleichungen ausgegangen bzw. auf eine Linearisierung dieserverzichtet. Damit ergibt sich für die Verbesserungen der Zusammenhang

vi = f(x)− li. (8.1)

Eine Homogenisierung [5] des funktionalen und stochastischen Modells führt unter Trans-formation der Verbesserungen v auf unkorrelierte und gleich genaue Beobachtungen l mitVarianzen σ2

li= 1.0 bzw. Cll = I.

Die Homogenisierung erfolgt durch Linksmultiplikation des funktionalen Modells (8.1) mitder Transformationsmatrix C−1/2

ll :

vi = C−1/2ll · vi = P1/2 · vi (8.2)

In dieser Arbeit und auch im Framework GENERAL wird von nicht korrelierten Beobach-tungen ausgegangen. In diesem Fall ergibt sich die Matrix C−1/2

ll aus den Kehrwerten derWurzeln der Hauptdiagonalelemente der Diagonalmatrix Cll.

55

8 Robuste Parameterschätzung mit dem Newton-Raphson-Verfahren

8.2 Allgemeines Konzept

Der Begriff M-Schätzer ist eine Abkürzung für die Bezeichnung Maximum-Likelihood-Schätzer.Das Prinzip der „maximalen Wahrscheinlichkeit“ besagt, dass mittels der M-Schätzer eineLösung xM gefunden wird, welche ein Maximum der Likelihood-Funktion L(x, l) liefert (x= Schätzwerte, l = tatsächlich durchgeführte Beobachtungen). In [5] ist mit L(x, l) z.B. dieDichtefunktion

L(x, l) =1

n√

2π · det Cll· e−

12vT·C−1

ll·v (8.3)

für normalverteilte Beobachtungen gemeint. Im Grunde wird jedoch bei diesem Konzept kei-ne spezielle Verteilungsfunktion vorausgesetzt. Das Maximum von L(x, l) ist äquivalent zurMinimierung des negativen Exponenten der Dichtefunktion (8.3). Für normalverteilte Beob-achtungsfehler ist die M-Schätzung mit der so genannten M-Schätzerfunktion

ρ(vi) =12(v2

i ) (8.4)

äquivalent zur klassischen Kleinste-Quadrate-Schätzung [5]. Dieses Konzept kann nun verall-gemeinert werden, indem statt der Funktion (8.4) beliebige -in der Literatur auch als Verlust-funktionen bezeichnete- Schätzfunktionen ρ(vi) zugelassen werden.

8.3 M-Schätzer

Eine Schätzung von Parametern nach der Methode der kleinsten Quadrate ergibt, unter derVoraussetzung dass die Messwerte frei von systematischen und groben Fehlern sind, bekannt-lich die wahrscheinlichste und demnach beste Lösung. Ein entscheidender Nachteil dieser Me-thode ist jedoch die große Anfälligkeit auf das Ergebnis, sobald die geforderten Bedingungenan die Messwerte nicht eingehalten werden. Ein grober Fehler wirkt sich hier auf alle Beob-achtungen bzw. Verbesserungen aus, wobei dann von „Verschmierungseffekten“ die Rede ist.Eine Schätzfunktion wird als robust bezeichnet, wenn der Einfluss von groben Fehlern aufdas Schätzergebnis minimal gehalten wird, so dass trotz grober Fehler ein nahezu optimalesErgebnis erzielt werden kann. Bei M-Schätzern wird, wie auch bei der verwandten Methodeder kleinsten Quadrate, eine Schätzfunktion gesucht, so dass die Summe der Verlustfunktionenρ(vi) minimal wird: ∑

ρ(vi)→ min. (8.5)

Es folgt eine Darstellung verschiedener robuster und nicht robuster Verlustfunktionen ρ(v),welche in der Klase der M-Schätzer zusammengefasst sind und in GENERAL implementiertwurden. Dabei ist jeweils die Verlust- und die Einflussfunktion dargestellt. An der Einfluss-funktion Ψ(v), welche die erste Ableitung der Verlustfunktion nach v, also ∂ρ(v)/∂v darstellt,kann man ablesen, wie groß der Einfluss einer Verbesserung v auf das Schätzergebnis ist. Einerobuste Schätzfunktion ρ(v) sollte eine kontinuierliche, überall beschränkte und eine im mitt-leren Bereich mit der Einflussfunktion der Methode der kleinsten Quadrate übereinstimmendeoder ähnliche Einflussfunktion aufweisen1.

1Mehr zu dem Eigenschaften robuster Schätzfunktionen in [7] Seite 182ff.

56


8.3.1 Huber-Schätzer

Verlustfunktion Einflussfunktion

ρ(v) =

12 · v

2 , |v| < k

k · |v| − 12 · k

2 , |v| ≥ k

Ψ(v) =

v , |v| < k

k · sign(v) , |v| ≥ k

Die Tuningkonstante wird meist mit k = 1.5 angesetzt.

0

0.5

1

1.5

-2 -1 0 1 2

ρ(v)

v

-2

-1

0

1

2

-3 -1.5 0 1.5 3

Ψ(v)

vAbbildung 8.1: links: Verlustfunktion ρ(v), rechts: Einflussfunktion Ψ(v)

Ab dem Wert |v| = k (hier: k = 1.5) geht der quadratische Teil in eine lineare Funktionüber. Daraus folgt eine beschränkte Einflussfunktion Ψ(v). Alle skalierten Verbesserungen miteinem Wert v > k haben demnach den gleichen betragsmäßig beschränkten Einfluss auf dasErgebnis.

8.3.2 modifizierter Huber-Schätzer


ρ(v) =

12 · v

2 , |v| ≤ k

k · |v| − 12 · k

2 , k < |v| ≤ b

k · b− 12 · b

2 , |v| > b

Ψ(v) =

v , |v| < k

k · sign(v) , k < |v| ≤ b

0 , |v| > b

Standardwerte für die Tuningkonstanten k = 1.5 und b = 3.0.

Verbesserungen mit |v| > b haben keinen Einfluss auf das Schätzergebnis.

57


0

1

2

3

-4 -2 0 2 4

ρ(v)

v

-2

-1

0

1

2

-4 -2 0 2 4

Ψ(v)

v

Abbildung 8.2: links: Verlustfunktion ρ(v), rechts: Einflussfunktion Ψ(v)

8.3.3 Hampel-Schätzer


ρ(v) =

12 · v

2 , |v| ≤ a

a · |v| − 12 · a

2 , a ≤ |v| < b

ab− 12 · a

2 + 12a(c− a)·

·[1−

(c−|v|c−b

)2]

, b ≤ |v| < c

ab− 12a + 1

2 (c− b)a, c ≤ |v|

Ψ(v) =

v , |v| < a

a · sign(v) , a ≤ |v| < b

a · c−|v|c−b · sign(v) , b ≤ |v| < c

0 , c ≤ |v|

Standardwerte für die Tuningkonstanten a = 2, b = 4 und c = 8.

0

2.5

5

7.5

10

-10 -5 0 5 10

ρ(v)

v

-3

-1.5

0

1.5

3

-10 -5 0 5 10

Ψ(v)

v


58


8.3.4 Biweight-Schätzer


ρ(v) =

12 · a

2 ·[1−

(1− |v|

a

)2]3

, |v| ≤ a

12 · a

2 , |v| > a

Ψ(v) =

v ·(1−

(va

)2)2

, |v| ≤ a

0 , |v| > a

Standard für die Tuningkonstante: a = 4.685.

0

3

6

9

12

-8 -4 0 4 8

ρ(v)

v

-1.2

-0.6

0

0.6

1.2

-8 -4 0 4 8

Ψ(v)

v


8.3.5 Fair-Schätzer


ρ(v) = a2·|v|a−log(1+(v/a)) Ψ(v) = v

1+|v/a|


59


0

10

20

30

40

-4 -2 0 2 4

ρ(v)

v

-1.5

-0.75

0

0.75

1.5

-4 -2 0 2 4

Ψ(v)

v


8.3.6 Talwar-Schätzer


ρ(v) =

12 · v

2 , |v| ≤ a

12 · a

2 , |v| > a

Ψ(v) =

v , |v| ≤ a

0 , |v| > a

Die Tuningkonstante wird meist mit a = 2.795 angesetzt.

0

1

2

3

4

-6 -3 0 3 6

ρ(v)

v

-3

-1.5

0

1.5

3

-5 -2.5 0 2.5 5

Ψ(v)

v


60


8.3.7 Welsch-Schätzer


ρ(v) = 12 · a

2 ·(1− e(−(v/a))2

)Ψ(v) = v · e−(v/a)2


0

1.125

2.25

3.375

4.5

-10 -5 0 5 10

ρ(v)

v

-1.5

-0.75

0

0.75

1.5

-10 -5 0 5 10

Ψ(v)

v


8.3.8 Lp-Norm-Schätzer: Sonderfall p = 1.5


ρ(v) = |v|1.5 Ψ(v) = 1.5 · sign(v) · |v|0.5

61


0

0.75

1.5

2.25

3

-2 -1 0 1 2

ρ(v)

v

-2

-1

0

1

2

-2 -1 0 1 2

Ψ(v)

v


8.3.9 Lp-Norm-Schätzer: Sonderfall p = 2


ρ(v) = 12 · v

2 Ψ(v) = v

0

4

8

12

16

-4 -2 0 2 4

ρ(v)

v

-4

-2

0

2

4

-4 -2 0 2 4

Ψ(v)

v


62


8.3.10 Krarup-Schätzer

Dieser Schätzer gehört nicht der Klasse der M-Schätzer an, soll aber dennoch in die Betrach-tungen einbezogen werden.


ρ(v) = 12 · v

2 · e−v2/2 Ψ(v) = v · e−v2/2 − v3

4 · e−v2/2

0

0.1

0.2

0.3

0.4

-1.4 -0.7 0 0.7 1.4

ρ(v)

v

-0.5

-0.25

0

0.25

0.5

-6 -3 0 3 6

Ψ(v)

v


8.4 M-Schätzung mit dem Newton-Raphson-Verfahren

Das Newton-Raphson-Verfahren kann auf die oben vorgestellten Schätzfunktionen angewen-det werden, indem die bis jetzt ausschließlich verwendete Funktion ρ(v) = v2 aus Abschnitt8.3.9 durch die gewünschte Verlustfunktion ersetzt wird. An dieser Stelle sei auf die Qualitätder Näherungswerte hingewiesen. Damit eine robuste Lösung mittels des Newton-Raphson-Verfahrens gefunden werden kann, ist es erforderlich, dass die Startwerte für die zu schät-zenden Parameter auf einen Funktionswert im nichtlinearen Teil der Verlustfunktion führen.So müssen die Startwerte für den Huber-Schätzer (Abschnitt 8.3.1) auf einen Funktionswertder Verlustfunktion führen, welcher innerhalb des Umkreises k um das Minimum der Funk-tion liegt. Ist diese Bedingung nicht eingehalten, kann aufgrund der lokalen Linearität derVerlustfunktion mit diesem Verfahren keine Lösung gefunden werden. Aus diesem Grund istdie Schätzung mittels L1-Norm mit dem Newton-Raphson-Verfahren nicht möglich, wobeibei dieser Schätzfunktion hinzu kommt, dass sie im Minimum nicht stetig differenzierbar ist.Bei ausreichend guten Näherungswerten können die Tuningparameter mit den vorgeschlagenenStandardwerten angesetzt werden. Meist haben grobe Fehler jedoch auch schlechte Näherungs-werte zur Folge, so dass es zu einer Überlagerung dieser beiden Effekte kommt. In diesem Fall

63


ist ein iteratives Vorgehen erforderlich, bei dem zunächst die Tuningparameter so gewähltwerden, dass eine Lösung gefunden werden kann. Anhand der Größe ihrer Verbesserung kanndann eine fehlerhafte Beobachtung erkannt und ausgeschaltet werden. Grundvoraussetzungfür das Lokalisieren von groben Fehlern ist eine gewisse lokale Redundanz. Je schlechter dieNäherungswerte sind und demnach große Werte für die Tuningparameter erforderlich werden,desto schlechter lassen sich grobe Fehler lokalisieren, da die Schätzfunktionen im mittlerenTeil, wie gefordert, der der Methode der Kleinsten Quadrate entsprechen oder ähneln. Esfolgt eine erneute Anpassung der Tuningparameter, bis alle groben Fehler gefunden werdenkonnten.

8.5 Untersuchung robuster Schätzer am Beispiel linearer undnichtlinearer Ausgleichungsprobleme

Anhand von Beispielen wird nun gezeigt, wie sich die vorgestellten Schätzfunktionen bei grobenFehlern verhalten. In jedem Beispiel ist eine bzw. ca. 30% der Beobachtungen kontaminiert,wobei im nichtlinearen Fall zusätzlich zwischen „guten“ bzw. „schlechten“ Näherungswertenunterschieden wird.

Es wird jeweils tabellarisch für jede Schätzfunktion die Abweichung ∆xL2 zum Ergebnis auseiner Schätzung mit der Methode der Kleinsten Quadrate ohne die grob fehlerhaften Beobach-tungen aufgelistet. Weiterhin werden die Verbesserungen der kontaminierten Beobachtungenvk dem groben Fehler fk durch die Differenz |vk − fk| gegenübergestellt und der „Verschmie-rungseffekt“ durch die höchste Verbesserung der nicht kontaminierten Beobachtung vmax einerjeden Beobachtungsgruppe aufgeführt. Für den Fall, dass eine Anpassung der Tuningparame-ter erforderlich wird, werden diese zusätzlich angegeben. Ist dies nicht der Fall, wurden dieStandardwerte verwendet. Für den mittleren Gewichtseinheitsfehler einer Beobachtung mitdem Gewicht p = 1 gilt bei jedem Beispiel σ0,apriori = 1.

8.5.1 Neupunktbestimmung

Dieses Beispiel entspricht dem Beispiel aus Abschnitt 7.2, wobei zwecks Erhöhung der Re-dundanz zusätzlich Richtungswinkelbeobachtungen (keine Richtungen!) eingeführt wurden.Es wurden 8 Beobachtungen (4 Richtungswinkel und 4 Strecken) vom Neupunkt mit denKoordinaten YN , XN zu den i = 4 Festpunkten getätigt. Die Redundanz beträgt somit r = 6.

Funktionales Modell Stochastisches Modell

Strecke: si =√

(Yi − YN )2 + (Xi −XN )2 ms = ±0.01 m

Richtungswinkel: ri = arctan(

Yi−YNXi−XN

)mr = ±0.01 gon

Tabelle 8.1: Funktionales und stochastisches Modell für das Beispiel Neupunktbestimmung.

64


Mit Näherungswerten einer Genauigkeit von ±2 cm (entsprechend den Messgenauigkeiten)um die gesuchte Lösung und einem groben Fehler fr1 = 5 gon ergeben sich folgende Ergebnisse:

Schätzer/ ∆xL2 vk |fr1 − vk| vmax

Tuningkonst. Richtung [gon] Strecke [m]

L2 Y : −0.035 m −5.008 gon 0.008 gon r2 : 0.012 s2 : 0.069

X : −0.052 m

L1,5 Y : −0.003 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.014

X : −0.003 m

Huber Y : 0.000 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.013

k = 2.8 X : 0.000 m

Huber-Mod Y : 0.000 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.013

k = 4, b = 8 X : 0.000 m

Hampel a = 4, Y : 0.000 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.013

b = 8, c = 12 X : 0.000 m

Biweight Y : 0.171 m −5.014 gon 0.014 gon r2 : 0.0001 s4 : 0.221

X : 0.126 m

Fair Y : 0.000 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.013

X : 0.000 m

Talwar Y : 0.000 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.013

X : 0.000 m

Welsch Y : 6.182 m −5.104 gon 0.104 gon r2 : −0.121 s3 : −5.042

a = 7 X : −0.226 m

Krarup Y : 0.015 m −5.009 gon 0.009 gon r2 : −0.010 s1 : 0.036

X : −0.018 m

Tabelle 8.2: Ergebnisse mit einem groben Fehler fr1 = 5 gon und „guten“ Startwerten.

Für einige Schätzfunktionen ist schon mit den recht guten Näherungswerten eine Anpas-sung der Tuningkonstanten erforderlich um eine Lösung berechnen zu können (z.B. Huber undHampel). Bei einer Schätzung nach L2- und L1.5-Norm treten die zu erwartenden Verschmie-rungseffekte auf. Während sich bei der L2-Schätzung der grobe Fehler durch die maximaleVerbesserung bei den Strecken von vs2 = 0.096 m auswirkt, tritt dieser Effekt bei der L1,5-Schätzung etwas gedämpfter auf. Mit den Schätzern Huber, Huber-Mod, Hampel, Fair undTalwar wird das gleiche Ergebnis erzielt, wie es bei einer L2-Schätzung ohne die fehlerhafteBeobachtung der Fall wäre. Auffällig ist, dass der M-Schätzer Welsch extrem empfindlich aufdie Änderung seiner Tuningkonstante reagiert.

In Tabelle 8.3 sind die Ergebnisse für die gleichen Näherungswerte, jedoch mit den drei

65


groben Fehlern fr1 = 5 gon, fr2 = −1 gon und fs3 = −10 m dargestellt.

Schätzer/ ∆xL2 vk |fk − vk| vmax


L2 Y : 3.439 m r1 : −5.001 gon 0.001 gon r4 : 0.128 s1 : 4.962

X : −3.598 m r2 : 0.875 gon 0.125 gon

s3 : 5.111 m 4.889 m

L1,5 Y : 3.212 m r1 : −5.000 gon 0.000 gon r4 : 0.1200 s1 : 4.671

X : −3.414 m r2 : 0.881 gon 0.119 gon

s3 : 5.403 m 4.597 m

Huber Y : 0.019 m r1 : −5.009 gon 0.009 gon r3 : −0.0098 s1 : 0.027

k = 2.8 X : −0.020 m r2 : 0.990 gon 0.010 gon

s3 : 9.999 m 0.001 m

Huber-mod Y : 0.000 m r1 : −5.010 gon 0.010 gon r4 : −0.010 s4 : 0.006

k = 4, b = 8 X : 0.000 m r2 : 0.990 gon 0.010 gon

s3 : 10.026 m 0.026 m

Hampel a = 4, Y : 0.000 m r1 : −5.010 gon 0.010 gon r4 : −0.010 s4 : 0.006

b = 8, c = 12 X : 0.000 m r2 : 0.990 gon 0.010 gon

s3 : 10.026 m 0.026 m

Biweight Y : −0.001 m r1 : −5.010 gon 0.010 gon r4 : −0.010 s4 : 0.006

X : 0.001 m r2 : 0.990 gon 0.010 gon

s3 : 10.027 m 0.027 m

Fair Y : 0.003 m r1 : −5.009 gon 0.009 gon r4 : −0.010 s4 : 0.007

X : −0.004 m r2 : 0.990 gon 0.010 gon

s3 : 10.021 m 0.021 m

Talwar Y : −0.029 m r1 : −5.010 gon 0.010 gon r4 : −0.0114 s1 : −0.044

X : 0.032 m r2 : 0.991 gon 0.009 gon

s3 : 10.068 m 0.068 m

Welsch Y : 0.000 m r1 : −5.010 gon 0.010 gon r4 : −0.010 s4 : 0.006

a = 7 X : 0.000 m r2 : 0.990 gon 0.010 gon

s3 : 10.026 m 0.026 m

Krarup Y : 0.026 m r1 : −5.009 gon 0.09 gon r3 : −0.010 s1 : 0.038

X : −0.029 m r2 : 0.989 gon 0.011 gon

s3 : 9.988 m 0.012 m

Tabelle 8.3: Ergebnisse mit drei groben Fehlern sowie „guten“ Näherungswerten.

66


Drei grobe Fehler wirken sich stark auf das Ergebnis der L2- und L1,5-Norm-Schätzungaus. Die Streckenbeobachtung s1 erhält hier eine Verbesserung von 4.96 m bzw. 4.67 m, ob-wohl sie nicht fehlerbehaftet ist. Für den modifizierten Huber-Schätzer, sowie für die SchätzerHampel und Welsch sind Ergebnisse erzielt worden, die einer L2-Norm Schätzung ohne diekontaminierten Beobachtungen entsprechen. Für diese drei Schätzer gilt, dass besonders großeskalierte Verbesserungen durch einen konstanten Teil der Zielfunktion keinen Einfluss auf dasSchätzergebnis haben. Diese Eigenschaft besitzen auch die Schätzer Biweight und Talwar, je-doch sind die Tuningkonstanten bei diesen offensichtlich nicht entsprechend gewählt worden.Es folgt die tabellarische Darstellung der Ergebnisse mit einem groben Fehler fr1 = 5 gon undmit Näherungswerten im Bereich von ±5 m um die gesuchte Lösung.

Schätzer/ ∆xL2 vk |fr1 − vk| vmax


L2 Y : −0.035 m −5.008 gon 0.008 gon r2 : 0.012 s2 : 0.069

X : −0.052 m

L1,5 Abbruchkriterium nicht erreicht

Huber Y : −0.035 m −5.008 gon 0.008 gon r3 = −0.012 s2 = 0.069

k = 710 X : −0.052 m

Huber-Mod Y : −0.035 m −5.008 gon 0.008 gon r3 : −0.012 s2 : 0.069

k = 710, b = 800 X : −0.052 m

Hampel a = 200, Y : −0.010 m −5.009 gon 0.009 gon r3 : −0.010 s2 : 0.025

b = 400, c = 800 X : −0.016 m

Biweight Y : 0.000 m −5.009 gon 0.009 gon r2 : 0.000 s3 : 0.013

a = 70 X : −0.001 m

Fair Y : −0.865 m −4.993 gon 0.007 gon r3 : −0.028 s4 : −0.776

a = 2 X : −0.142 m

Talwar Y : 0.000 m −5.009 gon 0.009 gon r2 : −0.010 s3 : 0.013

a = 40 X : 0.000 m

Welsch Y : −11.103 m −4.990 gon 0.010 gon r4 : −0.394 s3 : 14.219

a = 10 X : 8.868 m

Krarup Keine Lösung gefunden

Tabelle 8.4: Ergebnisse mit einem groben Fehler fr1 = 5 gon und „schlechten“ Näherungswer-ten.

Es überrascht, dass hier mit der L2-Norm eine Lösung gefunden werden konnte, die näher amgewünschten Ergebnis liegt, als mit guten Näherungswerten. Mit der L1.5-Norm wurde dasAbbruchkriterium nicht erreicht, da hier genau der Fall eingetreten ist, wie er in Abschnitt2.8.3 für das Gauß-Newton-Verfahren beschrieben wurde: Die Schrittweite eines Iterations-schrittes ist aufgrund des Funktionsverlaufes (Abbildung 8.11) und der daraus resultierenden

67


großen Gradienten offensichtlich zu weit, so dass sich ein Alternieren um die Lösung einstellt(siehe Tabelle).

Iteration ∆x [m] grad(x)

1 Y: 10.008 6779.18

X: -10.083 -4884.92

2 Y: -10.009 -6850.45

X: 10.079 4856.35

3 Y: 10.010 6783.22

X: -10.074 -4879.5

. . . .

98 Y: -10.124 -7105.09

X: 9.614 4523.78

99 Y: 10.125 7058.82

X: -9.608 -4527.9

100 Y: -10.127 -7113.22

X: 9.602 4513.61

Abbildung 8.11: Zielfunktion für die L1.5-Norm.

Die Tuningparameter mussten, um die Lösbarkeit des Gleichungssystems zu gewährleisten,teilweise sehr hoch angesetzt werden, so dass der grobe Fehler einen Einfluss äquivalent zurL2-Norm aufweist (siehe Huber- und modifizierter Huber-Schätzer). Mit den Schätzern Bi-weight und Talwar ist es gelungen, den Einfluss des groben Fehlers auf das Schätzergebnisnahezu gänzlich einzudämmen.

68




L2 Y : 3.439 m r1 : −5.001 gon 0.001 gon r4 : 0.128 s1 : 4.962

X : −3.598 m r2 : 0.875 gon 0.125 gon

s3 : 5.111 m 4.889 m

L1,5 Y : 3.212 m r1 : −5.000 gon 0.000 gon r4 : 0.1200 s1 : 4.671

X : −3.414 m r2 : 0.881 gon 0.119 gon

s3 : 5.403 m 4.597 m

Huber Y : 3.439 m r1 : −5.001 gon 0.001 gon r4 : 0.128 s1 : 4.962

k = 710 X : −3.598 m r2 : 0.875 gon 0.125 gon

s3 : 5.111 m 4.889 m

Huber-mod Y : −0.017 m r1 : −5.008 gon 0.008 gon r3 : −0.012 s2 : 0.070

k = 710, X : −0.072 m r2 : 0.990 gon 0.010 gon

b = 800 s3 : 9.996 m 0.004 m

Hampel a = 4, Y : 0.005 m r1 : −5.009 gon 0.009 gon r3 : −0.010 s2 : 0.027

b = 400, X : −0.033 m r2 : 0.990 gon 0.010 gon

c = 800 s3 : 10.002 m 0.002 m

Biweight Y : −0.001 m r1 : −5.010 gon 0.010 gon r4 : −0.010 s4 : 0.006

a = 70 X : 0.001 m r2 : 0.990 gon 0.010 gon

s3 : 10.027 m 0.027 m

Fair Y : 0.251 m r1 : −5.018 gon 0.009 gon r4 : −0.012 s4 : 0.369

a = 2 X : 0.273 m r2 : 0.990 gon 0.010 gon

s3 : 9.992 m 0.008 m

Talwar Y : 0.000 m r1 : −5.010 gon 0.010 gon r4 : −0.010 s4 : 0.006

a = 40 X : 0.000 m r2 : 0.990 gon 0.010 gon

s3 : 10.026 m 0.026 m

Welsch Y : −9.153 m r1 : −4.994 gon 0.006 gon r4 : −0.325 s1 : −11.744

a = 10 X : 7.384 m r2 : 1.264 gon 0.264 gon

s3 : 21.781 m 11.781 m

Krarup Keine Lösung gefunden

Tabelle 8.5: Ergebnisse mit drei groben Fehlern und „schlechten“ Näherungswerten.

Bei schlechten Näherungswerten und drei groben Fehlern setzt sich ebenfalls die Talwar-und die Biweight-Schätzfunktion bezüglich der gewünschten Lösung durch, wohingegen derKrarup-Schätzer erneut zu keinem sinnvollen Ergebnis führt (Tabelle 8.5). Die Schätzer mitkonstantem Funktionswert für hohe skalierte Verbesserungen v weisen erneut die geringstenVerschmierungseffekte auf und zeigen sich in diesem Beispiel als äußerst trennfähig. Das heißt,

69


dass sehr gut zwischen „guten“ und „schlechten“ Beobachtungen unterschieden werden kann.Um eventuelle kleinere grobe Fehler zu lokalisieren, ist es erforderlich die Ausgleichung erneutohne die als grob fehlerhaft erkannten Beobachtungen durchzuführen und die Tuningkonstan-ten entsprechend anzupassen. Diese Vorgehensweise setzt allerdings voraus, dass eine gewisselokale Redundanz auch nach dem Streichen von Beobachtungen vorhanden ist.

8.5.2 Ausgleichende Gerade

Zu fehlerfrei bekannten Zeitpunkten t wurden die Werte y gemessen. Der Verlauf der Messun-gen soll mittels ausgleichender Gerade

y = f(t) = a · t + b (8.6)

approximiert werden. Die Messungen sind gleich genau und nicht korreliert. Es handelt sichum ein lineares Problem mit zwei unbekannten Parametern, woraus bei n = 17 Beobachtungeneine Redundanz von r = 15 folgt.

Zeit t [s] 1 1.25 1.5 1.75 2 2.25 2.5 2.75 3 3.25 3.5 3.75 4 4.25 4.5 4.75 5

Messwert y 5.1 5.2 5.9 6.1 6.4 6.5 6.6 6.9 7.2 7.7 7.9 8.3 8.5 9.1 9.4 10 10.2

Tabelle 8.6: Messwerte

Mit der Methode der kleinsten Quadrate werden die Parameter

a = 1.2517, b = 3.7162

als wahrscheinlichste Lösung geschätzt. Im Datenmaterial sind anhand der normierten Ver-besserungen und auch rein optisch (Abbildung 8.12) keine groben Ausreisser zu lokalisieren.

Abbildung 8.12: Ergebnis der L2-Schätzung ohne grobe Fehler

70


Bei der Anwendung des Newton-Raphson-Verfahrens mit robusten Schätzern für lineareProbleme ist jedoch folgendes zu beachten:

• Für quadratische Zielfunktionen wird aufgrund der quadratischen Konvergenz, unabhän-gig von den Startwerten, eine exakte Lösung des Problems nach einem Iterationsschrittgefunden. Mit der Anwendung von Schätzfunktionen welche nicht quadratisch sind, giltdieser Umstand jedoch nicht mehr.

• Damit eine Lösung mit dem Newton-Raphson-Verfahren gefunden werden kann, bzw.die Hesse-Matrix invertierbar ist, müssen auch bei linearen Problemen für die robustenSchätzer hinreichend gute Näherungswerte angegeben werden. Ist dies nicht der Fall,so müssen die Tuningparameter unter Umständen so groß gewählt werden, dass grobeFehler einen ebenso großen Einfluss auf das Ergebnis haben, wie bei einer Schätzungnach der Methode der kleinsten Quadrate und somit nicht eindeutig lokalisiert werdenkönnen.

Auch in diesem Beispiel werden nun die Ergebnisse der verschiedenen Schätzfunktionen miteinem und mit ca. 30% kontaminierten Beobachtungen tabellarisch dargestelllt. Im Falle einesgroben Fehlers wurde die Beobachtung zum Zeitpunkt t = 3 s um ft3 = +3 verfälscht. Ausden oben genannten Gründen werden als Startwerte die Lösung aus der L2-Norm-Schätzungmit allen Beobachtungen angesetzt. Bei dem groben Fehler ft3 = +3 lauten die Startwertesomit

a = 1.2 b = 3.9.

Die Ergebnisse der Berechnungen sind in Tabelle 8.7 zusammengestellt. Auch hier entspre-chen die Ergebnisse der Schätzern Huber-Mod., Hampel und Talwar dem gewünschten Ziel,das Schätzergebnis nicht durch grobe Fehler zu beeinflussen. Das Finden der richtigen Tuning-parameter ist jedoch teilweise mühsam und zeitaufwendig.

Schätzer/ ∆xL2 vt3 |ft3 − vt3| vmax

Tuningkonst. Beobachtung Wert

L2 a : 0.000 −2.552 0.448 t = 2.75 : 0.435

b : 0.159

L1.5 a : −0.009 −2.653 0.347 t = 2.75 : 0.336

b : 0.086

Huber a : 0.000 −2.662 0.338 t = 2.75 : 0.325

k = 0.8 b : 0.050

Huber-Mod a : 0.000 −2.712 0.288 t = 4.74 : −0.334

k = 0.8, b = 1 b : 0.000

Hampel a : 0.000 −2.712 0.288 t = 4.74 : −0.334

k = 0.8, b = 1 b : 0.000

Fortsetzung auf der nächsten Seite ...

71


Schätzer/ ∆xL2 vt3 |ft3 − vt3| vmax

Tuningkonst. Beobachtung Wert

Biweight a : 0.002 −2.709 0.291 t = 4.74 : −0.327

k = 0.8, b = 1 b : −0.004

Fair Keine Lösung gefunden.

Talwar a : −0.001 −2.712 0.288 t = 4.74 : −0.337

a = 1 b : 0.000

Welsch a : 0.000 −2.713 0.287 t = 4.74 : −0.334

a = 1 b : 0.003

Krarup a : −0.003 −2.715 0.285 t = 4.74 : −0.341

a = 1 b : 0.004

Tabelle 8.7: Ergebnisse mit einem groben Fehler ft3 = 3 und Startwerten aus der L2-Lösungmit allen Beobachtungen.

Bei allen Schätzfunktionen wurde nach einem Iterationsschritt das Abbruchkriterium erfüllt.Für den Fair-Schätzer konnte kein günstiger Tuningparameter gefunden werden. Mit allen ge-

Abbildung 8.13: Zielfunktion des Fair-Schätzers für das Beispiel ausgleichende Gerade (a = 3).

72


wählten Tuningparametern wurde hier das Abbruchkriterium auch nach 100 Iterationen nichterfüllt. Die Zielfunktion mit dem Tuningparameter a = 3 ist in Abbildung 8.13 dargestellt.Das Minimum der Funktion befindet sich in einem langgestreckten Tal. Eine Analyse der Än-derungen ∆x und des Gradienten pro Iterationsschritt ergibt, dass sich ein Alternieren um dieLösung mit den differentiellen Änderungen ∆xa = ±22.4 und ∆xb = ±7.5 einstellt.

Die obigen Ergebnisse zeigen, dass ein grober Fehler bei n = 15 Beobachtungen selbst beider L2-Norm keine stark signifikanten Veränderungen in den Parametern hervorruft. Deshalbwurden die groben Fehler bei 30% kontaminierten Beobachtungen (= 5 grobe Fehler) wie folgtgewählt:

Zeit 1.25 1.5 3 4.74 5

Fehler +9 +10 +3 -7 -10

Die Ergebnisse mit den fehlerbehafteten Beobachtungen sind in Tabelle 8.8 zusammenge-fasst.


Tuningkonst. t [s] Wert t [s] Wert

L2 a: −2.415 1.25 −4.302 4.698 1.00 5.103

b: 7.582 1.50 −6.306 3.694 4.50 −3.458

3.00 −2.432 0.568

4.74 2.650 4.350

5.00 5.133 4.867

L1.5 a: −1.918 1.25 −5.183 3.817 1.00 4.097

b: 6.079 1.50 −7.064 2.936 4.50 −2.726

3.00 −2.445 0.555

4.74 3.501 3.499

5.00 6.114 3.886

Huber a: −2.050 1.25 −5.060 3.940 1.00 4.253

k = 4 b: 6.368 1.50 −6.973 3.027 4.50 −3.030

3.00 −2.551 0.449

4.74 3.165 3.835

5.00 5.744 4.256

Huber-Mod. a: −0.535 1.25 −8.045 0.955 4.25 −0.956

k = 4 b: 1.489 1.50 −9.579 0.421 4.50 −1.090

b = 6 3.00 −2.885 0.115

4.74 5.469 1.531

5.00 8.441 1.559


73



Tuningkonst. t [s] Wert t [s] Wert

Hampel a: −0.080 1.25 −8.565 0.435 2.75 0.432

a = 2.8 b: 0.401 1.50 −9.985 0.015 2.50 0.411

b = 5 3.00 −2.609 0.391

c = 7 4.74 6.535 0.465

5.00 9.625 0.375

Biweight a: −1.741 1.25 −5.796 3.204 3.25 −0.382

a = 8.5 b: 5.245 1.50 −7.631 2.369 1.00 3.440

3.00 −2.746 0.254

4.74 3.509 3.491

5.00 6.167 3.833

Fair Abbruchkriterium nicht erreicht.

Talwar a: 0.008 1.25 −8.666 0.334 2.75 0.443

b: 0.189 1.50 −10.064 0.064 2.50 0.441

3.00 −2.556 0.444

4.74 6.742 0.258

5.00 9.855 0.145

Welsch a: −0.003 1.25 −8.763 0.237 2.50 0.330

b: 0.106 1.50 −10.164 0.164 2.75 0.329

3.00 −2.673 0.327

4.74 6.606 0.394

5.00 9.716 0.284

Krarup a: −3.034 1.25 −2.712 6.288 1.75 4.470

b: 9.945 1.50 −4.871 5.129 2.75 0.329

3.00 −1.925 1.075

4.74 2.080 4.920

5.00 4.403 5.597

Tabelle 8.8: Ergebnisse mit fünf groben Fehlern.

Wie erwartet, ist der Einfluss der groben Fehler auf das Ergebnis für die Schätzung nach L2-und L1.5-Norm am größten. Das Ergebnis des Huber-Schätzers lässt vermuten, dass lediglichdie größten groben Fehler durch die Tuningkonstante k = 4 in ihrem Einfluss begrenzt werdenkonnten. Mit den Schätzern Talwar und Welsch ist eine Lösung erzielt worden, die den ge-wünschten Forderungen am besten entspricht. Abbildung 8.14 veranschaulicht die Ergebnisseam Beispiel ausgewählter Schätzer. Dabei ist die grüne Gerade das Ergebnis aus einer L2-

74


Schätzung ohne kontaminierte Beobachtungen und die blaue Linie das Ergebnis des jeweiligenSchätzers.

Abbildung 8.14: Vergleich ausgewählter Lösungen (blau) mit der L2-Lösung ohne fehlerhafteBeobachtungen (grün).

8.5.3 Ausgleichender Kreis

Die Kreisgleichung (8.7) führt ohne weitere Umformungen auf eine bedingte Ausgleichung mitUnbekannten (Gauß-Helmert-Modell).

(Xi −XM )2 + (Yi − YM )2 −R2 = 0 (8.7)

Dabei sind die Kreisparameter YM , XM und R die zu schätzenden Parameter und Xi undYi die Beobachtungen. Andere Darstellungen in Abhängigkeit von Richtungs- und Strecken-messungen sind selbstverständlich auch möglich. Durch eine elegante Umformung kann dieses

75


Problem in das Gauß-Markov-Modell überführt werden. Grundgedanke dabei ist, dass dieStrecken Ri vom Kreismittelpunkt zu den beobachteten Punkten Pi dem tatsächlichen RadiusR entsprechen (also R−Ri = 0), wenn alle Punkte auf dem Kreis liegen. Durch den geschicktgewählten Ausdruck

R2 −R2i = (R−Ri) · (R + Ri)⇔ R−Ri︸︷︷︸

vi

=(R2 −R2

i )R + Ri︸︷︷︸

2Ri

(8.8)

wird eine so genannte Pseudobeobachtung eingeführt, wobei es sich offensichtlich um den recht-winkligen Abstand eines Punktes Pi vom Kreis handelt. Für alle Punkte Pi, welche den Kreisbeschreiben, ergeben sich die Beobachtungen li = 0.0m und der Ausdruck R − Ri entsprichtden Verbesserungen vi. Mit der Formulierung der Radien Ri in Abhängigkeit von Koordinatenerhält man

(R−Ri)︸︷︷︸vi

·2Ri = R2 − (Xi −XM )2 − (Yi − YM )2 (8.9)

= 2XiXM + 2YiYM +(R2 −X2

M − Y 2M

)−X2

i − Y 2i . (8.10)

Wird nun für den Term(R2 −X2

M − Y 2M

)die Ersatzunbekannte a eingeführt, so hat man mit

vi = 2XiXM + 2YiYM + a−X2i − Y 2

i (8.11)

ein lineares Problem, bei dem die Koordinaten Yi, Xi als Konstanten einfließen. Da der Faktor2Ri auf der linken Seite aller Beobachtungsgleichungen einfließt, kann er einfach weggelassenwerden. Nach der Ausgleichung kann der Kreisradius R aus

R =√

a + Y 2M + X2

M (8.12)

bestimmt werden.

Es wurden folgende Punktbeobachtungen getätigt:

Punkt 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Y [m] 18.3 20.0 21.5 22.3 23.7 24.6 25.1 25.9 26 26.5 27 27.2 27.3 27.3 27.4

X [m] 19.1 20.1 20.8 22.3 22.7 23.5 25.6 26.5 28.3 41.2 31.3 33.3 29.7 35.6 38.4

Tabelle 8.9: Messwerte für das Beispiel ausgleichender Kreis.

Aus den n = 15 Punkten können ebenso viele Beobachtungsgleichungen für die Pseudobeob-achtungen formuliert werden. Alle Pseudobeobachtungen gelten als gleich genau und unkor-reliert. Die Redundanz beträgt somit bei u = 3 Unbekannten r = n − u = 12. In Abbildung8.15 ist das Ergebnis einer Ausgleichung mit der Methode der kleinsten Quadrate visualisiert.Das Schätzergebnis lautet

Y = 10.412 m

X = 34.250 m

a = −985.487 m2 → R = 17.203 m

Die Berechnungsergebnisse für die einzelnen Schätzer sind in Tabelle 8.10 den Ergebnissen derentsprechenden L2-Norm-Schätzung ohne die grob fehlerhafte Koordinate gegenübergestellt.

76


Abbildung 8.15: L2-Ergebnis ausgleichender Kreis ohne grobe Fehler

Schätzer/ ∆xL2 vk [m] |fk − vk| [m] vmax [m]

Tuningkonst.

L2 Y : 8.484 m 4.141 5.859 l10 : -2.351

X : −2.968 m l1 : -2.131

a : −256.818 m2

L1.5 Y : 7.010 m 5.235 4.765 l10 : -2.274

X : −2.968 m l1 : -1.621

a : −201.453 m2

Huber Y : 3.755 m 7.384 2.616 l10 : -1.177

k = 30 X : −1.374 m l1 : -0.733

a : −110.563 m2

Huber-Mod. Y : 0.000 m 9.072 0.928 l6 : -0.543

k = 30 X : 0.000 m l12 : 0.449

b = 40 a : 0.000 m2


77



Tuningkonst.

Hampel Y : 0.000 m 9.072 0.928 l6 : -0.543

a = 30, b = 40 X : 0.000 m l12 : 0.449

b = 50 a : 0.000 m2

Biweight Y : 9.755 m 0.029 9.971 l10 : -10.902

X : −8.243 m l15 : -10.338

a : −70.599 m2

Fair Y : 8.610 m 4.128 5.872 l1 : -2.276

X : −2.688 m l10 : -1.957

a : −276.252 m2

Talwar Y : 11.543 m −3.774 13.774 l1 : -13.213

a = 3 X : −8.973 m l15 : -9.604

a : −127.488 m2

Welsch Y : 7.743 m 5.191 4.809 l1 : -2.195

a = 5 X : −1.407 m l11 : 1.791

a : −294.597 m2

Krarup Y : 5.080 m 7.871 2.129 l10 : 4.505

a = 5 X : 3.466 m l15 : 4.283

a : −390.142 m2

Tabelle 8.10: Ergebnisse mit einem groben Fehler fk = −10 m und Startwerten aus der L2-Lösung mitallen Beobachtungen.

Es sei darauf hingewiesen, dass die Verbesserungen der Pseudobeobachtungen in dem obenbeschriebenen und hier angewendeten Modell multipliziert mit dem Faktor (R + Ri) ange-geben werden. Für eine anschauliche Darstellung wurden die Verbesserungen entsprechendumgerechnet. Die Schätzungen von Kreismittelpunkt und Radius variieren für die verschiede-nen Schätzer teilweise sehr stark. Mit dem modifizierten Huber- und dem Hampel-Schätzerkonnten die besten Ergebnisse erzielt werden. Dies war bei einem groben Fehler bei dem Bei-spiel ausgleichende Gerade auch mit der Talwar-Schätzfunktion möglich, welche jedoch hierzu keinem zufriedenstellenden Ergebnis führt. Der Radius beträgt hier R = 2.876 m, womiteine Abweichung von rund 14 m vom L2-Norm Ergebnis ohne die fehlerhafte Beobachtungvorliegt. Mit den fünf groben Fehlern

Koordinate Y3 Y4 Y9 Y14 Y15

Fehler [m] −15 −20 +5 +27 +18

78


liefert die L2-Norm die Näherungswerte

Y = 27.205 m

X = 30.286 m

a = −1470.244 m2 → R = 14.261 m,

womit die Unterschiede zur Lösung ohne die kontaminierten Beobachtungen ∆Y ≈ 17 m,∆Y ≈ 4 m und ∆R ≈ 3 m betragen.


Tuningkonst.

L2 Y : 16.694 m l3 : −11.611 26.611 l13 : 6.480

X : −3.793 m l4 : −17.211 37.211 l11 : 6.585

a : −476.704 m2 l9 : 5.308 10.308

l14 : −9.398 17.602

l15 : −3.721 14.279

L1.5 Y : 16.360 m l3 : −14.018 29.018 l13 : 4.917

X : −4.415 m l4 : −20.021 40.021 l11 : 4.932

a : −481.905 m2 l9 : 3.827 8.827

l14 : −11.337 15.663

l15 : −5.685 12.315

Huber Y : 13.128 m l3 : −10.987 25.987 l11 : 4.369

k = 4 X : −2.960 m l4 : −15.956 35.956 l13 : 4.135

a : −416.587 m2 l9 : 2.262 7.262

l14 : −14.748 12.252

l15: −8.257 9.743

Huber-Mod. Y : 2.866 m l3 : 11.836 25.987 l11 : 1.086

k = 4 X : −0.982 m l4 : −31.428 51.428 l12 : 1.924

b = 6 a : −74.366 m2 l9 : −3.047 1.953

l14 : −24.794 2.206

l15 : −16.564 1.436

Hampel Y : 16.702 m l3 : −19.600 34.600 l1 : −4.686

a = 2.8 X : −4.547 m l4 : −26.462 46.462 l13 : 2.903

b = 5 a : −560.777 m2 l9 : 2.057 7.057

c = 7 l14 : −13.033 13.967

l15 : −7.447 10.553


79



Tuningkonst.

Biweight Y : −5.410 m l3 : 5.166 9.834 l10 : 11.568

a = 8.5 X : 16.154 m l4 : 6.727 13.273 l12 : 7.032

a : −447.078 m2 l9 : −0.452 4.548

l14 : −19.431 7.569

l15 : −9.210 8.790

Fair Y : 17.167 m l3 : −12.205 27.205 l13 : 6.310

X : −4.508 m l4 : −18.054 38.054 l11 : 6.328

a : −466.951 m2 l9 : 5.306 10.306

l14 : −9.258 17.742

l15 : −3.783 14.217

Talwar Y : 2.010 m l3 : 0.818 14.182 l10 : −0.689

X : −0.593 m l4 : −0.381 20.381 l11 : 0.592

a : −67.557 m2 l9 : −3.695 1.305

l14 : −25.652 1.348

l15 : −17.278 0.722

Welsch Y : 19.316 m l3 : −13.173 28.173 l13 : 7.149

X : −4.819 m l4 : −19.342 39.342 l11 : 7.111

a : −528.914 m2 l9 : 6.556 11.556

l14 : −6.494 20.506

l15 : −1.502 16.498

Krarup Keine Lösung gefunden.

Tabelle 8.11: Ergebnisse mit fünf groben Fehlern fk und Startwerten aus der L2-Lösung mit allenBeobachtungen.

Der Forderung nach Übereinstimmung mit dem Ergebnis aus der Methode der kleinstenQuadrate ohne die kontaminierten Beobachtungen kommt der modifizierte Huber- und derTalwar-Schätzer in diesem Fall am besten nach. Mit dem Talwar-Schätzer haben die grobenFehler den kleinsten Einfluss auf die Verbesserungen der übrigen Pseudobeobachtungen. InAbbildung 8.16 sind einige Ergebnisse visualisiert. Dabei ist der rote Kreis das gewünschteErgebnis und der blaue Kreis das mit der jeweiligen Schätzfunktion berechnete. Die beobach-teten Koordinaten sind grün, die Kreismittelpunkte lila markiert. Mit dem Talwar-Schätzerkonnte der Einfluss auf das Ergebnis der beiden extrem großen Fehler (Y = 40− 60 m) kom-plett eingedämmt werden, wohingegen mit den übrigen drei Fehlern die betreffenden Punktenoch so nahe am Kreisbogen liegen, dass sich der Einfluss dieser durch ein „Ziehen“ des Kreisesin positiver Y -Richtung bemerkbar macht.

80


Abbildung 8.16: Ausgewählte Ergebnisse bei fünf goben Fehlern

8.5.4 Fazit

Die hier angeführten Beispiele verdeutlichen, dass sich die Lösungen der einzelnen Schätzerteilweise stark unterscheiden können und die Wahl der Tuningparameter unter Umständen sehrschwierig ist. Eine geringfügige Veränderung dieser kann das Ergebnis stark beeinflussen. Esist somit viel Erfahrung gefordert, um, unter Beachtung der Güte der Näherungswerte und derQualität der Messwerte, sinnvolle Ergebnisse mit den verschiedenen Schätzern zu berechnen.Des weiteren kann offensichtlich die Art der Aufgabenstellung darüber entscheiden, welcheSchätzfunktionen die besten Ergebnisse liefern. Die Schätzfunktionen Talwar, Biweight, Ham-pel, Mod.-Huber und Hampel haben für die hier betrachteten Aufgabenstellungen die bestenErgebnisse geliefert. In anderen Problemstellungen ist es jedoch durchaus möglich, dass dieseSchätzer versagen, so dass man sich nicht auf die Ergebnisse einer favorisierten Schätzfunktion

81


verlassen sollte. Unabhängig von der Problemstellung (linear/nichtlinear) sind Näherungswer-te erforderlich, wodurch für fast alle vorgestellten Schätzer bei schlechten Näherungswertendie Robustheit eingeschränkt wird.

8.6 Implementierung

Um dem Anwendungsprogrammierer zu ermöglichen zwischen verschiedenen Zielfunktionen zuwählen, wurde die Template-Klasse Adjustment_GMM_NR um den Template-Parameter ESTIM_TYPEerweitert. Da die partielle Template-Spezialisierung einer Memberfunktion von den Compilernnoch nicht unterstützt wird, wurde die gesamte Struktur der Klassen Adjustment_GMM_NR undBuilder_NR entsprechend angepasst. Die Funktion virtual Adjustment_GMM_AD::SetDiff,

#setSLEMatrices()#setSNE()#calculate_v()#calculate_Qvv()#calculate_v_ad()#calculate_Qxx()#testLinearization()#GetValues()#CalcEstimFunktn()#getA()

#pBuilderHG : Builder_HG *Adjustment_GMM_AD

+Adjustment_GMM_NR()+~Adjustment_GMM_NR()+setTuningParam(in t1 : double, in t2 : double, in t3 : double)+GetValues()+CalcEstimFunktn()

+m_HGBuilder : Builder_NR<AD_TYPE>+m_EstimationObj : IEstimation<AD_TYPE> *

Adjustment_GMM_NR

AD_TYPE, ESTIM_TYPE

+operateOn(in pAE : IAdjustmentElement*)+SetMatrixPointer()+declareArrays(in nBeob_ : int, in nPara_ : int)+SetDiff_FWD()+Build_HG()+test_hesse() : int+get_v()+get_A()

Builder_HG

+declareArrays(in nBeob_ : int, in nPara_ : int)+SetDiff_FWD()+Build_HG()+Builder_NR()+~Builder_NR()

+ArrayUnknowns_ : AD_TYPE *+ArrayObservations_ : AD_TYPE *+vtPv : AD_TYPE

Builder_NR

AD_TYPE

+CalcEstimFunktn(inout p : Builder_NR)+getName() : string+setTuningParam(in t1 : double, in t2 : double, in t3 : double)

IEstimation

AD_TYPE

+Hampel()+CalcEstimFunktn(inout p : Builder_NR)+getName() : string+setTuningParam(in t1 : double, in t2 : double, in t3 : double)

#a : double#b : double#c : double

Hampel

AD_TYPE

+Talwar()+CalcEstimFunktn(inout p : Builder_NR)+getName() : string+setTuningParam(in t1 : double, in t2 : double, in t3 : double)

#a : double

Talwar

AD_TYPE

Abbildung 8.17: Klassenstruktur mit erweiterter Funktionalität

für welche abhängig vom AD-Typ eine Spezialisierung erforderlich ist, wurde in die KlasseBuilder_HG verlagert und in SetDiff_FWD() umbenannt, da hier die partiellen Ableitungen

82


für den Forward-Modus eingeleitet werden. Dadurch kann der zusätzliche Template-ParameterESTIM_TYPE eingeführt werden, welcher den Typ der Schätzfunktion festlegt. Ein Objekt aglder Klasse Adjustment_GMM_NR mit den Typen BB und L2 wird wie folgt deklariert:

Adjustment_GMM_NR<BB,L2<BB> > agl;

Der Konstruktor von Adjustment_GMM_NR weist der Membervariable m_EstimationObj desTyps IEstimation* eine Instanz des gewünschten Zielfunktionstyps (z.B. L2, Hampel oderTalwar) zu. In der FunktionAdjustment_GMM_NR::CalcEstimFunktn() wird dann zur Lauf-zeit anhand des Typs ESTIM_TYPE entschieden, welche Zielfunktion berechnet wird. Jede vonIEstimation abgeleitete Klasse muss neben der Methode zur Berechnung der Zielfunktionnoch zwei weitere Methoden überschreiben. Die Methode getName() gibt den Namen der Ziel-funktion für das Zusammensetzen der Ausgabedateinamen zurück und mit setTuningParam(..)können die Tuningparameter verändert werden. Wird eine Veränderung nicht vorgenommen,so gelten die im Konstruktor des jeweiligen Schätzers festgelegten Standardwerte. Die Funk-tion Builder_HG::test_hesse() berechnet die Eigenwerte der Hesse-Matrix und gibt eineWarnung an den Nutzer, sobald die Definitheitsbedingungen nicht erfüllt sind.

83

9 Schlussbetrachtung und Ausblick

In dieser Arbeit konnte bestätigt werden, dass robuste Schätzverfahren durch die direkte Mi-nimierung der Zielfunktion mittels Newton-Raphson-Verfahren mit gewissen Einschränkungengute Ergebnisse liefern und recht einfach in Computerprogrammen umgesetzt werden können.Mit dem automatischen Differenzieren besteht dabei eine elegante Möglichkeit die partiellenAbleitungen der Zielfunktion ohne übermäßigen Mehraufwand zu bestimmen. Das Halley-Verfahren, für welches partielle Ableitungen dritter Ordnung benötigt werden, hat sich beiden Untersuchungen aufgrund extremer Ansprüche an die Rechnerressourcen als nicht prak-tikabel erwiesen.

Das Automatische Differenzieren bringt dem Programmierer, unabhängig vom Typ desAusgleichungsansatzes und des Minimierungsverfahrens, entscheidende Vorteile. So ist eineImplementierung der partiellen Ableitungen nicht erforderlich. Quellcode kann deshalb ein-gespart werden, bleibt übersichtlich und eine unter Umständen aufwendige Suche nach Im-plementierungsfehlern bleibt erspart. Für partielle Ableitungen bis zur zweiten Ordnung istdie Anwendung der Bibliothek FADBAD++ nach einer kurzen Eingewöhnungsphase rechtübersichtlich und einfach zu handhaben. Bezüglich des Newton-Raphson-Verfahrens hat sichherausgestellt, dass die Kombinationen Backward-Backward und Backward-Forward für dieBestimmung der partiellen Ableitungen der Zielfunktion zweiter Ordnung am effizientestensind. Bei der Bestimmung der Ableitungen dritter Ordnung für das Halley-Verfahren erreichtman jedoch schnell die Grenzen der Rechnerkapazitäten.

Mit dem Newton-Raphson-Verfahren ist im Kontext des Gauß-Markov-Modells ein alter-nativer Ansatz zum Gauß-Newton-Verfahren gegeben, welcher es ermöglicht durch die Analyseder Hesse-Matrix in jedem Iterationsschritt Aussagen über die iterierte Lösung zu treffen. Soentspricht das Schätzergebnis bei dem Hinweis, dass die Definitheitsbedingung nicht eingehal-ten wurde, möglicherweise nicht dem globalen Minimum der Schätzfunktion. Besonders beieiner großen Anzahl von Unbekannten ist, auch unter Abhängigkeit vom funktionalen Zusam-menhang, bei dem Newton-Raphson-Verfahren mit etwas längeren Laufzeiten zu rechnen alsmit dem Gauß-Newton-Verfahren.

Die Verwendung alternativer Schätzfunktionen ist mit dem Newton-Raphson-Verfahrenprogrammiertechnisch einfach umzusetzen, jedoch in mathematischer Sicht nur mit gewissenEinschränkungen möglich. Prinzipiell ist die Lösung eines überbestimmten Gleichungssystemshier nur für nichtlineare Bereiche der Zielfunktion möglich. Aus diesem Grund ist eine Lö-sung mit der L1-Norm mit diesem Verfahren nicht möglich. Da einige robuste Schätzer (z.B.Huber und Hampel) bei großen skalierten Verbesserungen ebenfalls eine lineare Zielfunktionaufweisen, ist die Qualität der Näherungswerte eng verknüpft mit der Robustheit der Zielfunk-tion. Durch eine Anpassung der Tuningkonstanten kann erreicht werden, dass die Parameterauf einen Funktionswert im nichtlinearen Teil der Zielfunktion führen. Je größer die Para-meter jedoch gewählt werden müssen, desto mehr wird die Robustheit einer Schätzfunktion

84

9 Schlussbetrachtung und Ausblick

eingeschränkt. Aus diesem Grund wird ein iteratives Vorgehen vorgeschlagen, bei dem nachElimination der als grob fehlerhaft erkannten Beobachtungen die Tuningparameter erneut an-gepasst werden. Die Parameter aus einer Schätzung ohne die als grob fehlerhaft erkanntenBeobachtungen können als neue Startwerte verwendet werden. Für dieses Vorgehen ist beson-ders bei mehreren groben Fehlern eine gewisse lokale Redundanz eine wichtige Voraussetzung.Sobald das Newton-Raphson-Verfahren auf eine nicht quadratische Zielfunktion angewendetwird, ergibt sich auch bei linearen funktionalen Zusammenhängen ein iteratives Verfahren,bei dem Näherungswerte aus einer entsprechenden Schätzung mit der Methode der kleinstenQuadrate angesetzt werden können.

Ausblickend bleibt die Untersuchung alternativer Minimierungsverfahren (z.B. Gradienten-verfahren, Simplex-Verfahren), in denen auch lineare Funktionen zugelassen werden, inter-essant. Des weiteren könnte die Implementierung einer automatische Anpassung der Tuning-parameter analysiert und vorgenommen werden, so dass der Anwendungsprogrammierer dieseteilweise zeitaufwendige Aufgabe nicht „manuell“ zu lösen hat.

85

10 Anhang

Hier soll näher auf die Struktur des Frameworks GENERAL und die in dieser Arbeit angewen-deten Programmiertechniken eingegangen werden. Zu diesen Techniken gehört das generischeProgrammieren und die Entwurfsmuster.

10.1 Generische Programmierung

Mittels generischer Programmierung soll eine möglichst abstrakte Repräsentation von Algo-rithmen und Datenstrukturen gefunden werden. Der Nutzen daraus ist, dass Codedoppelungenvermieden werden und der Code besser für andere Probleme wiederverwendet werden kann.Eine Zusammenstellung dieser abstrakten Repräsentationen wird Framework genannt. Dabeihandelt es sich jedoch nicht um ein fertiges Programm, sondern um eine Rahmenstruktur, dievom Programmierer für seine Anwendung genutzt wird. So löst GENERAL verschiedene Aus-gleichungsprobleme, wobei vom Anwedungsprogrammierer das funktionale und stochastischeModell anzugeben sind.

Die Bezeichnung GENERAL setzt sich zusammen aus Generic Adjustment Library. In derhier eingesetzten Programmiersprache C++ ist mit generischer Programmierung das Verwen-den von Templates (parametrisierbare Typen) gemeint. Als Beispiel soll hier die Struktur fürmathematische Gleichungen in GENERAL dienen. Es wurde ein parametrisiertes Interfacedefiniert, welches lediglich den Operator () deklariert.

1

2 template <class Type>3 class IMathEquation4 5 public: virtual Type operator()(Type** var,double* Konstanten=NULL)=0;6 ;7

Von allen abgeleiteten Klassen muss der Operator () überschrieben werden. Das Klassen-Template der Klasse Pythagoras ist folgendermaßen implementiert:

1

2 template <class Type>3 class Pytargoras: public IMathEquation<Type>4 5 Type result;6

7 public:8 Type operator()(Type** var,double* Konstanten=NULL)9

10 // Die Koordinatenunterschiede

86

10 Anhang

11 Type dx,dy;12

13 // (*var[0], *var[1]) = (X1,Y1)14 // (*var[2], *var[3]) = (X2,Y2)15 // (*var[4]) = Beobachtung16

17

18 // Die Differenzen19 dx=*var[0]-*var[2];20 dy=*var[1]-*var[3];21

22 // Verbesserung = Satz des Pytagoras - Beobachtung23 result=sqrt(dx*dx+dy*dy)-*var[4];24

25 return result;26 ;27 ;28

Damit ist die Gleichung Pythagoras nicht an einen bestimmten Datentyp wie z.B. doublegebunden. Alle Deklarationen (z.B. ein Funktionsprototyp) und Definitionen (z.B. der dazugehörige Funktionsrumpf) werden üblicherweise in Headerdateien angegeben, da der Compilerzum Übersetzungszeitpunkt den Code für das Anlegen der Klassen benötigt.

10.2 Entwurfsmuster

In der objektorientierten Programmierung ist man immer mit dem Problem des Entwurfs einerKlassenstruktur konfrontiert. Für die Lösung von sich oft wiederholenden Entwurfsproblemenhaben sich sogenannte Entwurfsmuster (Design Patterns) etabliert. Da die Anforderungen ver-schiedener Natur sein können, bieten diese Muster keine fertige Lösung, sondern lediglich einenmöglichen Lösungsweg. Im GoF-Buch [1] werden 23 verschiedene Enfwurfsmuster vorgestellt.Diese können in drei verschiedene Kategorien eingeteilt werden:

Erzeugungsmuster (creational patterns)

Mit einem Muster dieser Klasse können, unabhängig von einem System, Objekte mit ge-wünschten Eigenschaften erzeugt werden. Diese Klasse ist hier nur der Vollständigkeit halberaufgeführt, denn ein Muster dieser wird hier nicht verwendet.

Strukturmuster (structural patterns)

Mit einem Muster dieser Klasse können Vorschriften festgelegt werden, wie Klassen und Ob-jekte zu größeren Strukturen zusammengesetzt werden sollen. Auch diese Muster finden inGENERAL bis jetzt keine Verwendung.

87

10 Anhang

Verhaltensmuster (behavioral patterns)

Diese Kategorie beinhaltet die größte Anzahl an Entwurfsmustern. Ein Muster dieser Klassekümmert sich um die Zusammenarbeit und den Nachrichtenaustausch zwischen Objekten undKlassen. Von großer Relevanz für GENERAL sind die Muster Besucher (visitor pattern) undSchablonenmethode (template method), wobei der Begriff template in diesem Zusammenhangnichts mit der in 10.1 angesprochenen Template-Programmierung zu tun hat.

10.2.1 Besucher-Muster

Mit der Verwendung des Besucher-Musters können neue Operationen und Methoden definiertwerden, ohne die Objektstruktur bzw. Klassen auf die ein Visitor zugreift, zu ändern. Dazuwird jede Operation, welche auf die Elemente einer Objektstruktur zugreift, als ein Objektgekapselt. Damit wird erreicht, dass die Klassen der Objektstruktur klein und übersichtlichbleiben.

Es werden zwei Klassenhierarchien verwendet: Zum einen das Datenmodell, und zum ande-ren eine Visitor-Hierarchie. In Letzterer werden die Operationen bezüglich der Elemente derDatenklasse definiert. In [4] wird die Struktur in etwa wie folgt dargestellt.

Abbildung 10.1: Struktur des Besucher-Musters

Die Bindung eines Visitors an eine Datenklasse erfolgt mittels der Implementierung eineraccept-Methode innerhalb dieser. An diese wird eine Referenz auf den Visitor übergeben.accept ruft dann die visit-Methode (z.B. v->VisitConcreteElementA(this) des Visitor-Objekts auf. Der Parameter this ist eine Referenz auf die aufrufende Klasse. Damit erkenntder Visitor, welcher Code auszuführen ist. Sämtliche Daten (Beobachtungen etc.) im Fra-

88

10 Anhang

mework werden nach diesem Schema in der Elementklasse AdjustmentElementCollector inForm von Vektoren gespeichert. Für die Berechnung einer Ausgleichung kommen dann die„Algorithmen zu den Daten“ und nicht „die Daten zum Algorithmus“.

10.2.2 Schablonenmethode

Die Schablonenmethode stellt für diese Arbeit das wichtigste Entwurfsmuster dar. Mit ihr istes möglich, ein Grundgerüst zu definieren und dieses mit Unterklassen zu spezialisieren.

+Template Methode()+Operation1()+Operation2()

Abstrakte Klasse

+Operation1()+Operation2()

Konkrete Klasse 1

.....Operation1().....Operation2()

+Operation1()+Operation2()

Konkrete Klasse 2

Abbildung 10.2: Allgemeine Struktur des Schablonen-Entwurfsmusters

Der invariante Teil eines Algorithmus wird in der abstrakten Klasse definiert und die vari-ierenden Methoden in den Unterklassen implementiert. Da gemeinsame Operationen lediglichein mal implementiert werden, wird doppelter Code vermieden. Zur Laufzeit des Programmswird dann entschieden, aus welcher Unterklasse die betreffende Methode aufgerufen wird.

10.3 Implementierung verschiedener Ausgleichungsansätze

Um einen alternativen Ausgleichungsansatz im Framework zu implementieren, muss zunächstgeklärt werden, welche Ansätze schon vorhanden sind, und vor allem, wie diese strukturiertsind. Die bisherige Struktur ist durch lange Denkprozesse und Abwägungen hinsichtlich Effi-ziens, Übersichtlichkeit und Wiederverwendbarkeit entstanden, und sollte deshalb nach Mög-lichkeit nicht verändert, sondern lediglich erweitert werden (Open-Close-Prinzip).

Auf eine Herleitung und detaillierte Beschreibung der implementierten Ausgleichungsansät-ze soll hier verzichtet, und auf [5], [3] und die Diplomarbeit von Alexander Merx verwiesenwerden. In Abschnitt 2 werden die hier relevanten Verfahren vorgestellt.

Bislang sind in GENERAL das Gauß-Helmert-Modell, das Gauß-Markov-Modell und dierein bedingte Ausgleichung (PCM = pure conditional model) implementiert. Die Ansätzeunterscheiden sich zwar, jedoch treten in allen auch gleiche Berechnungen auf, wie z.B. dieBerechnung der gewichteten Verbesserungsquadratsumme vT Pv. Deshalb wurde hier die Scha-blonenmethode angewendet.

89

10 Anhang

Folgendes UML-Diagramm veranschaulicht die Anwendung des Entwurfsmusters.

+setName(in name : string)


Adjustment

Abbildung 10.3: Struktur der Ausgleichungsansätze

Für die Klasse Adjustment sind aus Gründen der Übersichtlichkeit nicht alle Attribu-te und Methoden aufgelistet. collector ist eine Instanz der oben angesprochenen KlasseAdjustmentElementCollector. Hier sind alle Beobachtungen, Unbekannte und Gleichungendes funktionalen Zusammenhangs gespeichert. Die restlichen Attribute werden im Laufe derBerechnungen mit der Template-Methode compute() benötigt. In dieser Methode ist der all-gemeine Ablauf der Berechnungen festgelegt und die virtuellen Funktionen werden hier aufge-rufen.

90

10 Anhang

Dazu ist folgendes zu beachten:

• Die Funktionen compute, setName(string name) (Namensgebung, z.B. 2DNetz) undder Konstruktor und Destruktor sind als public deklariert. Dies sind also die einzigenFunktionen die vom Anwendungsprogrammierer außerhalb von GENERAL aufgerufenwerden können.

• Alle als pure virtual und protected deklarierten Methoden müssen von den abgelei-teten Klassen überschrieben werden, da sich in der Basisklasse Adjustment keine Imple-mentation für diese befindet.

• Alle Methoden die als virtual und protected deklariert wurden, können von den ab-geleiteten Klassen überschrieben werden. Diese Funktionen werden als hook oder Ein-schubmethoden bezeichnet.

• Die als private deklarierten Methoden der Klasse Adjustment beinhalten die für alleAnsätze gleich bleibenden Berechnungsschritte.

Im Folgenden wird der Ablauf der Template-Methode compute() tabellarisch aufgelistet.

Nr. Methode Zugriff Aufgabe

GHM GMM PCM

1 createLfdNrUndDatum() private für alle

2 createTopoFehler() private Ansätze gleich

3 - - Matrizendimensionierung

4 setStochasticModel() private Qll und P erstellen

Beginn der Iterationsschleife: do...

5 - - Matrizen löschen

6 setSLEMatrices() protected und Bereitstellung von

pure virtual A, B, C, w, c A, C, ∆l, c B, w

7 setSNE() protected und Erstellung des

pure virtual Normalgleichungssystems - für alle

Ansätze unterschiedlich

8 border_N() private falls nötig, Normalgleichungsmatrix rändern

9 solveSNE() private Normalgleichungssystem lösen -

10 calculate_k() protected und virtual, Korrelaten default: Korrelaten

hook berechnen mache nichts berechnen

11 calculate_v() protected und virtual, default: überschrieben: default

hook v = Qll · B · k v = A · ∆x − ∆l

12 updateObservations() private Beobachtungen aufdatieren

13 updateUnknowns() private falls nötig, Beobachtungen aufdatieren

14 testLinearization() private Linearisierung testen


91

10 Anhang

Nr. Methode Zugriff Aufgabe

GHM GMM PCM

...(while(!test.ok()) && iteration<100) - Ende der Schleife

15 calculate_vtPv() private vT Pv berechnen

16 calculate_s02() private s20 berechnen

17 calculate_Qxx() private Qxx berechnen -

18 calculate_Qkk() protected und virtual, Qkk - Qkk

hook berechnen berechnen

19 calculate_Qvv() protected und virtual, default:Qvv = überschrieben: -

hook QllBQkkBT Qll Qvv = Qll − Qll

20 saveStatisticProperties() private statistische Größen speichern

21 generateResultFiles() private schreibe Ergebnisdateien

Tabelle 10.1: schematischer Berechnungsablauf

Entsprechend den drei Ansätzen sind in setSLEMatrices() unterschiedliche Matrizen be-reitzustellen1. Für diese Aufgabe ist jeweils ein Builder implementiert, welcher in der jeweiligenAusgleichungsklasse instanziert ist. Die Builder sind von der Interface-Klasse IVisitor abge-leitet, da hier auf die Elemente zugegriffen werden muss (Besucher-Muster). Diese Interface-Klasse ist in allen AdjustmentElement-Objekten (Beobachtungen, Unbekannte, Gleichungsob-jekte,..) bekannt. Jedes Objekt akzeptiert (durch die Funktion accept(..)) die von IVisitorabgeleiteten Implementierungen und führt operateOn(pAE:IAdjustmentElement*) aus. DasArgument pAE:IAdjustmentElement* gibt den Typ des AdjustmentElement-Objekts an, wel-ches besucht werden soll. Durch SetMatrixPointer(...) werden Zeiger auf die Matrizen in

+operateOn(in pAE : IAdjustmentElement*)

IVisitor

Abbildung 10.4: Die Struktur der Builder

1C und c sind die Ränderungsmatrix für die Normalgleichungsmatrix bzw. der Erweiterungsvektor für dierechte Seite.

92

10 Anhang

Adjustment bereit gestellt und in operateOn(...) werden diese Matrizen dann gefüllt. EineErweiterung um einen neuen Ausgleichungsansatz erfordert also auch einen neuen Builder.

10.4 Der bisherige Einsatz von AD in GENERAL

Für die Linearisierung der Beobachtungs-, bzw Verbesserungsgleichungen mittels Taylorap-proximation erster Ordnung, werden die partiellen Ableitungen für die A-, B- und C-Matrixbenötigt. A enthält die partiellen Ableitungen des funktionalen Zusammenhangs nach denUnbekannten, B nach den Beobachtungen und C die Ableitungen der zusäzlich eingeführtenRestriktionsgleichungen nach den Unbekannten. Für die Berechnung dieser Ableitungen wirdAD verwendet.

Entsprechend dem Besuchermuster wird in Berechnungsschritt 6 (setSLEMatrices()) eineaccept-Funktion des Collectors aufgerufen, und eine Referenz auf den Builder übergeben.Beim GMM werden die Matrizen A, C und die Vektoren ∆l und c benötigt.

1 void Adjustment_GMM::setSLEMatrices()2 3 cout<<"\tGenerate SLE-Matrices for GMM-Adjustment ... ";4

5 // Adressen der Matrizen in compute() übergeben6 ACBuilder.SetMatrixPointer(&A, &C, &dl, &c);7

8 // accept-Methode aufrufen9 collector.acceptToEquations(&ACBuilder);

10

Die Funktion acceptToEquations ruft dann operateOn auf, wobei durch den Parameter&ACBuilder entschieden wird, welche Funktion der Visitor-Struktur ausgeführt wird.

1 void AdjustmentElementCollector::acceptToEquations(IVisitor* pV)2 3 // für alle Gleichungen:4 for(iEquation_=equations_.begin();iEquation_!=equations_.end();iEquation_++)5 6 // erstelle einen Zeiger auf die Gleichung7 IEquationObject* pEO=(*iEquation_);8

9 // Umformung des Zeigers in Vererbungshierarchie (benachbarte Typen)10 IAdjustmentElement* pAE=dynamic_cast<IAdjustmentElement*>(pEO);11

12 // falls Umformung (zur Laufzeit!) nicht erfolgreich -> Abbruch13 assert(pAE);14

15 pV->operateOn(pAE);16 17 ;

In der Funktion operateOn(pAE) werden schliesslich die Matrizen gefüllt. Dafür muss diejeweilige Gleichung verfügbar sein, weshalb erneut eine Typenumformung erforderlich wird.

93

10 Anhang

IEquationObject* pEO=dynamic_cast<IEquationObject*>(pAE);assert(pEO);

Die Arrays für die Ableitungen und Variablen der jeweiligen Funktion werden mit

double *pAbleitungen=new double[anzahlVariablen];IAdjustmentElement** ppElements=new IAdjustmentElement*[anzahlVariablen];

bereitgestellt, und mit pEO->getPartialArray(&pAbleitungen) erhält man die Ableitungen.In dieser Funktion wird die betreffende mathematische Gleichung, wie sie z.B. in 10.1 imple-mentiert wurde, mit der Zeile

FDouble resultPartial=automaticDiff((FDouble**)(&pVar),Consts);

ausgeführt. Hier wird die in 10.1 angesprochene Überladung des Operators () verwendet,wobei automaticDiff eine Spezielisierung der Schablone für eine Gleichung mit dem TypFDouble ist:

TEquation<FDouble> automaticDiff;

Die partiellen Ableitungen sind dann verfügbar und können in die jeweiligen Matrizen über-tragen werden. Für die Indizes werden die internen SessionIDs der Gleichungen und Variablenverwendet.

10.5 Erweiterung von FADBAD++ durch die Funktion fabs()

Im Zuge der Berechnung der Verbesserungsgleichungen von Richtungswinkeln wird für dieQuadrantenabfrage der Absolutbetrag eines Wertes benötigt. Unter Einbindung der Dateimath.h ist die Funktion fabs() z.B. für Werte vom Typ double verwendbar. In der verwen-deten Version (1.4) der Bibliothek FADBAD++ ist diese Funktion jedoch nicht überladen.Deshalb wurde die Bibliothek um diese Funktion erweitert. Leider weist die Backward-Methodeeine etwas komplexere Klassentruktur auf, so dass die Erweiterung lediglich für den Forward-Modus vorgenommen wurde:

1 template <class T>2 INLINE2 FTypeName<T> fabs(const FTypeName<T>& a)3 4 // Outputvariable c5 FTypeName<T> c(a.v);6 // merke die Anzahl der Ableitungen7 c.touchg(a.gsize);8

9 if(a.v==0.0) cout<<"fabs = 0\n"<<endl;10

11 // partielle Ableitungen kopieren12 c.gradient.insert(a.gradient.begin(),a.gradient.end());13

14 // Iteratoren

94

10 Anhang

15 FTypeName<T>::S_GRADIENT_ITERATOR it=c.gradient.begin();16 FTypeName<T>::S_GRADIENT_ITERATOR it_end=c.gradient.end();17

18 // falls Realteil kleiner Null..19 if(a.v<0.0)20 21 // ..Vorzeichen des Realteils..22 c.v=-a.v;23 // ..und des Infinitesimalteils ändern24 for(;it!=it_end;it++) it->second=-it->second;25 26

27 return c;28

10.6 Entwicklungsumgebung und Rechnermerkmale

Es folgt eine Auflistung der verwendeten Entwicklungsumgebung sowie der Merkmale desRechners mit welchem die Laufzeituntersuchungen durchgeführt wurden.

Rechnermerkmale

Betriebssystem Microsoft Windows XP Professional

Version 5.1.2600 Service Pack 2 Build 2600

Systemmodell Montara-GM

Systemtyp X86-basierter PC

Prozessor x86 Family 6 Model 9 Stepping 5 GenuineIntel 1496 MHz

RAM 512 MB

Entwicklungsumgebung

Microsoft Visual Studio .NET 2003

Version 7.1.3088

Enterprise Edition

Verwendete Produktkomponente: Microsoft Visual C++ 7.1

95

Literaturverzeichnis

[1] Gamma/ Helm/ Johnson/ Vlissides (GoF): Design Patterns - Elements of ReusableObject-Oriented Software; Addison-Wesley Verlag, Boston 1995

[2] Griewank, Andreas: Evaluating Derivatives; SIAM Philadelphia, 2000

[3] Gründig, Lothar: Skript - Grundlagen der Ausgleichungsrechnung; April 2003

[4] Herold/Klar/Klar: C++, UML und Design Patterns; Addison-Wesley Verlag, 2005

[5] Jäger/Müller/Saler/Schwäble: Klassische und robuste Ausgleichungsverfahren;Herbert Wichmann Verlag 2005

[6] K. Madsen, H.B. Nielsen, O. Tingleff:Methods for non-linear least quares problems, 2nd Edition, April 2004

[7] Niemeier, Wolfgang: Ausgleichungsrechnung, de Gruyter 2002;

[8] Pope, Allen J.: Modern Trends in Adjustment calculus; 1974

[9] Rall, L. B.: The Arithmetic of Differentiation;Mathematics Magazine, Dezember 1986

[10] Schwetlick, Hubert: Numerische Lösung nichtlinearer Gleichungen;R. Oldenbourg Verlag München Wien, 1979

[11] Stauning/Bendtsen: FADBAD, a flexible C++ package for automatic differen-tiation; August 1996

[12] Steihaug, Trond: Newton and Halley are one step apart;4th European Workshop on Automatic Differentiation, 7.-8.12.2006, RWTH Aachen

[13] http://www.fadbad.com/fadbad.html, Stand: 2006

[14] http://64.233.183.104/search?q=cache:B27635BPf-MJ:ftp://ftp.math.tu-dresden.de/pub/reports/IOKOMO/IOKOMO-05-97.ps.Z

96

Documents

Diplomarbeit - uni-weimar.de · Lineare Systeme dieser Art können z.B. direkt mit dem Gauß-Jordan-Algorithmus gelöst werden. Die Lösung eines nichtlinearen Gleichungssystems dieser