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

Алгоритм метода состоит из следующих операций.

Отрезок [a,b] делят пополам точкой c (c=(a+b)/2) и находят значение функции в точке с. Если f(c)=0, то корень уравнения соответствует точке c. Если f(c)¹0, то можно сузить диапазон поиска корня: перейти от отрезка [a,b] к отрезку [a,c] или [c,b] в зависимости от знака f(c). Если f(a)f(c)<0, то корень находится на отрезке [a,c], и точку с будем считать точкой b; а если f(a)f(c)>0, то корень находится на отрезке [c,b], и точку с будем считать точкой a.

Каждый такой шаг уменьшает в два раза интервал, в котором находится корень уравнения f(x)=0. После нескольких шагов получится отрезок, длина которого будет меньше или равна числу e, т.е. ½a-b½£e. Любая точка такого отрезка, например, один из его концов, подходит в качестве решения поставленной задачи. На рис. 16.2 показано несколько этапов применения алгоритма.

Рис.16.2. Графическая иллюстрация метода половинного деления: 1…5 – интервалы уточнения корней на 1...5 шаге алгоритма

Пример 1. Найти с точностью e=0,001 на отрезке [-2,1] корень уравнения x³+x²+x+1=0. Приведём текст программы, которая решает эту задачу методом половинного деления (результат выводится на экран и, по желанию пользователя, на принтер):

Program Popolam;

Uses Crt, Printer;

Var

a,b,c,eps,a0,b0:real;

k:integer;

ch:char;

Function f(x:real):real;

begin

{ Здесь приводим выражение для вычисления функции }

f:=x*x*x+x*x+x+1;

end;

Begin

ClrScr;

Writeln(' Решение уравнения методом половинного деления ');

{ Ввод исходных данных }

a:=-2; b:=1; eps:=0.001;

a0:=a; b0:=b; { Запоминаем исходные данные }

{ Начинаем расчет }

k:=0; { Счетчик повторений }

While abs(b-a)>=eps do

begin

k:=k+1;

c:=(a+b)/2;

if f(a)*f(c)<=0 then b:=c

else a:=c;

end;

Writeln(' Уравнение x^3+x^2+x+1=0 на отрезке [',a0:4:1, ',',
b0:4:1, '] имеет корень x = ', c:10:8);

Writeln(' f(x) = ',f(c):10:8);

Writeln('Точность ',eps:10:8, ' достигнута за ',
k,' итераций');

Write(' Печатать результаты на принтере? (Y/N)');

Repeat

ch:=ReadKey;

ch:= UpCase(ch);

Until (ch='Y') or (ch='N');

if ch='Y' then

begin

Writeln(lst,'Решение уравнения методом половинного деления');

Writeln(lst,' Уравнение x^3+x^2+x+1=0 на отрезке [',
a0:4:1, ',', b0:4:1, '] имеет корень x = ', c:10:8);

Writeln(lst,' f(x) = ',f(c):10:8);

Writeln(lst,' Точность ',eps:10:8, ' достигнута за ',
k,' итераций');

Writeln('Печать выполнена. Нажмите ENTER ');

Readln;

end;

End.