Bisektionsverfahren

JustusJonas93

JustusJonas93

Mitglied
Hallo, ich versuche mit Hilfe eines Bisektionsverfahrens die Nullstellen eines Polynoms in einem bestimmten Intervall zu finde. Meine Idee war direkt 1000 Intervalle zu bilden um wirklich alle Nullstellen zu finden. Nun würde ich gerne alle Intervalle ablaufen und wenn es einen Vorzeichenwechsel gibt eine Nullstelle melden. Ich habe angefangen doch komme nun nicht weiter. Meine Java Kenntnisse halten sich bis jetzt leider sehr in Grenzen.

LG JJ
 

Anhänge

  • bisektion1.png
    bisektion1.png
    12,3 KB · Aufrufe: 185
JustusJonas93

JustusJonas93

Mitglied
Java: 
package Berechnung;

public class Bisektion {
   
    public static void main (String[]args){

        //Polynom
        double[] p={2,1,-4};
       
        //Intervall
        int a=1;
        int b=5;
       
        double m;
        double x;
        double y;
        double u;
       
        int[] Vorzeichen = new int[1000];     // Speicher für Vorzeichen
       
           
           
            // m festlegen
           
            if(a<0 && b<0){
                m=(Math.abs(b)-Math.abs(a))/1000;
                m=Math.abs(m);
            }else{
                m=(b-a)/1000;
            }
           
            y= Polynom.Fwert(p, a);
            if(y<0){                        // Anfangsfeld wird festgelegt
                Vorzeichen[0]=1;
            }else{
                Vorzeichen[0]=0;
            }
           
            for(int j=1;j<1000;j++){               // Schleife für Feld 1-1000
               
            for(u=a+m; u<b; u=u+m){               // Läuft alle 1000 Intervalle ab
                x= Polynom.Fwert(p, u);
                    if(x<0){
                        Vorzeichen[j]=1;          // wenn negativ
                    }else if(x>0){ 
                        Vorzeichen[j]=0;          // wenn positiv
                    }else{
                        System.out.println(u);    // wenn Nullstelle
                    }
                    if(Vorzeichen[j]!=Vorzeichen[j-1]){    // Vorzeichenvergleich
                        System.out.println(u);
                        }
                       }}
           
           
        }
}
 
JustusJonas93

JustusJonas93

Mitglied
Da kommt immer ein Wert raus mit 2 Punkten, das habe ich ja noch nie gesehen.
Code habe ich etwas verändert seit dem.

Edit: Jetzt gibt er die richtigen m Werte aus.
Code: 
package Berechnung;

public class Bisektion {
   
   public static void main (String[]args){

       //Polynom
       double[] p={1,0,-4};
       
       //Intervall
       double a=0;
       double b=30;
       
       double m;
       double x;
       double y;
       double u;
       
       int[] Vorzeichen = new int[1001];     // Speicher für Vorzeichen
       
           
           
           // m festlegen
           
           if(a<0 && b<0){
               m=(Math.abs(b)-Math.abs(a))/1000;
               m=Math.abs(m);
           }else{
               m=(b-a)/1000;
           }
           System.out.print(m);
           
           y= Polynom.Fwert(p, a);
           //System.out.println(y);
           
           if(y<0){                        // Anfangsfeld wird festgelegt
               Vorzeichen[0]=1;
           }else{
               Vorzeichen[0]=0;
           }
           //System.out.println(Vorzeichen[0]);
           
           for(int j=1;j<1000;j++){               // Schleife für Feld 1-1000
               
           for(u=a+m; u<b; u=u+m){               // Läuft alle 1000 Intervalle ab
               x= Polynom.Fwert(p, u);
                   if(x<0){
                       Vorzeichen[j]=1;          // wenn negativ
                   }else if(x>0){  
                       Vorzeichen[j]=0;          // wenn positiv
                   }else{
                       //System.out.println(u);    // wenn Nullstelle
                   }
                   if(Vorzeichen[j]!=Vorzeichen[j-1]){    // Vorzeichenvergleich
                       //System.out.println(u);
                       }
                     }}
           
           
       }
}
 
JustusJonas93

JustusJonas93

Mitglied
Hey, ich sitze nach einer kleinen Pause immernoch an dem Projekt. Ich habe mitlerweile viel am Code geändert und für 95% aller Polynome funktioniert der Code auch und er gibt mir die richtigen Nullstellen aus. Allerdings gibt es ein Problem: Zum Beispiel für das Polynom, welches ich gerade im Code als Beispiel habe findet er die Nullstellen nur wenn ich q = 10000000 setze, bei 100000 oder 10000001 zum Beispiel, findet er keine Nullstellen.

Woran kann das liegen? LG

Java: 
package Berechnung;

public class Bisektion {
    
    public static void main (String[]args){

        //Polynom
        double[] p={1,-10,35,-50,25};
        
        //Intervall
        double a=0;
        double b=10;
        
        double m;
        double x;
        double y;
        double u;
        int q =10000000;
        
        int[] Vorzeichen = new int[q];     // Speicher für Vorzeichen
        
            
            
            // m festlegen
            
            if(a<0 && b<0){
                m=(Math.abs(b)-Math.abs(a))/q;
                m=Math.abs(m);
            }else{
                m=(b-a)/q;
            }
            System.out.println(m);
            
            y= Polynom.Fwert(p, a);
            System.out.println(y);
            
            if(y<0){                        // Anfangsfeld wird festgelegt
                Vorzeichen[0]=1;
            }else{
                Vorzeichen[0]=0;
            }
            System.out.println(Vorzeichen[0]);
            
            int j=1;              // Schleife für Feld 1-q
                
            for(u=a+m; u<b; u=u+m){               // Läuft alle 1000 Intervalle ab
                x= Polynom.Fwert(p, u);
                    if(x<0){
                        Vorzeichen[j]=1;          // wenn negativ
                    }else if(x>0){ 
                        Vorzeichen[j]=0;          // wenn positiv
                    }else{
                        System.out.println(u);
                        Vorzeichen[j]=Vorzeichen[j-1];
                    }
                    if(Vorzeichen[j]!=Vorzeichen[j-1]){    // Vorzeichenvergleich
                        System.out.println(u);
                    
                    j++;
                    }}
            
            
        }}
 
H

httpdigest

Top Contributor
Was du da implementiert hast, ist nicht das Bisektionsverfahren.
Und ich weiß auch nicht, was dein 'm' eigentlich sein soll. Du scheinst das als irgendeine Schrittweite zu verwenden. Aber wieso und wofür? Das Bisektionsverfahren geht folgendermaßen:
1. Als Voraussetzung brauchen wir erstmal zwei Stellen der Funktion mit unterschiedlichem Vorzeichen
2. Jetzt ermitteln wir die Mitte zwischen beiden Punkten, also (a+b)/2 (halbieren das Intervall [a, b] also, daher der Namen Bisektion), und schauen, ob diese Stelle der Funktion nun dasselbe Vorzeichen wie bei a oder wie bei b hat
3. Dementsprechend setzen wir nun entweder a oder b auf diese halbierte Stelle und wiederholen mit 1 bis eine von uns gewünschte Genauigkeit erreicht ist

EDIT: Kannst dich hiervon inspirieren lassen: https://www.java-forum.org/thema/bisektionsverfahren-mathematische-funktion.99952/
 
Zuletzt bearbeitet:
JustusJonas93

JustusJonas93

Mitglied
Ich kenne das Bisektionsverfahren, aber aus Gründen ist es nun ein Sektionsverfahren. Die Methode ist egal, hauptsache die Nullstellen werden relativ genau gefunden.

LG
 
H

httpdigest

Top Contributor
Es gibt kein Verfahren, das zuverlässig in endlicher Zeit alle realen Nullstellen aller möglichen Polynome findet. Wenn du also sagst, dass dein Verfahren in 95% aller Fälle funktioniert, dann finde ich, ist das schon ziemlich gut und du bist fertig.
Das, was du machst, ist Rumprobieren in willkürlichen Intervallschritten. Bei dem einen Polynom kann es mit 1000000 Intervallschritten klappen, bei dem anderen funktioniert es nur mit 1000001 Schritten und wieder ein anderes geht nur mit 523233 Schritten. Das liegt doch total in der Natur der Sache, dass du einfach die Funktion an 'n' Stellen samplest und hoffst, dort zwei Stellen mit unterschiedlichem Vorzeichen erwischt zu haben.
Besonders tückisch ist für deinen Algorithmus (und sowieso auch für Bisektion) das Polynom 25x⁴ - 50x³ + 35x² - 10x + 1, welches nämlich keine Vorzeichenwechsel besitzt. Die Nullstellen sind auch gleichzeitig Minima.
Um solche Polynome auch noch abzudecken, könntest du einfach das Ableitungspolynom bilden und dessen Nullstellen mit deinem Verfahren finden. Wenn du die hast, testest du einfach, ob das auch Nullstellen des ursprünglichen Polynoms sind.
 
JustusJonas93

JustusJonas93

Mitglied
Ich könnte doch auch sagen, wenn eine Nullstelle genau getroffen wird, soll das Vorzeichen des letzten Wertes von 0 auf 1 bzw. 1 auf 0 geändert werden. Dann habe ich bei der nächsten Abfrage einen gefakten Vorzeichenwechsel, also eine Nullstelle. Den Rest des Verfahren sollte das nicht beeinflussen.

LG
 
H

httpdigest

Top Contributor
Wenn du eine Nullstelle tatsächlich durch Zufall genau triffst, dann brauchst du hier nichts mehr fake-mäßig auf 0 oder 1 setzen. Dann hast du die Nullstelle doch bereits gefunden und kannst sie dir merken bzw. ausgeben.
Die Wahrscheinlichkeit ist aber sehr sehr gering, dass durch das Sampling die Nullstelle tatsächlich genau (genug) getroffen wird. Hängt von der Schrittweite, der Steigung des Polynoms an der Stelle und von dem erlaubten Fehler (Epsilon) ab.

Also, wie gesagt: um Nullstellen vom Grad 2*n für n=1,2,3... zu finden (bzw. Extremstellen der Funktion) könntest du die ganz einfache Ableitung des Polynoms bilden (sehr sehr einfach) und hierauf dann dein Verfahren anwenden und anschließend bei den dort gefundenen Nullstellen prüfen, ob dies auch (näherungsweise) Nullstellen der eigentlichen Funktion sind.
 
H

httpdigest

Top Contributor
Desweiteren:
Java: 
int q =10000000;
int[] Vorzeichen = new int[q];
Wieso?
Du brauchst doch niemals Zugriff auf alle Vorzeichen aller gesampelten Stellen der Funktion. Dich interessiert immer nur die letzte Stelle und die aktuelle ausgewertete Stelle. Hier brauchst du also nicht Megabytes an integers zu alloziieren sondern eigentlich nur zwei Variablen, die du fortschreibst.
 
JustusJonas93

JustusJonas93

Mitglied
Werde das die Tage mal ausprobieren, danke.

LG
httpdigest hat gesagt.:
Desweiteren:
Java: 
int q =10000000;
int[] Vorzeichen = new int[q];
Wieso?
Du brauchst doch niemals Zugriff auf alle Vorzeichen aller gesampelten Stellen der Funktion. Dich interessiert immer nur die letzte Stelle und die aktuelle ausgewertete Stelle. Hier brauchst du also nicht Megabytes an integers zu alloziieren sondern eigentlich nur zwei Variablen, die du fortschreibst.
Zum Vergrößern anklicken....
Das stimmt wohl.
 
JustusJonas93

JustusJonas93

Mitglied
Ich habs mal auf die schnelle getestet, aber er findet bei der Ableitung auch keine Nullstellen.. :(

Javascript: 
package Berechnung;

public class Bisektion {
    
    public static void main (String[]args){

        //Polynom
        double[] p={1,-10,35,-50,25};
        
        //Intervall
        double a=-50;
        double b=50;
        
        double m;
        double x;
        double y;
        double u;
        int q =10000000;
        
        int[] Vorzeichen = new int[q];     // Speicher für Vorzeichen
        
            
            // m festlegen
            
            if(a<0 && b<0){
                m=(Math.abs(b)-Math.abs(a))/q;
                m=Math.abs(m);
            }else{
                m=(b-a)/q;
            }
            System.out.println(m);
            
            y= Polynom.Fwert(p, a);
            System.out.println(y);
            
            if(y<0){                        // Anfangsfeld wird festgelegt
                Vorzeichen[0]=1;
            }else{
                Vorzeichen[0]=0;
            }
            System.out.println(Vorzeichen[0]);
            
            int j=1;              // Schleife für Feld 1-q
                
            for(u=a+m; u<b; u=u+m){               // Läuft alle q Intervalle ab
                x= Polynom.Fwert(p, u);
                    if(x<0){
                        Vorzeichen[j]=1;          // wenn negativ
                    }else if(x>0){ 
                        Vorzeichen[j]=0;          // wenn positiv
                    }else{
                        System.out.println(u);
                        Vorzeichen[j]=Vorzeichen[j-1];
                        //if(Vorzeichen[j-1]==0){
                            //Vorzeichen[j]=1;
                        //}else{
                            //    Vorzeichen[j]=0;
                            //}
                        }
                    }
                    if(Vorzeichen[j]!=Vorzeichen[j-1]){    // Vorzeichenvergleich
                        System.out.println(u);
                    
                    j++;
                    }
                    double m2;
                    double x2;
                    double y2;
                    double u2;
                    
            double[] s=Polynom.Ableiten(p);
            
            y2 = Polynom.Fwert(s, a);
            if(y<0){                        // Anfangsfeld wird festgelegt
                Vorzeichen[0]=1;
            }else{
                Vorzeichen[0]=0;
            }
            int i=1;              // Schleife für Feld 1-q
            
            for(u2=a+m; u<b; u2=u2+m){               // Läuft alle q Intervalle ab
                x= Polynom.Fwert(p, u);
                    if(x<0){
                        Vorzeichen[i]=1;          // wenn negativ
                    }else if(x>0){ 
                        Vorzeichen[i]=0;          // wenn positiv
                    }else{
                        System.out.println(u2);
                        Vorzeichen[i]=Vorzeichen[i-1];
                        }
                    }
                    if(Vorzeichen[i]!=Vorzeichen[i-1]){    // Vorzeichenvergleich
                        System.out.println(u2);
                    
                    i++;
                    }
    
            }
        }
 
H

httpdigest

Top Contributor
Das hier sieht noch falsch aus: `for(u2=a+m; u<b; u2=u2+m){`
Und fange vielleicht mal an, Codeteile in Methoden auszulagern. Das wird ja langsam eine einzige Spaghetticode-Katastrophe. :)
 
JustusJonas93

JustusJonas93

Mitglied
Ja stimmt, aber daran hats nicht gelegen. Ich habe grade mal die Ableitung von Hand berechnet und direkt schon als Polynom gemommen und da findet er auch keine Nullstellen. :/
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
U Brauche Hilfe bei Bisektionsverfahren Java Basics - Anfänger-Themen 23
J Problem mit Bisektionsverfahren Java Basics - Anfänger-Themen 1
M Bisektionsverfahren (Mathematische Funktion) Java Basics - Anfänger-Themen 6

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben