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