Полиномиальная аппроксимация. 
Минимизация функций одной переменной

Квадратичная аппроксимация

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

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

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

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

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

q (x)=a₀ + a₁(x-x₁)+a₂(x-x₁)(x-x₂) (1.24).

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

f₁=f (x₁)=q (x₁)=a₀,.

имеем a₀=f₁.

Далее, поскольку.

f₂=f (x₂)=q (x₂)=f₁+ a₁(x₂-x₁),.

получаем.

a₁=(f₂-f₁)/(x₂-x₁).

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

f₃=f (x₃)=q (x₃)=f₁+(f₂-f₁)/(x₂-x₁)(x₃-x₁)+a₂(x₃-x₁)(x₃-x₂).

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

a₂=.

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

Если точность аппроксимации исследуемой функции в интервале [x₁, x₃] c помощью указанного полинома оказывается достаточно высокой, то в соответствии с предложенной стратегией поиска построенный полином можно использовать для оценивания координат точки минимума.

В данном случае, согласно необходимому условию экстремума, найдя первую производную полинома и приравняв ее нулю, получим.

q'(x)= a₁+a₂(x-x₂)+a₂(x-x₁)=0,.

откуда искомая оценка минимума равна.

x_a*=(x₂-x₁)/2 — (a₁/2a₂).

Пример. Методом квадратичной аппроксимации найти точку минимума функции.

f (x)= 2x² + (16/x).

в интервале 1×5.

Пусть пробные точки равны x₁=1, x₂=3, x₃=5, и соответствующие значения функции равны.

f₁=18.0, f₂=23.33, f₃=53.2.

Вычислим коэффициенты квадратичного приближения:

a₁=2.67, a₂=3.07,.

что дает следующую оценку точки минимума.

x_a*=1.565.

Точный минимум исходной функции равен x*=1.5874.

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

Алгоритм последовательной квадратичной аппроксимации Задано: x₁-начальная точка,.

x-величина шага по оси x.

Вычислить x₂=x₁+x.

Вычислить f₁=f (x₁) и f₂=f₂(x₂).

Если f₁> f₂, то x₃=x₁+2x;

иначе x₃=x₁-2x.

Вычислить f₃=f (x₃).

и найти.

f_min=min{f₁, f₂, f₃},.

x_min-точка, которой соответствует f_min.

Вычислить x_a* по трем точкам x₁, x₂ и x₃ в соответствии с формулой квадратичной аппроксимации.

Вычислить [f_min-f (x_a*)] и (x_min— x_a*).

Если обе разности достаточно малы, то Стоп.

Выбрать «наилучшую» точку из x_min и x_a* и две точки по обе стороны от нее. Пронумеровать эти точки в естественном порядке и перейти к 4.

Заметим, что при первой реализации шага 5 границы интервала, содержащего точку минимума, не обязательно оказываются установленными. При этом полученная точка x_а* может находиться за точкой x₃. Для того чтобы исключить возможность слишком большого экстраполяционного перемещения, следует провести после шага 5 дополнительную проверку и в случае, когда точка x_а* находится слишком далеко от x₃, заменить x_а* точкой, координата которой вычисляется с учетом заранее установленной длины шага.

Пример. Методом Пауэлла минимизировать.

f (x)= 2x³ + (16/x).

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

• (разность значений x)/x 310^-2,
• (разность значений f)/f 310^-3.

Итерация 1

Шаг 1. x₂=x₁+x=2.

Шаг 2. f (x₁)=18, f (x₂)=16.

Шаг 3. f (x₁)> f (x₂), следовательно, положить x₃=1+2=3.

Шаг 4. f (x₃)=22.33, F_min=16, X_min=x₂=2.

Шаг 5. a₁=(16−18)/(2−1)=-2,.

a₂=,.

x=.

f (x)=15.210.

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

> 0.003.

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

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

Итерация 2.

Шаг 4. x₁=1, f₁=18,.

x₂=1.714, f₂=15.210=F_min, X_min=x₂=171,.

x₃=2, f₃=16.

Шаг 5. a₁=(15.21−18)/(1.714−1)=-3.908,.

a₂=,.

x=.

f (x)=15.142.

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

> 0.003.

Условие не выполняется, следовательно, поиск продолжается.

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

Итерация 3.

Шаг 4. x₁=1, f₁=18,.

x₂=1.65, f₂=15.142=F_min, X_min=x₂=1.65,.

x₃=1.714, f₃=15.210.

Шаг 5. a₁=(15.142−18)/(1.65−1)=-4.397,.

a₂=,.

x=.

f (x)=15.123.

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

< 0.003,.

< 0.003.

Следовательно, поиск закончен.