Образовательный блог – всё для учебы

Пусть после проведения k испытаний имеет место ситуация III (рис. 3.7, в, см. предыдущий пост):

a_k < x_k < b_k; Q(a_k) > Q (x_k) < Q (b_k),

которая в силу унимодальности функции Q (х) гарантирует, что точка минимума л:* будет находиться внутри интервала [а_k, b_k]

a_k < x* < b_k.

В дальнейшем совокупность точек (a_k, x_k, b_k), приводящую к ситуации III, будем называть совокупностью «удачных точек».

Рассмотрим класс методов, называемых методами полиномиальной интерполяции, основная идея которых заключается в том, что по информации о m испытаниях (x_i, Q (x_i)) i = 1, 2, …, m строится интерполирующий полином ?_n(х) степени n ? m – 1, обладающий следующими свойствами:

?_n(х) является равномерным приближением минимизируемой функции на интервале [а_k, b_k]:
точка минимума х* полинома ?_n(х) определяется достаточно просто.

Отмеченные свойства полинома ?_n(х) позволяют на каждом шаге поиска использовать для сокращения текущего интервала неопределенности не только информацию о точках испытаний x_i, но и информацию о значениях функции Q (x_i) в этих точках.

Для трех точек испытаний (m = 3) в качестве полинома ?_n(х) в методе квадратичной интерполяции F⁵ используется интерполяционный многочлен Лагранжа:

?₂(x) = ?₀ – ?₁х + ?₂х² = Q (a_k)((x – x_k) (x – b_k))/((a_k – x_k)(a_k – b_k)) + Q (x_k)((x – a_k) (x – b_k))/((x_k – a_k)(x_k – b_k)) + Q (b_k)((x – a_k) (x – x_k))/((b_k – a_k)(b_k – x_k))

который имеет минимум x_min во внутренней точке интервала [а_k, b_k] только тогда, когда ?₂ > 0. т. е. тогда, когда для совокупности «удачных точек» выполняется неравенство:

Q (a_k)/(a_k – x_k)(а_k – b_k) + Q (x_k)/(x_k – a_k) (x_k – b_k) + Q (b_k)(b_k – x_k) (b_k – x_k) > 0.

В этом случае из условия d?₂/dx = 0 нетрудно получить, что

x* = -?₁/2?₂.

После проведения испытания в точке х осуществляется сокращение интервала неопределенности, содержащего точку минимума х*, и определяется новая совокупность «удачных точек». При этом возможны следующие четыре случая.

Случай 1: х* < х_k; Q(х*) < Q (х_k) (рис. 3.8, а), х*?[а_k, х_k];[x_k, b_k] — из рассмотрения исключается; a_k+i = а_k; b_k+i = х_k; х_k+1 = х*.

Случай 2: х* < x_k; Q (х*) ? Q (х_k) (рис. 3.8, б) х* ? [х, b_k]; [а_k, х] — из рассмотрения исключается; a_k+1 = х; b_k+1 = b_k; x_k+1 = х_k.

Случай 3: х* > х_k; Q (x*) < Q (х_k) (рис. 3.8, б) x* ? [x_k, b_k]; [а_k, х_k] — из рассмотрения исключается; a_k+1 = х_k; b_k+1 = b_k; x_k+1 = х*.

Случай 4: x* > x_k; Q (x*) > Q (x_k), (рис. 3.8, г) x* ? [a_k, x*]; [x*; b_k] — рассмотрения исключается;
a_k+1 = a_k; b_k+1 = x*; x_k+1 = x_k.

Предположим, что точка x_k делит отрезок [a_k, b_k] на две равные части длиной ?_k (a_k = x_k – ?_k, b_k = x_k + ?_k). Тогда, приняв, что ? ₁ = Q (x_k) – Q (a_k) и ?₂ = Q (x_k) – Q (b_k), для x получим

x* = x_k + ?_k+1,
где

?_k+1 = ?_k (?₁ – ?₂)/(?₁ + ?₂)

Рис. 3.8. Определние новой совокупности «удачных точек» в алгоритме F⁵

Нетрудно видеть, что для случаев 1 и 3 текущий интервал неопределенности [a_k+1, b_k+1] сокращается точно в два раза:

(b_k+1 – a_k+1)/(b_k – a_k) = 1/2,

а для случаев 2 и 4, о учетом условия (3.71), имеет место верхняя оценка:

(b_k+1 – a_k+1)/(b_k – a_k) ? 3/4.

Блок-схема метода F⁵, реализующего поиск минимума унимодальной функции Q (х), для которой задана исходная совокупность «удачных точек» (а, х₀, b), приведена на рис. 3.9.

Рис. 3.9. Блок-схема алгоритма F⁵, реализующего метод квадратичной интерполяции

Для четырех точек испытаний (m = 4) поизгс минимума уни «(бальной функции можно ввести с помощью метода кубической интерполяции F⁶, который отличаетоя от метода F⁵ тем, что в нем в качестве интерполирующего полинома ?_n(х) используется кубическая парабола:

?₃(x) = ?₀ + ?₁x + ?₂x² + ?₃x³.(3.72)

Не нарушая общности рассмотрения, предположим, что совокупность «удачных точек» на каждом шаге поиска приводится к единична му интервалу с помощью преобразования ? = (х – a_k)/(b_k – а_k);
а_k = 0; х_k = k; х_к = к, b_k = 1, где 0 < k < r < 1.

Тогда, взяв эти точки в качестве узлов интерполяции, для определения коэффициентов интерполирующего полинома (3.72) запишем систему линейных уравнений:

Q(a_k) = ?₀,
Q(x_k) = ?₀ – ?₁k + ?₂k² – ?₃k³,
Q(x_r) = ?₀ + ?₁r + ?₂r² + ?₃r³,
Q(b_k) = ?₀ + ?₁ + ?₂ + ?₃.

Интерполирующая функция (3.72) имеет один максимум и один минимум, если выполняется неравенство:

?₂² ? ?₁?₃, (3.73)

В этом случае точка минимума х* полинома ?₃(х) определяется по формуле

х* = a_k + (b_k – a_k)?*. (3.74)

Дальнейшая процедура поиска минимума унимодальной функции Q (х) по методу кубической интерполяции F* аналогична процедуре метода F⁵, так как связана с сокращением интервала неопределенности [a_k, b_k] и выбором новой совокупности «удачных точек» для (k + 1)-го шага из уже проведенных испытаний в точках (а_k, b_k, х_k, х_r, х*).

В связи с вышесказанным при поиске минимума унимодальной функции с высокой степенью точности ? необходимо последовательно применять сначала методы сокращения интервала неопределенности, до тех пор пока не будет получена совокупность «удачных точек», и затем методы полиномиальной интерполяции. Причем при минимизации функции, обладающей на интервале неопределенности большими по величине производными высших порядков, целесообразно использовать методы F¹ — F⁴, а в тех случаях, когда минимизируемая функция является гладкой функцией, близкой к квадратичной параболе,— методы F⁵ и F⁶.

1. Параллельные методы, комбинирующие пассивные и последовательные стратегии поиска
2. Построение аппроксимирующих моделей минимизируемой функции
3. Метод Фибоначчи
4. Поиск минимума унимодальной функции путем сокращения интервала неопределенности
5. Метод кусочно-кубической и кусочно-линейной аппроксимации.
6. Градиентные методы спуска
7. Квазиньютоновские методы минимизации
8. Повышение эффективности унимодального поиска за счет дополнительной информации о минимизируемой функции
9. Методы-функции и методы-процедуры – синтаксис объявления, реализация методов и варианты вызова методов
10. Виртуальные и динамические методы, замещающие методы
11. Численные методы интегрирования
12. Позитивизм. Общенаучные методы познания
13. Сеточный метод
14. Задачи и методы оптимизации в системах имитационного моделирования
15. Функции и переменные в GPSS
16. Абстрактные методы – объявление, наследование, полиморфизм
17. Рассылки сообщений, методы: Dispatch, Perform, Broadcast, NotifyControls, функции Windows API