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

Пример

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

Алгоритм метода состоит из операций, описанных ниже.

Отрезок [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)a; c], и точку с будем считать точкой b; а если f(a)f(c)0, то корень находится на отрезке [c; b], и точку с будем считать точкой a.

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

Рис.1. Графическая иллюстрация метода половинного деления:

1…5 – интервалы уточнения корней на 1...5 шаге алгоритма

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

program PD;

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)