Вещественный двоичный поиск
Вещественный двоичный поиск - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
Формулировка задачи
Пусть нам задана монотонная функция. Необходимо найти место, где значение функции становится меньше, чем какое-то заданное значение.
Решение задачи
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
Способы закончить поиск
- Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
- Алгоритм с большой точностью найдет значение аргумента
- Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
- Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон.
- В отличии от предыдущего, не зацикливается при больших значениях функции.
- Возможна большая погрешность, если функция будет очень медленно возрастать
- Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних по представлению значения в типе данных. Утверждается, что два числа - соседние, если середина их отрезка совпадает или с левой, или с правой границей.
- Возможно плохое поведение, если искомый аргумент равен 0.
- Итеративный способ. В этом способе выполниться только конечное число число итераций.
- Плюсом этого способа является фиксированная погрешность.
