Бинарный поиск по производной: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
(Новая страница: «Так мы только что научились находить корень непрерывной функции, у которой мы знаем знач...»)
 
Строка 7: Строка 7:
 
А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает.
 
А если функция выпуклая, то она вообще выглядит красиво: сначала возрастает, потом максимум, потом убывает.
  
Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!(очень-очень - точка на расстоянии $\epsilon < 1e-6$
+
Проблема только в одном: как по точке понять, в ее окрестности значение функции убывает или возрастает? Достаточно тыкнуть две точки очень-очень рядом с ней и сравнить их значения!(очень-очень - точка на расстоянии $\epsilon < 10^{-6}$

Версия 15:15, 20 сентября 2019

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

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

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

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

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