Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Lexikon:

Gedämpftes Newton-Verfahren

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Übersicht

Mit dem Newton-Verfahren wird eine Lösung $ x_*$ eines nichtlinearen Gleichungssystems

$\displaystyle f_k(x_1,\ldots,x_n) = 0,\quad k=1,\ldots,n \,, $

ausgehend von einer hinreichend guten Startnäherung $ x$ approximiert. Bei der gedämpften Variante hat ein Iterationsschritt $ x\to y$ die folgende Form.

(i) Durch Lösen des linearen Gleichungssystems

$\displaystyle f^\prime(x) \Delta x = f(x) $

wird ein Inkrement $ \Delta x$ berechnet.

(ii) Man bestimmt einen Dämpfungsparameter $ \lambda\in\{1,1/2,\ldots\}$, so dass

$\displaystyle y = x - \lambda \Delta x $

eine signifikant kleinere Norm von $ f$ als $ x$ liefert.

Als Test zur Bestimmung von $ \lambda$ dient der Vergleich

$\displaystyle \Vert\Delta y\Vert \le (1-\lambda/2)\Vert\Delta x\Vert,\quad f^\prime(x) \Delta y = f(y)\,, $

mit einer geeignet gewählten Norm $ \Vert\ \Vert$. Dabei kann eine bereits bestimmte $ LR-$ oder $ QR$-Zerlegung der Jacobi-Matrix $ f^\prime(x)$ zur schnelleren Berechnung von $ \Delta y$ benutzt werden. Durch die Multiplikation der Funktionswerte mit $ f^\prime(x)^{-1}$ wird der Vergleich affin invariant. Insbesondere ist damit auch das gedämpfte Newton-Verfahren skalierungsunabhängig, was in einem Vergleich der Form $ \Vert f(y)\Vert\le (1-\varrho)\Vert f(x)\Vert$ nicht gewährleistet wäre.

Bei der Implementierung empfiehlt es sich, $ \lambda$ nicht abrupt zu ändern. Man beginnt den Vergleich mit dem zuletzt gewählten Dämpfungsparameter. Entsprechend dem Resultat der Abfrage wird $ \lambda$ halbiert oder verdoppelt, wobei eine Verdopplung dann frühestens im nächsten Iterationsschritt realisiert wird. Ist die Jacobi-Matrix für die approximierte Lösung $ x_*$ regulär, so ist $ \lambda=1$ für Approximationen nahe genug bei $ x_*$. Die quadratische Konvergenz wird somit durch die Dämpfung nicht beeinträchtigt.

Erläuterung:

[Downloads] [Beispiele] [Verweise]
  automatisch erstellt am 19.  8. 2013