查找零點的算法

Question

我有以下挑戰：

實現一個函數，在a和b之間的間隔中搜索正弦函數的零點。搜索間隔[下限，上限]應該減半，直到下限和上限小於0.0001。

1. 找到一個條件來決定搜索必須繼續進行的時間。所以在將時間間隔分成兩個時間間隔後，我們必須選擇一個以進行搜索。

2. 我們假設在a和b之間的間隔中只有一個零點。

我用點1掙扎我已經對話題，幫了我很多的一些問題，但現在我要實現它在Java中，但還沒有成型。

這是到目前爲止我的代碼：

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; 
    } 

我試着用遞歸來實現，但也許一個其他的方式會更好，我不知道。 任何想法？

Answer 1

不同的跡象，如果有A和B之間只有一個零點段，這意味着符號（SIN（A））！=符號（SIN（B））。在你的中點更換或B，你需要確保這仍然是做這樣的情況：定義爲

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

Answer 2

你幾乎是正確的。你選擇的時間間隔基於符號變化 - 如果綁定的間隔的左側和右側的符號變化，您可以選擇間隔：

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; 
    } 

還要注意功能可能與x軸多次在給定間隔。然後這個符號可能會在兩個時間間隔內發生變化，這個函數只會選擇正確的一個（中間到b），您將失去一些解決方案。

Answer 3

既然有至多一個零交叉在我們考慮的間隔，有三種可能性：

1. 零點在左半
2. 零點在右半
3. 的平分是零點。

如果平分點是零點，就完成了。

否則，包含過零點的段在其端點上必須具有不同的符號。

遞歸上有其端點

Answer 4

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

用符號（X）給出x在[a，b]區間內（a < = x < = b）我們可以說應用程序f：[a，b] - > R在[a，b]上有一個根，也就是說，有限區間[a，b]滿足f（x）= o當且僅當f（a）* f（b）< 0.

簡而言之，間隔上的根是該間隔上功能改變的標誌。

爲了找到這一點，我們將使用間隔的二進制分區。

，因爲它遵循我會修改這個代碼：

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); 
     } 
    }