Поиск минимума функции на основе дихотомического подхода (метод половинного деления). Дроби Фибоначчи. Метод золотого сечения

1) Метод половинного деления.

Имеется интервал минимизированной функции. Известно значение функции по концам интервала. Делим интервал на два равных участка (рисунок 3).

Рисунок 3

; ; ; .

Если ; , то , тогда получим новый интервал .

Определение значения функции с одинаковым знаком.

Если и , то и тогда интервал будет постепенно сужаться.

Деление отрезков пополам резко снижает количество вычислений целевой функции, но ещё более заметное снижение будет, если этот отрезок делить в соответствии с методом Фибоначчи (метод золотого сечения).

2) Метод золотого сечения.

Для данного метода используют формулы Фибоначчи.

; .

.

.

Соотношение интервала, в котором находится корень, называется золотым.

В данном случае поиск минимумов заданных направлений ведётся с помощью указанных выше дробей.

С шагом и из четырёх значений функции находится самое большое, тем самым минимум уменьшается до при этом: ,

Суженный интервал делится в таком соотношении и выявляется наибольшее из четырёх значение. При постоянном сужении интервала мы определяем интервал локализации экстремума и рассматриваем его от начальной точки до экстремума.