2. Дихотомия (деление пополам).

Пусть мы нашли такие точки что , т. е. на отрезке лежит не менее одного корня уравнения. Найдем середину отрезка и вычислим Из двух половин отрезка выберем ту, для которой ибо один из корней лежит на этой половине. Затем новый отрезок опять делим пополам и выберем ту половину, на концах которой функция имеет разные знаки, и т. д. (рис. 26).

Если требуется найти корень с точностью , то продолжаем деление пополам до тех пор, пока длина отрезка не станет меньше . Тогда середина последнего отрезка даст значение корня с требуемой точностью.

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

Скорость сходимости невелика; за одну итерацию точность увеличивается примерно вдвое, т. е. уточнение трех цифр требует 10 итераций. Зато точность ответа гарантируется.

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

Дихотомия применяется тогда, когда требуется высокая надежность счета, а скорость сходимости малосущественна.

Рис. 26.

Рис. 27.