Метод половинного деления Паскаль: алгоритм, примеры решения

Метод половинного деления, он же метод дихотомии — это технический прием, при котором можно исключать половину отрезка (или любого промежутка) при каждом прохождении функции. Функция будет работать  непрерывно до тех пор, пока оставшийся промежуток от деления не будет слишком маленького значения. При каждом прохождении промежуток делится пополам — одна половина «отбрасывается», а вторая снова делится ровно посередине.

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

1.  У нас есть некий отрезок [c,d]: f(c)f(d)<0.


2.  Предположим что e=(c+d)/2.


3.  Если  f(c)f(d)<0, то предположим, что d=e, либо c=e.


4.  Если  х()= ,  тогда (х)= х + (x)f(x), либо должен выполниться второй пункт.

Что есть что:

• c — левосторонняя грань;


• d — правосторонняя грань;


• sigma — предел отклонения;


• max_step — максимальное количество итераций;


• х — корень;


• f_c — функция со значением начала исследуемого промежутка;


• f_d— функция с конечной величиной исследуемого промежутка;


• xm -  середина отрезка;


• f_xm — серединная величина функции отрезка;


• q — цикличная переменная.

На словах реализация метода деления отрезка пополам выглядит следующим образом:

• вводим значение начала и конца исследуемого промежутка [c,d];


• устанавливаем максимальную погрешность;


• устанавливаем максимальное количество прохождений функции;


• задаем функции первоначальное значение;


• находим середину отрезка и вычисляем функцию;


• повторяем  нахождение середины отрезка, в каждый раз исключая неподходящий интервал;


• находим нужный корень вычислений;


• завершаем наш  метод половинного деления.

Метод половинного деления на языке Паскаль

Смотрим, как все, что мы описывали выше словами, реализуется при помощи языка программирования Паскаль:
program dohometr;
var
с:real;  {левосторонняя грань}
d:real;  {правосторонняя грань}
sigma:real; {предел отклонения}
max_step:longint; {задаем наибольшее  количество прохождений}
x:real;  {корень, который нам нужно найти}
function f(x:real):real;{реализуем наш технический подход}
begin
f:=x*sin(x);
end;
function FindRoot(c,d:real):real;{уменьшаем промежуток неопределенных значений}
var f_с,f_в,xm,f_xm:real;k:longint;
begin
q:=0;
f_с:=f(с);   {присваиваем первостепенную величину c}
f_d:=f(d);  {присваиваем первостепенное величину d}
while (c-d > sigma)and(q< max_step) do
begin
xm:=(c+d)/2;   {отыскиваем центральную часть нашего исследуемого промежутка}
f_xm:=f(xm);
if (f_c*f_xm<=0) then  {наш подход должен включать равнозначное значение}
begin  {начинаем проверку окончаний промежутка}
d:=xm;
f_d:=f_xm   {исключаем подинтервал слева}
end
else
begin
c:=xm;
f_c:=f_xm;    {исключаем подинтервал справа}
end;
end;
findroot:=(с+в)/2;    {результат}
end;
begin
Write('Нужно ввести левостороннюю границу промежутка, с = ');ReadLN(с);
Write('Нужно ввести правостороннюю границу промежутка, d = ');ReadLN(d);
sigma:=0.0009;        {уровень отклонения}
max_step:=999999;
WriteLN('Найденный корень, х = ',FindRoot(c,d):11:4);
end.

Заключение

Метод половинного деления на Паскале реализуется довольно просто. При этом Pascal — это не единственный язык, чтобы реализовать метод деления отрезка пополам. Но об этом поговорим в других статьях.