2.2.2. Метод квадратичной аппроксимации.
Метод основан на предположении о том, что в ограниченном интервале можно аппроксимировать функцию квадратичным полиномом, который используется для оценивания координаты оптимума. Оценка оптимального значения рассчитывается по формуле:
= (x2 + x1)/2
- (a1/2a2).
Предполагается, что заданы x1, x2, x3, и известны значения функции в этих точках f1, f2, f3, а аппроксимирующая функция
g(x) = a0 + a1(x - x1) + a2(x - x1)(x - x2)
совпадает с f(x) в трех указанных точках.
Коэффициенты полинома определяются уравнениями
a0 = f1; a1 = (f2 - f1)/(x2 - x1); a2 = 1/(x3 - x2)[(f3 - f1)/(x3 - x1) - (f2 - f1)(x2 - x1)].
Для
унимодальных функций
оказывается
приемлемой для оценки оптимума x*.
Алгоритм метода квадратичной аппроксимации.
Шаг 1. Задать x1, x2, x3, и вычислить значения функции в этих точках f(х1), f(х2), f(х3).
Шаг 2. Рассчитать a0 = f(х1); a1 = (f(х2) - f(х1))/(x2 - x1); a2 = 1/(x3 - x2)[(f(х3) - f(х1))/(x3 - x1) - (f(х2) - f(х1))(x2 - x1)].
Шаг 2. Вычислить оптимальное решение: = (x2 + x1)/2 - (a1/2a2).
Пример расчета экстремума функции методом квадратичной аппроксимации.
Постановка задачи. Найти минимум функции f(x) = x2 + 5x методом квадратичной аппроксимации.
Для реализации метода необходимо выбрать три точки, по который будет производиться аппроксимация. Задаем следующие значения: x1=-5, x2=0, x3=5, Результаты расчета, реализованного средствами ECXEL, представлены в таблице 2.7
Таблица 2.7
Расчет экстремума функции f(x) = x2 + 5x методом квадратичной аппроксимации
x1 |
x2 |
x3 |
f(x1) |
f(x2) |
f(x3) |
a0 |
a1 |
a2 |
xопт |
-5,00 |
0,00 |
5,00 |
0,00 |
0,00 |
50,00 |
0,00 |
0,00 |
3,00 |
-2,50 |
Таким образом, с использованием метода квадратичной аппроксимации за одну итерацию найдена точка минимума xопт=-2,5, которая совпадает с точкой экстремума x*=-2,5, полученной аналитически.
2.2.3. Метод Пауэлла.
Заключается в последовательном применении процедуры оценивания с использованием квадратичной аппроксимации. Схему алгоритма можно описать следующим образом.
Алгоритм метода Пауэлла
Начальный этап. Выбрать x1 - начальную точку, x - величину шага по оси x. Задать точность поиска по х и f(x) 1=0,01 и 2=0,1. Перейти к основному этапу.
Основной этап. Шаг 1. Вычислить x2 = x1 + x.
Шаг 2. Вычислить f(x1), f(x2).
Шаг 3. Если f(x1) > f(x2), положить x3 = x1 + 2x. Если f(x1) f(x2), положить x3 = x1 - x.
Шаг 4. Вычислить f(x3) и найти Fмин = min{f1, f2, f3}.
Xмин = () xi, которая соответствует Fмин.
Шаг 5. По трем точкам x1, x2, x3 вычислить используя формулу для оценивания с помощью квадратичной аппроксимации.
Шаг 6. Проверка на окончание поиска:
является ли разность Xмин - достаточно малой(/Xмин - /<1)?
является ли разность Fмин - f( ) достаточно малой (/Fмин - f( )/<2)?
Если оба условия выполняются, закончить поиск. В противном случае перейти к шагу 7.
Шаг 7. Выбрать “наилучшую” точку (Xмин или ) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти к шагу 4.
Необходимо отметить, что за счет последовательных приближений, совмещенных с квадратичной аппроксимацией, метод имеет высокую эффективность.
Пример расчета экстремума функции методом Пауэлла.
Постановка задачи. Рассчитать минимум функции f(x) = (3-x)2 + 2x-1 методом Паулла. Выбираем начальную точку x1=0 и x=1 - величину шага по оси x, а также точность поиска по х и f(x) 1=0,01 и 2=0,1.
Результаты расчета минимума функции f(x) = (3-x)2 + 2x-1 представлены в таблице 2.8.
Таблица 2.8
Результаты расчета минимума функции f(x) = (3-x)2 + 2x-1 методом Пауэлла
x1 |
x2 |
x3 |
f(x1) |
f(x2) |
f(x3) |
a0 |
a1 |
a2 |
xmin |
f(xmin) |
xопт |
f(xопт) |
xmin-xопт |
f(xmin)-f(xопт) |
0,00 |
4,00 |
8,00 |
8,00 |
8,00 |
40,00 |
8,00 |
0,00 |
3,00 |
0,00 |
8,00 |
2,00 |
4,00 |
2,00 |
4,00 |
0,00 |
2,00 |
4,00 |
8,00 |
4,00 |
8,00 |
8,00 |
-2,00 |
1,00 |
2,00 |
4,00 |
2,00 |
4,00 |
0,00 |
0,00 |
Из расчетов видно, что экстремум найден за одну итерацию, что говорит о высокой эффективности метода.