Das Newton-Verfahren

Aus ProgrammingWiki

Wechseln zu: Navigation, Suche

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.

Persönliche Werkzeuge