Das Newton-Verfahren

Autoren: Schneider, Tim; Berger, Veit

Grundlagen

Zur näherungsweisen Bestimmung der Nullstelle einer stetigen Funktion f kann an einer beliebigen Stelle x die Tangente angelegt werden. Für den Anstieg m der Tangente gilt:

m = f'(x) = \frac{f(x)}{x-x_0}

wobei x_0 die Nullstelle der Tangente ist. Diese Nullstelle ist ein erster Näherungswert für die Nullstelle der Funktion f und wird als Startwert für die erneute Anwendung des Verfahrens genutzt. Die Nullstellensuche soll abgebrochen werden, wenn |f(x)| in einer hinreichend kleinen \varepsilon-Umgebung liegt.
Damit kann die Nullstelle der Funktion f mit beliebiger Genauigkeit angenähert werden.

Algorithmus

• Lege einen geeigneten Startwert x fest.

• Falls |f(x)|<\varepsilon ist, dann gib x als Nullstelle zurück.

• Anderenfalls berechne

  x_0 = x - \frac{f(x)}{f'(x)}

  und suche die Nullstelle mit dem neuen Startwert x_0.

Implementation

Zur Bestimmung des Anstiegs m=f'(x) nutzen wir die Prozedur höherer Ordnung ableitung (s. Prozeduren höherer Ordnung (II)).
Natürlich müssen wir auch daran denken, dass die stetige Funktion f u. U. keine reelle Nullstelle besitzt.

Nullstellensuche mit Schaubild

Wir wollen die Nullstellensuche am Schaubild der Funktion demonstrieren und damit das Ergebnis überprüfen. Dazu sammeln wir mit der Prozedur fkt-list die Lambda-Terme der Funktion sowie aller Tangenten, die zur Nullstellensuche benötigt werden. Abschließend wollen wir das numerische Ergebnis sinnvoll runden.

Hinweise:

• Die Prozedur rgb-list liefert eine beliebige Anzahl von aufeinander abgestimmten Farbwerten.
• Die zu untersuchende mathematische Funktion wird als Lambda-Term in einem Interaktionsfenster eingegeben, z.B.:

(lambda (x) (+ (expt x 3) (* -2 (expt x 2)) (* -11 x) 12))

Zurück zum Algorithmusbegriff.