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

Пусть дано уравнение f(x)=0. Будем считать, что его корень отделен на отрезке (a; b). Требуется найти приближенное значение корня с точностью до , где - достаточно малое положительное число. Примем, что искомая функция непрерывна на отрезке отделения, следовательно, можно утверждать, что выполняется неравенство . Разделим отрезок (a; b) пополам точкой с (рисунок 8):

и вычислим значение . Если , то корень найден и . В противном случае и надо переходить к другому отрезку, заменив одно из ограничений (a или b) на новое – с. Новые ограничения должны быть такими, чтобы на их концах функция f(x) опять имела разные знаки.

Вычислим f(c). Далее проведем следующий анализ:

- если , то необходимо произвести замену и теперь корень будем уточнять на отрезке (с; b);

Рисунок 8 - К вычислению корня методом деления пополам

- если , то необходимо произвести замену и тогда корень уточняем на отрезке (а; с) (выбор границы отрезка не имеет принципиального значения).

Предположим, имеет место первый вариант замены. Тогда на втором шаге рассчитывают

и снова вычисляют f(c₁). Производят анализ по вышеприведенной схеме. Если, например, произведение , то назначают новый отрезок (с₁; с) и т.д. В результате получают бесконечную последовательность вложенных отрезков таких, что при всех n. Для того, чтобы найти значение корня с точностью до , необходимо остановить процесс половинного деления на таком шаге n, на котором отрезок будет иметь длину

или .

Тогда приближенное значение корня можно рассчитать по выражению:

.

Метод половинного деления дает простой и удобный алгоритм уточнения корней с любой наперед заданной точностью. Он требует от функции f(x) легко проверяемых свойств: непрерывности на отрезке отделения корня и разницы знаков на его концах. Количество шагов приближения зависит лишь от отрезка (a; b) и заданной точности . Его можно рассчитать следующим образом:

.

Задача 7. Найти корень уравнения с двумя верными цифрами.

Решение. Выполним процедуру отделения корней. Обозначим и . Тогда можно записать или . Напишем ряд значений функций в районе нуля (таблица 3):

Таблица 3 - Отделение корня уравнения

x	-3	-2	-1
y1	-27	-8	-1
y2	-2	-1

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

На нулевом этапе расчета получаем с=1, 5, а . Уже тут можно утверждать, что в значении с первая цифра 1 – верная (т.к. ). Проведя серию вычислений, смысл которых ясен из таблицы, очевидно, что, когда на четвертом этапе вычислений получено значение , мы получим вторую верную цифру корня – 3. Таким образом, если следовать заданию, корень равен или 1, 31< < 1, 37.

Таблица 4 - Вычисление корня уравнения

	a	b	f(a)	f(b)	c=(a+b)/2	f(c)	(b-a)/2	f(a).f(c)
			-1		1, 5	0, 875	0, 5	< 0
		1, 5	-1	0, 875	1, 25	-0, 297	0, 25	> 0
	1, 25	1, 5	-0, 297	0, 875	1, 375	0, 2246	0, 125	< 0
	1, 25	1, 375	-0, 297	0, 2246	1, 3125	-0, 05151	0, 0625	> 0
	1, 3125	1, 375	-0, 05151	0, 2246	1, 3437	0, 0824	0, 03125	< 0
	1, 3125	1, 3437	-0, 05151	0, 0824	1, 3276	0, 01232	0, 0156	< 0

В приложении А приведена блок-схема алгоритма решения уравнения методом половинного деления (рисунок А.1).