Этап установления границ интервала
На этом этапе сначала выбирается исходная точка, а затем на основе правила исключения строится относительно широкий интервал, содержащий точку оптимума. Обычно поиск граничных точек такого интервала проводится с помощью эвристических методов поиска, хотя в ряде случаев можно также использовать методы, экстраполяции. В соответствии с одним из эвристических методов, который был предложен Свенном [1], (k+1)-я пробная точка определяется по рекуррентной формуле
где х0— произвольно выбранная начальная точка, Δ — подбираемая некоторым способом величина шага. Знак Δ определяется путем сравнения значений f(x0), f(x0+|Δ|) и f(x0— |Δ|). Если
то, согласно предположению об унимодальности, точка минимума должна располагаться правее точки х0и величина Δ выбирается положительной. Если изменить знаки неравенств на противоположные, то Δ следует выбирать отрицательной. Если же
то точка минимума лежит между х0—|Δ| и х0+|Δ| и поиск граничных точек завершен. Случай,когда
противоречит предположению об унимодальности. Выполнение этого условия свидетельствует о том, что функция не является унимодальной.
Этап уменьшения интервала
После того как установлены границы интервала, содержащего точку оптимума, можно применить более сложную процедуру уменьшения интервала поиска с целью получения уточненных оценок координат оптимума. Величина подынтервала, исключаемого на каждом шаге, зависит от расположения пробных точек xlи x2 внутри интервала поиска. Поскольку местонахождение точки оптимума априори неизвестно, целесообразно предположить, что размещение пробных точек должно обеспечивать уменьшение интервала в одном и том же отношении. Кроме того, в целях повышения эффективности алгоритма необходимо потребовать, чтобы указанное отношение было максимальным. Подобную стратегию иногда называют минимаксной стратегией поиска.
|
|
|
Методы с использованием производных
Все рассмотренные в предыдущих разделах методы поиска основываются на предположениях об унимодальности и в ряде случаев о непрерывности исследуемой целевой функции. Целесообразно предположить, что если в дополнение к условию непрерывности ввести требование дифференцируемости функции, то эффективность поисковых процедур можно существенно повысить. Напомним, что в разд. 2.2 установлено необходимое условие существования локального минимума функции в некоторой точке z, согласно которому первая производная функции в точке zдолжна обращаться в нуль, т. е. f '(z)=df/dx|x=2=0.
Если функция f(x) содержит члены, включающие х в третьей и более высоких степенях, то непосредственное получение аналитического решения уравнения f'(x)=0может оказаться затруднительным. В таких случаях используются приближенные методы последовательного поиска стационарной точки функции f. Прежде всего опишем классическую поисковую схему, ориентированную на нахождение корня нелинейного уравнения. Эта схема была разработана Ньютоном и позднее уточнена Рафсоном [5].
|
|
|
Метод средней точки
Если функция f(x) унимодальна в заданном интервале поиска, то точкой оптимума является точка, в которой f '(х)=0. Если при этом имеется возможность вычислять как значения функции, так и ее производной, то для нахождения корня уравнения f '(х)=0 можно воспользоваться эффективным алгоритмом исключения интервалов, на каждой итерации которого рассматривается лишь одна пробная точка. Например, если в точке z выполняется неравенство f '(z)<0, то с учетом предположения об унимодальности естественно утверждать, что точка минимума не может находиться левее точки z. Другими словами, интервал х≤z подлежит исключению. С другой стороны, если f '(z)>0, то точка минимума не может находиться правее z и интервал x≥z можно исключить. Приведенные рассуждения лежат в основе логической структуры метода средней точки, который иногда называют поиском Больцано.
|
|
|
Определим две точки L и R таким образом, что f '(L)<0 и f '(R)>0. Стационарная точка расположена между L и R. Вычислим значение производной функции в средней точке рассматриваемого интервала z=(L+R)/2. Если f '(z)>0, то интервал (z, R)-можно исключить из интервала поиска. С другой стороны, если f '(z)<0, то можно исключить интервал (L, z). Ниже дается формализованное описание шагов алгоритма.
Пусть имеется ограниченный интервал а≤ х≤ b и задан параметр сходимости e.
Шаг 1. Положить R=b, L=a; при этом f '(а)<0 и f '(b)>0.
Ш а г 2. Вычислить z=(R+L)/2 и f '(z).
Ш а г 3. Если |f '(z)|≤e, закончить поиск. В противном случае, если f '(z)<0, положить L=z и перейти к шагу 2. Если f '(z)>0, положить R=z и перейти к шагу 2.
Следует отметить, что логическая структура поиска в соответствии с изложенным методом исключения интервалов основана лишь на исследовании знака производной независимо от значений, которые эта производная принимает. В следующем подразделе рассматривается метод секущих, при реализации которого рассматриваются как знак производной, так и ее значения.
Дата добавления: 2018-06-01; просмотров: 185; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!