findRoot Methode schreiben in einem Intervall

[ocsme]

Guten Tag, ja ich mal wieder

wir haben eine Aufgabe heute bekommen und ich verstehe nicht so ganz was zu tun ist
Hier mal die Aufgabe:

Schreiben Sie eine Methode findRoot um innerhalb eines Intervalls [a,b] eine Nährung der Nullstelle einer vorgegebenen stetigen Funktion f(x) zu berechnen.
Das Verfahren versucht einen Punkt x im Intervall [a,b] zu finden, für den f(x)=0 gilt oder der zumindest möglichst nahe an Null ist. Dafür wird das Intervall mit einer bestimmten Schrittweite e untersucht, d.h. zuerst wird f(a), dann f(a+e), dann f(a+2e), ... usw. bis f(b) berechnet. Die Stelle, an welcher der Funktionswert der Null am nächsten ist, wird gespeichert. Die Anfangsschrittweite sei e=(b-a)/2. Nach jedem Durchlauf durch das Intervall wird die Schrittweite halbiert. Das Verfahren endet, wenn eine Stelle x mit f(x)=0 gefunden wurde oder die Schrittweite einen definierten Wert eps unterschreitet (e<eps).

Hab nachgefragt und es hieß nur naja so machen wie es da steht
Ich verstehe es nur leider nicht.
Natürlich brauch ich erstmal sowas:

public static double findRoot(double a,double b, double eps){
double e=(b-a)/2;
}

Aber was soll da jetzt genau gemacht werden

LG

 

[mihe7]

Naja, das steht doch wirklich alles da:

... d.h. zuerst wird f(a), dann f(a+e), dann f(a+2e), ... usw. bis f(b) berechnet. Die Stelle, an welcher der Funktionswert der Null am nächsten ist, wird gespeichert
...
Nach jedem Durchlauf durch das Intervall wird die Schrittweite halbiert. Das Verfahren endet, wenn eine Stelle x mit f(x)=0 gefunden wurde oder die Schrittweite einen definierten Wert eps unterschreitet (e<eps).

Hier mal ein Algorithmus, der so formuliert ist, dass Du selbst auch noch was zu tun hast

e := (b-a)/2
minX := a
so lange e >= eps
    minX := arg min |f(x)| mit x aus {minX, a, a+e, a+2e, ... b}
    e := e / 2
gib minX zurück

EDIT: Betragsstriche hinzugefügt. Anfangsschrittweite korrigiert.

 

[ocsme]

Wieso habe ich mit solchen Textaufgaben nur so Probleme da fehlt die Übung Übung Übung!
Werde das später versuchen und natürlich wie immer berichten
Aber erstmal super lieben dank an dich *wie alt so oft *

 

[ocsme]

soll ich mir das ganze so vorstellen?

    public static double f(double x) { // zu verwendende Methode f(x)
        return Math.cos(x);
    }
   
    public static double findRoot(double a,double b, double eps){
        double e=(b-a)/2;
        double min=a;
        int i=1;
        while(e>=eps) {
            min=Math.abs(f(min+i*e));
            e=e/2;
            i++;
        }
        return min;
        }

 

[mihe7]

Nein.

arg min |f(x)| mit x aus {minX, a, a+e, a+2e, ... b}

bedeutet salopp formuliert: ermittle dasjenige x aus {minX, a, a+e, ..., b}, so dass |f(x)| minimal ist.

 

[ocsme]

Okay dann würde mir sowas einfallen:

  min+=Math.abs(f(min+i*e));

Denn nur so komme ich z. B. bei der Funktion von oben also beim cosinus an PI/2 ran. Dann habe ich
1.5690873418960243
und PI/2 sind:
1.5707963267948966
ändert man nun 1e-4 zu 1e-10 kommt das raus:
1.5707963228367756
also noch näher an Pi/2
Ist das nun richtig?
Ich denke ich hab auch jetzt erst die Aufgabe richtig verstanden dank deiner Erklärung

 

[mihe7]

Okay dann würde mir sowas einfallen:

Nein. Wie ermittelst Du denn das Minimum z. B. aus einem int-Array?

 

[ocsme]

Naja indem ich schaue ob im Array a a<min.
Also so:

int[] a=new int[10];
        for(int i=0;i<a.length;i++)
            a[i]=(int) (Math.random()*10+1);
       
        for(int b:a)
            System.out.println(b);
       
        int min=Integer.MAX_VALUE;
        for(int i=0;i<a.length;i++)
            if(a[i]<min)
                min=a[i];
       
        System.out.println(min);

Ich komme aber nicht drauf wie ich das oben machen muss dachte jetzt hätte ich es verstanden so ein misst!

 

[Xyz1]

@mihe7 Geht es um ein (nicht rekursives) Intervallhalbierungsverfahren?

 

[mihe7]

dachte jetzt hätte ich es verstanden so ein misst!

Das kriegen wir schon hin.

Dein Code für das Array passt soweit. Jetzt ändern wir mal die Anforderung ein wenig: mich interessiert nicht der minimale Wert, sondern der Index des minimalen Werts.

 

[ocsme]

Die Position ermittele ich so:

int pos=0;
        int min=Integer.MAX_VALUE;
        for(int i=0;i<a.length;i++)
            if(a[i]<min) {
                min=a[i];
                pos=i+1;
            }
       
        System.out.println(min+" "+pos);

und das hier stimmt sicherlich auch nicht oder?

public static double findRoot(double a,double b, double eps){
        double e=(b-a)/2;
        double min=Integer.MAX_VALUE;
        int i=1;
        while(e>=eps) {
            if(Math.abs(f(a+i*e))<min)
            min=Math.abs(f(min+i*e));
            e=e/2;
            i++;
        }
        return min;
        }

 

[ocsme]

Intervallhalbierungsverfahren meinst du sowas wie Bisektionsverfahren? Das hatten wir vor ein paar Wochen erst in Mathe. Kommt das hier aufs selbe raus?

 

[mihe7]

Geht es um ein (nicht rekursives) Intervallhalbierungsverfahren?

Sowas in der Richtung, oder evtl. auch https://de.wikipedia.org/wiki/Regula_falsi

 

[mihe7]

Die Position ermittele ich so:

Ja, der Index ist halt pos-1.

Wenn Du jetzt nicht die Werte a[i] sondern Math.abs(f(a[i])) minimierst, wie sieht dann der Code aus?

EDIT: Formatierungszeichen ersetzt.

 

[ocsme]

soll ich jetzt einfach min=Math.abs(f(min)) machen?

public static double findRoot(double a,double b, double eps){
        double e=(b-a)/2;
        double min=a;
        while(e>=eps) {
            min=Math.abs(f(min));
            e=e/2;
        }
        return min;
        }

lasse ich e und min ausgeben kommt das raus:

1.0 1.0
0.5 0.5403023058681398
0.25 0.8575532158463934
0.125 0.6542897904977791
0.0625 0.7934803587425656
0.03125 0.7013687736227565
0.015625 0.7639596829006542
0.0078125 0.7221024250267077
0.00390625 0.7504177617637605
0.001953125 0.7314040424225098
9.765625E-4 0.7442373549005569
4.8828125E-4 0.7356047404363474
2.44140625E-4 0.7414250866101092
1.220703125E-4 0.7375068905132428

 

[mihe7]

Du sollst jetzt erstmal bei dem Minimierungscode bleiben. S. Kommentar #14.

 

[ocsme]

so wahrscheinlich:

if(Math.abs(f(a[i]))<min) {
                min=a[i];
                pos=i+1;
            }

 

[Xyz1]

Intervallhalbierungsverfahren meinst du sowas wie Bisektionsverfahren? Das hatten wir vor ein paar Wochen erst in Mathe. Kommt das hier aufs selbe raus

jo Bisektionsverfahren meinte ich.

 

[mihe7]

Fast, Du musst Dir schon das Minimum merken. Ich melde mich nachher nochmal.

 

[mihe7]

OK, ich kürze das ab.

public class Min {
    public static double findRoot(double a,double b, double eps){
        double e=(b-a)/2;
        double min=a;
        double minF = Math.abs(f(min));
        while(e>=eps) {
            double curX = a;
            do {
                double curF = Math.abs(f(curX));
                if (curF < minF) {
                    min = curX;
                    minF = curF;
                }
                curX += e;
            } while (curX <= b);
            e=e/2;
        }
        return min;
    }

    public static double f(double x) { return Math.cos(x); }

    public static void main(String[] args) {
        double v = findRoot(-1, 2, 0.01);
        System.out.println(v + ": " + f(v));
    }
}

 

[ocsme]

Dank dir *wieder*
nur für mein verständniss denn ich glaube ich hab das ganze die Ganze Zeit nicht wirklich verstanden.
Hier soll nun ein Intervall von sagen wir mal [0,2] und der Funktion cos(x) betrachtet werden. Das intervall wird immer mit e halbe durchlaufen das bedeutet der erste Schritt läuft so ab:
0,1/2,1,1 1/2, 2 dann wird e halbiert und es beginnt von vorne so:
0,1/4,1/2,3/4,1,... dann wird e wieder halbiert etc.
Ist das korrekt?

LG

 

[Flown]

Ist das korrekt?

ja

 

[mihe7]

Ja. In jeder Iteration erhältst Du eine endliche Menge von x-Werten (in der ersten Iteration eben 0, 1/2, 1, 1 1/2, 2). Für jeden dieser x-Werte wird der Funktionswert |f(x)| ermittelt und geprüft, ob dieser der bisher kleinste gefundene ist. Ist dies der Fall, merkt man sich das x (und aus Gründen der Performance auch gleich noch das |f(x)|). So, wie Du das eben aus #11/#17 schon kennst

 

[ocsme]

das hätte ich so niemals ordentlich verstanden echt übel
Naja ich werde weiter am Ball bleiben was bleibt einem sonst übrig hab ich recht wie bei Javinner ja steht:

while( !lebenVorbei() ) {
    lerne();
}

 

[mihe7]

Ich denke, es sind drei Dinge: erstens brauchst Du einen Grundstock an Wissen. Zweitens musst Du lernen, zu abstrahieren, um Dein Wissen auf unbekannte Probleme anwenden zu können. Und drittens brauchst Du etwas Gespür für die Formulierungen.

Bei bestimmten Formulierungen sollten die Alarmglocken schrillen.

An der Uni wird (meist) versucht, die Aufgabenstellung so zu formulieren, dass sie korrekt und vollständig ist. Das führt dazu, dass z. T. sehr viel Text geschrieben steht. Dafür bekommst Du aber eine Beschreibung, von der Du in der Praxis nicht einmal zu träumen wagst.

Ich kann Dir ja mal ein paar mögliche Gedankengänge zu Deinem Aufgabentext schreiben:

Schreiben Sie eine Methode findRoot um innerhalb eines Intervalls [a,b] eine Nährung der Nullstelle einer vorgegebenen stetigen Funktion f(x) zu berechnen.

Was lese ich daraus?
1. Intervall [a,b]
2. Funktion f(x)
3. Näherung der Nullstelle.

Hm... Nullstellen sind die Werte, die von einer Funktion auf 0 abgebildet werden. Wir suchen also einen Wert x, so dass f(x) möglichst Nahe an 0 herankommt. Und jetzt Alarmglocke (Formulierung(!)): "möglichst Nahe" = "minimaler Abstand" -> gesucht ist ein Minimum. Wie ist nun der Abstand von f(x) zu 0? Naja: |f(x) - 0|, also |f(x)|

Damit weiß ich, dass das x gesucht wird, so dass |f(x)| minimal wird. OK. Wären die x-Werte z. B. ganze Zahlen, wäre das Thema schon erledigt, denn wie ich in dem Fall ein Minimum finde, wüsste ich. Ich würde einfach alle Zahlen im Intervall [a,b] durchlaufen und könnte dann |f(x)| berechnen, mir das x merken, bei dem |f(x)| minimal ist - fertig.

Dieser Durchlauf durch alle Zahlen in einem Intervall funktioniert bei rationalen Zahlen bekanntermaßen nicht, weil es zwischen zwei rationalen Zahlen ja unendlich viele weitere gibt. Wie soll das jetzt funktionieren?!?

Dafür wird das Intervall mit einer bestimmten Schrittweite e untersucht, d.h. zuerst wird f(a), dann f(a+e), dann f(a+2e), ... usw. bis f(b) berechnet. Die Stelle, an welcher der Funktionswert der Null am nächsten ist, wird gespeichert.

Aha. Man tut so, als hätte man eine endliche Menge konkreter Werte: a, a+e, a+2e, ..., b. Damit lässt sich wieder die bekannte Suche nach dem Minimum anwenden. Soweit kein Problem.

Wie groß soll nun die Schrittweite e sein?

Die Anfangsschrittweite sei e=(b-a)/2.

OK, würde man nur das machen, dann hätte man aber nur eine handvoll an Werten untersucht. Für das Intervall [0, 2] wäre e = 1. D. h. man würde gerade mal die Werte 0, 1 und 2 abdecken. Das kann ja nicht alles sein.

Nach jedem Durchlauf durch das Intervall wird die Schrittweite halbiert.

Aaaaha. Formulierung(!) "Nach jedem Durchlauf" -> der Spaß soll wiederholt werden. Und in jeder Iteration wird die Schrittweite halbiert, die Schlinge zieht sich also immer weiter zu. Das macht Sinn.

Jetzt kann man sich überlegen, dass man gewonnen hat, sobald man auf ein x trifft, so dass |f(x)| = 0 gilt. Problem: was passiert, wenn es dieses x nicht gibt? Dann würde man ja ewig suchen. Antwort liefert wieder die Aufgabenstellung:

Das Verfahren endet, wenn eine Stelle x mit f(x)=0 gefunden wurde oder die Schrittweite einen definierten Wert eps unterschreitet (e<eps).

Damit ist alles klar, sogar die Schleifenbedingung ist angegeben

 

[ocsme]

Das hört sich super an und das verstehe denke ich nun auch jeder wobei ich denke das der Text von mir auch schon viele andere vorher verstanden haben!
Mein Problem sind deine drein genanten Probleme:

Ich denke, es sind drei Dinge: erstens brauchst Du einen Grundstock an Wissen. Zweitens musst Du lernen, zu abstrahieren, um Dein Wissen auf unbekannte Probleme anwenden zu können. Und drittens brauchst Du etwas Gespür für die Formulierungen.

Wenn ich mir an meiner Uni viele Leute anschaue verstehe ich eh vieles nicht. Ich sitze hier Stunden über Stunden rum und bekomme die Sachen vielleicht gerade so hin und die meisten "angeblich" machen so gut wie nix.
Leider fehlt mir auch viel Grundwissen aus der Schulzeit da ich erst Hauptschule gemacht habe dann alles nachgeholt habe! und das auf sagen wir mal nicht so tollen Schulen also mein Fachabi habe ich wirklich geschenkt bekommen "leider" jetzt rächt es sich ganz ganz böse :/

Doch ich bleibe am Ball
Nochmals danke

 

[mihe7]

Wenn ich mir an meiner Uni viele Leute anschaue verstehe ich eh vieles nicht.

Naja, die Leute haben alle einen unterschiedlichen Hintergrund. Es ist doch völlig klar, dass z. B. jemand, der von Kindesbeinen an programmiert hat, sich in dem Bereich leichter tut, als jemand, der gerade damit anfängt.

Logisch ist auch, dass jemand, der z. B. nicht weiß, was Nullstellen sind, ein Problem mit der Aufgabe haben wird. In dem Fall muss derjenige sich erstmal einlesen. Das dürfte im Zeitalter des Internets aber kein größeren Problem darstellen.

Im Beispiel oben: Nullstellen? Kann man das Essen? Google -> aha, alles klar.

 

[ocsme]

Genau so sehe ich es ja auch
Hinzukommen Theoretisch noch weitere Faktoren! wie z. B. Gesundheit, Zeit, Geld, ... die einen an der Uni in die Bredouille bringen können. Da das bei mir auch noch alles hinzukommt verzögert sich bei mir das Studium so oder so um das doppelte! Ich kann nichts dran ändern und freue mich auch für die anderen die sich damit so leicht tun
Es gibt eben solche und solche habe ich recht Hauptsache ist doch das es morgen weiter geht und das man immer dran bleibt
So genug davon.
schade das man dir keine Nachricht schicken kann mihe7!

LG

 

[Xyz1]

schade das man dir keine Nachricht schicken kann mihe7

Es gibt doch die PN Möglichkeit wenn man auf den Nickname klickt bei dem Beitrag.

 

[mihe7]

Es gibt doch die PN Möglichkeit wenn man auf den Nickname klickt bei dem Beitrag.

Aber nicht bei mir

 

[Xyz1]

Aber nicht bei mir

Haha, sorry, da habe ich nicht dran gedacht.

 

[ocsme]

ja bei mihe7 nicht. Ich weiß nicht mehr was ich die Tage wollte da hab ich es fest gestellt. Gut kann mir das auch vorstellen wenn man so viel Hilft und aktiv ist dann bekommt man sicherlich die ein oder andere Nervige Mail
es geht ja auch so

LG