代码之家 › 专栏 › 技术社区 › DarkLeafyGreen

寻找零点的算法

iteration recursion algorithm java

-2

DarkLeafyGreen · 技术社区 · 14 年前

我面临以下挑战:

实现在A和B之间的间隔内搜索窦性功能零点的功能。搜索间隔[下限,上限]应减半,直到下限和上限彼此之间的距离小于0.0001。

找到一个条件来决定搜索必须在哪个半间隔内继续。因此,在将时间间隔缩短为两个时间间隔之后,我们必须选择一个时间间隔来继续搜索。
我们假设A和B之间的区间只有一个零点。

alt text

我正在努力解决第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;
    }

我尝试使用递归实现,但也许另一种方法更好,我不知道。有什么想法吗?

4 回复 | 直到 14 年前

Luke Hutteman 14 年前

如果A和B之间只有一个零点,那就意味着符号(sin(a))!=符号(sin(b))。在用中点替换A或B时,您需要通过这样做来确保情况仍然如此:

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

符号(x)定义为

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

Ari Gesher 14 年前

由于我们考虑的区间内最多有一个零交叉点,因此有三种可能性:

零点在左半部分
零点在右半
平分是零点。

如果平分点是零点,你就完了。

否则,包含零交叉的段的端点上必须有不同的符号。

在其端点具有不同符号的段上重复

Karel Petranek 14 年前

你差一点就答对了。根据符号更改选择间隔-如果符号在间隔的左右边界之间更改,则选择该间隔:

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),您将失去一些解决方案。

Daniel Voina 14 年前

给定[a,b]丰富区间中的x(a<=x<=b),我们可以说应用程序f:[a,b]->r在[a,b]上有根,即有界区间[a,b]中有一个x满足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);
        }
    }