4.6. Метод параболической аппроксимации

 Метод заключается в замене нелинейной функции F(X) квадратичной параболой F2(X), построенной по трем точкам, принадлежащим F(X), с последующим нахождением максимума (минимума) параболической функции, используя аналитические условия оптимальности:

На первом этапе в качестве исходных трех точек используется

В этих точках вычисляется F(X) и по полученным точкам F(X1), F(X2), F(X3) строится парабола

Коэффициенты которой находятся из решения соответствующей системы уравнений:

Условие оптимальности приводит к уравнению

Где Х4 – точка максимума (минимума) параболы F2(X). Далее выбирается новый отрезок, внутри которого находится точка Х4, и, используя Х3, Х4, строится новая парабола, по которой уточняется положение максимума (минимума) F(X) и т. д. До тех пор, пока величина отрезка, внутри которого находится оптимум, не будет меньше заданной погрешности . Таким образом, метод имеет итерационный характер.

К достоинству метода относится высокая скорость сходимости, хотя метод может не всегда сходится.

На рис. 19 рассмотрена ситуация, когда метод параболической аппроксимации сходится к решению уже на третьем этапе. Парабола, построенная по точкам Х3, х4, х5, практически совпадает с исходной функцией. На рис. 20 парабола не имеет максимума уже на втором этапе. В первом случае решение найти можно, во втором – нельзя.

Пример 19. Дана функция F(X) = Sin (X + 1). Найти максимум на интервале  [-1; 2], точность = 0,01.

Решение. Для построения аппроксимирующей параболы находим точки  В первом случае система уравнений для нахождения коэффициентов параболы примет вид:

Решение системы можно найти любым из известных способов, например, по формулам Крамера. На первом шаге получаем = 0,5571, F() = 0.9999. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола.

Таблица 14

П
X1
X2
X3
F(х1)
F(x2)
F(x3)
C2
C1
C0
1
-1
0.5
2
0
0.9975
0.1411
-0.412
0.459
0.871
0.5571
0.9999
2
0.5
0.5571
2
0.9975
0.9999
0.1411
-0.4249
0.4914
0.858
0.5782
1
3
0.5571
0.5782
2
0.9999
1
0,1411
-0,4208
0.4809
0.8626
0.5714
1
4
0,5571
0,5714
0,5782
0,9999
1
1
-0,5
0,5708
0,8371
0,5708
1

 Поскольку уже на третьем шаге разница между двумя точками максимума менее заданной погрешности, то поиск можно заканчивать (четвертый шаг присутствует для наглядности вычислений).

Поэтому Х* 0,5708, и  F* F (0,5708) = 1.

Для реализации данного метода существует ещё один подход.

Если задана последовательность точек Х1, х2, х3 и известны соответствующие этим точкам значения функции F1, F2, F3, то можно определить постоянные величины  А0, а1, а2 таким образом, что значения квадратичной функции

Совпадут со значениями F(X) в трех указанных точках. Перейдем к вычислению Q(X) в каждой из трех заданных точек. Прежде всего, так как

Поскольку

Наконец, при  Х = х3

Разрешая последнее уравнение относительно А2, получаем

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

Можно получить

Поскольку функция F(X) на рассматриваемом интервале обладает свойством унимодальности, а аппроксимирующий квадратичный полином также является унимодальной функцией, то можно ожидать, что величина  окажется приемлемой оценкой координаты точки истинного оптимума Х*.

Видно, что оба подхода отличаются друг от друга только способом вычисления коэффициентов (в первом случае - C0, C1, C2; во втором - А0, а1, а2) квадратичного полинома. Результаты при этом нисколько ни отличаются. Легко убедиться, что для практических вычислений удобнее использовать формулы

Пример 20. Найти минимальное значение F* и точку минимума Х* функции На отрезке [1.5; 2]. Точку Х* Найти с точностью =0,05.

Решение. Значения  Х1, х2, х3 находим также как и в предыдущем примере.

  Таблица 15

П
X1
X2
X3
F1
F2
F3
А0
А1
А2
1
1,5
1,75
2
-89,4375
-92,1211
-88
-89,4375
-10,7344
54,4375
1,7236
-92,1346
2
1,5
1,7236
1,75
-89,4375
-92,1346
-92,1211
-89,4375
-12,0623
50,2988
1,7317
-92,1384

Уже после второго шага можно закончить вычисления, так как заданная точность достигнута (1,7317-1,7236 = 0,0081 <  = 0,05).

Значит, Х* 1,7317, и  F* F (1,7317) = -92,1384.

Пример 21. НАйти точку минимума Х* функции  на отрезке [0.5; 1] с точностью =0,05.

Решение. Вычисления представим в виде табл. 16:

Таблица 16

П
X1
X2
X3
F1
F2
F3
А0
А1
А2
1
0,5
0,75
1
-3,5907
-2,4389
-0,5
-3,5907
4,6075
6,296
0,2591
-3,5328
2
0,2591
0,5
1
-3,5328
-3,5907
-0,5
-3,5328
-0,2404
8,6677
0,3934
-3,7475
3
0,3934
0,5
1
-3,7475
-3,5907
-0,5
-3,7475
1,4708
7,7657
0,352
-3,7373

Точность достигнута (0,3934 – 0,352 = 0,414 <  = 0,05).

Значит, Х* 0,352, и  F* F (0,352) = -3,7373.

Яндекс.Метрика