Newton-Verfahren

Das Newtonsche Näherungsverfahren dient zur numerischen Lösung von nichtlinearen Gleichungen und Gleichungssystemen.

Anschauliche Beschreibung

Im Falle einer Gleichung mit einer Variablen lassen sich zu einer gegebenen stetig differenzierbaren Funktion \(\displaystyle f: \mathbb{R} \to \mathbb{R} \) Näherungswerte zu Lösungen der Gleichung \(\displaystyle f(x)=0\), d.h. Näherungen der Nullstellen dieser Funktion finden. Die grundlegende Idee dieses Verfahrens ist, die Funktion in einem Ausgangspunkt zu linearisieren, d.h. ihre Tangente zu bestimmen, und die Nullstelle der Tangente als verbesserte Näherung der Nullstelle der Funktion zu verwenden. Die erhaltene Näherung dient als Ausgangspunkt für einen weiteren Verbesserungsschritt. Diese Iteration erfolgt bis die Änderung in der Näherungslösung eine festgesetzte Schranke unterschritten hat.
Newton.png
 
 

Newton-Verfahren für reelle Funktionen einer Veränderlichen

Sei \(\displaystyle f: \mathbb{R} \to \mathbb{R} \) eine stetig differenzierbare reelle Funktion, von der wir eine Stelle \(\displaystyle x_n \) im Definitionsbereich mit "kleinem" Funktionswert kennen. Wir wollen einen Punkt \(\displaystyle x_{n+1} \) nahe \(\displaystyle x_n \) finden, der eine verbesserte Näherung der Nullstelle darstellt. Dazu linearisieren wir die Funktion \(\displaystyle f \) an der Stelle \(\displaystyle x_n \), d.h. wir ersetzen sie durch ihre Tangente im Punkt \(\displaystyle P(x_n\,;\,f(x_n)) \) mit Anstieg \(\displaystyle f\, \prime(x_n) \).
Die Tangente ist durch die Funktion \(\displaystyle t(x_n+h):=f(x_n)+f\, \prime(x_n)h \) gegeben. Setzen wir \(\displaystyle h=x-x_n \) ein, so erhalten wir
\(\displaystyle t(x):=f(x_n)+f\, \prime(x_n) (x-x_n)\).
Wir wählen als \(\displaystyle x_{n+1} \) die einzige Nullstelle dieser linearen Funktion,
\(\displaystyle 0=t(x_{n+1})=f(x_n)+f\, \prime(x_n) (x_{n+1}-x_n) \quad\)\(\displaystyle \Rightarrow\quad x_{n+1}=x_n-f(x_n)/f'(x_n) \).
Wenden wir diese Konstruktion mehrfach an, so erhalten wir aus einer ersten Stelle \(\displaystyle x_0\) eine unendliche Folge von Stellen \(\displaystyle (x_n)_{n\in\mathbb N}\), die durch die Rekursionsvorschrift
\(\displaystyle x_{n+1}:=N_f(x_n):=x_n-\dfrac{f(x_n)}{f\, '(x_n)}\)
definiert ist. Diese Vorschrift wird auch als Newton-Iteration bezeichnet, die Funktion \(\displaystyle N_f \) als Newton-Operator. Die Newton-Iteration ist ein spezieller Fall einer Fixpunktiteration, falls die Folge gegen \(\displaystyle \xi=\lim_{n\to\infty} x_n\,\) konvergiert, so gilt \(\displaystyle \xi=N_f(\xi)=\xi-f(\xi)/f'(\xi)\) und daher \(\displaystyle f(\xi)=0\).
Die Kunst der Anwendung des Newton-Verfahrens besteht darin, geeignete Startwerte \(\displaystyle x_0 \) zu finden. Je mehr über die Funktion \(\displaystyle f \) bekannt ist, desto kleiner lässt sich die notwendige Menge von Startwerten gestalten.
Viele nichtlineare Gleichungen haben mehrere Lösungen, so hat ein Polynom \(\displaystyle n \)-ten Grades bis zu \(\displaystyle n \) Nullstellen. Will man alle Nullstellen in einem bestimmten Bereich \(\displaystyle D \subseteq \R \) ermitteln, so muss zu jeder Nullstelle ein passender Startwert in \(\displaystyle D \) gefunden werden, für den die Newton-Iteration konvergiert.

Abbruchkriterien

Mögliche Abbruchkriterien bezüglich einer Restgröße (zum Beispiel Rechner-Arithmetik) sind:
\(\displaystyle \| f(x_n)\|< \varepsilon_1\qquad\mathrm{oder}\qquad \| x_{n+1}-x_n\|<\varepsilon_2\),
wobei \(\displaystyle \varepsilon_1,\varepsilon_2\in\mathbb{R}^+ \) die Qualität der "Nullstelle" bestimmt. In beiden Fällen kann es vorkommen, dass das Abbruchkriterium zu einem "schlechten" Zeitpunkt erfüllt ist.

Siehe auch

Jede Wissenschaft bedarf der Mathematik, die Mathematik bedarf keiner.

Jakob I. Bernoulli

Copyright- und Lizenzinformationen: Diese Seite basiert dem Artikel Newton-Verfahren aus der frеiеn Enzyklοpädιe Wιkιpеdιa und stеht unter der Dοppellizеnz GNU-Lιzenz für freie Dokumentation und Crеative Commons CC-BY-SA 3.0 Unportеd (Kurzfassung). In der Wιkιpеdιa ist eine Listе dеr Autorеn des Originalartikels verfügbar. Da der Artikel geändert wurde, reicht die Angabe dieser Liste für eine lizenzkonforme Weiternutzung nicht aus!
Anbieterkеnnzeichnung: Mathеpеdιa von Тhοmas Stеιnfеld  • Dοrfplatz 25  •  17237 Blankеnsее  • Tel.: 01734332309 (Vodafone/D2)  •  Email: cο@maτhepedιa.dе