Методы полиномиальной интерполяции

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

ak < xk < bk; Q(ak) > Q (xk) < Q (bk),

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

ak < x* < bk.

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

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

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

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

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

φ2(x) = α0 — α1х + α2х2 = Q (ak)((x — xk) (x — bk))/((ak — xk)(ak — bk)) + Q (xk)((x — ak) (x — bk))/((xk — ak)(xk — bk)) + Q (bk)((x — ak) (x — xk))/((bk — ak)(bk — xk))

который имеет минимум xmin во внутренней точке интервала [аk, bk] только тогда, когда α2 > 0. т. е. тогда, когда для совокупности «удачных точек» выполняется неравенство:

Q (ak)/(ak — xk)(аk — bk) + Q (xk)/(xk — ak) (xk — bk) + Q (bk)(bk — xk) (bk — xk) > 0.

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

x* = -α1/2α2.

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

Случай 1: х* < хk; Q(х*) < Q (хk) (рис. 3.8, а), х*∈[аk, хk];[xk, bk] — из рассмотрения исключается; ak+i = аk; bk+i = хk; хk+1 = х*.

Случай 2: х* < xk; Q (х*) ≥ Q (хk) (рис. 3.8, б) х* ∈ [х, bk]; [аk, х] — из рассмотрения исключается; ak+1 = х; bk+1 = bk; xk+1 = хk.

Случай 3: х* > хk; Q (x*) < Q (хk) (рис. 3.8, б) x* ∈ [xk, bk]; [аk, хk] — из рассмотрения исключается; ak+1 = хk; bk+1 = bk; xk+1 = х*.

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

Предположим, что точка xk делит отрезок [ak, bk] на две равные части длиной δk (ak = xk — δk, bk = xk + δk). Тогда, приняв, что Δ1 = Q (xk) — Q (ak) и Δ2 = Q (xk) — Q (bk), для x получим

x* = xk + δk+1,
где

δk+1 = δk1 — Δ2)/(Δ1 + Δ2)



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

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

(bk+1 — ak+1)/(bk — ak) = 1/2,

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

(bk+1 — ak+1)/(bk — ak) ≤ 3/4.

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



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

Для четырех точек испытаний (m = 4) поиск минимума унимодальной функции можно ввести с помощью метода кубической интерполяции F6, который отличаетоя от метода F5 тем, что в нем в качестве интерполирующего полинома φn(х) используется кубическая парабола:

φ3(x) = α0 + α1x + α2x2 + α3x3.(3.72)

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

ξ = (х — ak)/(bk — аk);
аk = 0; хk = k; хк = к, bk = 1, где 0 < k < r < 1.

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

Q(ak) = α0,
Q(xk) = α0 — α1k + α2k2 — α3k3,
Q(xr) = α0 + α1r + α2r2 + α3r3,
Q(bk) = α0 + α1 + α2 + α3.

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

α22 ≥ α1α3, (3.73)

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

х* = ak + (bk — ak)ξ*. (3.74)

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

В связи с вышесказанным при поиске минимума унимодальной функции с высокой степенью точности ε необходимо последовательно применять сначала методы сокращения интервала неопределенности, до тех пор пока не будет получена совокупность «удачных точек», и затем методы полиномиальной интерполяции. Причем при минимизации функции, обладающей на интервале неопределенности большими по величине производными высших порядков, целесообразно использовать методы F1 — F4, а в тех случаях, когда минимизируемая функция является гладкой функцией, близкой к квадратичной параболе,— методы F5 и F6.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru