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

Метод основан на последовательном сужении интервала, содержащего единственный корень уравнения F(x)=0 до тех пор, пока не будет достигнута заданная точность. Пусть задан отрезок [a,b], содержащий один корень уравнения. Этот отрезок может быть предварительно найден с помощью шагового метода.

Рис. 3.4. иллюстрирует метод половинного деления, который состоит в постепенном сужении отрезка поиска корня до заданной величины e. На каждом шаге отрезок уменьшается вдвое.

Рис. 3.4. Иллюстрация метода половинного деления

В начале каждой итерации находим середину нового отрезка [a , b]

Затем следует определить, с какой стороны от середины отрезка x находится корень x*. Для этого достаточно сравнить знаки f (x) и f (b) или знаки f (x) и f (a).

Если знаки f (x) и f (b) не совпадают, то это означает, что f (x) пересекает ось x на правом полуотрезке [x, b]. Следовательно, корня нет на левом полуотрезке [a, x], и этот полуотрезок можно отбросить, то есть можно перенести левую границу a в среднюю точку x (заменить значение приближения a на значение x).

Если же знаки f (x) и f (b) совпадают, то f (x) пересекает ось x на левом полуотрезке [a, x] и, следовательно, корня нет на правом полуотрезке [x ,b], и этот полуотрезок можно отбросить, то есть можно перенести правую границу b в среднюю точку x (заменить значение приближения b на значение x).

Итак, в результате выполнения итерации отрезок [a, b] как и прежде, содержит единственный корень, но его длина стала меньше в два раза.

Вычисления следует прекратить, если на очередном шаге длина отрезка [a, b] станет меньше e. Тогда с точностью e любая точка этого отрезка будет являться корнем уравнения f(x), а середина этого отрезка - с точностью e/2.

Рассмотрим пример ручной реализации метода. Дано уравнение x²– 4x+ 3 = 0. Известно, что единственный корень уравнения расположен на отрезке [0,9;1,2]. Требуется уточнить значение корня методом половинного деления с точностью= 0,01. Построим таблицу в соответствии с алгоритмом метода.

a	x	b	F(a)	F(x)	F(a)*F(x)<0
0,9	1,05	1,2	0,21	-0,0975	да
0,9	0,975	1,05	0,21	0,050625	нет
0,975	1,0125	1,05	0,050625	-0,02484	да
0,975	0,99375	1,0125	0,050625	0,012539	нет
0,99375	1,003125	1,0125	0,012539	-0,00624	стоп

Алгоритм остановлен, поскольку -0,00624<0,01.

Ответ: уточненное значение корня x1,0031.

Достоинство метода:более быстрая сходимость к заданной точности, чем у шагового.Недостаток:если на отрезке [a,b] содержится более одного корня, то метод не работает.

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

Рис. 3.5. Корень является экстремумом функции (функция не меняет знак)