Метод квадратичной аппроксимации: 2.2.2. Метод квадратичной аппроксимации.

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

Положим, что в ограниченном интервале функцию f(x) можно аппроксимировать квадратичным полиномом. Пусть задана последовательность точек x₁, x₂, x₃ и известны значения функции в этих точках: f(x₁) = f₁, f(x₂) = f₂, f(x₃) = f₃. Тогда можно определить постоянные коэффициенты a₀, a₁ и a₂ таким образом, что значения квадратичного полинома [4]:

(32)

совпадут со значениями функции f(x) в трех указанных точках. Для этого вычислим значение j(x) в трех заданных точках.

Так как , получаем . Поскольку получаем . При имеем или

(33)

Если точность аппроксимации функции f(x) на отрезке [x₁, x₂] квадратичным полиномом оказывается достаточно высокой, то построенный полином далее используется для оценивания координаты точки минимума функции f(x).

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

. (34)

Тогда для оценки координаты точки минимума функции f(x) получаем формулу

(35)

Приведем описание алгоритма метода последовательного оценивания с использованием квадратичной аппроксимации, разработанного Пауэллом [4].

1 Пусть f(x) – оптимизируемая функция, х₁ – начальная точка, Dх – величина шага по оси абсцисс. Вычислить х₂ = х₁+Dх и значения функции f(x₁) и f(x₂).

2 Если f(x₁) >f(x₂), то положить х₃ = х₁ +2 Dх. Если f(x₁) £ f(x₂), то положить х₃ = х₁ -Dх.

3 Вычислить значение функции f(x₃). Найти f_min = min{ f(x₁), f(x₂), f(x₃)}, x_min – точка, которой соответствует f_min.

4 По трем точкам x₁, x₂, x₃ вычислить по формуле (34).

5 Произвести проверку на окончание поиска минимума. Если разности и являются достаточно малыми величиннами, то закончить поиск; иначе перейти к п. 6.

6 Выбрать «наилучшую» точку ( или ) и две точки по обе стороны от нее. Обозначить эти точки в естественном порядке и перейти к п. 3.

Пример 6. Найти минимум [9], с e₁ =0.003, e₂ = 0.03. Пусть начальная точка х₁ = 1 и длина шага Dх = 1. Находим минимум f(x) методом квадратичной аппроксимации.

Решение:

Итерация 1.

1 х₂ = х₁ +Dх = 2;

2 f(x₁) = 18; f(x₂) = 16; f(x₁) > f(x₂), следовательно, х₃ = 1+2 =3;

3 f(x₃) =23.33, f_min =16, x_min = x₂.

4 Находим значения коэффициентов полинома по формулам (32) – (34):

5 Проверка на окончание поиска

,

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

6 Наилучшей точкой является , а х₁ =1 и х₂ = 2 – точки, которые ее окружают. Обозначаем выбранные точки в естественном порядке, т.е. х₁ =1, х₂ = 1.714, х₃ = 2.

Итерация 2.

3 x₁ =1, f₁ =18, x₂ = 1.714, f₂ =15.210, x₃ =2, f₃ =16.

Получаем x_min = x₂, f_min = 15.210.

4 a₁ = — 3.908, a₂ = 6.671, =1.1650, f() =15.42.

5 Проверка на окончание поиска

.

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

6 Наилучшая точка , х₁ =1 и х₂ = 1.714 – ее окружают. Следовательно, х₁ =1, х₂ = 1.650, х₃ = 1.714.

Итерация 3.

3 x₁ =1, f₁ =18, x₂ = 1.650, f₂ =15.42, x₃ =1.714, f₃ =15.210.

Получаем x_min = 1.65, f_min = 15.42.

4 a₁ = — 4. 397, a₂ = 7.647, =1.6125, f() =15.123.

5 Проверка на окончание поиска

, .

Следовательно, поиск закончен и x_min = 1.6125, f_min = 15.123.

Предлагаю ознакомиться с аналогичными статьями:

Следующее Предыдущее Главная страница

Подписаться на: Комментарии к сообщению (Atom)

4.7. Метод Пауэлла

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

Алгоритм метода Пауэлла:

Шаг 1. Вычислить

Шаг 2. Вычислить F(X1) и F(X2).

Шаг 3. Если F(X1) > F(X2), положить  Если Положить .

Шаг 4. Вычислить F(X3) и найти

Шаг 5. По трем точкам

Х1, х2, х3 Вычислить, Используя формулу оценивания квадратичной аппроксимации:

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

А) является ли разность  достаточно малой?

Б) является ли разность  достаточно малой?

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

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

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

Пример 22. Минимизировать функцию F(X) = 2X2 + (16/X).

Решение. Пусть начальная точка X1 = 1 и длина шага X = 1. Для проверки на окончание поиска используются следующие параметры сходимости:

Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Шаг 5. Используя метод параболической аппроксимации, находим

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

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

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

Итерация 2.

Шаг 4.

Шаг 5.

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

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

Шаг 7. Выбираем «наилучшую» точку, и точки, их окружающие. Обозначаем эти точки  в естественном порядке  Переходим к итерации 3, которая начинается с шага 4.

Итерация 3.

Шаг 4.

Шаг 5.

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

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

Получили

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

Решение. Пусть начальная точка X1 =3 и длина шага X = 1. Для проверки на окончание поиска используются следующие параметры сходимости:

Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Шаг 5. Используя метод параболической аппроксимации, находим

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

Так как пункт А) Не выполняется, то продолжаем поиск.

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

Итерация 2.

Шаг 4.

 

Шаг 5.

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

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

Шаг 7. Выбираем «наилучшую» точку, и точки, их окружающие. Обозначаем эти точки  в естественном порядке  Переходим к итерации 3, которая начинается с шага 4.

 Итерация 3.

Шаг 4.

Шаг 5.

Шаг 6.

Проверка на окончание поиска:

Продолжаем поиск.

Шаг 7. Выбираем «наилучшую» точку, и точки, их окружающие. Обозначаем эти точки  в естественном порядке  Переходим к итерации 4, которая начинается с шага 4.

Итерация 4.

Шаг 4.

Шаг 5.

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

Условия окончания поиска выполняются, следовательно, вычисления заканчиваем.

Получили

Пример 24. НАйти точку минимума Х* функции  с точностью =0,05.

Решение. Пусть начальная точка X1 = 0,5 и длина шага X = 0,2. Для проверки на окончание поиска используются следующие параметры сходимости:

 Итерация 1.

Шаг 1.

Шаг 2.

Шаг 3.

Шаг 4.

Шаг 5.

Используя метод параболической аппроксимации, находим

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

Так как пункт А) Не выполняется, то продолжаем поиск.

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

Итерация 2.

Шаг 4.

Шаг 5.

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

Условия окончания поиска выполняются, следовательно, вычисления заканчиваем.

Получили

< Предыдущая		Следующая >

Квадратичная аппроксимация: пошаговый пример

Определения вычислений >

Квадратичная аппроксимация — это один из способов аппроксимации кривой. Квадратичные полиномиальные аппроксимации являются конкретными примерами полезного класса квадратичных аппроксимаций, называемых полиномами Тейлора .

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

Общая форма квадратичной аппроксимации

Общая форма квадратичной аппроксимации:

Если это выглядит сложно, не беспокойтесь: вам не нужно решать уравнение; все, что вам нужно сделать, это подключить некоторые термины.

Допустим, вы пытались аппроксимировать функцию в точке x = 1. Формула в основном говорит найти три значения в точке x = 1 и сложить их:

• f: Функция в точке x = 1
• f′: первая производная при x = 1
• f′′: вторая производная при x = 1,

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

Пример задачи : Найти квадратичное приближение для f(x) = xe ^-2x вблизи x = 1

Шаг 1: Найти первую производную функции . Используйте правило произведения для этой функции (с x и e ^-2x ), а затем цепное правило (для e ^-2x ):

f′(x) = e ^-2x — 2xe ^-2x = e ^-2x (1 — 2x).

Шаг 2: Найдите вторую производную функции . Другими словами, найдите производную производной, вычисленной на шаге 1.

f′′(x) = -2e ^-2x – 2(e ^-2x – 2xe ^-2x )
= -4e ^-2x + 4xe ^{-2x 9038 900 2x} (1 – х).

Шаг 3: Найдите значения при x = 1 для функции, а также первую и вторую производные , вычисленные на шагах 1 и 2:

1. f(1) = (1)e ^-2(1) = е ^-2
2. f′(1) = e ^-2(1) (1 – 2(1)) = -e ^-2
3. f′′(1) = -4(1) ^-2(1) (1 – (1)) = 0.

Шаг 4: Возьмите три значения , которые вы вычислили на шаге 3, и подставьте их в общую формулу . Обратите внимание, что вторая производная (из шага 3) равна нулю, поэтому мы можем игнорировать третью часть формулы:
f(x) &приблизительно; f(1) + f′(1)(x – 1)
&приблизительно; е ^-2 – е ^{– 2} (х – 1).

Вот и все!

Квадратичная аппроксимация хорошо подходит для x = 1 (на графике с помощью Desmos).

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

Помимо функций моделирования, аппроксимации используются для:

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

Next : Как использовать полиномы Тейлора для аппроксимации функции.

Ссылки

Графический калькулятор Desmos.

УКАЗЫВАЙТЕ ЭТО КАК:
Стефани Глен . «Квадратичная аппроксимация: пошаговый пример» Из StatisticsHowTo. com : Элементарная статистика для всех нас! https://www.statisticshowto.com/quadratic-apprimation/

————————————————— ————————-

     

Нужна помощь с домашним заданием или контрольным вопросом? С Chegg Study вы можете получить пошаговые ответы на ваши вопросы от эксперта в данной области. Ваши первые 30 минут с репетитором Chegg бесплатны! 92, \end{aligned} \end{aligned}$$

(A.5)

где второе неравенство следует из (A.1) и (A.2), а последнее неравенство следует из (A. 4). Обратите внимание, что \(\sigma \in (0,\, 1)\) и \({\lambda _{\min}({\varvec{B}_{k}}) — \epsilon _k > 0}\) . Из (П.5) видно, что его левая часть неположительна, когда {B}_{k}}) — \epsilon _k}\right) /L]\). Это доказывает корректность \((\text {LS}_1)\). Аналогично рассмотрим критерий завершения \ ((\text {LS}_2)\). В силу (A.1), (A.2) и (A.