Глава 2. Методы минимизации функции одной переменной

 

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

 

Для минимизации унимодальных функций применяются методы, не требующие вычисления производных. Наиболее простой из них – метод деления отрезка пополам. Он заключается в том, что, взяв некоторое достаточно малое положительное число d, определяют точки c и d следующими равенствами [7]

,                           (1)

Затем вычисляют значения ,  и сравнивают между собой. Если

1) , то полагают ,

2) , то полагают ,

Из определения унимодальной на  функции следует, что точка локального минимума  функции  расположена на отрезке . Заменив в равенствах (1) a на a1, b на b1, вычислим точки c1, d1. Затем в найденных точках находим значения функции , которые опять сравниваются между собой.

Если повторить подобные операции n раз, то найдем отрезок  длины , на котором расположена точка . Полагая , получим, что погрешность определения точки   не будет превышать числа . Число  принимается за минимальное значение функции  на  .

Метод относится к последовательным стратегиям и позволяет исключить из дальнейшего рассмотрения на каждой итерации в точности половину текущего интервала неопределенности. Условия окончания поиска стандартные: поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины.

Для метода деления отрезка пополам характеристика относительного уменьшения начального интервала неопределенности находится по формуле  , где N - количество вычислений функций.

Замечания.

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

2. Если задана величина  , то требуемое для достижения желаемой точности количество вычислений функции находится как наименьшее целое, удовлетворяющее условию

.

3. Текущие интервалы имеют четные номера  L0, L2, L4,..., где индекс указывает на сделанное количество вычислений функций.

Пример 1. Найти минимум функции  .

Решение. Решение будем выполнять по следующим шагам:

10. Зададим начальный интервал неопределенности   (см. пример 2 п. 1.3). Пусть l = 1.

20. Положим k = 0.

30. Вычислим

,   ,   .

40.Вычислим

;   ;

50. Сравним  и . Так как   < , то положим  .

70. Получим 

Переходим к шагу 4.

41. Вычислим

; ;

 

51. Сравним   и    = .

Так как  , то перейдем к шагу 6.

61. Сравним    и   = .

Так как  , то положим

 

71. Получим    Положим  Переходим к шагу 4.

42. Вычислим

;

 

52. Сравним   и   = .

Так как  , то перейдем к шагу 6.

62. Сравним   = .

Так как  , то положим

72. Получим   Положим  Переходим к шагу 4.

43. Вычислим

;

; 

53. Сравним   и    = .

Так как , то перейдем к шагу 6.

63. Сравним    и   = .

Так как  , то положим

 

73. Получим   Поэтому    В качестве решения можно взять среднюю точку последнего интервала  .

Первые итерации поиска приведены на рисунке 2:

 

Рис. 2. Первые итерации поиска