2.5. Метод ломаных

Говорят, что функция  удовлетворяет на отрезке   условию Липшица, если существует такое число  (константа Липшица), что

                       (9)

для всех  .

Для проверки условия Липшица на практике используют следующий факт: если функция  имеет на отрезке ограниченную производную, то она удовлетворяет условию (9), где .

Метод ломаных является последовательным методом, рассчитанным на минимизацию произвольных (но обязательно унимодальных) функций, удовлетворяющих условию Липшица.

Пусть функция  удовлетворяет на  условию Липшица с константой L. Опишем метод ломаных для минимизации функции  [7] .

Положим

и реализуем следующую схему вычислений:

Шаг 1. Вместо пары чисел  образуем две новые пары  и  следующим образом:

где

Шаг 2. Из полученных двух пар  и  выберем ту, у которой вторая компонента минимальна. Обозначим её  и исключим из рассмотрения множества (очевидно; на данном шаге в качестве  можно взять любую из пар  и . Вместо пары  добавляем две новые пары  и , компоненты которых находятся по формулам

где

В результате получим множество, состоящее из трех пар чисел

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

      (10)

где

Полагая , получим приближенное решение задачи минимизации. Точность определения  характеризуется неравенствами .

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

Рис. 5. Метод ломаных

Пример 5. Методом ломаных найти минимум  функции  на отрезке [10; 15] с точностью 0,01 и точку минимума  .

Функция  дифференцируема на указанном отрезке. Так как

при , то  удовлетворяет условию Липшица с константой  L = 0,11.

Найдя , продолжим вычисления, используя соотношения (10). Результаты вычислений представим в таблице 2.

Таблица 2.

Метод ломаных

Из таблицы находим . Отметим, что Q = [10; 15], т.е. не является унимодальной функцией, поэтому из методов минимизации в данном случае применим только метод ломаных.