Методы оценивания с использованием квадратичной аппроксимации

 

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

Если задана последовательность точек x₁, х₂, х₃и известны соот­ветствующие этим точкам значения функции f₁ f₂ и f₃, то можно определить постоянные величины а₀, а₁и а₂таким образом, что зна­чения квадратичной функции

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

имеем a₀=f₁. Далее, поскольку

получаем a₁=(f₂—f₁)/(x₂—x₁).

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

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

Таким образом, по трем заданным точкам и соответствующим зна­чениям функции можно оценить параметры а₀, a₁ и а₂ аппроксими­рующего квадратичного полинома с помощью приведенных выше формул.

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

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

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

Пример 2.8. Поиск с использованием квадратичной аппроксима­ции

 

Рассмотрим процедуру оценивания координаты точки минимума функции

в интервале 1£ x £ 5. Пусть x₁=l, х₃=5, а х₂есть средняя точка, интервала, т. е. х₂=3. Вычислим соответствующие значения функ­ции:

Для того чтобы оценить `х, необходимо найти значения парамет­ров а₁ и а₂ аппроксимирующей функции. Имеем

Подстановка этих значений в формулу для `х позволяет получить

Точный минимум достигается при х* = 1, 5874.

Метод последовательного оценивания с использованием квадра­тичной аппроксимации

 

Этот метод, разработанный Пауэллом [4], основан на последова­тельном применении процедуры оценивания с использованием квад­ратичной аппроксимации. Схему алгоритма можно описать следую­щим образом. Пусть х₁— начальная точка, Δ x — выбранная вели­чина шага по оси х.

Шаг 1. Вычислить х₂=х₁+ Δ х.

Ш а г 2. Вычислить f(x_l) и f(х₂).

Ш а г 3. Если f(x₁)> f(x₂), положить x₃=x₁+2Δ х. Если f(x₁)≤ f(х₂), положить х₃ =x₁—Dх.

Ш а г 4. Вычислить f (x₃) и найти

Ш а г 5. По трем точкам x₁, x₂, x₃вычислить `х, используя фор­мулу для оценивания с помощью квадратичной аппроксимации.

Шаг 6. Проверка на окончание поиска.

(а) Является ли разность F_мин— f(`x) достаточно малой?

(б) Является ли разность Х_мин —`х достаточно малой?

Если оба условия выполняются, закончить поиск. В противном, случае перейти к шагу 7.

Ш а г 7. Выбрать «наилучшую» точку (x_минили `х) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти к шагу 4.

Заметим, что при первой реализации шага 5 границы интервала содержащего точку минимума, не обязательно оказываются установленными. При этом полученная точка `х может находиться за точкой х<sub>3</sub>. Для того чтобы исключить возможность слишком боль того экстраполяционного перемещения, следует провести после шага 5 дополнительную проверку и в случае, когда точка `х находится слишком далеко от х₃, заменить `х точкой, координата которой вы­числяется с учетом заранее установленной длины шага.

Пример 2.9. Метод Пауэлла

Рассмотрим задачу из примера 2.8:

минимизировать f (х) = 2x²+ (16/х).

Пусть начальная точка x₁=l и длина шага Dх=1. Для проверки на окончание поиска используются следующие параметры сходимости

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

Ш а г 7. Выбираем `х как «наилучшую» точку, a x₁=1и ₂=2 — как точки, которые ее окружают. Обозначаем эти точки в естествен­ном порядке и переходим к итерации 2, которая начинается с шага 4.

 

Итерация2

Шаг 4. x₁ = 1, f₁=18, x₂=1, 714, f₂=15, 210=F_минХ_мин=х₂ х₃=2, f₃=16

Шаг 7. Выбираем `х как «наилучшую» точку, а х₁=1и х₂= 1, 714 — как точки, которые ее окружают.

 

Итерация 3

Шаг 4. x₁ = 1, f₁=18, x₂=1, 65 f₂=15, 142=F_минХ_мин=х₂ х₃=1, 714, f₃=15, 210.

Шаг 5.

⇐ Предыдущая12345Следующая ⇒

Поделиться:

Популярное:

1. Вот как выглядит версия программы разбиения строки на слова с использованием арифметики указателей.
2. Вычисление выражений с использованием стандартных функций
3. Гадание с использованием домино
4. Государственный Контроль За Использованием И Сохранностью Жилищного Фонда
5. ДОБРОВОЛЬНОГО СТРАХОВАНИЯ РИСКОВ, СВЯЗАННЫХ С ИСПОЛЬЗОВАНИЕМ
6. Измерение тесноты и силы корреляционной связи с использованием коэффициента детерминации и эмпирического корреляционного отношения
7. Изучение динамики ВВП и ВДС. Анализ взаимосвязи стоимостных показателей продукции с использованием индексных моделей
8. Кипячение при низком избыточном давлении с использованием внутреннего кипятильника
9. Критерии для оценивания компетенций по практике
10. Критерии оценивания выполнения индивидуальных домашних заданий
11. КРИТЕРИИ ОЦЕНИВАНИЯ КОНТРОЛЬНОЙ РАБОТЫ
12. Критерии оценивания презентации