Ing Mathematik: Numerisches Lösen nichtlinearer Gleichungen

Zurück zu Numerisches Lösen von linearen Gleichungssystemen |

Dieser Abschnitt ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib den Autoren Zeit, den Inhalt anzupassen!

Nullstellenprobleme

Nullstellen (oder Wurzeln) einer Funktion sind diejenigen Punkte, welche die x-Achse berühren oder schneiden (y=0). Wichtig sind insbesondere die Fragen

existieren Nullstellen,
in welchem Bereich liegen sie und
wieviele Nullstellen gibt es?

Zwischenwertsatz

Eine stetige Funktion $f:[a,b]\rightarrow \mathbb {R}$ nimmt jeden Wert $s$ zwischen $f(a)$ und $f(b)$ an. Mit $s=0$ ist der Zwischenwertsatz für die Lösung von Nullstellenproblemen wichtig. Man nennt ihn dann auch Nullstellensatz (von Bolzano). Er besagt dann: Haben $f(a)$ und $f(b)$ verschiedene Vorzeichen, so existiert mindestens eine Nullstelle von $f$ im Intervall $(a,b)$ .

Siehe zu diesem Thema insbesondere Zwischenwertsatz.

Bisektion

Das Bisektions- oder Intervallhalbierungsverfahren kann benutzt werden, um Nullstellen grob zu bestimmen. Es ist bei Weitem nicht das schnellste Verfahren um Nullstellen genau zu bestimmen. Allerdings konvergieren die schnelleren Verfahren nicht immer und das Bisektionsverfahren kann hier ggf. Hilfestellung leisten. Das Bisektionsverfahren läuft wie folgt ab:

Sei $f:[a,b]\rightarrow \mathbb {R}$ mit $f(a)\cdot f(b)<0$ stetig.

$[a_{0},b_{0}]=[a,b]$

$[a_{i+1},b_{i+1}]={\begin{cases}{\begin{bmatrix}a_{i},{\frac {a_{i}+b_{i}}{2}}\end{bmatrix}}&{\text{wenn}}\quad f{\begin{pmatrix}{\frac {a_{i}+b_{i}}{2}}\end{pmatrix}}\cdot f(a_{i})\leq 0\\{\begin{bmatrix}{\frac {a_{i}+b_{i}}{2}},b_{i}\end{bmatrix}}&{\text{sonst}}\end{cases}}$

In jedem der erzeugten Intervalle gibt es eine Nullstelle von $f$ .

Natürlich kann man auch das Bisektionsverfahren durch ein Python-Programm realisieren:

import numpy as np

def funktion(x):
    y = x**3-x+0.3
    return y

def bisektion(a, b, maxit):
    ai = a
    bi = b

    for i in np.arange(0, maxit):
        if funktion((ai+bi)/2.) * funktion(ai) <= 0.:
            bi = (ai+bi) / 2.
        else:
            ai = (ai+bi) / 2.
        print(ai, bi)

bisektion(0., 0.5, 10)

Ausgabe:

0.25 0.5
0.25 0.375
0.3125 0.375
0.3125 0.34375
...
0.3388671875 0.33935546875

Die Zahlenwerte für das Polynom in funktion und das Startintervall wurden aus einem Beispiel in Knorrenschild: Seite 27 entnommen. Die anderen Nullstellen lassen sich genauso bestimmen. Es muss nur das Startintervall entsprechend gesetzt werden.

Auch SciPy bietet eine vorgefertigte Funktion namens scipy.optimize.bisect:

from scipy.optimize import bisect

def funktion(x):
    y = x**3-x+0.3
    return y

print (bisect(funktion, 0., 0.5))

Ausgabe:

0.33893624159645697

Die Nullstellen des Beispiels und den Graphen allgemein zeigt folgender Plot:

Fixpunktiteration

Gleichungen der Form $x=f(x)$ (Fixpunktgleichungen) sollen gelöst werden. In diese Form muss die Gleichung umgeformt werden. Anschließend wird eine Startnäherung $x_{0}$ gewählt und $x_{1}=f(x_{0})$ berechnet und weiter iterativ verfeinert $x_{2}=f(x_{1})$ etc. Unter bestimmten Voraussetzungen nähert sich die Folge $x_{0},x_{1},x_{2}\dots$ einer Lösung des ursprünglichen Problems an.

Für weitere Details siehe z.B. Fixpunktiteration.

Beispiel:

\log x+x-10=0

Fixpunktgleichung:

x_{n+1}=10-\log x_{n}

Startwert:

x_{0}=1

Iterationen:

x_{1}=10

x_{2}=9

x_{3}=9.046

x_{4}=9.0436

x_{5}=9.0437

\dots

Sehr einfach lässt sich das auch mittels Python-Programm rechnen:

import numpy as np

x_i = 1. 

for i in np.arange(0, 10):
    x_i = 10 - np.log10(x_i)
    print(x_i)

Ausgabe:

10.0
9.0
9.045757490560675
...
9.043655967157635

Banachscher Fixpunktsatz

Mit dem banachschen Fixpunktsatz lässt sich die Konvergenz von iterativen Verfahren (wie z.B. dem Newton-Verfahren) zeigen. S. Banach veröffentlichte diesen Satz im Jahr 1922.

Eine Abbildung $f$ heißt kontrahierend, wenn $\|f(x_{1})-f(x_{2})\|\leq K\|x_{1}-x_{2}\|$ mit $0<K<1$ . $K$ heißt auch Kontraktionszahl von $f$ . Daraus folgt: $f$ hat genau einen Fixpunkt. Die Iterationsfolge $(x_{n})$ konvergiert gegen diesen Fixpunkt. Der Startwert sei $x_{0}\in \mathbb {R}$ .

Es gelten die

a-priori-Fehlerabschätzung: $\|x_{n}-x\|\leq {\frac {K^{n}}{1-K}}\|x_{1}-x_{0}\|$

und die

a-posteriori-Fehlerabschätzung: $\|x_{n}-x\|\leq {\frac {K}{1-K}}\|x_{n}-x_{n-1}\|$

mit $n=0,1,\dots$

Siehe auch Fixpunktsatz von Banach. Für die Beweise siehe z.B. Meister: Seite 30ff oder auch Burg, Haf, Wille, Meister: Bd. I, Seite 72ff, Burg, Haf, Wille, Meister: Bd. VI, Seite 20f.

Newton-Verfahren

Steigung der Tangente: $\tan \alpha _{0}=f'(x_{0})$

Mit der Tangente wird ein Dreieck aufgespannt:

$\tan \alpha _{0}=f'(x_{0})={\frac {f(x_{0})}{x_{0}-x_{1}}}$

$x_{0}-x_{1}={\frac {f(x_{0})}{f'(x_{0})}}$

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}$

oder allgemein

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}};\quad n=0,1,\dots$

Obiges Beispiel mit der von SciPy bereitgestellten Funktion newton liefert wieder das gewünschte Ergebnis. Der Solver verwendet je nach gelieferten Informationen das Newton-Raphson-Verfahren (kurz: Newton-Verfahren) oder das später vorgestellte Sekantenverfahren oder das Halley-Verfahren. Details siehe auch [1]. Zum Halley-Verfahren siehe Halley-Verfahren. Es benötigt auch die zweite Ableitung. Wird nur die erste Ableitung angegeben, so kommt das Newton-Verfahren zum Einsatz. Wird keine Ableitung angegeben, so wird das Sekantenverfahren verwendet.

from scipy.optimize import newton

def funktion(x):
    y = x**3 - x + 0.3
    return y

print (newton(funktion, 0.))

Ausgabe:

0.3389362415949407

Heron-Verfahren

Sekantenverfahren

Regula falsi

Gedruckte Werke (auszugsweise)

Burg, Haf, Wille, Meister: Höhere Mathematik für Ingenieure, Band I: Analysis. 9. Auflage, Springer Vieweg, 2011, ISBN 978-3-8348-1218-6
Burg, Haf, Wille, Meister: Partielle Differentialgleichungen und funktionalanalytische Grundlagen, Höhere Mathematik für Ingenieure, Naturwissenschaftler und Mathematiker (Band VI). 5. Auflage, Vieweg+Teubner, 2010, ISBN 978-3-8348-1294-0
Hanke-Bourgeois: Grundlagen der Numerischen Mathematik und des Wissenschaftlichen Rechnens. 3. Aufl., Vieweg+Teubner, 2009, ISBN 978-3-8348-0708-3
Knorrenschild: Numerische Mathematik, Eine beispielorientierte Einführung. 6. Aufl., Hanser, 2017, ISBN 978-3-446-45161-2
Meister: Numerik linearer Gleichungssysteme. 4. Aufl., Vieweg+Teubner, 2011, ISBN 978-3-8348-1550-7

Zurück zu Numerisches Lösen von linearen Gleichungssystemen |

Hoch zu Gesamtinhaltsverzeichnis |