Лекция: Метод дихотомии (метод деления отрезка пополам)
Метод дихотомии применяется только для унимодальной функции. В этом методе сравнение значений целевой функции 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
k | Новый отрезок | |||
3.12125 | 3.1325 | 14.76888 | 14.77315 | правая |
3.308125 | 3.318125 | 14.81418 | 14.81458 | правая |
3.401562 | 3.411563 | 14.81019 | 14.80874 | левая |
3.354844 | 3.364844 | 14.81435 | 14.81382 | левая |
3.331484 | 3.341485 | 14.81481 | 14.81475 | левая |
3.319805 | 3.329805 | 14.81463 | 14.8148 | правая |
3.325644 | 3.335645 | 14.81476 | 14.81481 | правая |
=3.333565 = 14.81481 |