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

Метод основан на делении текущего отрезка [ а, b ],где содержится искомый экстремум, на две равные части с последующим выбором одной из половин, в которой находится максимум в качестве следующего текущего отрезка. Экстремум определяется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на ε/2,

Если R (x + ε /2) > R (x - ε/2), то максимум располагается на пра­вой половине текущего отрезка [а, b ],в противном случае — на левой.

Процесс поиска завершается при достижении отрезком [а, b ] величины заданной погрешности ε.

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

Рис. 3.2 Иллюстрация метода половинного деления:

1 — ин­тервал, включающий в себя искомый максимум функции после

первого этапа (первого деления пополам);

2, 3 — то же соответственно после вто­рого и третьего этапов

На рис. 3.2 приведены три этапа метода половинного деле­ния. Сплошными вертикальны­ми линиями отмечены середины отрезков, а пунктирными — вы­числяемые значения критерия оптимальности слева и справа на ε/2 от середин.

Существует и другой вари­ант алгоритма, заключающийся в следующем. После нахожде­ния середины отрезка (напри­мер, точка с ₁) в одной из полови­нок (допустим, в левой) находят среднюю точку (точка с ₂) и, срав­нивая значения функции в этих точках, определяют, в какой из половинок находится экстремум. Если R (с ₁) < R (с ₂), то в качестве следующего отрезка выбираем отрезок [ а, с ₁ ], если же R (с ₁) > R (с ₂), то берут новую точку в середине правой половины (точка с ₃) и в ней вычисляют функцию. В зависимости от сравнения зна­чений функции в точках с ₃ и с ₁ выбирают новый отрезок [ с ₁, b ] или [ с₂,с₃ ] и т.д.

Второй вариант метода не имеет с точки зрения эффективно­сти принципиального отличия от первого, так как эффективность принято оценивать по наихудшему варианту (т.е. по двум вычис­лениям f(x) на каждом шаге). В первом варианте метода есть одна особенность, которая его делает очень эффективным при экспериментальном отыскании экстремума (например, при авто­матической настройке технических систем). Малые отклонения от текущей точки обеспечивают в процес­се поиска отсутствие "шараханий", сопровождающихся резкими отклонениями состояния системы.