Метод поиска с использованием кубичной аппроксимации
В соответствии с рассматриваемым методом подлежащая минимизации функция f аппроксимируется полиномом третьего порядка. Логическая схема метода аналогична схеме методов с использованием квадратичной аппроксимации. Однако в данном случае построение аппроксимирующего полинома проводится на основе меньшего числа точек, поскольку в каждой точке можно вычислять значения как функции, так и ее производной.
Работа алгоритма начинается в произвольно выбранной точке x1. находится другая точка х2, такая, что производные f '(x1) и f '(х2) имеют различные знаки. Другими словами, необходимо заключить стационарную точку `х, в которой f '(х)=0, в интервал между х1и х2. Аппроксимирующая кубичная функция записывается в следующем виде:
`f (Х)=а0+а1(х—х1)+а2(х—х1) (х—х2} +а3(х—х1)2(х—х2). (2.8)
Параметры уравнения (2.8) подбираются таким образом, чтобы значения `f (х) и ее производной в точках х1и х2 совпадали со значениями f (х) и f '(x) в этих точках. Первая производная функции `f(x) равна
Коэффициенты а0, a1, a2 и a3 уравнения (2.8) определяются по известным значениям f(x1), f(x2), f '(x1) и f '(х2) путем решения следующей системы линейных уравнений:
Заметим, что данная система легко решается рекурсивным методом. После того как коэффициенты найдены, действуя по аналогии со случаем квадратичной аппроксимации, можно оценить координату стационарной точки функции f с помощью аппроксимирующего полинома (2.8). При этом приравнивание к нулю производной (2.9) приводит к квадратному уравнению. Используя формулу для вычисления корней квадратного уравнения, запишем решение, определяющее стационарную точку аппроксимирующего кубичного полинома, в следующем виде:
|
|
|
Формула для w обеспечивает надлежащий выбор одного из двух корней квадратного уравнения; для значений m, заключенных в интервале от 0 до 1, формула (2.10) гарантирует, что получаемая точка `х расположена между х1и х2. Затем снова выбираются две точки для реализации процедуры кубичной аппроксимации — `х, и одна из точек x1или х2, причем значения производной исследуемой функции в этих точках должны быть противоположны по знаку, и процедура кубичной аппроксимации повторяется.
Приведем формализованное описание алгоритма. Пусть заданы начальная точка х0, положительная величина шага D и параметры сходимости e1 и e2.
Шаг 1. Вычислить f ‘(х0).
Шаг 2. Вычислить значения f '(x) в точках хк+1при K=0, 1, 2, ... вплоть до точки хM, в которой f '(xM-l) f '(xM)≤0. Затем положить xl=xM-1, х2=хM. Вычислить значения f1 f2, f 1’ и f ’2.
Ш а г 3. Найти стационарную точку `х аппроксимирующего кубичного полинома, пользуясь формулой (2.10).
Ш а г 4. Если f(x)<f(x1 ), перейти к шагу 5. В противном случае вычислять `х по формуле `x=`x+1/2(`x—х2) до тех пор, пока не будет выполняться неравенство f(`x)≤f(xl).
|
|
|
Ш а г 5. Проверка на окончание поиска.
Затем перейти к шагу 3.
Заметим, что шаги 1 и 2 реализуют процедуру поиска границ интервала по эвристическому методу, причем изменение знака производной используется в качестве критерия перехода через точку оптимума. На шаге 3 проводятся вычисления координаты точки оптимума аппроксимирующего полинома. Шаг 4 ассоциирован с проверкой того факта, что полученная оценка действительно является улучшенным приближением к точке оптимума. В случае когда значения производной вычисляются непосредственно, метод поиска с использованием кубичной аппроксимации, безусловно, оказывается более эффективным по сравнению с любым из представленных выше методов поиска. Однако если значения производной вычисляются путем разностного дифференцирования, то предпочтение следует отдать методу Пауэлла, основанному на квадратичной аппроксимации.
Дата добавления: 2018-06-01; просмотров: 200; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!