Бинарный поиск с вещественными числами

Материал из Algocode wiki
Версия от 13:20, 26 сентября 2019; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Бинарный поиск с вещественными числами

У нас все еще есть функция f(x), которая сначала равна 0, а потом равна 1, и мы хотим найти это место, где она меняет значение. Но теперь аргумент функции - вещественное число. Например:

  • $f(x) = 1$, если $x^2 > 2$
  • $f(x) = 0$, если $x^2 \leq 2$

Понятно, что при $x = \sqrt 2$ $f(x) = 0$, а при любом даже немного большем значении $f(x) = 1$. Если мы научимся решать такую задачу, то мы научимся находить корень из двух!

Увы, возникает проблема: действительные числа хранятся в компьютере неточно

Тем более не сможем найти точное значение $\sqrt 2$, потому что это бесконечная непериодическая дробь. Так что давайте снова воспользуемся бинарным поиском, причем всегда $f(left) = 0$, $f(right) = 1$, и мы остановимся тогда, когда left и right будет очень-очень близко.

И тут снова возникает проблема. Помимо того, что бесконечную дробь в принципе невозможно точно хранить в компьютере, ещё и арифметические операции понижают эту точность. Поэтому, чтобы явно не использовать разность между правым и левым указателем, можно задать фиксированное число шагов, которое будет выполняться.

Так как мы знаем, что двоичный поиск работает за двоичный логарифм, можно сказать, что на угадывание десятичного разряда числа потребуется примерно три шага бинпоиска (т. к. $\log 10 \approx 3 $). Значит, например, если нам нужно посчитать значение функции до шести знаков после запятой, то нам нужно ещё примерно 18 шагов уже после того, как расстояние между left и right достигло одного.

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

long double left = 0.0; // 0^2 < 2, а значит f(0) = 0
long double right = 10.0; // 10^2 > 2, а значит f(10) = 1
for (int i = 0; i < 100; i++) {
    long double middle = (left + right) / 2 // теперь деление не нацело, а вещественное
    if (middle * middle > 2) {
        right = middle;
    }
    else {
        left = middle;
    }
}

Вот мы и нашли корень из 2 с достаточно высокой точностью.

На самом деле, так можно искать ноль любой непрерывной функции (мы сейчас искали ноль функции $x^2 - 2$), у которой вы знаете значение меньше нуля и значение больше нуля.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin