1.2.3. Numerische Algorithmen

Newton-Raphson-Verfahren

Eines der einfachsten und auch ältesten Verfahren zur Suche von Nullstellen von Funktionen ist das Newton-Raphson-Verfahren, welches bereits im 17-ten Jahrhundert entwickelt und eingestetzt wurde.

Anwendungen

Das Finden von Nullstellen ist die Grundlage für viele Verfahren, welche z.B. für

• das Lösen von nicht-linearen Gleichungen,

• das Finden von Extremwerten, oder

• Optimierungsverfahren

eingesetzt werden kann.

Grundidee

Die Grundidee beruht auf einer iterativen Suche der Nullstelle \(\sf x_{ns}\) einer stetig differenzierbaren Funktion \(\sf f(x)\) mit Hilfe der ersten Ableitung \(\sf f'(x)\). Durch das Anlegen von Tangenten an die aktuelle Näherung der Nullstelle \(\sf x_i\) kann die nächste Näherung bestimmt werden.

Bei gegebenen Startwert, \(\sf x_0\) für den ersten Iterationsschritt (\(\sf i=0\)), können die folgenden Näherungen durch

\[\sf x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)} \]

berechnet werden. Dabei bestimmt die Wahl des Startwerts, welche der ggf. mehreren Nullstellen gefunden wird.

Beispiel 1

Gegeben ist die Funktion \(\sf f(x) = x^2 - 1\). Die Ableitung ist gegeben durch \(\sf f'(x) = 2x\) und die Nullstellen lauten \(\sf x_{ns} = \{-1, 1\}\).

Bei einem Startwert von \(\sf x_0 = 0.3\) führt zu folgender Iteration:

Startwert x_0 = 0.3000

Iterationsschritt i =  1, x_i = 0.3000
   f(x_i)  = -0.9100
   fp(x_i) = 0.6000
   x_(i+1) = 1.8167

Iterationsschritt i =  2, x_i = 1.8167
   f(x_i)  = 2.3003
   fp(x_i) = 3.6333
   x_(i+1) = 1.1836

Iterationsschritt i =  3, x_i = 1.1836
   f(x_i)  = 0.4008
   fp(x_i) = 2.3671
   x_(i+1) = 1.0142

Iterationsschritt i =  4, x_i = 1.0142
   f(x_i)  = 0.0287
   fp(x_i) = 2.0285
   x_(i+1) = 1.0001


Endergebnis nach 5 Iterationen: x_(ns) = 1.0001

Fig. 1.23 Newton-Verfahren, Beispiel 1

Schritt 0

Schritt 1

Schritt 2

Schritt 3

Schritt 4

Beispiel 2

Gegeben ist die Funktion \(\sf f(x) = \sin(x) - 0.5\) mit der Ableitung \(\sf f'(x) = \cos(x)\).

Startwert x_0 = 1.3000

Iterationsschritt i =  1, x_i = 1.3000
   f(x_i)  = 0.4636
   fp(x_i) = 0.2675
   x_(i+1) = -0.4329

Iterationsschritt i =  2, x_i = -0.4329
   f(x_i)  = -0.9195
   fp(x_i) = 0.9077
   x_(i+1) = 0.5801

Iterationsschritt i =  3, x_i = 0.5801
   f(x_i)  = 0.0481
   fp(x_i) = 0.8364
   x_(i+1) = 0.5226

Iterationsschritt i =  4, x_i = 0.5226
   f(x_i)  = -0.0009
   fp(x_i) = 0.8665
   x_(i+1) = 0.5236


Endergebnis nach 5 Iterationen: x_(ns) = 0.5236

Fig. 1.24 Newton-Verfahren, Beispiel 2

Schritt 0

Schritt 1

Schritt 2

Schritt 3

Schritt 4