Метод парабол

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

Пусть дифференцируемая функция унимодальна на отрезке .

Определение 2. Назовём тройку чисел выпуклой тройкой для функции , если и

, . (1)

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

. (2)

Полученная точка принимается за приближенное значение минимума функции .

Удобно, когда в этом методе узлы –равноотстоящие, то есть , где . В этом случае из формулы (2) получаем

.

Если полученное приближение – недостаточно точное, то процесс может быть продолжен для новой выпуклой тройки, которая находится с использованием точки . Имеются различные ва-рианты построения новой выпуклой тройки. С одним из них мы познакомимся ниже.

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