Das Newton-Verfahren
Aus ProgrammingWiki
Autoren: Tim Schneider; Veit Berger (2014)
Inhaltsverzeichnis |
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.
