Newtonsches Näherungsverfahren

Man erhält dann folgende Iterationsgleichung :

Inhaltsverzeichnis

1 Anfangsbedingungen 2 Konvergenz 3 Geometrische Deutung 3.1 Bemerkungen 4 Das Verfahren im Mehrdimensionalen 5 Abbruchkriterien 6 Anwendungen 6.1 Berechnung der Quadratwurzel 6.2 Schnittpunkt zweier Funktionen 7 Weblinks

Anfangsbedingungen

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

Diese Voraussetzung:

Sei <math>f:\R\rightarrow\R</math> differenzierbar mit <math>f'(x)\neq0\quad\forall\quad x x_2]\qquad(x_1\neq x_2)</math>

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

Konvergenz

Das Newton Verfahren ist ein sogenanntes konvergentes Verfahren. Konvergenz zu einer Nullstelle ist nur garantiert wenn der Startwert hinreichend nah der Nullstelle liegt. Ist der Startwert zu weg kann alles passieren: das Verfahren divergiert konvergiert trotzdem oder falls die Funktion mehrere hat ist es auch möglich dass das eine andere als die gewünschte Nullstelle findet. geeigneter Wahl des Startwertes x ₀ kann das Newtonsche Verfahren quadratisch also der Konvergenzordnung 2 konvergieren.

Geometrische Deutung

<math>x_{n+1}</math> lässt sich geometrisch als die der Tangente durch den Punkt P(<math>x_n</math>; f(<math>x_n</math>)) deuten:

Bemerkungen

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

Um alle Nullstellen zu finden muss das Newtonverfahren mehrmals mit verschiedenen Startwerten durchführen.

• Der Konvergenzbeweis wird anders geführt.

Satz von Kantorovich

• Jede Gleichung lässt sich in eine bringen.

Das Newtonverfahren ist also zur Lösung fast beliebigen nichtlinearen Gleichungen geeignet.

Das Verfahren im Mehrdimensionalen

Das Newton-Verfahren kann auch benutzt werden Nullstellen von mehrdimensionalen Funktionen <math>f(x):R^{n} \rightarrow R^{n}</math> bestimmen. Ausgangspunkt der Iteration ist wieder die Fixpunktgleichung:

die das Newton-Verfahren inspiriert:

wobei f'(x) die Jacobi-Matrix also die Matrix der partiellen Ableitungen f(x) ist. Da die Berechnung der Inversen Matrix sehr aufwändig ist wird auf die von <math>f'(x)^{-1}</math> verzichtet und statt dessen folgender gewählt:

Statt die Inverse auszurechnen wird also lineares Gleichungssystem gelöst. Häufig kann man hier der Jacobi-Matrix ausnutzen um schnell und effizient einer Lösung zu kommen. Die weiteren Eigenschaften Newton-Verfahrens (lokale quadratische Konvergenz) sind im mehrdimensionalen wie im eindimensionalen Fall.

Abbruchkriterien

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

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

Anwendungen

Berechnung der Quadratwurzel

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

Wendet man die Iterationsformel auf die

 <math>f(x) = x^2 - a =  
  

<math> x_{n+1}:={1 \over 2} (x_n + \over x_n}) </math>
Diese Verfahren konvergiert für jeden beliebigen x ₀ .

Schnittpunkt zweier Funktionen

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

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

<math>f(x) - g(x) = 0</math>

Weblinks

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

Bücher zum Thema Newtonsches Näherungsverfahren

Dieser Artikel von Wikipedia unterliegt der GNU FDL.