Алгоритм нахождения нулевой точки

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

Поскольку в рассматриваемом нами интервале не более одного пересечения нуля, существует три возможности:

1. Нулевая точка находится в левой половине
2. Нулевая точка находится в правойполовина
3. деление пополам - это нулевая точка.

Если точка деления пополам - это нулевая точка, вы закончили.пересечение нуля должно иметь разные знаки на своих конечных точках.

Рекурсировать в сегменте с разными знаками на конечных точках

Answer 2

Если есть только одна нулевая точка между 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; }

Answer 3

учитывая x в [a, b] расширенном интервале (a <= x <= b), мы можем сказать, что приложение f: [a, b] -> R имеет корень на [a, b], т.е. x в ограниченном интервале [a, b], который удовлетворяет f (x) = o тогда и только тогда, когда f (a) * f (b) <0. </p>

Проще говоря, на интервале есть корень - знак изменения функции на этом интервале.

Чтобы найти эту точку, мы использовали бы двоичное разбиение интервала.

Я бы изменил этот код следующим образом:

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

Answer 4

Вы почти правильно поняли.Вы выбираете интервал на основе изменения знака - если знак изменяется между левой и правой границами интервала, вы выбираете этот интервал:

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), и вы потеряете некоторые решения.