Поиск экстремума унимодальной функции

Пусть известно, что целевая функция имеет только один экстремум на интервале a, b. Такая функция F=f(x) называются унимодальными. Определим значения ЦФ при X=x₁ и x₂. С точки зрения расположения экстремума (в примере – максимума) возможны три варианта:

F(x₁) < F(x₂) – максимум лежит в между x₂ и b.

F(x₁) = F(x₂) – максимум лежит между x₂ и x₁.

F(x₁) > F(x₂) – максимум лежит в между x₁ и a.

Это означает, что при выполнении первого условия на отрезке [x₁, b] не может находиться x_opt, следовательно, его можно исключить из дальнейшего рассмотрения. Если же выполняется третье условие, то на отрезке [a, x₂] не может находиться x_opt, следовательно, его можно исключить из рассмотрения. Выбирая новые x₂ и x₁ и последовательно повторяя анализ, сужаем область определения экстремума до любого разумного предела. Выбор значений x₂ и x₁ с учетом предыдущих результатов определяет различие методов последовательного поиска.

Например, метод половинного деления (дихотомии), когда пары x₂ и x₁ выбираются симметрично относительно центра текущего интервала, на расстоянии ±d от него, где d - некоторая константа. Если при прямом переборе эффективность поиска оптимума прямо пропорционально числу расчетов, то по методу дихотомии она возрастает с ростом итераций экспоненциально. Например, если при прямом переборе требуется 1000 расчетов для того, чтобы сузить зону поиска экстремума в N раз, то по методу дихотомии – только 20.