Метод деления отрезка пополам (метод дихотомии, метод бисекции)

Метод деления отрезка пополам является самым простым и надежным способом решения нелинейного уравнения.

Пусть из предварительного анализа известно, что корень уравнения (2.1) находится на отрезке [a0, b0], т. е. x* [a0, b0], так, что f(x*) = 0.

Пусть функция f(x) непрерывна на отрезке [a0, b0] и принимает на концах отрезка значения разных знаков, т.е.

f(a0)f(b0) < 0. (2.2)

Разделим отрезок [a0, b0] пополам. Получим точку x0 = . Вычислим значение функции в этой точке: f(x0). Если f(x0) = 0, то x0 – искомый корень, и задача решена. Если f(x0) 0, то f(x0) – число определенного знака: f(x0) > 0, либо f(x0) < 0. Тогда либо на концах отрезка [a0, x0], либо на концах отрезка [x0, b0] значения функции f(x) имеют разные знаки. Обозначим такой отрезок [a1, b1]. Очевидно, что x* [a1, b1], и длина отрезка [a1, b1] в два раза меньше, чем длина отрезка [a0, b0]. Поступим аналогично с отрезком [a1, b1]. В результате получим либо корень x*, либо новый отрезок [a2, b2], и т.д. (рис. 2.2).

Середина n-го отрезка xn = . Очевидно, что длина отрезка [an, bn] будет равна , а т. к. x* [an, bn], то

| xn – x*| Ј Ј . (2.3)

Погрешность метода. Оценка (2.3) характеризует погрешность метода деления отрезка пополам и указывает на скорость сходимости: метод сходится со скоростью геометрической прогрессии, знаменатель которой q = 1/2. Заметим, что оценка (2.3) является априорной.

Критерий окончания. Из соотношения (2.3) следует, что при заданной точности приближения e вычисления заканчиваются, когда будет выполнено неравенство bn – an < 2e или неравенство n > log2((b0 – a0)/e) – 1. Таким образом, количество итераций можно определить заранее. За приближенное значение корня берется величина xn.