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

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

(32)

совпадут со значениями функции f(x) в трех указанных точках. Для этого вычислим значение j(x) в трех заданных точках.

Так как , получаем . Поскольку получаем . При имеем или

(33)

Если точность аппроксимации функции f(x) на отрезке [x₁, x₂] квадратичным полиномом оказывается достаточно высокой, то построенный полином далее используется для оценивания координаты точки минимума функции f(x).

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

. (34)

Тогда для оценки координаты точки минимума функции f(x) получаем формулу

(35)

Приведем описание алгоритма метода последовательного оценивания с использованием квадратичной аппроксимации, разработанного Пауэллом [4].

1 Пусть f(x) – оптимизируемая функция, х₁ – начальная точка, Dх – величина шага по оси абсцисс. Вычислить х₂ = х₁+Dх и значения функции f(x₁) и f(x₂).

2 Если f(x₁) >f(x₂), то положить х₃ = х₁ +2 Dх. Если f(x₁) £ f(x₂), то положить х₃ = х₁ -Dх.

3 Вычислить значение функции f(x₃). Найти f_min = min{ f(x₁), f(x₂), f(x₃)}, x_min – точка, которой соответствует f_min.

4 По трем точкам x₁, x₂, x₃ вычислить по формуле (34).

5 Произвести проверку на окончание поиска минимума. Если разности и являются достаточно малыми величиннами, то закончить поиск; иначе перейти к п. 6.

6 Выбрать «наилучшую» точку ( или ) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти к п. 3.

Пример 6. Найти минимум [9], с e₁ =0.003, e₂ = 0.03. Пусть начальная точка х₁ = 1 и длина шага Dх = 1. Находим минимум f(x) методом квадратичной аппроксимации.

Решение:

Итерация 1.

1 х₂ = х₁ +Dх = 2;

2 f(x₁) = 18; f(x₂) = 16; f(x₁) > f(x₂), следовательно, х₃ = 1+2 =3;

3 f(x₃) =23.33, f_min =16, x_min = x₂.

4 Находим значения коэффициентов полинома по формулам (32) – (34):

5 Проверка на окончание поиска

следовательно, поиск продолжается.

6 Наилучшей точкой является , а х₁ =1 и х₂ = 2 – точки, которые ее окружают. Обозначаем выбранные точки в естественном порядке, т.е. х₁ =1, х₂ = 1.714, х₃ = 2.