Newton-Raphson-Verfahren

Die Aufgabe besteht nun darin, $x$ zu finden, das $f(x) = 0$ erfüllt. Dazu führen wir die folgenden Schritte aus.

1. Zunächst wird ein Punkt $x_0$ auf der $x$-Achse gewählt.

2. Dann wird die Tangente von $f(x)$ an $x = x_0$, d. h. an den Punkt $(x_0, f(x_0))$, bestimmt.

3. Danach wird der Schnittpunkt der Tangentenlinie mit der $x$-Achse bestimmt. Der Wert von $x$ an diesem Punkt wird $x_1$ genannt.

4. In ähnlicher Weise wiederholt man diesen Vorgang, die Tangente an den Punkt zu finden, den Schnittpunkt mit der $x$-Achse zu finden … usw.

Auf diese Weise kommt $x_n$ der gewünschten Lösung immer näher. Probieren Sie die folgende Demonstration aus.

Haben Sie die Grundidee verstanden? Nun müssen wir dies in ein konkretes Programm umsetzen.

Aber vorher lösen Sie die folgenden Aufgaben. Es gibt einige Formeln, aber sie sind sehr einfach (man muss nur die Tangente und den Schnittpunkt finden). Es sieht nur unübersichtlich wegen »$_n$« bzw »$_{n-1}$« aus.

(Lösung) In $x = x_{n-1}$

1. der Wert von $f(x)$ ist $f(x_{n-1})$, und

2. die Steigung der Tangente von $f(x)$ ist $f'(x_{n-1})$.

Gesucht ist also die Gleichung der Geraden, die durch die Punkte $(x_{n-1}, f(x_{n-1}))$ verläuft und deren Steigung $f'(x_{n-1})$ ist .

Es gibt mehrere Möglichkeiten, dies herauszufinden. Eine davon ist: Im Allgemeinen kann eine Linie mit der Steigung $m$, die durch den Punkt $(X, Y)$ verläuft, als $y - Y = m (x - X)$ geschrieben werden. Die gesuchte Formel lautet also \[ y - f(x_{n-1}) = f'(x_{n-1}) (x - x_{n-1}) \; . \]

Alternativ (und das ist Ihnen wahrscheinlich geläufiger): Wenn der $y$-Achsenabschnitt $b$ ist, lautet die zu findende Formel \[ y = f'(x_{n-1}) x + b \; . \] Da sie durch den Punkt $(x_{n-1}, f(x_{n-1}))$ verläuft, gilt \[ f(x_{n-1}) = f'(x_{n-1}) x_{n-1} + b \; . \] Daraus ergibt sich $b = f(x_{n-1}) - f'(x_{n-1}) x_{n-1}$. Der zu erhaltende Ausdruck lautet daher \[ y = f'(x_{n-1}) x + f(x_{n-1}) - f'(x_{n-1}) x_{n-1} \; . \]

(Lösung) Der Schnittpunkt dieser Tangente mit der $x$-Achse kann gefunden werden, indem man $y = 0$ in die obige Gleichung einsetzt. \[ 0 - f(x_{n-1}) = f'(x_{n-1}) (x - x_{n-1}) \] Man soll nur diese für $x$ lösen: \[ x = x_{n-1} - f(x_{n-1}) / f'(x_{n-1}) \] Dies ist das gesuchte $x_n$. \[ x_n = x_{n-1} - f(x_{n-1}) / f'(x_{n-1}) \]

Kehren wir nochmal zum Ausgangspunkt zurück.

Wie wir in Grundgedanke gesehen haben, nähert sich $x_n$ der gewünschten Lösung, wenn $n \rightarrow \infty$.

Das bedeutet, dass wir zunächst den Ausdruck für $x_n$ finden wollen. Wie wir bereits gesehen haben, ist es \[ x_n = x_{n-1} - f(x_{n-1}) / f'(x_{n-1}) \quad (n \ge 1) \; . \] Für $n = 1$ gilt \[ x_1 = x_0 - f(x_0) / f'(x_0) \; . \] Wenn also $x_0$ gegeben ist, wird $x_1$ bestimmt, und daraus wird $x_2$ bestimmt… usw. Der erste Schritt besteht also darin, $x_0$ zu geben. (Beachten Sie, dass wir davon ausgehen, dass $f(x)$ gegeben ist und $f'(x)$ damit berechnet werden kann.)

Beachten Sie auch, dass die Gleichung der Tangente oben nur notwendig war, um $x_n$ aus $x_{n-1}$ zu finden, aber sie ist nicht mehr notwendig, wenn man die obige Gleichung erhält.

Sie haben vielleicht bemerkt, dass es hier ein großes Problem gibt. Mathematisch gesehen können wir es mit einem Wort $n \rightarrow \infty$ sagen, aber wir können es nicht wirklich unendlich oft berechnen.

Ein Algorithmus ist, ein Verfahren zur Durchführung einer bestimmten Berechnung (oder einer Prozedur) . Bislang haben wir uns also mit der Herleitung von Algorithmen beschäftigt.

Damit ein Algorithmus ein Algorithmus ist, ist es natürlich wichtig, dass das Ergebnis der Zielberechnung korrekt ist, aber es ist auch sehr wichtig, dass die Prozedur nach endlich vielen Schritten zu einem Ende kommt (Terminiertheit). In der obigen Diskussion war es notwendig, $n \rightarrow \infty$ zu machen, aber solches Programm endet nie.

Sie werden vielleicht denken, dass ich etwas sehr Offensichtliches sage, aber dieser Punkt ist sehr wichtig, also seien Sie sich dessen bewusst.

Beim Newton-Raphson-Verfahren ist die Frage, wann man aufhören soll, nicht so einfach. Es gibt verschiedene Möglichkeiten dies zu tun, aber im Allgemeinen wird oft angenommen, dass die Differenz zwischen $x_n$ und $x_{n-1}$ klein genug wird oder, dass der Wert von $f(x_n)$ nahe genug bei 0 liegt. (Wenn man bedenkt, dass das Newton-Raphson-Verfahren darin besteht, die Lösung von $f(x) = 0$ zu finden, ist letzteres intuitiver). Das Wort genug ist ebenfalls ein vager Begriff, aber es kommt auf die erforderliche Genauigkeit an.

Sie sollten nun alle benötigte Baumaterialien haben. Versuchen Sie, das Programm zu schreiben.

Es sollte ungefähr wie folgt aussehen (Sie können den Funktionsnamen usw. ändern.):

function f(x) {
  return ...;
}

function df(x) {
  return ...;
}

console.log(f(2), df(2));

Es sollte ungefähr wie folgt aussehen (Sie können den Funktionsnamen usw. ändern.):

function newton() {
  // ...
  return ...;
}

let root = newton();
console.log(root);
// or:
// console.log(newton());

Das Newton-Raphson-Verfahren ist eine sehr nützliche Methode, aber sie ist nicht ohne Nachteile.

Oft möchte man den Extremwert einer Funktion $g(x)$ finden statt die Lösung von $f(x) = 0$. In diesem Fall sollte man die Lösung von $g'(x) = 0$ finden. Um das Newton-Raphson-Verfahren auf diese Aufgabe anzuwenden, kann man $f(x)$ und $f'(x)$ wie folgt definieren: $$\begin{align*} f(x) & = g'(x) \\ f'(x) & = g''(x) \end{align*}$$