Метод половинного деления

Иначе этот метод также называют методом Больцано деления пополам или методом биекций, или методом дихотомии

Рис. 4. 2. Решение уравнения .

Пусть дано уравнение , известный интервал изоляции корня для данного уравнения, непрерывна на отрезке . Тогда график функции пересекает ось на интервале (начальном интервале) в точке и функция на концах интервала имеет разные знаки, то есть

. (4.2)

Основная идея метода дихотомии состоит в следующем: делим интервал изоляции пополам и выбираем ту половину, где функция меняет знак, получаем новый отрезок изоляции, длина которого в два раза меньше предыдущего. Эту процедуру повторяем до тех пор, пока длина отрезка изоляции не станет меньше заданной точности (рис.4.3). Рассмотрим это более детально.

Для нахождения корня делим интервал пополам. Если , то точка является корнем. Считаем, что . Тогда выберем ту из половин интервала или , на концах которой функция имеет разные знаки, и обозначим этот отрезок . Длина этого отрезка равна: .

Интервал снова делим пополам и выбираем новый интервал аналогично. Строим последовательность интервалов , каждый из которых вдвое меньше предыдущего, таким образом, получим последовательность вложенных друг в друга интервалов таких, что .

Рис. 4. 3. Последовательное сжатие интервалов изоляции корня

Этот процесс последовательного деления пополам продолжаем до тех пор, пока не выполнится одно из двух условий:

1. Или найдется такая точка , в которой и – точное значения корня (на практике получают достаточно редко).

2. Или на некотором шаге получаем интервал изоляции , длина которого меньше необходимой точности:

(4.3)

Левые концы отрезков образуют монотонную неубывающую последовательность , а правые – , образуют монотонную невозрастающую последовательность. Итак, эти последовательности имеют тот же предел :

Подставляя в (4. 2), перейдем к пределу получим

.

Получили противоречие, таким образом .

Поскольку корень принадлежит интервалу изоляции , то в этом случае, какое-либо число из этого отрезка отличается от точного значения корня меньше, чем на . Числа и являются приближенными значениями корня. Обычно берут число из середины последнего отрезка изоляции:

(4.4)

Можно заранее оценить количество делений пополам начального отрезка. Так как при делении длина отрезка уменьшается в два раза, то при достижении необходимой точности за шагов получим отрезок длиной . Отсюда можно выразить, прологарифмировав, :

(4. 5)

или

(4. 6)

Из этой формулы можно оценить число шагов. Кроме того, из нее можно увидеть, что для того, чтобы увеличить точность в раз, то есть, предположив, что , необходимо сделать дополнительно шагов.

Основным преимуществом метода биекций является надежность, устойчивость к ошибкам округления, уменьшение ограничений на вид функции (необходима также непрерывность). Главный недостаток – слабая сходимость к точному решению.

На практике метод биекций используют в комбинации с каким –нибудь быстросходящимся методом: методом биекций сначала грубо определяют начальное приближение, а потом используют быстросходящийся метод (например, метод Ньютона).

С точки зрения машинной реализации (рис. 4. 4) этот метод является наиболее простым и используется во многих стандартных программах.

Рис. 4.4. Блок-схема метода половинного деления