Уточнение корней методом половинного деления (дихотомии)

Самым простейшим из методов уточнения корней является метод половинного деления, или метод дихотомии, предназначенный для нахождения корней уравнений, представленных в виде (1).

Пусть функция f(x) удовлетворяет всем условиям теоремы о существовании корня непрерывной функции (см. с. 5). Предположим вначале, что мы находимся в условиях следствия 1 этой теоремы. Тогда на отрезке [a,b] (предполагаем, что a<b) существует единственный корень уравнения (1).

Метод половинного деления заключается в следующем:

Возьмем середину отрезка x₀=(a+b)/2. Если f(a)×f(x₀)£ 0, то корень явно принадлежит отрезку от a до x₀ и, в противном случае, от x₀ до b (рис.6). Отбрасываем “пустой” отрезок (не содержащий корня) и проводим соответствующие переобозначения концов отрезка. К примеру, на рис.6 после первого деления отрезка [a,b] пополам его серединой x₀, мы переходим к отрезку [a,x₀] и, следовательно, в качестве нового конца отрезка естественно выбрать b=x₀.

Рис. 6. Несколько этапов применения метода деления пополам

Полученный отрезок снова делим пополам точкой x₁ и выполняем действия сначала и т.д. Каждый такой шаг уменьшает в два раза длину отрезка, в границах которого заведомо имеется корень уравнения (1). Процесс деления отрезка продолжаем до тех пор, пока длина отрезка, на концах которого функция имеет противоположные знаки, не будет меньше заданного числа e. Любая точка такого отрезка подходит в качестве решения поставленной задачи. Удобно за приближенное значение корня принять середину отрезка [a,b], т.е. число . Реализация алгоритма метода половинного деления представлена на блок-схеме в прил. (см. с.52). Так как каждое очередное вычисление середины отрезка x_n и значения функции f(x_n) сужает интервал поиска вдвое, то при исходном отрезке [a,b] и предельной погрешности eколичество вычислений n определяется условием (b-a)/2ⁿ<e , или n>log₂((b-a)/e ). Например, при исходном единичном интервале и точности порядка 6 знаков (e ~ 10^-6) после десятичной точки достаточно провести 20 вычислений (итераций) значений функции.

Обратим внимание на следующее обстоятельство. Мы вначале предполагали, что на [a,b] существует единственный корень. Вообще говоря, если выполнены условия теоремы о существовании корней непрерывной функции (см. с.5), то уравнение (1), может иметь несколько корней (см., к примеру рис.3). Описанный выше алгоритм метода деления пополам позволит все-таки получить один из этих корней. Это следует из того, что после деления отрезка пополам мы всегда выбираем из двух меньших отрезков такой, в котором обязательно имеется корень уравнения (1). Как правило, перед тем как прибегать к помощи подобных алгоритмов, пытаются определить границы a и b настолько точно, чтобы в отрезке [a,b] содержался ровно один корень (см. следствие 1 или 2).