Numerische Berechnung von Nullstellen
Lokalisieren
Betrachtet wird das Problem, einen reellen Wert x
zu finden, für den die Gleichung
f(x) = 0
erfüllt ist. Dafür muss zunächst mindestens ein Wert
x0 "in der Nähe der
gesuchten Nullstelle" bekannt sein. Viel besser ist es, wenn ein Bereich
x0 ≤ x ≤ x1
angegeben werden kann, in dem eine Nullstelle liegt. Strategien für
dieses so genannte
"Lokalisieren" sind zum Beispiel:
- Man
kann auf der Basis des zu behandelnden Problems
eine Nullstelle in einem bestimmten Bereich oder in der
Nähe eines bestimmten Wertes vermuten, zum Beispiel:
"Gleichgewicht kann sich nur einstellen, wenn das System etwa
diese Lage einnimmt."
- Die grafische Darstellung der Funktion
y = f(x)
liefert eigentlich immer Aussagen über die ungefähre Lage
der Nullstellen.
- Die Berechnung einer Wertetabelle
y = f(x)
für den interessierenden
Bereich mit nicht zu großer Schrittweite liefert mit dem
Vorzeichenwechsel der y-Werte
ein Intervall, in dem garantiert (mindestens) eine
Nullstelle liegt.
Numerische Berechnung
Die Strategien gleichen sich in folgender Eigenschaft: Aus einer
oder mehreren Anfangsnäherungen wird eine möglichst bessere
Näherung der Nullstelle berechnet. Diese ersetzt dann eine der
Anfangsnäherungen, und der Prozess wird wiederholt, bis sich
die Näherungswerte zweier Schritte nur noch um weniger als
einen vorgegebenen tolerierten Fehler unterscheiden.
- Das Verfahren von NEWTON
basiert auf der Idee, die (in der Skizze
rechts rot gezeichnete) Funktion
y = f(x)
in der Umgebung einer Näherungslösung
xi ; yi
zu linearisieren (Funktion wird durch die blau gezeichnete Tangente an diesen
Punkt ersetzt). Für den Anstiegswinkel der Tangente
tan α = y'(xi) = yi'
liest man aus der Sizze ab:
Die Formel wird nach xi+1
umgestellt und liefert dann den verbesserten
Nach Berechnung des zugehörigen Funktionswertes
yi+1 = f(xi+1)
folgt der nächste Newton-Schritt usw.
- REGULA FALSI: Wenn die
für das Newton-Verfahren zu
bildende Ableitung y' schwierig
oder gegebenenfalls gar nicht zu erzeugen ist, kann diese
auch numerisch genähert werden. Dafür werden zwei
(nah beieinander liegende) Näherungswerte benötigt (Start mit
x0 und
x1, dann
xi−1 und
xi und den jeweils zugehörigen
Funktionswerten). Die Ableitung
yi' kann damit so
genähert werden:
Diese Formel wird in die "Newton-Formel" eingesetzt, und man erhält die
Diese Formel kann für zwei unterschiedliche Strategien genutzt werden:
-
REGULA FALSI (1.Form):
Man geht exakt nach der Strategie des Newton-Verfahrens vor
und streicht den "jeweils ältesten" Näherungswert,
setzt also die Rechnung nach Berechnung von
xi+1
nach der Regula-Falsi-Formel mit den beiden Werten
xi und
xi+1 fort.
- REGULA FALSI (2.Form, "Lineares Eingabeln"):
Voraussetzung sind zwei Anfangsnäherungen
x0 und
x1, deren zugehörige
Funktionswerte
y0 und
y1 unterschiedliche Vorzeichen
haben. Nach Berechnung von
xi+1
nach der Regula-Falsi-Formel und
yi+1
sortiert man jeweils den "alten Wert"
aus, dessen y-Wert
das gleiche Vorzeichen wie
yi+1 hat,
so dass auch für die weitere Rechnung die gesuchte
Nullstelle immer zwischen den beiden Näherungen liegt.
- Sukzessive Intervallhalbierung:
Voraussetzung sind (wie bei der Regula falsi, 2. Form)
zwei Anfangsnäherungen
x0 und
x1, deren zugehörige
Funktionswerte
y0 und
y1 unterschiedliche Vorzeichen
haben. Auch die Strategie ist exakt das oben beschriebene
"Eingabeln", nur die Formel für die Berechnung
des verbesserten Näherungswertes ist einfacher, entspricht
schlicht einer
Konvergenz
Die beiden folgenden Aussagen haben zwar nur "qualitativen" Charakter,
sind aber ausreichend, weil die numerische Nullstellen-Berechnung
wohl immer dem Computer übertragen wird:
- Das
Newton-Verfahren
konvergiert im Allgemeinen am schnellsten, aber die
erforderliche Ableitung y'
ist eine in der Regel lästige Voraussetzung.
Dieser Nachteil wird durch die
Regula falsi (1. Form) behoben.
Beide Verfahren konvergieren aber nicht garantiert,
es kann durchaus zum "Abwandern" von der
gesuchten Nullstelle kommen.
- Die "Eingabel-Verfahren" (Lineares Eingabeln
und Intervallhalbierung) konvergieren
langsamer, aber garantiert.
Verfahrensauswahl, Abbruchkriterien
- Bei der
"Handrechnung" kann man auf das "Abwandern" (Gefahr
zum Beispiel beim Newton-Verfahren) sofort reagieren
(aber wer rechnet schon noch "von Hand"?). Bei der
Computerrechnung ist die Konvergenzgeschwindigkeit
in der Regel ohnehin kein Problem, deshalb sollten unbedingt
die Verfahren mit garantierter Konvergenz ("Eingabeln")
verwendet werden.
- Das "Lineare Eingabeln" liefert wegen der "Wichtung" der
y-Werte im Allgemeinen die bessere
neue Näherung als die Intervallhalbierung. Häufig aber
bleibt ein "sehr schlechter Wert" sehr lange in der Rechnung,
was die Konvergenzgeschwindigkeit negativ beeinflusst.
Die nebenstehende Skizze zeigt diese Situation:
Mit den beiden Anfangswerten
x0 und
x1 wird
x2 berechnet,
x0 fällt heraus
(gleiches Vorzeichen wie
x2), und mit
x1 und
x2 wird
x3 berechnet, und bei
diesem Schritt und den nachfolgenden Schritten bleibt immer
die sehr schlechte Anfangsnäherung
x1 in der Rechnung.
Dieser Effekt tritt bei der Intervallhalbierung nicht auf.
Fazit: Aus "strategischen Gründen"
ist die "Sukzessive Intervallhalbierung" für die
numerische Berechnung einer Nullstelle mit dem Computer
das günstigste Verfahren.
Ein iteratives Verfahren endet, wenn die vorzugebende Genauigkeit
des Ergebnisses erreicht ist. Zwei Kriterien bieten sich an, bei deren
Erfüllung der in einem Schritt erreichte Wert
xi+1 als
Nullstelle in dem Sinne akzeptiert wird, dass
y = f(xi+1) = 0
zufriedenstellend erfüllt ist. Man beachte, dass bei der
Computer-Rechnung praktisch nie eine exakte Null erzeugt
wird. Empfehlenswert sind folgende
Abbruchkriterien:
- Das Ergebnis
xi+1
eines Iterationsschrittes liefert einen Funktionswert
yi+1 = f(xi+1),
dessen Absolutwert nicht mehr größer als eine vorgegebene Schranke
εy ist:
|yi+1| ≤ εy .
- Die Ergebnisse zweier aufeinander folgender Iterationsschritte
xi und
xi+1
unterscheiden sich nur noch unwesentlich voneinander:
|xi+1 − xi| ≤ εx .
Im Allgemeinen sollte man dem zweiten Kriterium den Vorzug geben,
weil damit für das gesuchte Ergebnis die gewünschte Genauigkeit
gefordert wird.
Das Programm
"Funktionen analysieren",
das man unter
"TM-interaktiv"
findet (kein Download einer Software erforderlich, Lösungen direkt
im Browser erzeugen), realisiert neben der grafischen Darstellung
von Funktionen u. a. auch die Nullstellenberechnung nach den
hier gegebenen Empfehlungen: Ein Bereich wird mit einer
vorzugebenen Schrittweite gescannt, bei Vorzeichenwechsel der
Funktionswerte wird eine Nullstelle vermutet und mit Hilfe
der sukzessiven Intervallhalbierung berechnet.
Mehrfache Nullstellen, Polstellen
Die nebenstehende Grafik der Funktion
y = x tan x
verdeutlicht zwei Probleme, die bei der numerischen Berechnung
von Nullstellen auftauchen können:
- Eine
"Doppelte Nullstelle"
(hier bei x = 0)
ist dadurch gekennzeichnet, dass die Funktion keinen
Nulldurchgang (mit unterschiedlichen Vorzeichen der
Funktionswerte "links und rechts" von der Nullstelle)
hat. Dies führt sowohl zu einem Problem beim Lokalisieren
(beim "Scannen" eines Bereichs wird diese Nullstelle
nicht gefunden) als auch bei der Berechnung
verbesserter Werte (bei der Newtonformel und der
Regula falsi nähert sich der Nenner dem Wert 0,
bei den "Eingabel-Verfahren" haben immer alle
Näherungswerte das gleiche Vorzeichen).
- Bei einer
"Ungeraden Polstelle"
(hier bei x = −π/2
und x = π/2)
wird beim "Scannen" des Bereichs ein Vorzeichenwechsel entdeckt,
der auf eine Nullstelle schließen lässt, beim Verbessern der
Näherung werden die Beträge der Funktionswerte aber immer größer.
Die Strategien, die die genannten Probleme vermeiden, werden
auf der Seite
"Mehrfach-Nullstellen und Polstellen"
beschrieben. Die Berechnung der Nullstellen für die Funktion
y = x tan x
findet man als Beispiel 1
des Programms "Funktionen analysieren"
unter
TM-interaktiv.