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

Самым естественным и наиболее распространенным на практике является метод поиска экстремума путем последовательного деления отрезка пополам. Этот метод, известный еще в древней Греции, назван дихотомией (dicha - на две части + tome - сечение).

Ранее было показано, что при двух экспериментах (первая пара на рис. 15-9) лучше всего выбирать точки в середине интервала возможно ближе друг к другу. Тогда длина интервала неопределенности будет равна 0,5 + ε/2.

В третьем и четвертом экспериментах (вторая пара) точки выбираются вблизи середины получившегося интервала. Новый интервал неопределенности при этом равен:

После шести опытов (третья пара) интервал неопределенности составит:

После N опытов, где N - четное и конечное число, интервал неопределенности запишется как

Отсюда следует, что эффективность поиска при методе дихотомии растет с ростом N экспоненциально, тогда как при пассивном поиске однородными парами эффективность растет лишь прямо пропорционально N [см. формулу (15-5)].

Рис. 15-9. Пояснение к методу дихотомии