Programmierkurs
für Naturwissenschaftler/innen

Newton-Raphson-Verfahren

Das Newton-Raphson-Verfahren (auch Newton-Verfahren) ist eine Methode zur Bestimmung des Schnittpunkts einer Funktion f(x)f(x) mit der xx-Achse. Man kann auch sagen, dass es eine Methode ist, um die Lösung von f(x)=0f(x) = 0 zu finden.

Nehmen wir zum Beispiel an, wir möchten den Wert von 2\sqrt{2} finden. Da 2\sqrt{2} die Lösung von x2=2 x^2 = 2 ist, sollten wir dafür die Lösung von f(x)=0f(x) = 0 finden1, wobei f(x)=x22f(x) = x^2 - 2.

Grundgedanke

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

  1. Zunächst wird ein Punkt x0x_0 auf der xx-Achse gewählt.

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

  3. Danach wird der Schnittpunkt der Tangentenlinie mit der xx-Achse bestimmt. Der Wert von xx an diesem Punkt wird x1x_1 genannt.

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

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

1230510
Aktualisiere ...

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_n« bzw »n1_{n-1}« aus.

Bestimmen Sie die Gleichung der Tangente von y=f(x)y = f(x) an x=xn1x = x_{n-1}.

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

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

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

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

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

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

Finden Sie den Schnittpunkt xnx_n zwischen der oben erhaltenen Tangente und der xx-Achse.

(Lösung) Der Schnittpunkt dieser Tangente mit der xx-Achse kann gefunden werden, indem man y=0y = 0 in die obige Gleichung einsetzt. 0f(xn1)=f(xn1)(xxn1) 0 - f(x_{n-1}) = f'(x_{n-1}) (x - x_{n-1}) Man soll nur diese für xx lösen: x=xn1f(xn1)/f(xn1) x = x_{n-1} - f(x_{n-1}) / f'(x_{n-1}) Dies ist das gesuchte xnx_n. xn=xn1f(xn1)/f(xn1) 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 xnx_n der gewünschten Lösung, wenn nn \rightarrow \infty.

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

Beachten Sie auch, dass die Gleichung der Tangente oben nur notwendig war, um xnx_n aus xn1x_{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 nn \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, nn \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 xnx_n und xn1x_{n-1} klein genug wird oder, dass der Wert von f(xn)f(x_n) nahe genug bei 0 liegt. (Wenn man bedenkt, dass das Newton-Raphson-Verfahren darin besteht, die Lösung von f(x)=0f(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 xnx_n und so weiter geschrieben haben, möchten Sie die Werte von xx vielleicht in einem Array speichern. Da jedoch nur xn1x_{n-1} notwendig ist, um xnx_n zu erhalten, ist das alte xx (nämlich x0,,xn2x_0, \cdots, x_{n-2}) unnötig. Mit anderen Worten: Wir brauchen nur das xx, das unmittelbar davor war.

Im Folgenden verwenden wir xprevx_\mathrm{prev} als die Variable, die vorherige xx speichert. Es wird angenommen, dass f(x)f(x), f(x)f'(x) schon definiert sind.

  1. x0x_0 wird bestimmt (gegeben). Dies sei (das erste) xprevx_\mathrm{prev}.

  2. xx wird aus xprevx_\mathrm{prev} gefunden. Das heißt, man berechnet x=xprevf(xprev)/f(xprev)x = x_\mathrm{prev} - f(x_\mathrm{prev}) / f'(x_\mathrm{prev}).

  3. Es wird festgestellt, ob die Bedingungen für die Beendigung erfüllt sind (Konvergenzprüfung)

  4. Wenn noch nicht konvergiert, xprevxx_\mathrm{prev} \leftarrow x und die Prozedur kehrt zu Schritt 2 zurück. Andernfalls fährt die Prozedur mit dem nächsten Schritt fort.

  5. Ende

Zeichnen Sie ein Flussdiagramm dieses Algorithmus.

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.

Für f(x)=x22f(x) = x^2 - 2:

  1. Schreiben Sie eine Funktion, um f(x)f(x) und f(x)f'(x) zu berechnen.

  2. Finden Sie mithilfe dieser Funktionen f(2)f(2) und f(2)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 2\sqrt{2} mit dem Newton-Raphson-Verfahren zu finden.

Finden Sie mithilfe dieser Funktion 2\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 2\sqrt{2} finden, aber Sie möchten vielleicht a\sqrt{a} für jedes aa finden.

Ändern Sie also das obige Programm, um a\sqrt{a} für aa im Allgemeinen zu finden (wobei aa 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-1 setzen, erhalten Sie einen negativen Wert (2-\sqrt{2} bzw. a-\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)=x22f(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)f(x), sondern auch f(x)f'(x), was ein Problem darstellen kann. Für den Fall, dass f(x)f'(x) nicht einfach darstellbar ist, muss man sich darum irgendwie kümmern.

Anmerkung

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


Footnotes:


1

Wie einige von Ihnen vielleicht schon bemerkt haben, gibt es ein großes Problem. Hierauf wird später noch eingegangen.