Метод деления отрезка пополам (метод дихотомии).

К этому методу может прийти любой человек, который имеет опыт вычислительной работы. Если функция на концах интервала [ a, b ] имеет разные знаки f (a)*f(b)< 0, то определяем точку c=0.5*(a+b) и проверяем знаки функций в точках a и c, b и c. Переходим к паре точек, где знаки разные и т.д. Процесс итераций окончен, если заданная точность по определению корня достигнута | b-a |< ε ₁. Можно использовать также заданную точность по значению функции в точке c: | f(c)| < ε ₂. Проиллюстрируем алгоритм на рис 1.7 и 1.8.

рис. 1.7 рис.1.8

Метод позволяет оценить скорость сходимости решения. Обозначим два последующих приближения x_i и x_i+1. Запишем очевидное соотношение . Можно утверждать, что метод сходится со скоростью n, если lim_{n→ ∞} .Если n=1, то имеет место линейная сходимость, а, если n=2, то сходимость квадратичная.

Отметим ряд особенностей метода, которые полезно знать для других методов. При малых значениях функций в исследуемых точках, например f(a) =10^-30 и f(b) =10^-30, их произведение может выйти за пределы разрядной сетки. Кроме того, вычисление с=0.5(a+b) лучше выполнять по формуле с=a+0.5(b-a). Пусть a =0.982 b =0.984и, в случае 3-х разрядной сетки, среднее значение может выйти за пределы интервала [ a, b ] c=0.5(a+b)=0.5*1.97=0.985. Для разных знаков a и b точнее оказывается обычная формула половинного деления (корень близок к нулю 0).

Поскольку скорость сходимости метода дихотомии не велика, большее распространение получили следующие методы.