8.3    Newton-Verfahren

Mit dem Newton-Verfahren können Nullstellen von differenzierbaren Funktionen mit geringem Programmieraufwand numerisch berechnet werden.

In Abbildung 8.4 sehen Sie den Graphen der Funktionsgleichung:

Für diese Funktion soll die Nullstelle (x > 0) berechnet werden.

Abbildung 8.4     Tangente an der Nullstelle

Die Grundidee des Newton-Verfahrens besteht darin, den Schnittpunkt eines Funktionsgraphen mit der x-Achse durch eine Tangente zu approximieren. Dieses Verfahren kann aus der Tangentengleichung hergeleitet werden.

Für die Steigung der Tangente gilt an der Stelle x₀:

Durch Auflösen nach x₁ und mit f(x₁) = 0 erhält man:

Daraus ergibt sich die rekursive Berechnungsvorschrift für eine Nullstelle:

An der Iterationsformel erkennt man, dass ƒ'(x_n) nicht 0 werden darf. In diesem Fall verläuft die Tangente des Funktionsgraphen parallel zur x-Achse, und das Verfahren würde nicht konvergieren. Das Newton-Verfahren konvergiert also nur für ƒ'(x_n) ≠ 0.

Der A-posteriori-Fehler kann mit

geschätzt werden [Richter: 195f.]. Wobei für m und M gilt:

Das Newton-Verfahren benötigt noch die 1. Ableitung der Nullstellengleichung:

Ein sinnvoller Startwert liegt in der Nähe der Nullstelle. Er wird entweder aus der Skizze des Funktionsgraphen oder aus einer Wertetabelle ermittelt. Wenn der Funktionswert innerhalb eines Intervalls [x₀₁,x₀₂] sein Vorzeichen wechselt, dann sind x₀₁ oder x₀₂ sinnvolle Startwerte. Aus den vorherigen Berechnungen ist bekannt, dass die Nullstelle in der Nähe von 18 liegen muss.

Mit Listing 8.3 können Sie die Nullstelle der Testfunktionen für eine vorgegebene Genauigkeit mit dem Newton-Verfahren berechnen. Den Startwert können Sie in Zeile 13 ändern.

01  #03_newton.py
02  from math import *
03  #Funktionsdefinition
04  def f(x):
05      return exp(x/4)-5*x-1
06  #1. Ableitung
07  def diff1(x):
08      return exp(x/4)/4-5
09  #2. Ableitung
10  def diff2(x):
11      return exp(x/4)/16
12  #Hauptprogramm
13  x=18   #Startwert
14  eps=1e-6
15  a,b=17,19
16  xa=f(x)
17  n=0
18  while abs(xa-x)>eps:
19      xa=x
20      x = x - f(x)/diff1(x)
21      n=n+1
22      print(n,"",x)
23  from scipy.optimize import newton
24  print("  ",newton(f,18),"scipy")
25  #Fehlerabschätzung
26  m=min(abs(diff1(a)),abs(diff1(b)))
27  M=max(abs(diff2(a)),abs(diff2(b)))
28  E = 0.5*M*abs(xa-x)**2/m
29  print("A-posteriori-Fehlerabschätzung",E)

Listing 8.3     Newton-Verfahren

Ausgabe

1  18.056150183889116
2  18.055650212082014
3  18.05565017206474
   18.05565017206474 scipy
A-posteriori-Fehlerabschätzung 4.617630125111607e-16

Analyse

Zeile 13 legt den Startwert fest. Die Hilfsvariable xa in Zeile 16 hat die Aufgabe, zusammen mit dem aktuellen Wert von x (Zeile 20) ein Abbruchkriterium für die while-Schleife bereitzustellen (Zeile 18). Solange der Betrag der Differenz aus xa und dem aktuellen Wert von x größer als die Genauigkeitsschranke (Toleranz) eps ist, werden die Anweisungen im Schleifenrumpf ausgeführt. In Zeile 19 wird der Wert von xa bei jedem neuen Schleifendurchlauf aktualisiert.

In Zeile 20 steht die Berechnungsvorschrift des Newton-Verfahrens. Ein Nachteil dieses Verfahrens besteht darin, dass für andere mathematische Funktionen die 1. Ableitung jeweils neu bestimmt werden muss. Sie können die Berechnung der 1. Ableitung vermeiden, indem Sie statt der Ableitung in Zeile 20 den zentralen Differenzenquotienten

x = x - 2*h*f(x)/(f(x+h)-f(x-h))

verwenden. Für die Schrittweite können Sie h=1e-4 wählen. Der zentrale Differenzenquotient wird in Abschnitt 9.3.3 ausführlich besprochen.

Erstaunlich ist, wie schnell das Newton-Verfahren konvergiert. Schon nach drei Iterationen wird der Wert mit der gewünschten Genauigkeit erreicht. Die Konvergenzgeschwindigkeit ist allerdings von der Wahl des Startwertes abhängig. Mit zunehmendem Abstand zwischen der Nullstelle und dem Startwert vergrößert sich auch die Anzahl der Iterationen.

Testen Sie das Programm mit verschiedenen Startwerten, z. B. 16, 17, 18, 19, 20 ..., und beobachten Sie, wie viele Iterationen das Programm benötigt, um die geforderte Genauigkeit zu erreichen. Sie werden feststellen, dass sich die Anzahl der Iterationen verringert, je besser Sie den Startwert der Nullstelle annähern.

Testen Sie das Programm mit dem Startwert 12. Was passiert? Wie können Sie sich diesen Effekt erklären? Was berechnet das Programm, wenn die Startwerte zwischen 0 und 11 liegen? Um eine Antwort auf diese Fragen zu finden, schauen Sie sich noch einmal Abbildung 8.4 an.