Бинарный поиск по производной: различия между версиями
Глеб (обсуждение | вклад) (Новая страница: «Так мы только что научились находить корень непрерывной функции, у которой мы знаем знач...») |
Глеб (обсуждение | вклад) |
||
(не показана 1 промежуточная версия этого же участника) | |||
Строка 7: | Строка 7: | ||
А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает. | А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает. | ||
− | Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!(очень-очень - точка на расстоянии $\epsilon < | + | Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!(очень-очень - точка на расстоянии $\epsilon < 10^{-6}$ |
+ | |||
+ | {{Автор|Глеб Лобанов|glebodin}} |
Текущая версия на 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