Алгоритм нахождения корня уравнения на отрезке методом деления пополам

Рассмотрим рисунок 1. На нем видно, что на участке от А до В функция f(x) имеет один корень уравнения f(x)=0, но точного значения мы не знаем. Для того чтобы удостовериться в наличии корней уравнения на отрезке, можно подставить в уравнение известной функции значения концов отрезка и перемножить их. Если итоговое значение отрицательно, это значит, что функция точно лежит по обе стороны от оси Х; в противном случае это может означать, что функция расположена с одной стороны от оси Х (причем график может проходить , как над осью Х (см. рис. 2), так и под ней), и корней не существует, либо корни есть, но они находятся где-то внутри интервала А-В.

Сейчас рассмотрим только первый случай – функция пересекает ось Х на интервале, т.е. имеет корень. Возьмем среднее значение между А и В (точку С), посчитаем в ней значение функции, если произведение f(a)·f(c) меньше нуля, то корень нужно искать уже на меньшем отрезке (А;С), если же произведение значений функции было бы положительным, то поиск продолжился бы на отрезке (В;С). Таким образом, за одну итерацию мы уменьшили область поиска в 2 раза. В новом отрезке необходимо повторить эти действия; область поиска повторно уменьшится в 2 раза – искать корень надо на отрезке (С2;С) (см. рис. 1). Выполнять данные итерации можно до бесконечности, поэтому необходимо установить критерий окончания поиска, например, это может быть сближение значений концов отрезка до определенной величины, т.е. выполнять повторные действия пока В-А>ε. Как только мы выходим из цикла, это значит, что корень найден с определенной точностью ε.

При реализации данного алгоритма будут введены только две дополнительных переменных fc и С, С необходима для получения средней точки текущего отрезка, fc соответственно для хранения значения функции в данной точке. Уменьшать же отрезок можно простым переприсваиванием значения С либо переменной А, либо В.

Рис.1. Пересечением графиком функции f(x) оси х

Рис.2. Расположение графика при отсутствии корней уравнения f(x)=0