2.4. Метод касательных

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

Определение 4. Функция , определенная на отрезке , называется выпуклой на этом отрезке, если

(4)

при всех и всех .

Когда пробегает отрезок , точки

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

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

Наряду с выпуклыми функциями в оптимизационных задачах встречаются вогнутые функции.

Определение 5. Функция , определенная на отрезке , называется вогнутой на этом отрезке, если

при всех и всех .

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

Следующая теорема устанавливает связь между выпуклыми и унимодальными функциями.

Теорема 1. Если функция выпукла на и , , то она является унимодальной на отрезке .

Сформулируем критерии выпуклости для выпуклых функций.

Теорема 2. Для того, чтобы дифференцируемая функция на отрезке была выпуклой, необходимо и достаточно, чтобы ее производная не убывала на .

Теорема 3. Для того чтобы дважды дифференцируемая функция на отрезке была выпуклой, необходимо и достаточно, чтобы на .

Вывод. Для функции , удовлетворяющей условиям теорем 1-3, множество на . Поэтому для минимизации на применимы методы, рассмотренные ранее в п. 2.1-2.3. Однако, если значения функции и ее производной вычисляются достаточно просто, то здесь можно предложить более эффективный метод – так называемый метод касательных. Изложим этот метод.

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

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

. (5)

Из выпуклости функции следует:

а) если , то ; (6)

б) если , то ; (7)

в) если , , то . (8)

Соотношения (5)-(8) лежат в основе метода касательных. А именно, в случае:

а) вводим новые обозначения , и находим точку по формуле (5), заменив в этой формуле на , на ;

б) вводим новые обозначения , и находим точку по формуле (5), заменив в этой формуле на , на ;

в) условия , являются необходимыми и достаточными для того, чтобы .

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

Если условие в) выполнилось на шаге , то . Значит точку минимума мы нашли точно.

Если условие в) не выполнилось на шаге , то продолжаем итерационный процесс до тех пор, пока . Здесь число задано. Считаем, что значение найдено с заданной точностью . Заметим, что в начале вычислений нужно определить числа , , , , , .

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

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