Метод деления отрезка пополам (метод дихотомии)

Рассмотрим поиск максимума в данном случае на отрезке АВ (рис. 2):

Рисунок 2 — Графическое представление метода деления отрезка пополам Алгоритм:

Делим отрезок АВ пополам точкой L и рассчитываем в точке L значение функции F (L).

Выбираем малое приращение или () и откладываем его влево или вправо от точки L и рассчитываем в точке Р значение функции.

Сравниваем значения функций F (L) и F (Р): если F (L)>F (Р), то максимум может находиться в левой части отрезка.

Отбрасываем ту часть отрезка, где максимума нет (в данном случае правую) и переносим точку В в точку Р или L.

Получили отрезок АВ. Алгоритм повторяется.

Новый отрезок АВ делится пополам. Если F (L).

Вновь переносим точку, А в L и повторяем процедуру деления отрезка пополам.

Процедура продолжается до тех пор, пока не выполнится заданное условие:

.

Метод «Золотого сечения»

Поиск оптимума основан на делении отрезка на 2 части, при этом отношение длины всего отрезка к большей его части равно отношению большей части к меньшей:

— точка «Золотого сечения».

Рассмотрим поиск оптимума максимума методом «Золотого сечения».

Делим отрезок АВ слева и справа в отношении «Золотого сечения». Получаем точки L и Р (рис.3). Рассчитываем значения функций в точках L и Р и сравниваем их.

Рисунок 3 — Графическое представление метода «Золотого сечения».

Если F (L) > F (P), то максимум может находиться либо на участке АL, либо LP на участке PB максимума быть не может, если функция унимодальна.

Отбрасываем PB и переносим точку В в точку Р. Получаем новый отрезок АВ.

На новом отрезке уже есть точка L точка «Золотого сечения».

Процедура поиска продолжается до тех пор, пока не выполнится условие: