Алгоритм метода половинного деления (метод дихотомии)

Метод деления пополам позволяет исключать в точности половину интервала на каждой итерации. При использовании метода считается, что функция непрерывна и имеет на концах интервала разный знак. После вычисления значения функции в середине интервала одна часть интервала отбрасывается так, чтобы функция имела разный знак на концах оставшейся части. Итерации метода деления пополам прекращаются, если интервал становится достаточно малым.
Словесный алгоритм.
  1. Найдем отрезок [a,b]: f(a)f(b)<0.
  2. Положим c=(a+b)/2.
  3. Если f(a)f(c)<0, то положим b=c, в противном случае a=c.
  4. Если tex2html_wrap_inline1294, то tex2html_wrap_inline1296, в противном случае выполнить пункт 2.
Описание переменных
a - левая граница
b - правая граница
sigma - погрешность
max_step - максимальное кол-во шагов
x - найденный корень
f_a – значение функции в начале интервала
f_b – значение функции в конце интервала
xm – середина интервала
f_xm – значение функции в середине интервала
k – переменная цикла

Блок – схема алгоритма

Метод половинного деления на языке Pascal. Листинг

program dohometr;
var
a:real;		{левая граница}
b:real;		{правая граница}
sigma:real;	{погрешность}
max_step:longint;	{максимальное кол-во шагов}
x:real;		{найденный корень}

function f(x:real):real;{функция}
begin
f:=x*sin(x);
end;

function FindKoren(a,b:real):real;{уменьшение интервала неопределенности} 
var f_a,f_b,xm,f_xm:real;k:longint;
begin
k:=0;
f_a:=f(a);	       {устанавливаем первоначальное значение}
f_b:=f(b);	       {устанавливаем первоначальное значение}
while (b-a > sigma)and(k < max_step) do
		begin
		xm:=(a+b)/2;	          {середина интервала}
		f_xm:=f(xm);
if (f_a*f_xm <=0) then       {функция должна иметь разный знак}
			begin	          {на границах интервала}
			b:=xm;
			f_b:=f_xm	          {исключен левый подынтервал}
			end
			else
			begin
			a:=xm;
			f_a:=f_xm;	    {исключен правый подынтервал}
			end;
	end;
findkoren:=(a+b)/2;	    {ответ}
end;

begin
Write('Введите левый интервал, a = ');ReadLN(a);
Write('Введите правый интервал, b = ');ReadLN(b); 
sigma:=0.001;         {погрешность} 
max_step:=1000000;
WriteLN('Корень равен, х = ',FindKoren(a,b):10:3); 
end.

Перейти к онлайн решению своей задачи

Пример решения

Найти корни уравнения: x•sin(x) = 0
Решение.
Чтобы отыскать предварительные интервалы, строим график функции.

Как видно, первый корень лежит в интервале [-2;2], второй корень функции находится в интервале [2;4].
Уточним интервалы, в которых будут находиться корни уравнения. Для этого исходный интервал [2;4] разобьем на 10 подынтервалов.
h5 = 2 + 5*(4-2)/10 = 3
h6 = 2 + (5+1)*(4-2)/10 = 3.2
Поскольку F(3)*F(3.2)<0, то корень лежит в пределах [3;3.2].
Итерация 1.
Находим середину отрезка: c = (3 + 3.2)/2 = 3.1
F(c) = 0.13
F(x) = 0.42
Поскольку F(c)•F(x) > 0, то a=3.1
Итерация 2.
Находим середину отрезка: c = (3.1 + 3.2)/2 = 3.15
F(c) = -0.0265
F(x) = 0.13
Поскольку F(c)•F(x) < 0, то b=3.15
Итерация 3.
Находим середину отрезка: c = (3.1 + 3.15)/2 = 3.13
F(c) = 0.0518
F(x) = 0.13
Поскольку F(c)•F(x) > 0, то a=3.13
Итерация 4.
Находим середину отрезка: c = (3.13 + 3.15)/2 = 3.14
F(c) = 0.0128
F(x) = 0.0518
Поскольку F(c)•F(x) > 0, то a=3.14
Остальные расчеты сведем в таблицу.
N c a b f(c) f(x)
1 3.1 3 3.2 0.1289 0.1289
2 3.15 3.1 3.2 0.1289 -0.02648
3 3.125 3.1 3.15 0.05185 0.05185
4 3.1375 3.125 3.15 0.01284 0.01284
5 3.1438 3.1375 3.15 0.01284 -0.00678
6 3.1406 3.1375 3.1438 0.00304 0.00304
7 3.1422 3.1406 3.1438 0.00304 -0.00187
8 3.1414 3.1406 3.1422 0.000586 0.000586

Ответ: x = 3.14; F(x) = 0.000586
Количество итераций, N = 8
Параметр сходимости.
загрузка...