Алгоритм равномерного поиска

Рассмотрим следующую задачу условной оптимизации: найти минимум одномерной унимодальной функции ( ), определенной в замкнутой области допустимых значений =[ , ],

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

Текущий интервал неопределенности будем обозначать ТИН, а его длину |ТИН|. Так что, если , то .

В алгоритме равномерного поиска испытания проводятся в точках, которые определяются путем равномерного деления интервала [ , ] на одинаковых подынтервалов. Из вычисленных значений функции выбирается наименьшее. Пусть это значение достигается в точке . Тогда в связи с унимодальностью функции подынтервалы , можно исключить из рассмотрения, т.е. сделать очередным интервалом неопределенности интервал . Алгоритм относится к классу пассивных методов поиска.

Более строго описанную схему алгоритма можно записать в нижеследующем виде.

1. Выполняем присваивания , , , .

2. На текущем ТИН строим равномерную сетку с +1 узлами (см. рис. 1).

3. Вычисляем значения функции ( ) в узлах построенной сетки .

4. Находим минимальное из этих значений:

5. Выполняем присваивания , , .

6. Если , то заканчиваем вычисления. Иначе - выполняем присваивание = +1 и переходим на п.2. Здесь _x – требуемая точность решения.

Рис. 2. Построение сетки на текущем интервале неопределенности.

В качестве приближенного значения точки минимума с равными основаниями может быть принята любая точка последнего текущего интервала неопределенности.

Первую итерацию приведенной схемы алгоритма равномерного поиска иллюстрирует рис. 3.

Рис. 3. Первая итерация поиск минимума одномерной унимодальной функции Ф(х) с помощью алгоритма равномерного поиска: N=13.

Легко видеть, что после одной итерации алгоритма равномерного поиска ТИН уменьшается в раз. Поэтому количество итераций , необходимых для нахождения минимума функции с точностью _x, может быть найдено из условия

1.2. Метод деления интервала пополам Метод деления интервала пополам позволяет исключить в точности половину интервала на каждой итерации. Реализация метода основана на выборе трех пробных точек, равномерно распределенных на интервале неопределенности. Пусть I = b - а длина интервала неопределенности [а,b]. Разделим интервал [а,b] точками x₁, x_c и х₂ на четыре равные части: х_с =

; x₁=

; x₂=b-

Вычисляются значения функции f( ), f( ) и f(x₂). Сравниваются полученные значения и находится новый интервал неопределенности следующим образом:

1) если f(x₁) < f(x_c), то полагают b= х_с. Средняя точка нового интервала х_с = x₁;

2) если f(x₂) < f(x_c), то полагают а = х_с. Средняя точка нового интервала х_с = х₂;

3) если f(x₁) = f(x₂), то полагают а = x_1, b = х₂, х_с — остается средней точкой нового интервала.

Затем снова вычисляют координаты х₁ , х₂ и продолжают поиск до выполнения условия b - а < s. За минимальное значение принимают х* = х_с.

Метод дихотомии

В алгоритм деления пополам или алгоритме равномерного дихотомического поиска испытания проводятся парами. Координаты каждой последующей пары испытаний разнесены между собой на величину , где - требуемая точность решения. Испытания производятся в середине ТИН. По значениям , полученным в этих точках, одна половина ТИН в силу унимодальности функции исключается из дальнейшего рассмотрения. Величина определяется требуемой точностью решения. Алгоритм относится к классу методов последовательного поиска.

Более строго описанную схему алгоритма можно записать в нижеследующем виде.

1. Выполняем присваивания , , , .

2. Вычисляем величины (см. рис. 1)
; .

3. Вычисляем значения функции ( ).

4. Если , то выполняем присваивания , , . Иначе - выполняем присваивания , ,

5. Если , то заканчиваем вычисления. Иначе - выполняем присваивание = +1 и переходим на п.2.

Рис. 4. К определению величин x₀^r,x₁^r,x₂^r.

Приведенную схему алгоритма равномерного дихотомического поиска иллюстрирует рис. 5.

Рис. 5. Первые две итерации поиска минимума одномерной унимодальной функции с помощью алгоритма равномерного дихотомического поиска.

Легко видеть, что после одной итерации алгоритма равномерного поиска ТИН уменьшается в 2 раза. Поэтому количество итераций , необходимых для нахождения минимума функции с точностью _x, находится из условия

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

( )= ( ).