Direkt zum Inhalt

Lexikon der Mathematik: Gauß-Newton-Methode

Verfahren zur Lösung eines überbestimmten Systems von N nichtlinearen Gleichungen \begin{eqnarray}{f}_{i}({z}_{i};{x}_{1},\ldots,{x}_{n})={y}_{i}\end{eqnarray} zur Bestimmung von n < N Unbekannten x1, x2, …, xn aus N Meßdaten (zk, yk).

Typischerweise kann ein solches Gleichungssystem nicht exakt gelöst werden. Man versucht stattdessen, die x1,…, xn, so zu bestimmen, daß für \begin{eqnarray}\begin{array}{cc}{r}_{i}={f}_{i}({z}_{i};{x}_{1},\ldots,{x}_{n})-{y}_{i}, \end{array}\end{eqnarray} wobei r = (r1,…, rN)T und x = (x1, …, xn)T, der Ausdruck \begin{eqnarray}F(x)={r}^{T}r\end{eqnarray} minimal wird (Methode der kleinsten Quadrate).

Die notwendige Bedingung zur Minimierung der Funktion F ist für j = 1,…, n \begin{eqnarray}\begin{array}{lll}0 & = & \frac{\partial F(x)}{\partial {x}_{j}}\\ & = & \displaystyle \sum _{i=1}^{N}({f}_{i}({z}_{i};{x}_{1},\ldots,{x}_{n})-{y}_{i})\times \frac{\partial {f}_{i}({z}_{i};{x}_{1},\ldots,{x}_{n})}{\partial {x}_{j}},\end{array}\end{eqnarray} ein System von n nichtlinearen Gleichungen für die Unbekannten xj.

Ein solches System kann i. a. nur iterativ gelöst werden. Dazu führt man das Problem durch Linearisierung der Fehlergleichungen (1) auf eine Folge von linearen Ausgleichsproblemen zurück.

Ausgehend von einem Startvektor \({x}^{(0)}\space =\space {({x}_{1}^{(0)},\ldots,\space {x}_{n}^{(0)})}^{T}\) bestimmt man weitere Näherungslösungen x(1), x(2),… wie folgt: Für x(i) berechne man die Lösung s(i) des linearen Ausgleichsproblems \begin{eqnarray}\mathop{\min }\limits_{s\in {{\mathbb{R}}}^{N}}{\Vert r({x}^{(i)})-Df({x}^{(i)})s\Vert }_{2}^{2}\end{eqnarray} mit der Fundamentalmatrix \begin{eqnarray}Df(x)=\left(\begin{array}{ccc}\frac{\partial {f}_{1}}{\partial {x}_{1}}(x) & \cdots & \frac{\partial {f}_{1}}{\partial {x}_{n}}(x)\\ \vdots & & \vdots \\ \frac{\partial {f}_{N}}{\partial {x}_{1}}(x) & \cdots & \frac{\partial {f}_{N}}{\partial {x}_{n}}(x)\end{array}\right)\end{eqnarray} und \begin{eqnarray}r(x)=\left(\begin{array}{c}{y}_{1}\\ \vdots \\ {y}_{N}\end{array}\right)-\left(\begin{array}{c}{f}_{1}({z}_{1};{x}_{1},\ldots,{x}_{n})\\ \vdots \\ {f}_{N}({z}_{N};{x}_{1},\ldots,{x}_{n})\end{array}\right).\end{eqnarray}

Dies kann, wie unter Methode der kleinsten Quadrate beschrieben, mittels der QR-Zerlegung von Df geschehen. Der Vektor \begin{eqnarray}{x}^{(i+1)}={x}^{(i)}+{2}^{-k}{s}^{(i)},\space \space \space k=0,\space \space 1,\space \space 2,\space \space 3,\ldots,\end{eqnarray} für welchen zum ersten Mal \begin{eqnarray}F({x}^{(i+1)})\lt F({x}^{(i)})\end{eqnarray} gilt, ist dann eine bessere Näherung an die gesuchte Lösung.

Bei ungünstiger Wahl des Startvektors x(0) kann die Konvergenz der Folge x(k zu Beginn der Iteration sehr langsam sein. In der Nähe des Lösungsvektors x ist die Konvergenz annährend quadratisch.

Das Iterationsverfahren bezeichnet man als Gauß-Newton-Methode, da die Korrektur s(i) nach der von Gauß verwendeten Methode der kleinsten Quadrate ermittelt wurde und sich die linearisierten Fehlergleichungen im Sonderfall N = n auf die linearen Gleichungen reduzieren, die in der Methode von Newton zur Lösung von nichtlinearen Gleichungen auftreten.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos