knigechka: Метод поиска минимума функции одной переменной с использованием кубичной аппроксимации

Пусть функцию f(x) можно аппроксимировать полиномом третьего порядка. Тогда произвольно выбираем точку х₁ и находим другую точку х₂, такую, что производные f¢(x₁) и f¢(x₂) в этих точках имеют различные знаки. При этом стационарная точка , в которой , будет находиться на отрезке [x₁, x₂].

Аппроксимирующий кубичный полином j(х) будет иметь вид [9]:

(36)

Коэффициенты уравнения (36) подбираются таким образом, чтобы значения j(х) и ее производной в точках x₁ и x₂ совпадали со значениями f(x) и f¢(x) в этих точках. Первая производная полинома j(х) имеет вид

.(37)

Значения коэффициентов а₁, а₂ и а₃ уравнения (36) вычисляются по известным значениям f(x₁), f(x₂), f¢(x₁) и f¢(x₂) путем решения рекурсивным методом системы следующих линейных уравнений

(38)

После того, как коэффициенты а₁, а₂, а₃ найдены, оценка координаты стационарной точки функции f(x) производится с помощью аппроксимирующего полинома (36). Приравнивание к нулю производной (37) приводит к квадратному уравнению. В результате решения квадратного уравнения получаем следующую формулу для оценки координаты стационарной точки полинома

(39)

где

(40)

(41)

(42)

В результате получаем точку , расположенную между х₁ и х₂. Затем снова выбираются две точки для реализации процедуры кубичной аппроксимации - и одна из точек х₁ и х₂, причем значения производной функции f(x) в этих точках должны быть противоположны по знаку. Описанная процедура повторяется до тех пор, пока не будет достигнута заданная точность оценки координаты точки х^* экстремума функции f(x).

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

1 Вычислить значение производной в начальной точке х₀. Если значение < 0, вычислить х_k+1= x_k +2^kD для k = 0, 1, …. Если > 0, вычислить х_k+1= x_k -2^kD для k = 0, 1, ….