Ich muss diesen selbst programmierten Code (Bisektionsverfahren) rekursiv darstellen, jedoch tue ich mir da schwer. Kann mir jemand zur Hand gehen?
public class Bisektion {
public static void main(String[] args) {
double Nst = bisektion(-10, 10, 0.01);
System.out.println("Ermittelte Nullstelle: " + Nst);
System.out.println("Funktionswert an dieser Stelle: " + fkt1(Nst));
System.out.println();
double Nst2 = bisektion(-1000, 1000, 0.01);
System.out.println("Ermittelte Nullstelle: " + Nst2);
System.out.println("Funktionswert an dieser Stelle: " + fkt2(Nst2));
}
// Test Funktionen
public static double fkt1(double x) {
double fx;
//fx = x * x * x - 24 * x * x + 59 * x + 420;
fx = x + 5;
return fx;
}
public static double fkt2(double x) {
double fx2;
fx2 = -1/Math.exp(x) + 1e20;
return fx2;
}
public static double bisektion(double lower, double upper, double epsilon) {
double mid = lower;
double width = upper - lower; //20
// Intervall
while (width > epsilon) { //20 > 0.1
mid = (lower + upper) / 2;//0 //-5
if (fkt1(lower) * fkt1(mid) <= 0) { // if root is in [lower, mid] //-5 * 0
upper = mid; // move upper left //upper = 0
} else { // else root is in (mid, upper]
lower = mid; // move lower right
}
width = upper - lower; //width = 10
System.out.println("root = " + mid );
}
return mid;
}} // f(lower)<0 und f(upper)>0 // f besitzt nullstelle im Intervall [lower,upper] // middle // entweder lower oder upper durch ein kriterium mit middle ersetzen // stoppen wenn funktionswert näherungsweise 0 ist // ==> betrag kleiner als vorgegebene zahl epsilon
3 Antworten
Deine Funktion sollte funktionieren, soweit ich das sehe. Was fehlt denn noch?
Soll der Abstand des Arguments (x) von der Minimumstelle oder die Abweichung des Funktionswerts vom Minimalwert kleiner als epsilon werden? Du hast so programmiert, dass auf Abweichung von x getestet wird.
Probleme, die ich noch sehe
- ggf. an der Aufgabenstellung vorbei (Vergleich von x statt y)
- Nebenwirkungen (Falls der Aufrufer Variablen für lower und upper übergibt, werden die je nach Compiler unbeabsichtigt verändert)
- die Funktion sollte als Argument übergeben werden
- falls f(lower) und f(upper) dasselbe Vorzeichen haben, sollte eine Ausnahme ausgelöst werden
- für den Vergleich der Vorzeichen würde ich keine Multiplikation nehmen sondern die sgn-Funktion, falls vorhanden, oder irgendwo das Vorzeichen von f(lower) (für den ersten Wert von lower) speichern und damit vergleichen. Multiplikation ist zwar nicht besonders langsam, aber auch nicht besonders schnell.
Da bin ich überfordert. Bin noch nicht lange im "Programmiergame" drin :( . Könntet ihr mir netter weise es für mich rekursiv programmieren und es noch etwas erklären, wenn das nicht zu viel verlangt ist.
Wir geben hier gerne Hilfestellung bei Hausaufgaben, aber sie für andere zu lösen, ist nicht Sinn der Sache.
Was weißt du über Rekursion?
Ich weiß nur das grundlegendste und zwar das sich eine Methode selbst aufruft.
Was meinst du mit "falls f(lower) und f(upper) dasselbe Vorzeichen haben, sollte eine Ausnahme ausgelöst werden"? Es funktioniert doch auch wenn sie das selbe Vorzeichen haben.
(Schauen wir mal, welche Variablen innerhalb der wichtigsten Schleife geändert werden.
Das sind hier lower und upper, die jeweils durch mid ersetzt werden.
Wie Variablen in Funktionen gefüllt werden, solltest du verstanden haben - du rufst ja z. B. bisektion mit Zahlenwerten auf. (Diese werden von bisektion in die entsprechenden benannten Variablen eingetragen.)
Im Fall von
upper = mid;
wird iterativ die Variable upper mit dem aktuellen Wert der Variablen mid gefüllt.
Die Aufgabe besteht jetzt darin, das nicht per Zuweisung in der Iteration zu machen, sondern durch (rekursiven) Aufruf der Funktion. Die Funktion sieht ja so aus:
bisektion(double lower, double upper, double epsilon)Wir befinden uns im Moment in der Aufrufer-Instanz der Funktion.
Für die nächste Stufe, die aufgerufene Instanz der Funktion, brauchen wir einen anderen Wert in upper.
Dieser Wert steht in der Aufrufer-Instanz (wo wir momentan sind) in der Variablen mid.
Um den Wert dieser Variablen an die richtige Stelle zu übergeben, müssen wir bisektion so aufrufen:
bisektion(lower, mid, epsilon)
Das allein hilft noch nicht weiter, da bisektion den interessierenden Wert zurückgibt.
Um möglichst wenig an der Funktion zu ändern, können wir die Schleife weglassen und statt
upper = mid;
schreiben
upper = bisektion(lower, mid, epsilon)
dann haben wir aber den Rückgabewert in upper, brauchen ihn aber in der Rückgabe in mid. Wir müssten also noch schreiben
mid = upper;
Weitere Analyse der Funktion ergibt, dass mit mid nach der Schleife nichts gemacht wird, wir können also direkt das Ergebnis von bisektion zurückgeben:
return bisektion(lower, mid, epsilon);Entsprechendes machen wir auch für den Fall
lower = mid;
Die Funktion sieht also (im Pseudocode) so aus:
Funktion Bijektive_Nullstellensuche(Zahl unten, Zahl oben, Zahl epsilon, Funktion f)
berechne yu = f(unten)
berechne yo = f(oben)
berechne mitte = (unten + oben) / 2
berechne ym = f(mitte)
Falls Abweichung klein genug
Rückgabe mitte
Sonst Falls Vorzeichen von yu und ym verschieden
Rückgabe Bijektive_Nullstellensuche(unten, mitte, epsilon, f)
Sonst
Rückgabe Bijektive_Nullstellensuche(mitte, oben, epsilon, f)
Du kannst die Funktion noch etwas effektiver machen, indem du die Werte von yo und yu mit übergibst. Dazu nimmst du am besten eine eigene Funktion:
Funktion Bijektive_Nullstellensuche(unten, oben, epsilon, f)
berechne yUnten = f(unten)
berechne yOben = f(oben)
Rückgabe Bijektive_Nullstellensuche2(xUnten, yUnten, xOben, yOben, epsilon, f)
Funktion Bijektive_Nullstellensuche2(xUnten, yUnten, xOben, yOben, epsilon, f)
berechne xMitte = (xUnten + x=ben) / 2
berechne yMitte = f(xMitte)
Falls Abweichung klein genug
Rückgabe xMitte
Sonst Falls Vorzeichen von yUnten und yMitte verschieden
Rückgabe Bijektive_Nullstellensuche2(xUnten, yUnten, xMitte, yMitte, epsilon, f)
Sonst
Rückgabe Bijektive_Nullstellensuche2(xMitte, yMitte, xOben, yOben, epsilon, f)
(Eine vom Aufrufer übergebene Funktion sollte man grundsätzlich so selten wie möglich verwenden - man weiß nie, wie lange die braucht)
Was meinst du mit "falls f(lower) und f(upper) dasselbe Vorzeichen haben, sollte eine Ausnahme ausgelöst werden"? Es funktioniert doch auch wenn sie das selbe Vorzeichen haben.
Dann such mal eine Nullstelle von f(x) = 1.
Wie würde man es realisieren die Funktion als Argument zu übergeben ?
Es ist eigentlich sinnlos eine Aufgabe, die nicht rekursiv ist, rekursiv zu lösen, aber gut:
Baue Dir eine Methode, die das Intervall (gem. Algorithmus) halbiert und sich dann mit den neuen Intervallgrenzen selbst aufruft. Die Abbruchbedingung führt dann eben zu keinem Selbstaufruf.
Ich hab´s jetzt so gut ich konnte rekursiv umgesetzt. (Siehe Bild im Anhang)
Kann mir jemand sagen wieso die Funktion f(x) = -1/Math.exp(x) + 1e20 nicht korrekt berechnet wird und wie man es besser machen kann?
