Beispiele zum Newton-Verfahren

Quadratwurzel

Die Quadratwurzel einer Zahl a>0 a>0 sind die Nullstellen der Funktion f(x)=1−a/x2 f(x)=1-a/x^2 . Diese Funktion hat die Ableitung f ′(x)=2a/x3 f\, \prime(x)=2a/x^3 , die Newton-Iteration erfolgt also nach der Vorschrift
xn+1:=Nf(xn)=xn−1−a/xn22a/xn3 x_{n+1}:=N_f(x_n)=x_n-\dfrac{1-a/x_n^2}{2a/x_n^3}=xn−xn32a+xn2=x_n-\dfrac{x_n^3}{2a}+\dfrac{x_n}{2} =xn2(3−xn2a)=\dfrac{x_n}{2}\left(3-\dfrac{x_n^2}{a}\right)
Der Vorteil dieser Vorschrift gegenüber dem Wurzelziehen nach Heron (siehe unten) ist, dass es divisionsfrei ist, sobald einmal der Kehrwert von a a bestimmt wurde. Als Startwert wurde in der Tabelle x0:=(1+a)/2 x_0:=(1+a)/2 gewählt. Die Iterierten wurden an der ersten ungenauen Stelle abgeschnitten. Es ist zu erkennen, dass nach wenigen Schritten die Anzahl gültiger Stellen schnell wächst.
n xn x_n bei a=2a=2 xn x_n bei a=3a=3 xn x_n bei a=5a=5
0 1,5 1{,}5 22 33
1 1,401{,}40 1,61{,}6 1,81{,}8
2 1,41411{,}4141 1,721{,}72 2,12{,}1
3 1,414213551{,}41421355 1,732031{,}73203 2,222{,}22
4 1,414213562373095021{,}41421356237309502 1,73205080741{,}7320508074 2,236012{,}23601
Betrachten wir die Differenz xn+1−ax_{n+1}-\sqrt a zum Grenzwert im (n+1) (n+1)-ten Schritt, so kann mittels der binomischen Formeln die Differenz im n n -ten Schritt zweimal abgespalten werden:
xn+1−a=32xn−xn32a−32a+a32a=(xn−a)⋅(32−xn2+xna+a2a)x_{n+1}-\sqrt a =\dfrac{3}{2}x_n-\dfrac{x_n^3}{2a}-\dfrac{3}{2}\sqrt a+\dfrac{\sqrt{a}^3}{2a} =(x_n-\sqrt a)\cdot\left(\dfrac32-\dfrac{x_n^2+x_n\sqrt a+a}{2a}\right)
=(xn−a)⋅a−xn2+a−xna2a=−(xn−a)2⋅(xn+2a)=(x_n-\sqrt a)\cdot\dfrac{a-x_n^2+a-x_n\sqrt a}{2a}=-(x_n-\sqrt a)^2\cdot(x_n+2\sqrt a)
Nach der Ungleichung vom arithmetischen und geometrischen Mittel gilt 0<a≤1+a20<\sqrt a\le \dfrac{1+a}2, so dass der zweite Faktor sinnvoll durch 3/2(1+a) 3/2(1+a) beschränkt werden kann. Ist die Differenz im n n -ten Schritt eine kleine Zahl, so ist die Differenz im (n+1) (n+1)-ten Schritt proportional zum Quadrat davon, also wesentlich kleiner. So entsteht durch Quadrieren eines Fehlers 10−m10^{-m} eine Fehlerabschätzung proportional zu 10−2m10^{-2m}. Deshalb spricht man davon, dass sich die Anzahl der gültigen Stellen in jedem Schritt der Newton-Iteration in etwa verdoppelt.
 
 

Berechnung der Quadratwurzel nach Heron

Ein Spezialfall des Newtonschen Näherungsverfahrens ist das Babylonische Wurzelziehen, auch bekannt als Heronverfahren nach Heron von Alexandria:
Wendet man die Iterationsformel zur Nullstellenbestimmung auf die Funktion
f(x)=x2−af(x) = x^2 - a
an, so erhält man wegen der Ableitungsfunktion f′(x)=2xf'(x) = 2x für die Lösung a\sqrt{a} das Näherungsverfahren
xn+1:=xn−xn2−a2xn=12(xn+axn) x_{n+1}:=x_n-\dfrac{x_n^2 - a}{2x_n}=\dfrac12 \left(x_n + \dfrac{a}{x_n}\right) .
Dieses Verfahren konvergiert für jedes a≥0a\geq0 und für jeden beliebigen Anfangswert x0≠0x_0 \neq 0.

Schnittpunkt zweier Funktionen

Auf ähnliche Weise lässt sich auch der x x -Wert des Schnittpunktes zweier Funktionen g(x) g(x) und f(x) 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)=0f(x) - g(x) = 0

Trigonometrische Funktion

Gesucht sei die positive Lösung eines Problems x x wobei cos⁡(x)=x3 \cos(x) = x^3 . Das Problem kann umformuliert werden als f(x)=cos⁡(x)−x3 f(x) = \cos(x) - x^3 .
Wir haben nun f′(x)=−sin⁡(x)−3x2 f'(x) = -\sin(x) - 3x^2 . Da cos⁡(x)≤1 \cos(x) \leq 1 für alle x x gilt und x3>1 x^3 > 1 für x>1 x>1 , wissen wir, dass die Nullstelle zwischen 0 und 1 liegt. Wir starten die Iteration mit dem Wert x0=0,5 x_0 = 0,5 .
x1=x0−f(x0)f′(x0)=0,5−cos⁡(0,5)−0,53−sin⁡(0,5)−3⋅0,52=1,1121416371x2=x1−f(x1)f′(x1)⋮=0,909672693736x3⋮⋮=0,867263818209x4⋮⋮=0,865477135298x5⋮⋮=0,865474033111x6⋮⋮=0,865474033101x7⋮⋮=0,865474033102\begin{matrix} x_1 & = & x_0 - \dfrac{f(x_0)}{f'(x_0)} & = & 0{,}5 - \dfrac{\cos(0{,}5) - 0{,}5^3}{-\sin(0{,}5) - 3 \cdot 0{,}5^2} & = & 1{,}1121416371 \\ x_2 & = & x_1 - \dfrac{f(x_1)}{f'(x_1)} & & \vdots & = & 0{,}909672693736 \\ x_3 & & \vdots & & \vdots & = & 0{,}867263818209 \\ x_4 & & \vdots & & \vdots & = & 0{,}865477135298 \\ x_5 & & \vdots & & \vdots & = & 0{,}865474033111 \\ x_6 & & \vdots & & \vdots & = & 0{,}865474033101 \\ x_7 & & \vdots & & \vdots & = & 0{,}865474033102 \end{matrix}
Damit haben wir die ersten zwölf Ziffern der Nullstelle.

Die beste von allen Sprachen der Welt ist eine künstliche Sprache, eine ziemlich gedrängte Sprache, die Sprache der Mathematik.

N. I. Lobatschewski

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е
Datenschutzerklärung

 

Nichtlineare Gleichungssysteme