Метод половинного деления
Ме́тод полови́нного деле́ния (метод дихотомии), 1) один из методов численного решения уравнений с одним неизвестным. Пусть имеется уравнение с непрерывной на отрезке функцией , принимающей на концах отрезка значения разных знаков и имеющей внутри единственный корень . Для приближённого нахождения отрезок делят пополам и вычисляют значение в средней точке . Если , то из двух отрезков и для последующего деления пополам выбирается тот, на концах которого значения функции различны по знаку. Возникающая в процессе такого дробления последовательность середин отрезков сходится к корню со скоростью геометрической прогрессии:
причём в рассматриваемом классе функций оценка (1) неулучшаема. В случае когда функция имеет на более одного корня, последовательность будет сходиться к одному из них.
2) Один из методов минимизации функций одного переменного. Пусть требуется найти минимум
унимодальной функции на отрезке и указать точку , в которой он достигается. Тогда отрезок делят пополам и вблизи его середины вычисляют значения функции в двух точках и , где число , являющееся параметром метода, достаточно мало. Затем значения и сравнивают и с учётом унимодальности функции из двух отрезков и выбирают тот, который заведомо содержит точку . Так, если , это будет отрезок , в противном случае – отрезок . Выбранный отрезок вновь делят пополам, вблизи его середины берут две точки и , сравнивают в них значения функции и т. д. В результате возникает последовательность срединных точек , для которой
За приближения к принимают значения при достаточно больших .
Название метода объясняется тем, что на каждом следующем шаге описанного алгоритма отрезок, содержащий точку минимума, становится примерно вдвое короче. На классе унимодальных функций метод половинного деления не является наилучшим. Существуют более эффективные методы, позволяющие при том же количестве вычислений значений функции достигнуть лучшей по сравнению с (2) точности (см., например, Метод Фибоначчи).