Numerische Näherungsverfahren

NäherungsverfahrenNullstellen von Funktionen bzw. Lösungen von Gleichungen werden mittels Computer sehr oft unter Nutzung verschiedener Näherungs- bzw. Iterationsverfahren ermittelt – insbesondere, wenn für die Gleichung kein exakter analytischer Lösungsalgorithmus existiert.
Dies ist in der Praxis der typische Fall und nicht die stets exakt lösbare Aufgabe wie in der klassischen Schulmathematik.

Die Grundprinzipien dieser Verfahren sind dabei Iteration und Intervallschachtelung, d.h., durch wiederholtes Anwenden einer Berechnungsvorschrift wird der Bereich, in dem die gesuchte Lösung liegt, immer weiter eingeschränkt. Ergibt ein Verfahren bei bestimmten Anfangswerten eine Lösung, so nennt man das Verfahren konvergent, andernfalls divergent. Die Güte eines Verfahrens wird durch seine Konvergenzgeschwindigkeit charakterisiert.

Nach Eingabe einer Funktion unter Funktion y= und eines Anfangsintervalls in Startwert x0= bzw. Endwert x1= ermittelt dieses Unterprogramm auf 18 verschiedene Arten eine in diesem Intervall existierende Nullstelle. Für die Intervallgrenzen können Sie auch Terme der Form PI oder SIN(1) … verwenden.
Über das grafische Vorschaubild können Sie sich schnell über den Verlauf der Funktion informieren. Insbesondere, wenn unterschiedliche Vorzeichen der Funktionswerte an den Stellen x0 und x1 notwendig sind, hilft dies weiter. Das Vorschaubild wird bei der Eingabe der Funktionsgleichung automatisch aktualisiert.

Bisektion
Beim Bisektions- bzw. Intervallhalbierungsverfahren wird der Funktionswert des arithmetischen Mittels xm der aktuellen Intervallgrenzen – zu Beginn x0 und x1 – berechnet.
Die Intervallgrenze, deren Funktionswert dasselbe Vorzeichen wie der Funktionswert f(xm) besitzt, wird durch xm ersetzt, sodass die Länge des Intervalls mit jedem Iterationsschritt halbiert wird. Wiederholt man dies immer wieder, schließt das Intervall immer genauer den gesuchten Wert ein.

Wünscht man z.B., dass die Nullstelle auf vier Dezimalstellen nach dem Komma genau ermittelt wird, bricht man die Iteration ab, wenn beide Intervallgrenzen bis auf die vierte Kommastelle identisch sind. Dieses Verfahren führt bei im Intervall [x0;x1] stetigen Funktionen immer zum Ziel, wenn die Funktionswerte von x0 und x1 unterschiedliche Vorzeichen haben, obgleich mitunter mehrere Schritte erforderlich sind.

Wählen Sie das Verfahren der Trisektion, wird das jeweilige Intervall gedrittelt und entsprechend ausgewertet. Etwas höherer Rechenaufwand garantiert schnellere Konvergenz. Prinzipiell wäre es möglich, die Konvergenz durch Unterteilung in n Intervalle noch stärker zu beschleunigen – wegen des nun höheren Rechenaufwandes empfiehlt es sich jedoch, andere Verfahren zu nutzen.

Beachten Sie: Die Grenzen des Anfangsintervalls müssen Funktionswerte entgegengesetzten Vorzeichens besitzen. Außerdem muss das Argument x1 größer sein als x0. Andernfalls erfolgen diese Fehlermeldungen: x1 größer x0 erforderlich ! bzw. f(x0) und f(x1) müssen verschiedene Vorzeichen haben!

Monte-Carlo-Methode
Unter einer Monte-Carlo-Methode versteht man ein Verfahren, in dem durch einen Zufallsgenerator gewonnene Zahlen genutzt werden. Trotz des zufälligen Charakters der Werte ist es dennoch möglich, die gewünschten Ergebnisse zu erzielen. Die hier umgesetzte Variante unterscheidet sich vom Verfahren der Bisektion dadurch, dass im Intervall von x0 bis x1 zufällig ein neuer Iterationswert ausgewählt wird.
Je nach Art der untersuchten Funktion und mit etwas Glück (ein Monte-Carlo-Verfahren eben!) erhält man selten eine bessere, meist eine ungünstigere Konvergenz als im Bisektionsverfahren.

Nutzt man nicht gleich verteilte Zufallszahlen, sondern setzt für die Bestimmung des neuen Wertes Gauß-normalverteilte Zufallszahlen ein, verbessert sich die Konvergenz dieses Verfahrens. Unter Monte-Carlo-Methode 2 können Sie dieses Verfahren mit normalverteilten Zufallswerten testen.

Regula falsi
Das Näherungsverfahren Regula falsi (lat. „Regel des Falschen“) oder auch Sekantenverfahren ermittelt einen Iterationswert durch Ermittlung des Schnittpunktes der Sekante der Intervallpunkte (x0, f(x0)) und (x1, f(x1)) mit der Abszissenachse. Der neue Wert ergibt sich nach der Gleichung

    \[ x_2=x_0-f(x_0)\frac{x_1-x_0}{f(x_1)-f(x_0)} \]

Regula falsiDie berechnete neue Abszisse ersetzt eine der Intervallgrenzen x0 oder x1, je nach Modifikation der Iterationsgleichung.

Bei der Fixpunktmethode wird x0 festgehalten, im anderen Fall kann auch die untere Grenze verschoben werden. Regula falsi konvergiert im Allgemeinen schneller als das Halbierungsverfahren, versagt jedoch bei einem großen Anstieg der Funktion an der Nullstelle bzw. bei schlecht gewählten Anfangs-Intervallgrenzen.

Im Programm wird die Fixpunktmethode als Regula falsi, die Methode der gleitenden unteren Grenze als Regula falsi 2. Form (Sekantenmethode) bezeichnet. Die zweite Methode ergibt eine wesentlich schnellere Konvergenz. Beide Methoden können genutzt werden.

Beachten Sie bitte Folgendes: Gestattet man, dass auch die untere Grenze verschoben wird, so gibt es dafür prinzipiell zwei Möglichkeiten: Zum einen wandelt man die Iterationsgleichung in die Form

    \[ x_{n+2}=x_n-f(x_n)\frac{x_{n+1}-x_n}{f(x_{n+1})-f(x_n)} \]

um und benutzt stets die zwei zuletzt berechneten Werte zur Ermittlung des neuen Näherungspunktes. In diesem Fall kann es durchaus vorkommen, dass sowohl xn als auch xn+1 auf der gleichen Seite bezüglich der Nullstelle liegen. Dennoch erhält man quadratische Konvergenzgeschwindigkeit. Dieses Verfahren repräsentiert Regula falsi 2. Form.

Wenn man nun glaubt, die Tatsache, dass zwei Ausgangswerte auf der gleichen Seite der Nullstelle liegen, sei ein Nachteil und eine „Verbesserung“ derart durchführt, dass von den aufeinander folgenden Näherungswerten immer derjenige durch den neuen Wert ersetzt wird, der einen Funktionswert mit dem gleichen Vorzeichen liefert, so verliert man erstaunlicherweise wieder die quadratische Konvergenzgeschwindigkeit und erhält nur noch eine lineare Konvergenz. Diese „verbesserte“ Variante können Sie unter Regula falsi 3. Form testen.

Trotz der Tatsache, dass dieses Verfahren wesentlich schlechter konvergiert als Regula falsi 2. Form, ja mitunter keinerlei Geschwindigkeitsgewinn gegenüber der 1. Form bringt, hält sich die „verbesserte“ Variante in der Praxis und selbst in ansonsten hervorragenden Mathematikbüchern hartnäckig. Besonders bedauerlich ist es, dass dieser Fehler auch in den Mathematiklehrbüchern führender Verlage für die Sekundarstufe II auftritt.

Beispiel: Die Funktion y = x³ – 4x² + 5x – 3 besitzt zwischen x = 1 und x = 3 eine Nullstelle. Geben Sie die Intervallgrenzen x(0) = 1.9 und x(1) = 3 ein, so erhalten Sie die Lösung x = 2.4656.
Regula falsi benötigt 81 Iterationen, Regula falsi 2.Form 8 und Regula falsi 3.Form 17.

Wählen Sie das Anfangsintervall [2.2 ; 3], konvergiert die Fixpunktmethode (14 Iterationen) sogar schneller als die „verbesserte“ Methode der 3. Form (16 Iterationen).

Das Illinois-Verfahren ist eine modifizierte Variante von Regula falsi. Wird im Regula falsi-Verfahren eine Näherungsstelle x mit dem Funktionswert f(x) gefunden, so liegt für ein beliebiges positives α auch α f(x) auf der gleichen Seite der Nullstelle. Setzt man nun

    \[ x_{n+1}=\frac{af(x_n)x_{n-1}-f(x_{n-1})x_n}{af(x_n)-f(x_{n-1})} \]

so kann sich eine bessere Konvergenz gegen die Lösung ergeben. Im Illinois-Verfahren setzt man α = 1/2.

Newton-Verfahren
Das Newton-Verfahren oder Tangentenverfahren (Tangentennäherungsverfahren) ersetzt die Sekante von Regula falsi durch die Tangente am Iterationspunkt x0. Voraussetzung ist dabei, dass die Funktion f(x) in der Umgebung von x0 wenigstens einmal differenzierbar ist. Eine näher an der gesuchten Nullstelle liegende Abszisse ergibt sich mit der Gleichung

    \[ x_1=x_0-\frac{f(x_0)}{f'(x_0)} \]

Neben dem Newton-Verfahren mit fester Steigung – der Anstieg der Tangente f'(x0) wird nicht neu berechnet – wird auch eine variable Steigung betrachtet (im Programm unter der Bezeichnung Newton-Verfahren in der Liste umgesetzt).

Newton-VerfahrenDieses Verfahren konvergiert sehr schnell – versagt jedoch, wenn die Kurve von f(x) an der Näherungsstelle der x-Achse nahezu parallel ist oder wenn zwischen dem Näherungswert und dem genauen Wurzelwert eine Extremstelle oder ein Wendepunkt mit zur x-Achse paralleler Wendetangente (Horizontalwendepunkt) liegt.

Außerdem finden Sie in der Liste die Bezeichnung Newton-Verfahren (2).
Hierbei handelt es sich um die Umsetzung der Berechnungsvorschrift, bei der f'(x0) nur für den Startwert berechnet und dann konstant gehalten wird. Vergleichen Sie dies mit dem Original-Newton-Verfahren, so werden Sie eine um vieles schlechtere Konvergenz feststellen. Liegt zwischen dem Startwert und der Nullstelle ein lokaler Extrempunkt, versagt das Verfahren vollständig, da die Iterationswerte divergieren.

Halley-Verfahren
Das Halley-Verfahren oder Verfahren der berührenden Hyperbeln ist wie das Newton-Verfahren eine Methode der numerischen Mathematik zur Bestimmung von Nullstellen reeller Funktionen f(x). Im Gegensatz zum Newton-Verfahren hat es eine kubische Konvergenz, benötigt dazu aber zusätzlich zur 1. auch die 2. Ableitung. Es ist nach dem Astronomen Edmond Halley benannt. Ein vergleichbares Verfahren ist das Euler-Tschebyschow-Verfahren.

Ist f(x) eine reelle Funktion mit zwei stetigen Ableitungen f'(x) und f“(x) und a eine Nullstelle von f(x), dann wird der Funktionsverlauf von f(x) in der Nähe von a durch die Funktion

    \[ g(x)=\frac{f(x)}{\sqrt{f'(x)}} \]

Dies hat auf die Nullstelle keinen Einfluss. Wird nun das Newton-Verfahren auf g(x) angewendet, ergibt sich

    \[ g'(x)=\frac{2f'(x)^2-f(x)f"(x)}{2f'(x)\sqrt{|f'(x)|}} \]

und als Iterationsformel

    \[ x_{k+1}=x_k-\frac{2f(x_k)f'(x_k)}{2f'(x_k)^2-f(x_k)f"(x_k)} \]

Brent-Verfahren
Ein sehr starkes Näherungsverfahren wurde 1973 durch Richard Brent entwickelt. Für eine Vielzahl von Anwendungen ist es wesentlich leistungsfähiger als das Newton-Verfahren.
Sind drei Punkte x1, x2, x3 und deren Funktionswerte gegeben, so ergibt sich der nächste Interpolationswert mit

    \[ x = x_3\frac{(y-f(x_1))(y-f(x_2))}{(f(x_3)-f(x_1))(f(x_3)-f(x_2))} \]

    \[ +x_1\frac{(y-f(x_2))(y-f(x_3))}{(f(x_1)-f(x_2))(f(x_1)-f(x_3))} \]

    \[ +x_2\frac{(y-f(x_1))(y-f(x_3))}{(f(x_2)-f(x_1))(f(x_2)-f(x_3))} \]

Anmerkung: Das Brent-Verfahren wird in vielen Unterprogrammen zur Ermittlung der Null-, Extrem- und Wendestellen eingesetzt.

Allgemeines Iterationsverfahren
Allgemein wird zur Bestimmung der Nullstelle die Gleichung f(x) = 0 auf die iterationsfähige Gleichung xi+1 = F(xi) gebracht. In der einfachsten Form geschieht dies mit

    \[ x_{i+1}=x_i-cf(x_i) \]

Je nach Wahl des Parameters c konvergiert oder divergiert die wiederholte Anwendung dieser Gleichung gegen die gesuchte Nullstelle. Im Programm wird voreingestellt c = 0.8 gesetzt, wodurch prinzipiell nur dann eine Konvergenz zu verzeichnen ist, wenn der Anstieg der Funktion an der Nullstelle kleiner 1 ist.

IterationIn der grafischen Veranschaulichung erkennt man gut das konvergente bzw. divergente Verhalten des Iterationsprozesses.

Möchten Sie den Faktor c variieren, dann geben Sie Ihren Wert in das Feld Iterationsfaktor ein. Dieser Faktor wird ebenso bei den Näherungsverfahren δ2-Aitken-Iteration und der Steffensen-Iteration genutzt. Erfahrungsgemäß sollte der Wert von c für eine gute Konvergenz kleiner als 1 sein.
Haben Sie die Absicht Ihren eingegebenen Wert für c mitzwei festen anderen zu vergleichen, so finden Sie in der Liste der Näherungsverfahren zwei Iterationsmöglichkeiten mit festem Iterationsfaktor. Wählen Sie dazu den Eintrag X = X – f(x) mit c = 1 oder den Eintrag X = X – 0.3 * f(x) mit einem festen Iterationsfaktor von 0.3.

x = cos x x = sin 3x

δ2-Aitken-Iteration
Zur Verbesserung der Konvergenz des allgemeinen Iterationsverfahrens existiert eine Vielzahl von Methoden. Zuerst passt man die Konstante c der Funktion an, d.h., durch unterschiedliche Werte für c versucht man die Konvergenz zu verbessern.

Beispiel: Zur Bestimmung einer Nullstelle der Funktion Y = X^4-X-2 im Intervall [1;2] wird das allgemeine Iterationsverfahren mit c = 1 getestet; mit dem Ergebnis, dass das Verfahren nach fünf Schritten divergiert und damit abbricht. Wird c schrittweise gesenkt, so divergiert das Verfahren bis c = 0.55328. Für kleinere Werte konvergiert das Iterationsverfahren plötzlich und ermittelt die Nullstelle bei 1.3532.

Darüber hinaus führt der δ2-Aitken-Prozess (Alexander C.Aitken, 1926) zu einer deutlichen Erhöhung der Konvergenz. Nach je zwei normalen Iterationsschritten wird unter Nutzung der drei zuletzt erzielten Iterationswerte ein Aitken-Schritt eingeführt.

    \[ x_{3i+3}=x_{3i}-\frac{(x_{3i+1}-x_{3i})^2}{x_{3i+2}-2x_{3i+1}+x_{3i}} \]

Es zeigt sich sogar, dass mit dem allgemeinen Iterationsverfahren divergente Iterationen nun konvergent sind.

Beachten Sie bitte, dass der Iterationsfaktor c auch in diesem Verfahren Bedeutung besitzt, da weiterhin je Aitken-Schritt zwei „normale“ Iterationen durchgeführt werden.


Die Konvergenz ist bei Nutzung des Aitken-Schrittes trotz Verbesserung immer noch linear. Einer Idee von Johan F. Steffensen (1933) folgend, erhält man eine quadratische Konvergenz, wenn nach einem normalen Iterationsschritt unter Beachtung von x(i+1) = f(x(i)) und x(i+2) = f(x(i+1)) = f(f(x(i))) alle weiteren Werte mit der Iterationsformel

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

gewonnen werden.

Müller-Steffensen-Iteration
Eine deutliche Verbesserung der Konvergenz erhält man mit der Müller-Steffensen-Iteration. Ausgehend von drei Stützpunkten werden Parabeln ermittelt. Deren kleinste Wurzeln werden als neuer Iterationspunkt genutzt. Die Besonderheit dieses Verfahrens besteht darin, dass es auch bei kleinen Funktionswerten oder schlechter Konvergenz des δ2-Aitken-Prozesses genutzt werden kann.

Vergleich der allgemeinen Iterationsverfahren
Beispiel: Für die Funktion Y = X^3-X-3 soll mit dem Startintervall [1.5;2] eine Nullstelle gesucht werden (Genauigkeit 6 Ziffern). Das allgemeine Iterationsverfahren bricht für den voreingestellten Iterationsfaktor c = 0.8 über die Argumente X(i) = 1.5 , 2.4 , -4.3392 , 59.9505, … auf Grund der Divergenz ab. Damit versagt auch die Iteration mit c = 1.

Bei Einführung des Aitken-Schrittes konvergiert das Verfahren nach Anfangsschwankungen und ermittelt im 18. Schritt x = 1.6717 als gesuchte Nullstelle. Das Steffensen-Verfahren erreicht schon nach 11 Schritten die erforderliche Genauigkeit.

Wählen Sie jedoch den Iterationsfaktor c = 0.2, so erhalten Sie bei der allgemeinen Iteration nach 18 Schritten, beim Aitken-Verfahren nach 12 Schritten, bei der Steffensen-Iteration allerdings erst nach 23 Schritten das Ergebnis. Weitere Tests zeigen, dass mit dem Steffensen-Verfahren mit c = 1 beste Ergebnisse erzielt werden.

Anmerkung zu den anderen Verfahren: Das Newton-Verfahren benötigt 4 Schritte, ebenso das Brent-Verfahren (das sich aber schneller der Nullstelle annähert), die Bisektion 21, Regula falsi mit Fixpunkt 9 und Regula falsi mit gleitenden Grenzen 6 Näherungsschritte, das Illinois-Verfahren 7 Schritte.

Allgemeine Hinweise zu den Näherungsverfahren
In diesem Unterprogramm werden die beschriebenen Verfahren nebeneinander betrachtet.

In den drei aufklappbaren Boxen wählen Sie je Box eines der genannten Näherungsverfahren aus. Nach der Eingabe der Funktion und des Startintervalls wird mit dem Schalter Berechnung die Iteration begonnen.
Die ermittelten Näherungen werden mit Abszisse und Ordinate in den Listboxen angezeigt. Zum schnelleren Ermitteln eines günstigen Anfangsintervalls können Sie zuvor die Funktion mittels Schalter Darstellung grafisch darstellen.

Bei schlechter Konvergenz oder Divergenz bricht das Programm nach den unter maximalen Einträge (Voreinstellung 100) eingegebenen Schritten ab. Zusätzlich kann die angestrebte Genauigkeit für den Funktionswert von einer bis zu sechs Kommastellen (Voreinstellung 6) festgelegt werden.

Ist die Funktion nicht differenzierbar oder versagt das Newton-Verfahren aus den oben genannten Gründen, erscheint eine entsprechende Meldung.
Mit diesem Teilprogramm können beliebige Gleichungen der Form g(x) = h(x) näherungsweise gelöst werden, indem die Funktion f(x) = g(x) – h(x) untersucht wird.