Бинарный поиск по производной

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

Так мы только что научились находить корень непрерывной функции, у которой мы знаем значение меньше и больше 0. Но можно ли найти с помощью бинарного поиска локальный максимум функции? Можно!

Как известно, локальный максимум функции $f$ - это просто такое $x_0$, что для всех близких к нему $x$ значения $f(x) < f(x_0)$. Для непрерывных функций выполняется более крутая вещь: слева от максимума функция возрастает, а справа от максимума функция убывает. Так это как раз отличное условие для нашего вещественного бинарного поиска!

Если вы знаете $x_1$ такое, что в его окрестности f(x) возрастает, и $x_2$ такое, что в его окрестности f(x) убывает, то можно запустить между ними бинпоиск и найти точку $x_0$ такую, что слева от нее возрастает значение функции, а справа - убывает. Это и есть локальный максимум.

А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает.

Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!(очень-очень - точка на расстоянии $\epsilon < 10^{-6}$



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

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