Das Newton-Raphson-Verfahren (auch Newton-Verfahren) ist eine Methode zur Bestimmung des Schnittpunkts einer Funktion mit der -Achse. Man kann auch sagen, dass es eine Methode ist, um die Lösung von zu finden.
Nehmen wir zum Beispiel an, wir möchten den Wert von finden. Da die Lösung von ist, sollten wir dafür die Lösung von finden1, wobei .
Grundgedanke
Die Aufgabe besteht nun darin, zu finden, das erfüllt. Dazu führen wir die folgenden Schritte aus.
-
Zunächst wird ein Punkt auf der -Achse gewählt.
-
Dann wird die Tangente von an , d. h. an den Punkt , bestimmt.
-
Danach wird der Schnittpunkt der Tangentenlinie mit der -Achse bestimmt. Der Wert von an diesem Punkt wird genannt.
-
In ähnlicher Weise wiederholt man diesen Vorgang, die Tangente an den Punkt zu finden, den Schnittpunkt mit der -Achse zu finden … usw.
Auf diese Weise kommt 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 »« bzw »« aus.
(Lösung) In
-
der Wert von ist , und
-
die Steigung der Tangente von ist .
Gesucht ist also die Gleichung der Geraden, die durch die Punkte
verläuft und deren Steigung
ist
.
Es gibt mehrere Möglichkeiten, dies herauszufinden. Eine davon ist: Im Allgemeinen kann eine Linie mit der Steigung , die durch den Punkt verläuft, als geschrieben werden. Die gesuchte Formel lautet also
Alternativ (und das ist Ihnen wahrscheinlich geläufiger): Wenn der -Achsenabschnitt ist, lautet die zu findende Formel Da sie durch den Punkt verläuft, gilt Daraus ergibt sich . Der zu erhaltende Ausdruck lautet daher
Finden Sie den Schnittpunkt zwischen der oben erhaltenen Tangente und der -Achse.
(Lösung) Der Schnittpunkt dieser Tangente mit der -Achse kann gefunden werden, indem man in die obige Gleichung einsetzt. Man soll nur diese für lösen: Dies ist das gesuchte .
Was sollten wir suchen?
Kehren wir nochmal zum Ausgangspunkt zurück.
Wie wir in Grundgedanke gesehen haben, nähert sich der gewünschten Lösung, wenn .
Das bedeutet, dass wir zunächst den Ausdruck für finden wollen. Wie wir bereits gesehen haben, ist es Für gilt Wenn also gegeben ist, wird bestimmt, und daraus wird bestimmt… usw. Der erste Schritt besteht also darin, zu geben. (Beachten Sie, dass wir davon ausgehen, dass gegeben ist und damit berechnet werden kann.)
Beachten Sie auch, dass die Gleichung der Tangente oben nur notwendig war, um aus 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
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, 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 und
klein genug wird oder, dass der Wert von nahe genug bei 0
liegt.
(Wenn man bedenkt, dass das Newton-Raphson-Verfahren darin besteht,
die Lösung von 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 und so weiter geschrieben haben, möchten Sie die Werte von vielleicht in einem Array speichern. Da jedoch nur notwendig ist, um zu erhalten, ist das alte (nämlich ) unnötig. Mit anderen Worten: Wir brauchen nur das , das unmittelbar davor war.
Im Folgenden verwenden wir als die Variable, die vorherige speichert. Es wird angenommen, dass , schon definiert sind.
-
wird bestimmt (gegeben). Dies sei (das erste) .
-
wird aus gefunden. Das heißt, man berechnet .
-
Es wird festgestellt, ob die Bedingungen für die Beendigung erfüllt sind (Konvergenzprüfung)
-
Wenn noch nicht konvergiert, 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 und zu berechnen.
-
Finden Sie mithilfe dieser Funktionen und .
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 mit dem Newton-Raphson-Verfahren zu finden.
Finden Sie mithilfe dieser Funktion .
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 finden, aber Sie möchten vielleicht für jedes finden.
Ändern Sie also das obige Programm, um für im Allgemeinen zu finden (wobei 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 setzen, erhalten Sie einen negativen Wert ( bzw. ). 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 () 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 , sondern auch , was ein Problem darstellen kann. Für den Fall, dass nicht einfach darstellbar ist, muss man sich darum irgendwie kümmern.
Anmerkung
Oft möchte man den Extremwert einer Funktion finden statt die Lösung von . In diesem Fall sollte man die Lösung von finden. Um das Newton-Raphson-Verfahren auf diese Aufgabe anzuwenden, kann man und wie folgt definieren:
Footnotes:
Wie einige von Ihnen vielleicht schon bemerkt haben, gibt es ein großes Problem. Hierauf wird später noch eingegangen.