Методы исключения интервалов

М е т о д д е л е н и я о т р е з к а п о п о л а м

Этот метод позволяет исключать на каждой итерации ровно половину интервала. Иногда этот метод называют трех точечным поиском на равных интервалах, поскольку для его реализации на каждой итерации производится три вычисления целевой функции в трех опорных точках, равномерно распределенных в интервале поиска. Ниже приведен алгоритм этого метода (см. рис.1.2.3).

Рис.1.2.3

Алгоритм деления отрезка по полам

{{{Начало алгоритма.

1) Положим a₃=(a₁+a₂)/2, L=a₂-a₁. Вычислим значение J₃=J(a₃).

2) Положим a₄=a₁+L/4 и a₅=a₂-L/4. Вычислим значения целевой функции в этих точках - J₄=J(a₄), J₅=J(a₅).

3) Если J₄<J₃, то исключается правая половина интервала путем следующей системы пере обозначений: a₂=a₃, a₄=a₄ и переходим к пункту 5), иначе к пункту 4).

4) Если J₅<J₃, то исключается левая половина интервала путем следующей замены переменных - a₁=a₃, a₃=a₅ и переходим к пункту 5), иначе выбирается средняя половина интервала следующим образом: a₁=a₄, a₂=a₅, и переходим к пункту 5).

5) Вычислим L=a₂-a₁. Если величина |L|< e, то заканчиваем одномерный поиск, в противном случае переходим к пункту 2).

}}}Конец алгоритма.

Если проведено n вычислений целевой функции, то длина полученного интервала составит (1/2)^n/2 величины исходного интервала. В работе [31] показано, что из всех методов на равных интервалах (двухточечный, трех точечный, четырех точечный и т.д.) трех точечный поиск, или метод деления интервала пополам, отличается наибольшей эффективностью.

М е т о д з о л о т о г о с е ч е н и я

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

1/t=t/(1-t), (1.2.3)

из которого следует, что t²+t-1=0, или для положительного решения

(1.2.4)

Рис.1.2.4

Алгоритм золотого сечения

Для симметричной точки B (см. рис.1.2.4) значение расстояния от ближайшей границы равно (1-t)=0.38197. Для отрезка 0-А можно записать аналогичное соотношение: t/(1-t)=(1-t)/(t-(1-t)), из которого следует тоже решение (1.2.4).

{{{ Начало алгоритма метода золотого сечения.

1) Начальный интервал разбивается на три части по правилу:

L=a₂-a₁, a₃=a₁+L×(1-t), a₄=a₁+L×t. Вычислим значения функций в этих двух новых точках J₃=J(a₃), J₄=J(a₄).

2) Если J₃<J₄, то

а) исключается правый под интервал по правилу: a₂=a₄, J₂=J₄, a₄=a₃, J₄=J₃. Рассчитывается новая точка a₃=a₁+(a₂-a₁)×(1-t) и в ней значение функции J₃=J(a₃). Переходим к пункту 3).

иначе б) исключается левый под интервал по правилу: a₁=a₃, J₁=J₃, a₃=a₃, J₃=J₄. Рассчитывается новая точка a₄=a₁+(a₂-a₁)×t и в ней значение функции J₄=J(a₄). Переходим к пункту 3).

3) Если a₂-a₁<e, то заканчиваем поиск, иначе идем к пункту 2).

}}} Конец алгоритма.

В этом методе на первой итерации целевая функция рассчитывается два раза, а в последующих делениях отрезка - один раз. Следовательно, если произведено n вычислений целевой функции, то начальный отрезок уменьшится в t^n-1 раз. Метод золотого сечения более эффективен по сравнению с методом деления отрезка пополам в (0.5)^n/2 /(0.618)^n-1 раз.

Дата добавления: 2015-11-14