Hallo!
Das Programm sieht ja recht kompliziert aus, aber da steig ich
sicher noch durch. Muss es mir mal in aller Ruhe zu Gemüte
führen.
Hier ein paar techn. Details:
Zur Klasse „Intervall“:
Ist nur eine Klasse um ein Intervall zu speichern.
-Besitzt nur einen Konstruktor zum Setzen der Intervallgrenzen.
Zur Klasse „Intervallschachtelung“:
Hauptprogramm.
-Besitzt eine main - Methode für den Programmstart. Ruft den Konstruktor auf, um mit den Parametern des Aufrufs die Systemparameter zu setzen (Approximation, Intervall etc.). Anschließend wird mit findValue die Nullstelle gesucht.
-getValue berechnet den zu einer Stelle x gehörenden y - Wert
-goodApproximation prüft, ob eine gegebene Annäherung an eine Nullstelle ausreichend genau ist. Dazu wird der y - Wert der approximierten Stelle mit einer Zehnerpotenz multipliziert um zu sehen, ob eine gewisse Genauigkeit erreicht ist (pow( 10,approximation) bedeutet 10^approximation).
findValue ist der eigentliche Analyse-Algorithmus. Er implementiert eine verkettete Liste von Intervallen in der die zu untersuchenden Intervalle eingetragen werden. Technisch funktioniert diese Liste wie eine FIFO - Warteschlange (first in, first out). Der Algorithmus funktioniert nun nach folgendem Prinzip (siehe while - Schleife): „Hole ein neues Intervall aus der Liste. Berechne den Funktionswert f(x) in der Mitte des Intervalls. Ist das eine ausreichend gute Näherung für die Nullstelle? Wenn ja: Toll, gib’ das Ergebnis aus. Wenn nein: Füge das Intervall [Intervallstart,x] und das Intervall [x,Intervallende] zur Liste hinzu. Starte wieder von vorne“.
Darüber hinaus zählt die Schleife ihre Durchläufe mit, um nach einer bestimmten Grenzanzahl (test_limit) abzubrechen - dient nur der Sicherheit. Ist die Grenze überschritten, bricht der Analyse-Algorithmus ab und gibt die beste gefunde Näherung an die Nullstelle zurück (best_approximation).
Es ist wichtig zu verstehen, warum ich das so und nicht anders implementiert habe. Dein rekursiver Ansatz funktioniert nämlich schon rein theoretisch nicht! Warum? Nun ja: Ein rekursiver Algorithmus für dieses Problem wäre eigentlich nichts anderes als mein Lösungsalgorithmus mit einer LIFO - Warteschlange - auch „Stack“ genannt. Das liegt daran, dass sich jeder rekursive Algorithmus durch einen Stack nicht-rekursiv ausformulieren lässt (das macht übrigens der Compiler mit einem rekursiven Algorithmus den du in den Quellcode gefuscht hast; deswegen gibt’s bei zu hoher Rekursionstiefe auch mal einen „Stack-overflow“). Das Problem: In einer solchen Implementierung würde nur eine Hälfte des angegebenen Intervalls bis zum Verrecken untersucht werden bevor der Computer auf die Idee kommt, die andere Hälfte zu untersuchen - weil alle bei der Untersuchung des Intervalls entstehenden neuen Intervalle sozusagen „an den Anfang“ der Liste gesetzt werden. Dann gibt’s zwei Möglichkeiten wie das ganze ausgeht: Entweder der Rechner rechnet sich bis in alle Ewigkeit dumm und dämlich weil die Nullstelle gar nicht in dieser einen Intervallhälfte liegt oder er findet durch Glück irgendwann die Nullstelle, weil sie zufälligerweise in diesem Intervall liegt - erinnert mich ein bißchen an russisches Roulette 
.
Mit meiner Methode - also mit einer FIFO - Schleife - werden aber abwechselnd das linke und rechte Intervall untersucht. Somit kann dieses Problem nicht auftauchen und der Algorithmus funktioniert!
Übrigens mit Vorzeichenwechseln kann man auch nicht nach der Nullstelle suchen: Bei einer Funktion wie z.B. x^2 gibt es nämlich keinen Vorzeichenwechsel bei der Nullstelle, weil die Nullstelle zweifach - also gerade - gesetzt ist.
Florian
