algorithme pour trouver un point zéro

Question

j'après la provocation:

implémenter une fonction qui recherche un point nul de la fonction de sinus dans un intervalle entre a et b. L'intervalle de recherche [limite inférieure, limite supérieure] doit être réduit de moitié jusqu'à ce que la limite inférieure et la limite supérieure soient à moins de 0,0001 l'une de l'autre.

1. Trouvez une condition pour décider dans quel intervalle divisé par deux la recherche doit être poursuivie. Donc, après avoir coupé l'intervalle en deux intervalles, nous devons en choisir un pour poursuivre notre recherche.

2. Nous supposons qu'il y a juste un point zéro dans l'intervalle entre a et b.

Je me bats avec le point 1. J'avais déjà quelques questions sur ce sujet qui m'a beaucoup aidé, mais maintenant je dois la mettre en œuvre en Java, mais il ne fonctionne pas encore.

Voici mon code à ce jour:

private static double nullstelle(double a, double b){ 
     double middle = (a + b)/2; 
     double result = middle; 

     if(Math.abs(a-b) > 0.0001){ 
      double sin = Math.sin(middle); 
      if(sin > 0){ 
       result = nullstelle(a, middle); 
      }else{ 
       result = nullstelle(middle, b); 
      } 
     } 
     return result; 
    } 

J'ai essayé de mettre en œuvre à l'aide récursion, mais peut-être une autre façon serait mieux, je ne sais pas. Des idées?

Answer 1

S'il y a juste un point zéro entre a et b, ce qui signifie signe (sin (a))! = Signe (sin (b)).En remplacement d'un ou b avec votre point milieu, vous devez vous assurer que cela reste le cas en faisant quelque chose comme ceci:

if (sign(sin(a)) == sign(sin(middle))) 
    result = nullstelle(middle, b); 
else 
    result = nullstelle(a, middle); 

avec le signe (x) définie comme

int sign(double x) { return x >= 0 ? 1 : -1; } 

Answer 2

Vous l'avez presque compris. Vous choisissez l'intervalle en fonction du changement de signe - si le signe des changements entre la gauche et la droite liée de l'intervalle, vous choisissez cet intervalle:

private static double nullstelle(double a, double b){ 
     double middle = (a + b)/2; 
     double result = middle; 

     if(Math.abs(a-b) > 0.0001){ 
      double sin = Math.sin(middle); 
      if(sin == 0) { // Rare case but might happen 
       result = middle; 
      } else if (Math.signum(sin) != Math.signum(b)) { // The sign changes between middle and b 
       result = nullstelle(middle, b); 
      } else if (Math.signum(sin) != Math.signum(a)) { // The sign changes between a and middle 
       result = nullstelle(a, middle); 
      } else { 
       // Throw an exception here, the sin function does not cross x axis in the given interval 
      } 
     } 
     return result; 
    } 

Notez également que la fonction pourrait traverser l'axe X fois plus dans le intervalle donné. Alors le signum peut changer dans les deux intervalles et cette fonction choisira seulement la bonne (au milieu de b) et vous perdrez certaines des solutions.

Answer 3

Comme il est au plus un passage à zéro dans notre intervalle considéré, il y a trois possibilités:

1. point zéro est dans la moitié gauche
2. point zéro est dans la moitié droite
3. Le La bissection est le point zéro.

Si le point de bissection est le point zéro, vous avez terminé. Dans le cas contraire, le segment qui contient le passage à zéro doit avoir des signes différents sur ses points d'extrémité.

Recurse sur le segment qui a des signes différents sur ses points d'extrémité

Answer 4

donné x dans [a, b] intervalle abondant (a < = x < = b) on peut dire qu'une application f: [a, b] -> R a une racine sur [a, b] c'est-à-dire qu'il y a un x dans le intervalle borné [a, b] qui satisfait f (x) = o si et seulement si f (a) * f (b) < 0.

En mots simples, il y a une racine sur l'intervalle est le signe des changements de fonction sur cet intervalle. Pour trouver ce point, nous utiliserions le partitionnement binaire de l'intervalle.

Je modifier ce code comme suit:

private static double nullstelle(double a, double b){ 
     double middle = (a + b)/2; 

     if(Math.abs(a-b) < 0.0001){ 
      return middle; 
     } 
     if(Math.sin(a)*Math.sin(middle)<0) { 
      return nullstelle(a, middle); 
     } 
     if(Math.sin(middle)*Math.sin(b)<0) { 
      return nullstelle(middle, b); 
     } 
    }