![[Ja]](https://interaktiv.chemie.uni-mainz.de/programming/flags/ja.svg)
Das Newton-Raphson-Verfahren (auch Newton-Verfahren) ist eine Methode zur Bestimmung des Schnittpunkts einer Funktion $f(x)$ mit der $x$-Achse. Man kann auch sagen, dass es eine Methode ist, um die Lösung von $f(x) = 0$ zu finden.
Nehmen wir zum Beispiel an, wir möchten den Wert von $\sqrt{2}$ finden. Da $\sqrt{2}$ die Lösung von $$ x^2 = 2 $$ ist, sollten wir dafür die Lösung von $f(x) = 0$ finden1, wobei $f(x) = x^2 - 2$.
Grundgedanke
Die Aufgabe besteht nun darin, $x$ zu finden, das $f(x) = 0$ erfüllt. Dazu führen wir die folgenden Schritte aus.
-
Zunächst wird ein Punkt $x_0$ auf der $x$-Achse gewählt.
-
Dann wird die Tangente von $f(x)$ an $x = x_0$, d. h. an den Punkt $(x_0, f(x_0))$, bestimmt.
-
Danach wird der Schnittpunkt der Tangentenlinie mit der $x$-Achse bestimmt. Der Wert von $x$ an diesem Punkt wird $x_1$ genannt.
-
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.
Mathematische Vorbereitung
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}$
-
der Wert von $f(x)$ ist $f(x_{n-1})$, und
-
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} \; . \]
Finden Sie den Schnittpunkt $x_n$ zwischen der oben erhaltenen Tangente und der $x$-Achse.
(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}) \]
Was sollten wir suchen?
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.
Algorithmus
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.
Algorithmus des Newton-Raphson-Verfahrens
Leiten wir nun den Algorithmus des Newton-Raphson-Verfahrens konkret her. Es geht nur darum, das was wir oben geschrieben haben, so umzuformulieren, dass es zu programmieren ist.
Es gibt jedoch einen Punkt, der zu beachten ist. Da wir $x_n$ und so weiter geschrieben haben, möchten Sie die Werte von $x$ vielleicht in einem Array speichern. Da jedoch nur $x_{n-1}$ notwendig ist, um $x_n$ zu erhalten, ist das alte $x$ (nämlich $x_0, \cdots, x_{n-2}$) unnötig. Mit anderen Worten: Wir brauchen nur das $x$, das unmittelbar davor war.
Im Folgenden verwenden wir $x_\mathrm{prev}$ als die Variable, die vorherige $x$ speichert. Es wird angenommen, dass $f(x)$, $f'(x)$ schon definiert sind.
-
$x_0$ wird bestimmt (gegeben). Dies sei (das erste) $x_\mathrm{prev}$.
-
$x$ wird aus $x_\mathrm{prev}$ gefunden. Das heißt, man berechnet $x = x_\mathrm{prev} - f(x_\mathrm{prev}) / f'(x_\mathrm{prev})$.
-
Es wird festgestellt, ob die Bedingungen für die Beendigung erfüllt sind (Konvergenzprüfung)
-
Wenn noch nicht konvergiert, $x_\mathrm{prev} \leftarrow x$ und die Prozedur kehrt zu Schritt 2 zurück. Andernfalls fährt die Prozedur mit dem nächsten Schritt fort.
-
Ende
Was ist zu tun, wenn keine Konvergenz vorliegt?
Bis jetzt sind wir davon ausgegangen, dass die Konvergenz immer eintritt, aber tatsächlich konvergiert das Newton-Raphson-Verfahren nicht immer. Im schlimmsten Fall wird es also nicht aufhören. In solchen Fällen setzt man sich oft im Voraus eine maximale Anzahl der Iterationen und gibt auf, wenn die Anzahl der Iterationen diese Zahl überschreitet.
Übungen
Sie sollten nun alle benötigte Baumaterialien
haben.
Versuchen Sie, das Programm zu schreiben.
-
Schreiben Sie eine Funktion, um $f(x)$ und $f'(x)$ zu berechnen.
-
Finden Sie mithilfe dieser Funktionen $f(2)$ und $f'(2)$.
Es sollte ungefähr wie folgt aussehen (Sie können den Funktionsnamen usw. ändern.):
def f(x):
...
return ...
def df(x):
...
return ...
print(f(2), df(2))
Schreiben Sie unter Verwendung der oben definierten Funktionen eine Funktion, um $\sqrt{2}$ mit dem Newton-Raphson-Verfahren zu finden.
Finden Sie mithilfe dieser Funktion $\sqrt{2}$.
Es sollte ungefähr wie folgt aussehen (Sie können den Funktionsnamen usw. ändern.):
def newton():
...
return ...
root = newton()
print(root)
# or:
# print(newton())
: Für Fortgeschrittene
Das obige Programm kann nur $\sqrt{2}$ finden, aber Sie möchten vielleicht $\sqrt{a}$ für jedes $a$ finden.
Ändern Sie also das obige Programm, um $\sqrt{a}$ für $a$ im Allgemeinen zu finden (wobei $a$ eine reelle Zahl größer oder gleich 0 ist).
Probleme mit dem Newton-Raphson-Verfahren
Das Newton-Raphson-Verfahren ist eine sehr nützliche Methode, aber sie ist nicht ohne Nachteile.
Konvergenz
Wie bereits erwähnt, konvergiert das Newton-Raphson-Verfahren nicht immer. Dies hängt weitgehend von der Art der Funktion (und den Ausgangswerten) ab.
Wahl der Ausgangswerte
Ein weiterer wichtiger Punkt ist, dass, auch wenn es mehrere Lösungen
gibt, nur eine Lösung gefunden werden kann, und welche das ist, hängt
vom Anfangswert ab.
(Dies ist das große Problem
, das in der ersten Fußnote erwähnt wurde.)
Wenn Sie beispielsweise in dem oberen Programm den Anfangswert auf $-1$ setzen, erhalten Sie einen negativen Wert ($-\sqrt{2}$ bzw. $-\sqrt{a}$). Das ist zwar eine von der richtigen Lösungen, aber es ist nicht die, die wir haben wollten.
Im Fall der Quadratwurzeln sind die Eigenschaften der Funktion ($f(x) = x^2 - 2$) gut bekannt, so dass wir sehen können, dass wir eine positive Lösung erhalten, wenn wir den Anfangswert als positiv annehmen.
Bei allgemeinen Funktionen ist die Sache jedoch nicht so einfach. Wenn die Anzahl der Lösungen nicht bekannt ist, wird alles noch komplizierter. Das Newton-Raphson-Verfahren sagt uns nicht, wie viele Lösungen die Funktion hat. Wenn die Anzahl der Lösungen unbekannt ist, ist es daher notwendig, beispielsweise verschiedene Anfangswerte auszuprobieren.
Im Allgemeinen ist es notwendig, einen Ausgangspunkt zu wählen, der nahe genug an der Lösung liegt.
Differenzierungskoeffizienten sind erforderlich
Für die Anwendung des Newton-Raphson-Verfahrens benötigen wir nicht nur $f(x)$, sondern auch $f'(x)$, was ein Problem darstellen kann. Für den Fall, dass $f'(x)$ nicht einfach darstellbar ist, muss man sich darum irgendwie kümmern.
Anmerkung
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*}$$
Wie einige von Ihnen vielleicht schon bemerkt haben, gibt es ein großes Problem. Hierauf wird später noch eingegangen.