Метод поділу проміжку пополам

Н ехай на проміжку [а; b] функція f(х) неперервна і набуває на кінцях проміжку значень різних знаків, тобто f(а)•f(b) < 0. Це означає, що на [а; b] рівняння (1) має принаймні один корінь. Цей корінь можна визначити з наперед заданою точністю методом поділу проміжку пополам.

Суть методу полягає в тому, що проміжок, на якому міститься корінь, поступово звужують, зменшуючи його щоразу вдвоє, поки не досягнуть потрібної точності визначення кореня.

Позначимо лівий кінець проміжку, на якому міститься корінь, буквою u, правий – буквою v і знайдемо середину цього проміжку: х = (u+v)/2. Оскільки (за умовою) f(u)f(v)<0, то f(x)f(a)>0, або f (х)  f (а)< 0

Якщо f(x) = 0, то корінь х* = х.

Зрозуміло, що у випадку f(х)f(а)>0 корінь міститься на проміжку [x; v].

У випадку f(х)f(а)<0 корінь міститься на проміжку [u; х]. Якщо довжина проміжку, на якому міститься корінь, не перевищує заданої величини , то це означає, що х* знайдено з точністю до , бо |х - х*|  x-u. Якщо заданої точності ще не досягнуто, то, позначивши х через u у випадку f(х) f(а) > 0 або через v у випадку f(х)f(а)<0, знову знаходимо середину проміжку [u; v] і повторюємо обчислення.

Переконатися в тому, що потрібна точність при обчисленні кореня х* уже досягнута, можна й іншим способом. Якщо на деякому проміжку [u; v] функція f(х) диференційовна і 0 < m  |f(х)| (у цьому випадку на [u; v] міститься єдиний корінь рівняння f(х) = 0) і якщо

то можна вважати, що х — наближене значення кореня х* з точністю до .

Приклад.

Методом поділу проміжку пополам знайти з точністю до 0,005 корінь рівняння x³+1,76439x²+2,21584x – 3,31344 = 0, що лежить на проміжку [0;1].

Розв’язання.

Як бачимо, проміжок локалізації кореня рівняння нам задано: [0;1], тобто залишилось скласти програму для даної задачі. Оскільки точність наближеного визначення кореня буде визначати момент закінчення циклу, то, очевидно, доцільно скористатись в даному випадку циклом з умовою. Той факт, що проміжок локалізації кореня значно перевищує точність, то наперед можна сказати, що як мінімум один раз тіло циклу буде виконуватись, а отже ми можемо використовувати як цикл з передумовою, так і цикл з післяумовою без будь-яких обмежень. Один з варіантів програми реалізації поставленої задачі може виглядати так:

program Podil;

const e = 0.005;

var a, b, c, d, y1, у2: real;

begin

writeln (’ввести значення кінців проміжка локалізації кореня’);

readln (a, b);

repeat

c:=(a+b)/2;

y1:=a*a*a+1.76439*a*a+2.21584*a – 3.31344;

y2:=c*c*c+1.76439*c*c+2.21584*c – 3.31344;

if y1*y2<0 then b:=c else a:=c;

d:=b-a;

until d >= e;

writeln (‘x*=’,c,’+-e’);

end.

Результатом розв’язку даної задачі буде х*=0,785  0,005;