Gauß-Newton-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Racine carrée bleue.svg
Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen.

Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

Das Gauß-Newton-Verfahren (nach Carl Friedrich Gauß und Isaac Newton) ist ein numerisches Verfahren zur Lösung nichtlinearer Minimierungsprobleme, die durch Anwendung der Methode der kleinsten Quadrate auf nichtlineare Ausgleichsprobleme entstehen. Das Verfahren ist eine Erweiterung/Vereinfachung des Newton-Verfahrens, bei dem in jedem Schritt die zu minimierende Funktion durch eine quadratische Näherung ersetzt wird, deren Minimum explizit berechnet werden kann. Wegen der speziellen Struktur der zu minimierenden Funktion ("Summe von Fehlerquadraten") benötigt das Gauß-Newton-Verfahren im Gegensatz zum Newton-Verfahren jedoch nicht die zweite Ableitung der Funktion.

Iterationsprinzip[Bearbeiten]

Im Gegensatz zum Newton-Verfahren, welches versucht, sich durch die Minimierung einer Taylor-Approximation der eigentlichen Funktion in jedem Iterationsschritt einem Minimum zu nähern, versucht das Gauß-Newton-Verfahren das Residuum mittels der Methode der kleinsten Quadrate zu minimieren. Auf diese Weise überführt das Verfahren ein nicht-lineares Gleichungssystem in eine Folge linearer Ausgleichsprobleme.

Grundzüge des Verfahrens[Bearbeiten]

Im Folgenden wird angenommen, dass Daten mit folgenden Merkmalen vorliegen:

  • Die Tabelle der Messwerte hat k Zeilen, es wurden also k Messungen durchgeführt
  • Bei jeder Messung wurden n Stellgrößen  \, x_1, ..., x_n vorgegeben und das Ergebnis y gemessen
  • Es gibt eine Modellfunktion  \, f(x_1, ..., x_n) = y , welche den Zusammenhang zwischen  \, x_1, ..., x_n und y beschreibt. Diese Funktion hat p verschiedene Parameter  \, a_1, ..., a_p , die nun so berechnet werden sollen, dass mit der Funktion y möglichst genau aus den  \, x_1, ..., x_n berechnet werden kann. Das besondere an der Funktion ist, dass sie nichtlinear in den Parametern ist.

Es ist dabei nicht notwendig, dass die Anzahl p der Parameter a gleich der Anzahl der Variablen x ist. Sucht man z. B. die Koeffizienten eines kubischen Polynoms, so liegt nur ein x je Datensatz vor, aber beim kubischen Polynom hat jede Potenz einen eigenen Koeffizienten a, so dass (einschließlich des absoluten Gliedes) vier Koeffizienten zu bestimmen wären.

Wenn die Messungen als Tabelle vorliegen, können sie so dargestellt werden:

 \mathbf{x_1}  \mathbf{x_2}  \cdots  \mathbf{x_n}  \mathbf{y}
 \, x_{1,1}  \, x_{1,2}  \cdots  \, x_{1,n}  \, y_1
 \, x_{2,1}  \, x_{2,2}  \cdots  \, x_{2,n}  \, y_2
 \vdots  \vdots  \cdots  \vdots  \vdots
 \, x_{k,1}  \, x_{k,2}  \cdots  \, x_{k,n}  \, y_k

Der Ansatz, die Summe der Fehlerquadrate zu minimieren, liefert:

 \sum_{i=1}^k (f(x_{i,1}, ..., x_{i,n}) - y_i)^2 \rightarrow \min!

Algorithmus[Bearbeiten]

Zur Bestimmung der Parameter  \, a_1, a_2, ..., a_p geht man nach diesem Schema vor:

Vorbereitung[Bearbeiten]

  • Gegeben ist die Funktion  \, f(x_1, ..., x_n) = y mit n Variablen  x_1, ..., x_n \, und p gesuchten Parametern  a_1, ..., a_p \,
\, r = f(x_1, ..., x_n) - y
 \mathbf{r} mit  r_i = f(x_{i,1}, ..., x_{i,n}) - y_i,   i=1..k  \,
  • Berechnung der partiellen Ableitungen der Residuumsfunktion \, r nach jedem Parameter ( a_1, ..., a_p \, ):
 r'_1 = \frac{\part r}{\part a_1}; \quad r'_2 = \frac{\part r}{\part a_2}; \quad ... ; \quad r'_p = \frac{\part r}{\part a_p}
\, r'_{i,j} = \frac{\part r}{\part a_j}(x_{i,1}, ..., x_{i,n})
  • Aufbau der Matrizen für die Iteration:
 \mathbf{D} = \begin{pmatrix} r'_{1,1} & r'_{1,2} & \cdots & r'_{1,p}  \\  r'_{2,1} & r'_{2,2} & \cdots & r'_{2,p}  \\ \vdots & \vdots & \vdots & \vdots \\   r'_{k,1} & r'_{k,2} & \cdots & r'_{k,p} \end{pmatrix}; \qquad \mathbf{r} = \begin{pmatrix} r_1 \\ r_2 \\ \vdots \\ r_k  \end{pmatrix};  \qquad \mathbf{a} = \begin{pmatrix} a_1 \\ a_2 \\ \vdots \\ a_p \end{pmatrix}
Dabei ist \mathbf{D} die Jacobi-Matrix des Residuenvektors \mathbf{r} in Abhängigkeit vom Parametervektor \mathbf{a}.
Für den Aufbau der Matrizen ist Folgendes zu beachten:
    • Die Matrix D und der Spaltenvektor r haben k Zeilen, also für jede Zeile der oben angegebenen Tabelle eine.
    • Der Spaltenvektor a hat p Zeilen, also für jeden Parameter  a_1, ..., a_p \, eine
    • Die Spalten in der Matrix D sind die partiellen Ableitungen nach den Parametern  a_1, ..., a_p \, . Die Reihenfolge der Spalten in D hängt mit der Reihenfolge der Parameter in a zusammen. Steht in Zeile 1 von a der Parameter  a_1 \, , so muss in D die erste Spalte die Ableitungen nach  a_1 \, enthalten. Dementsprechend hat D p Spalten, also für jeden Parameter  a_1, ..., a_p \, eine.
  • Die Anzahl der Variablen n hat keinen Einfluss auf den Aufbau der Matrix D und der beiden Vektoren r, a.
  • Zu Beginn der Iteration müssen Startwerte für die Parameter  a_1, a_2, ..., a_p \, und eine Fehlerschranke  c\ , die größer Null sein muss, festgelegt werden.

Iteration[Bearbeiten]

  • Die Iteration wird mit folgender Matrixgleichung durchgeführt:
 \mathbf{a}_{i+1} = \mathbf{a}_i - (\mathbf{D}^T \cdot \mathbf{D})^{-1} \cdot \mathbf{D}^T \cdot \mathbf{r}
Dabei wird in jedem Schritt der Vektor  \mathbf{a}_i , der die Parameter  a_1, a_2, ..., a_p \, enthält, verbessert.
Die Matrix D wird berechnet, indem man zunächst alle Werte in den k Zeilen der Tabelle in die Funktion  r'_1 \, einsetzt. Das Ergebnis schreibt man untereinander in die Spalte 1 von D. Danach setzt man alle Werte in den k Zeilen der Tabelle in die Funktion  r'_2 \, ein und schreibt sie in Spalte 2 der Matrix D usw.
Um den Vektor r zu berechnen, setzt man alle Werte in den k Zeilen der Tabelle in die Funktion  r_i \, und schreibt die Ergebnisse jeweils untereinander als Vektor r auf.
Für die numerische Berechnung empfiehlt sich eine Aufspaltung der Berechnung, damit die Matrixinversion durch die Lösung eines linearen Gleichungssystems für den unbekannten Lösungsvektor s ersetzt werden kann:
 (\mathbf{D}^T \cdot \mathbf{D}) \cdot \mathbf{s} = \mathbf{D}^T \cdot \mathbf{r}; \qquad \mathbf{a}_{i+1} = \mathbf{a}_i -  \mathbf{s}
Die Vorteile liegen in einer schnelleren Berechnung bei höherer Genauigkeit.
  • Sobald  \mathbf{a}_{i+1} berechnet wurde, müssen auch Matrizen neu berechnet werden, um den nächsten Iterationsschritt vorzubereiten. Um den Rechenaufwand zu verringern, kann auch mehrfach ohne Neuberechnung von s iteriert werden. Dieses Vorgehen wird beim Newtonschen Verfahren häufig empfohlen, reduziert aber die Konvergenzgeschwindigkeit und sollte erst angewendet werden, wenn sich a nur noch wenig ändert.
  • Die Iteration wird abgebrochen, falls || \mathbf{a}_{i+1} - \mathbf{a}_i|| < c , also bei den  a_1, a_2, ..., a_p \, der Betrag der Änderung unterhalb der Fehlerschranke  c\ liegt.

Anmerkungen[Bearbeiten]

  • Die Anzahl der Zeilen in der Tabelle (k) muss stets größer als die Anzahl der Parameter  a_1, a_2, ..., a_p \, sein. Falls die Anzahl der Parameter gleich k ist, bestimmt das Verfahren die Parameter exakt (im Rahmen der Genauigkeit der Iteration), es ist also nicht nur die optimale Lösung im Sinne der Fehlerquadrate. Das System ist unterbestimmt, wenn die Anzahl der Parameter größer als k ist.
  • Um eine konvergente Näherung zu erreichen, sollte man eine grobe Vorstellung über die Größenordnung der Parameter haben. Das Verfahren divergiert, wenn die Startwerte der Parameter  a_1, a_2, ..., a_p \, ungünstig gewählt wurden.
  • Durch Einführung eines Schrittweiteparameters  \gamma lässt sich ein Abstieg, d. h. die Verringerung der Fehlerquadratsumme erzwingen, indem die Funktion an der neuen Stelle für verschiedene  \gamma ausgewertet wird (siehe auch Levenberg-Marquardt-Algorithmus).
  • Je näher die Fehlerschranke  c\ bei Null liegt, umso genauer wird die Lösung; allerdings mit der Nebenwirkung, dass sich die Zahl der Iterationen erhöht.

Unterschied zwischen Gauß-Newton-Verfahren und Newton-Verfahren[Bearbeiten]

Beim Newton-Verfahren werden die Jacobi- und die Hesse-Matrix benutzt, um das Minimum einer nichtlinearen-Funktion (in diesem Fall der Summe der Fehlerquadrate) iterativ zu bestimmen.

Im Gauß-Newton-Verfahren hingegen hat man immer eine Summe von Fehlerquadraten (zwischen Messwerten und Funktionswerten), die iterativ minimiert werden soll. Jede einzelne der Funktionen wird im Gauß-Newton-Schritt durch eine lineare Näherung ersetzt (Taylor-Reihe erster Ordnung). Die Summe der Fehlerquadrate ist damit quadratisch in den Parametern und kann explizit gelöst werden, ohne dass die exakte Hesse-Matrix der Summe der Fehlerquadrate benötigt würde (Voraussetzung für das Newton-Verfahren). Ist der Schritt berechnet, wird (wie beim Newton-Verfahren) der Schritt an der neuen Stelle wiederholt.

Literatur[Bearbeiten]

  • Ralf Pfeifer: Effektive Messauswertung mit der Gauß'schen Fehlerquadratmethode, ISBN 3-89001-251-5

Weblinks[Bearbeiten]

  • www.ArsTechnica.de Excel-Berechnungsbeispiel für den Luft- und Rollwiderstand eines Fahrzeuges mit Ausrollversuchen