1.7. Метод средней точки.

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

Рассмотрим метод средней точки, который называется также методом бисекции или методом деления отрезка пополам.

Пусть f(x) – унимодальная, непрерывно дифференцируемая на отрезке [a, b] функция и на этом отрезке точка x^* является единственной стационарной точкой. Сведем задачу нахождения минимума функции f(x) к решению нелинейного уравнения

f ^'(x) = 0. (1.14)

Положим a₀ = a, b₀ = b.

Так как функция f ^'(x) удовлетворяет условию (1.14), то она принимает на концах отрезка [a₀, b₀] значения разных знаков, т.е.

f(a₀)f(b₀) < 0.

Разделим отрезок [a₀, b₀] пополам. Получим точку x₀ = . Вычислим f ^'(x₀). Если f ^'(x₀) = 0, то x₀ – искомый корень, и задача решена. Если f ^'(x₀)  0, то f ^'(x₀) – число определенного знака: f ^'(x₀) > 0, либо f ^'(x₀) < 0. Тогда либо на концах отрезка [a₀, x₀], либо на концах отрезка [x₀, b₀] значения функции f ^'(x) имеют разные знаки. Обозначим такой отрезок [a₁, b₁]. Очевидно, что x^* [a₁, b₁], и длина отрезка [a₁, b₁] в два раза меньше, чем длина отрезка [a₀, b₀]. Поступим аналогично с отрезком [a₁, b₁]. В результате получим либо корень x^*, либо новый отрезок [a₂, b₂], и т.д. (рис.1.4 ).

Рис. 1.4

Середина n-го отрезка x_n = . Очевидно, что длина отрезка [a_n, b_n] будет равна , а т. к. x^* [a_n, b_n], то

| x_n – x^*|   . (1.15)

Оценка (1.15) характеризует погрешность метода средней точки и указывает на скорость сходимости: метод сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/2.

Если задана требуемая точность  , то процесс вычислений следует закончить, когда выполнится условие  f ^'(x_n)  , после чего полагают x^*  x_n.

Алгоритм 1.5 (Алгоритм метода средней точки).

Шаг 1. Ввести исходные данные: a, b, .

Шаг 2. Определить x₀ = .

Шаг 3. Вычислить f ^'(x₀).

Шаг 4. Проверить критерий окончания вычислений. Если f ^'(x₀)  , , перейти к шагу 6, иначе – к шагу 5.

Шаг 5. Перейти к новому отрезку локализации [a, b]. Если f ^'(x₀) > 0, то положить b = x₀. Иначе положить a = x₀. Перейти к шагу 2.

Шаг 6. Положить x^*  x₀. Вычислить f^'(x^*).

Пример 1.6.

Методом средней точки решим задачу, рассмотренную ранее:

f(x) = x⁴ + e ^{- x}  min, x  [0, 1],  = 0.02.

Очевидно, что f ^'(x) = 4x³ – e ^–x.

Результаты вычислений приведены в табл. 1.7.

Таблица 1.7

Номер итерации	a	b	x0	f '(x0)	Знак f '(x0)
1 2 3 4 5	0 0.5 0.5 0.5 0.5	1 1.000 0.750 0.625 0.563	0.5 0.750 0.625 0.563 0.531	-0.107 1.215 0.441 0.142 0.012	– + + +

Вычисления прекращаются после 5-ой итерации, так как требуемая точность достигнута (0.012 < 0.02).

Таким образом, x^*  0.531 и f(x^*)  0.668.