3.2. Пассивный поиск.

Пассивные методы недостаточно эффективны по сравнению с последовательными. Однако они все-таки используются, в частности, если все эксперименты должны проводиться одновременно.

Чтобы уменьшить интервал неопределенности, требуется провести по крайней мере два эксперимента. Информация, получаемая из единственного эксперимента бесполезна, т.к. . Если проводятся только два эксперимента, то наилучшим их размещением являются и , т.е. эксперименты должны проводиться в центре интервала, как можно ближе друг к другу, как показано на Рис.2. Интервал неопределенности после двух таких экспериментов , т.е. уменьшается приблизительно в два раза.

Рис.2

Общая формула для оптимального размещения экспериментов при их четном числе имеет вид

,

Где означает целую часть числа. При этом максимум находится в интервале , где - эксперимент, в котором получено наибольшее значение . Интервал неопределенности равен , т.е. он уменьшается прямо пропорционально числу опытов. На Рис.3 показано оптимальное размещение 6 экспериментов при последовательном поиске. Такое размещение экспериментов называется поиском однородными парами. Проведение нечетного числа опытов обычно нецелесообразно.

Рис.3

3.3. Последовательный поиск.

Метод дихотомии (половинного деления)

Первые два эксперимента проводятся посередине исходного интервала возможно ближе друг к другу: и . Интервал, не содержащий максимума отбрасывается, как показано на Рис.4. Длина оставшегося интервала равна

Третий и четвертый эксперименты проводятся в центре оставшегося интервала. Новый интервал неопределенности равен . Подобным же образом проводятся пятый и шестой эксперимент, а также последующие. На Рис.4 , , . После экспериментов ( должно быть четным) интервал неопределенности .

Рис.4

Как видно, интервал неопределенности уменьшается экспоненциально с ростом . Условие окончания итерационного процесса . При пассивном поиске для уменьшения исходного интервала неопределенности в 100 раз требуется 198 экспериментов, тот же результат достигается дихотомией уже после 14 экспериментов (см. Табл.1)

Метод Фибоначчи.

Еще более совершенной является стратегия поиска с использованием последовательности чисел Фибоначчи, определяемой следующим образом:

,

Первыми членами этой последовательности являются числа 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

В методе Фибоначчи число экспериментов задается априорно. Соответственно, - й эксперимент производится на расстоянии от одного из концов текущего интервала неопределенности или на расстоянии от другого конца. При этом , , а остальные интервалы неопределенности могут определяться из соотношения

Допустим, . Тогда , , , , , , . Схема проведения эксперимента показана на Рис.5. Предполагается, что , , ,

Рис.5

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

В методе Фибоначчи каждый новый эксперимент сокращает интервал неопределенности в отличии от метода дихотомии, где интервал неопределенности уменьшается только после первых двух экспериментов. Поэтому эффективность метода Фибоначчи выше, чем метода дихотомии (см.Таблицу 1). Так например, для уменьшения исходного интервала неопределенности в 100 раз метод Фибоначчи требует 11 экспериментов, а метод дихотомии - 14. Единственный недостаток у метода Фибоначчи – это необходимость до начала опытов определять их необходимое число. Воспользоваться методом Фибоначчи, не зная заранее числа предполагаемых опытов, нельзя.

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

Метод золотого сечения почти также эффективен, как и метод Фибоначчи. Однако он совершенно не зависит от числа готовящихся экспериментов. К тому же организация его вычислительного процесса проще.

Золотым сечением отрезка называется деление отрезка на две части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей. Золотое сечение отрезка производят две точки: , , где Замечательно то, что в свою очередь производит золотое сечение отрезка , а - золотое сечение .

У метода золотого сечения начальный отрезок делится точками и , расположенными на расстоянии от концов отрезка. По результатам экспериментов и определяют, какой отрезок необходимо оставить для дальнейшего исследования, а какой отбросить. На оставшемся интервале уже есть одна точка производящая золотое сечение. Симметрично этому эксперименту определяется третья точка на расстоянии от отброшенного конца и т.д. После экспериментов интервал неопределенности . Применение метода золотого сечения иллюстрируется на Рис.6. Здесь , , . Условие окончания итерационного процесса

Рис.6

В методе золотого сечения интервал неопределенности после каждого шага уменьшается в раз. Для уменьшения интервала неопределенности в 100 раз требуется 11 экспериментов. При достаточно больших интервал неопределенности в методе золотого сечения только на 17,5 больше, чем в методе Фибоначчи (см.Таблицу 1)

Таблица 1.

Сокращение исходного интервала при различных методах последовательного поиска

Число опытов	Метод дихотомии	Метод Фибоначчи	Метод золотого сечения
2	2	2	1,618
3	2	3	2,618
4	4	5	4,236
5	4	8	6,854
6	8	13	11,089
7	8	21	17,942
8	16	34	29,030
9	16	55	46,971
10	32	89	75,999
11	32	144	122,966
12	64	233	198,959
13	63	377	321,916
14	128	610	520,860
15	128	987	842,751
16	256	1597	1363,571
17	256	2584	2206,258
18	512	4181	3569,725
19	512	6765	5775,815
20	1024	10946	9345,269
21	1024	17711	15120,645
22	2048	28657	24465,203
23	2038	46368	39584,699
24	4096	75025	64018,043
25	4096	121393	103629,733

Задание

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

Используйте процедуры для нахождения

а). максимума функций: , ,

б). минимума функций: , ,