Метод деления отрезка пополам

Рассмотрим простой, но надежный метод для вычисления корней. Пусть некоторый отрезок [a, b] = I содержит единственный корень. Стратегия этого метода состоит в том, что мы делим интервал I пополам и затем оставляем только половину этого интервала, содержащую корень. Очевидно, что половина, на которой функция f (x) меняет знак, содержит корень. Это дает нам способ определить, какую половину оставить и затем использовать для дальнейших вычислений. Метод деления отрезка пополам можно представить в виде блок-схемы, показанной на рис. 2.2.

Таким образом, на каждом шаге вычислительного процесса х* лежит внутри интервала [ak, bk —> а^_у b^), и как только длина этого интервала становится меньше чем г_р, итерационный процесс завершается. В этом методе используется минимальная информация о функции f (x) (знак f (x)). Поэтому требуется относительно большое число итераций, но сходимость этого метода гарантирована.

Рис. 2.2. Блок-схема, представляющая метод деления отрезка пополам.

Оценим количество итераций, необходимых для вычисления корня. Легко видеть, что длина интервала [аb уменьшается в два раза на каждом шаге итерационного процесса. Вычисления завершаются, когда.

Для оценки числа итераций k выберем знак «= «, тогда.

где [у] означает целую часть у. Например, если b — а = 1 и г_р= 10^-5, мы получим k = 17.

Пример 2.1 (метод деления отрезка пополам) Результаты расчетов представлены в табл. 2.1.

Таблица 2.1