Newtonverfahren

Mit dem Newtonschen Näherungsverfahren (benannt nach Isaac Newton, auch Newton-Raphsonsche Methode) lassen sich Näherungswerte der Gleichung f(x)=0, d.h. Näherungen der Nullstellen dieser Funktion finden. Dazu konstruiert man sich die Fixpunktgleichung wie folgt (keine Vollständige Herleitung eher eine veranschaulichung):

$x-({f'(x)})^{-1}\cdot f(x)=x-\underbrace {({f'(x)})^{-1}\cdot 0} _{=0}=x$ $\Leftrightarrow x=x-{\frac {f(x)}{f'(x)}}:=F(x)\qquad \mathrm {Fixpunktgleichung}$

Man erhält dann folgende Iterationsgleichung:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}:=F(x_{n})\qquad \mathrm {Iterationsgleichung}$

Anfangsbedingungen

Es muss anfänglich ein Näherungswert x₀ bekannt sein. Die Funktion f(x) muß in jedem Punkt der Ausgangsmenge differenzierbar sein. Das heißt für f(x) muß dort die Ableitung f'(x) existieren. Weiterhin muß gelten, daß f'(x) stetig invertierbar ist. Das heißt die Funktion von x₀ darf bis zur anzunähernden Nullstelle keine Extrema oder Sattelpunkte besitzen, da dort die Ableitung f'(x) gegen 0 ginge.

Diese Voraussetzung:

Sei $f:\mathbb {R} \rightarrow \mathbb {R}$ differenzierbar mit $f'(x)\neq 0\quad \forall \quad x\in [x_{1},x_{2}]\qquad (x_{1}\neq x_{2})$

ist zum Beispiel erfüllt, wenn f streng monoton steigend.

Konvergenz

Das Problem beim Newton Verfahren ist, daß es möglicherweise nicht konvergiert. Bei geeigneter Wahl der Startwerte x₀ kann das Newtonsche Verfahren mit quadratischer Konvergenz also mit der Konvergenzordnung 2 konvergieren. Wird das Newtonverfahren beispielsweise zyklisch, tritt keine Konvergenz ein.

Geometrische Deutung

$x_{n+1}$ lässt sich geometrisch als die Nullstelle der Tangente durch den Punkt P($x_{n}$; f($x_{n}$)) deuten:

Bemerkungen

• Schon bei Polynomen gibt es schon oft mehr als eine Nullstelle von f
  

Das heißt der Satz von Banach kann nicht gelten.

• Der Konvergenzbeweis wird anders geführt

Satz von Kantorovich

• Das Verfahren verbessert nur eine Nullstellen Näherung, wenn es konvergiert.

Geometrische Deutung: Einzugsbereiche von Nullstellen.

Abbruchkriterien

Mögliche Abbruchkriterien bezüglich einer Restgröße (zum Beispiel Rechner-Arithmetik) sind:

$\vert f(x_{n})\vert \approx 0\qquad \mathrm {oder} \qquad \vert x_{n+1}-x_{n}\vert \approx 0$

In beiden Fällen kann es vorkommen, dass das Abbruchkriterium zu einem "schlechten" Zeitpunkt erfüllt ist.

Anwendungen

Berechnung der Quadratwurzel

Ein Spezialfall des Newtonschen Näherungsverfahrens ist das Babylonische Wurzelziehen, auch bekannt als Heronverfahren:

Wendet man die Iterationsformel auf die Funktion

$f(x)=x^{2}-a=0$ 

an, dann erhält man die für die Lösung ${\sqrt {a}}$ das Näherungsverfahren

$x_{n+1}:={1 \over 2}(x_{n}+{a \over x_{n}})$
Diese Verfahren konvergiert für jeden beliebigen Anfangswert x₀.

Schnittpunkt zweier Funktionen

Auf ähnliche Weise lässt sich auch der x-Wert des Schnittpunktes zweier Funktionen g(x) und f(x) bestimmen:

Da man die beiden Funktionen zur Lösung des Problems gleichsetzt, lässt sich immer durch Umformung folgende Form, auf die das Newtonsche Näherungsverfahren angewendet werden kann, bestimmen:

$f(x)-g(x)=0$

Weblinks

• Facharbeit über das Newtonsche Näherungsverfahren und die Regula Falsi