Алгоритм

1. На начальном этапе отрезок, на котором ищется минимум, задаётся равным интервалу допустимых значений [ a, b ]

2. Вычисляется положение центра отрезка c =(a + b)/2 и центров его правой и левой половин: x ₁=(a + c)/2, x ₂=(c + b)/2

3. Вычисляются значения целевой функции в точках f(c), f(x ₁), f(x ₂)

4. Значения функции в точках c, x ₁, x ₂ сравниваются, и определяется положение нового, уточнённого интервала поиска. При этом интервал поиска уменьшается в 2 раза:

1. Если f(c) > f(x ₁), то новый отрезок: [ a, c ]

2. Если f(c) > f(x ₂), то новый отрезок: [ c, b ]

3. Иначе новый отрезок: [ x ₁, x ₂]

5. Если длина отрезка меньше заданной точности ε, то алгоритм завершается, иначе осуществляется переход на шаг 2.

Алгоритм проиллюстрирован рис. 2.

Рис. 2. Метод дихотомии. Показан случай, когда f(x ₁)<f(c)

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

Так как каждый последующий отрезок всегда ровно в 2 раза меньше предыдущего, метод дихотомии обеспечивает увеличение точности в 2 раза за каждые 2 вычисления целевой функции, или, в среднем, в 2^1/2 = 1,41... раза на 1 вычисление целевой функции.