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

Поиск точки минимума методами исключения отрезков основан на сравнении значений функции в двух точках. При таком сравнении раз­ности значений f (x) в этих точках не учитываются, важны только их знаки.

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

Обоснованием указанных методов является известная из матема­тического анализа теорема Вейерштрасса об аппроксимации [4], согласно которой непрерывную на отрезке функцию можно с любой точностью приблизить на этом отрезке некоторым полиномом.

Для повышения точности аппроксимации можно, во-первых, увеличивать порядок полинома и, во-вторых, уменьшать длину отрезка аппроксимации. Первый путь приводит к быстрому усложнению вы­числительных процедур, поэтому на практике используются аппрок­симирующие полиномы не выше треть­его порядка. В то же время уменьшить отрезок, содержащий точку минимума унимодальной функции, не представляет особого труда.

В простейшем методе полиномиальной аппроксимации — методе парабол используются полиномы второго порядка. На каждой итерации этого метода строят квадратный трехчлен, график которого (парабола) проходит через три выбранные точки графика функции f (x) (рис. 2.8).

Опишем метод парабол. Рассмотрим унимодальную на отрезке [а; b] функцию f(x), достигающую минимума во внутренней точке этого отрезка. Выберем три точки х₁, х₂ и х₃ отрезка [а; b], для которых выполняются неравенства:

х ₁ < х ₂ < х ₃, f (x ₁) ³ f (x ₂) £ f (x ₃). * (2.19)

Из унимодальности f (x) следует, что х* Î [ х ₁; х ₃].

Построим квадратный трехчлен q (x) = а ₀ + a ₁(x-x ₁) + a ₂(x-x ₁)(x-x ₂),график которого проходит через точки (x ₁, f (x ₁)), (x ₂, f (x ₃)) (x ₃, f (x ₃)) графика функции f (x). Будем считать, что если хотя бы одно из неравенств (2.19) для f (x_i) является строгим (если f (x ₁)= f (x ₂) = f (x ₃), то поиск точки х * на этом закончен, так как из унимодальности функции f (x) следует, что она достигает минимума в каждой точке отрезка [ х ₁; х ₃]). Тогда из (2.19) следует, что ветви искомой параболы направлены вверх, а точка минимума трехчлена q (x) принадлежит отрезку [ х ₁; х ₃].

Определяя коэффициенты а ₀, a ₁ и a ₂ из системы уравнений:

q (x ₁) = f (x ₁) = f ₁;

q (x ₂) = f (x ₂) = f ₂ ;

q (x ₃) = f (x ₃) = f ₃,

находим

, , .

Точку минимума квадратного трехчлена q (x) вычислим, приравняв его производную к нулю. Получим

(2.20)

Число из (2.20) служит очередным приближением метода парабол к х*. Далее описанная процедура повторяется для новых точек x ₁, x ₂, x ₃,удовлетворяющих неравенствам (2.19).

Выбрать эти точки среди x ₁, x ₂, x ₃, и можно с помощью перехода от исходного к новому отрезку [ x ₁; x ₃], содержащему точку х *, ме­тодом исключения отрезков. Для этого перехода используют проб­ные точки x ₂ и и сравнивают значения f (x) в этих точках *⁾. Начало и конец нового отрезка, а также пробная точка, попавшая на него, образуют тройку точек, обладающих свойством (2.19).

Заметим, что на каждой итерации метода парабол, кроме первой, определяетсятолько одно новое значение f (x).

Условием окончания поиска служит близость к нулю разности D чисел , найденных на данной и предыдущей итерациях, т.е. неравенство |D| £ e, где e— заданное число, характеризующее точность определения х*.

Перечислим основные шаги алгоритма метода парабол.

Шаг 1. Выбрать точки x ₁, x ₂, x ₃, удовлетворяющие условиям (2.19). Перейти к шагу 2.

Шаг 2. Найти по формуле (2.20). На первой итерации перейти к шагу 4, на остальных — к шагу 3.

Шаг 3. Проверка на окончание поиска. Сравнить модуль разно­сти значений на данной и предыдущей итерациях D с числом e. Если |D| £ e, то поиск завершить, полагая х *» , f *» f (x), иначе — перейти к шагу 4.

Шаг 4. Вычислить значение f (). Перейти к шагу 5.

Шаг 5. Определить новую тройку чисел x ₁, x ₂, x ₃. Присвоить f (x ₁), f (x ₂) и f (x ₃) соответствующие значения f (x) найденные ранее. Пе­рейти к шагу 2.

Пример 2.8. Метод парабол.

Решить задачу f (x) =х ⁴ + е ^{- x} ® min, х Î[0; 1] с точностью |D| £ e = 0,0025.