Алгоритм приближенного вычисления корня методом половинного деления.

Исходные данные:

f (x) – функция;

ε; – требуемая точность;

a, b – границы заданного интервала (границы поиска корня).

Результат: x_пр – приближенный корень уравнения f (x) = 0.

Метод решения:

Шаг 1. Выбрать середину отрезка в качестве приближенного корня.

Шаг 2. Если , то c – искомый корень уравнения, на этом прекращаем вычисления. В противном случае перейти к шагу 3.

Шаг 3. Точный корень уравнения x^* отличается от c не более чем на половину длины отрезка, т.е. не более чем на (полученная точность). Проверяем условие . Если условие не выполняется, т.е. полученная точность нас не устраивает (она больше, чем требуемая), то перейти к шагу 4; в противном случае прекратить вычисления, поскольку мы достигли требуемой точности, и приближенным корнем уравнения f (x) = 0 считать середину c отрезка .

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

Случай 1 (рис. 7). Корень на отрезке . , граница b сдвигается влево – заменить b на с: b:= c.

Случай 2 (рис. 7). Корень на отрезке . , граница a сдвигается вправо – заменить a на с: a:= c.

 

Рис. 7. Графическая иллюстрация метода половинного деления.

 

Перейти к шагу 1.

 

Алгоритм деления отрезка пополам довольно медленный, но зато абсолютно застрахован от неудач. Основное достоинство метода состоит в том, что его скорость сходимости не зависит от вида функции f (x). Данный метод не имеет дополнительных условий сходимости, кроме .