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

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

Интервал неопределенности [ a, b ] делится пополам и вычисляются координаты двух точек, симметрично расположенных относительно середины интервала [ a, b ] на расстоянии : и . В этих точках вычисляются значения целевой функции и , а затем проверяется условие < (при поиске минимума). Если оно выполняется, полагают и из дальнейшего рассмотрения исключается интервал . Если же условие не выполняется полагают и из дальнейшего рассмотрения исключается интервал . Затем для нового интервала неопределенности проверяем условие , где – заданная погрешность вычислений. Если условие выполняется, т.е. длина интервала неопределенности стала меньше заданной погрешности, то вычисляются координата точки оптимума и значение целевой функции в этой точке. Если же условие не выполняется, тогда интервал неопределенности делится снова пополам и вычисляются новые значения точек и симметрично расположенных относительно середины нового интервала неопределенности и выполняется операция сравнения значений целевой функции в этих точках и и т.д.

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

В отличие от метода сканирования, в котором эффективность поиска прямо пропорциональна числу расчетов, в методе дихотомии эффективность возрастает с ростом числа шагов n экспоненциально. Интервал, в котором находится оптимум, после n шагов определяется из соотношения , где – первоначальный интервал исследования.

На рис. 3.13 приведена блок-схема метода дихотомии.

Рис. 3.13. Блок-схема метода дихотомии

Пример 3.3. Найти максимум функции на интервале [ 2,5 ] c точностью вычисления e=0.01.

Решение. Вычисляем координаты середины отрезка = 3.5, точек = = 3.495 и = =3.505, а затем и значения функции
в этих точках =14.7891, =14.78585. Следовательно, максимум функции находится в левой половине интервала, поэтому для дальнейшего рассмотрения выбираем отрезок [2, 3.505]. Середина этого нового отрезка = 2.7525, а = 2.7475 и = 2.7575. Значения целевой функции
= 14.45151 и = 14.46414, т.е. максимум функции находится в правой половине интервала и новый отрезок [2.775, 3.505]. В табл. 3.13 приведены результаты всех последующих этапов вычислений, указаны номер итерации k, координаты точек разбиения , и значения функции в этих точках , и часть интервала (левая или правая), которая выбирается для дальнейшего разбиения.

Максимум функции = 14.81481 в точке = 3.333568 методом дихотомии был получен за 9 вычислений.

Таблица 3.13