Метод бісекції

Метод бісекції або метод поділу відрізка навпіл — найпростіший чисельний метод для вирішення нелінійних рівнянь виду f(x)=0. Передбачається тільки безперервність функції f(x). Пошук ґрунтується на теоремі про проміжні значення.

Обґрунтування

Алгоритм заснований на наступному наслідку з теореми Больцано — Коші:

Нехай безперервна функція $f(x)\in \mathrm {C} ([a,\;b])$, тоді, якщо $sign(f(a))\neq sign(f(b))$, то $\exists c\in [a,\;b]:\;f(c)=0$.

Таким чином, якщо ми шукаємо нуль, то на кінцях відрізка функція повинна бути протилежних знаків. Розділимо відрізок навпіл і візьмемо ту з половинок, на кінцях якої функція як і раніше приймає значення протилежних знаків. Якщо значення функції в серединній точці виявилося потрібним нулем, то процес завершується.

Точність обчислень задається одним з двох способів:

1. $\varepsilon _{f(x)}$ по осі $y$, що ближче до умови $f(x)=0$ з опису алгоритму; або
2. $\varepsilon _{x}$, по осі $x$, що може виявитися зручним в деяких випадках.

Процедуру слід продовжувати до досягнення заданої точності.

Для пошуку довільного значення досить відняти від значення функції шукане значення і шукати нуль функції що вийшла.

Опис алгоритму

Завдання полягає в знаходженні коренів нелінійного рівняння

$f(x)=0.\qquad (1)$

Для початку ітерацій необхідно знати відрізок $[x_{L},x_{R}]$ значень $x$, на кінцях якого функція приймає значення протилежних знаків. Протилежність знаків значень функції на кінцях відрізка можна визначити багатьма способами. Один з безлічі цих способів — множення значень функції на кінцях відрізка і визначення знака похідної шляхом порівняння результату множення з нулем:

$f(x_{L})\cdot f(x_{R})<0,\qquad (2.1)$

в дійсних обчисленнях такий спосіб перевірки протилежності знаків при крутих функціях призводить до передчасного переповнення.

Для усунення переповнення і зменшення витрат часу, тобто для збільшення швидкодії, на деяких програмно-комп'ютерних комплексах протилежність знаків значень функції на кінцях відрізка потрібно визначати за формулою:

$sign(f(x_{L}))\neq sign(f(x_{R})),\qquad (2.2)$

так як одна операція порівняння двох знаків двох чисел вимагає меншого часу ніж дві операції: множення двох чисел (особливо з плаваючою комою і подвійною довжиною) і порівняння результату з нулем. При даному порівнянні, значення функції $f(x)$ в точках $x_{L}$ і $x_{R}$ можна не обчислювати, досить обчислити тільки знаки функції $f(x)$ в цих точках, що вимагає меншого машинного часу.

З безперервності функції $f(x)$ і умови (2.2) випливає, що на відрізку $[x_{L},x_{R}]$ існує хоча б один корінь рівняння (в разі не монотонної функції $f(x)$ функція має кілька коренів і метод призводить до знаходження одного з них).

Знайдемо значення $x$ в середині відрізка:

$x_{M}=(x_{L}+x_{R})/2,\qquad (3)$

в дійсних обчисленнях, для зменшення числа операцій, на початку, поза циклом, обчислюють довжину відрізка за формулою:

$x_{D}=(x_{R}-x_{L}),$

а в циклі обчислюють довжину чергових нових відрізків за формулою: $x_{D}=x_{D}/2$ і нову середину за формулою:

$x_{M}=x_{L}+x_{D}.$

Обчислимо значення функції $f(x_{M})$ в середині відрізка $x_{M}$:

• Якщо $f(x_{M})=0$ або, в дійсних обчисленнях, $|f(x_{M})|\leq \varepsilon _{f(x)}$, де $\varepsilon _{f(x)}$ — задана точність по осі $y$, то корінь знайдений.
• Інакше $f(x_{M})\neq 0$ або, в дійсних обчисленнях, $|f(x_{M})|>\varepsilon _{f(x)}$, то розіб'ємо відрізок $[x_{L},x_{R}]$ на два рівних відрізка: $[x_{L},x_{M}]$ і $[x_{M},x_{R}]$.

Тепер знайдемо новий відрізок, на якому функція змінює знак:

• Якщо значення функції на кінцях відрізка мають протилежні знаки на лівому відрізку, $f(x_{L})\cdot f(x_{M})<0$ або $sign(f(x_{L}))\neq sign(f(x_{M}))$, то, відповідно, корінь знаходиться всередині лівого відрізка $[x_{L},x_{M}]$. Тоді візьмемо лівий відрізок присвоєнням $x_{R}=x_{M}$, і повторимо описану процедуру до досягнення необхідної точності $\varepsilon _{f(x)}$ по осі $y$.
• Інакше значення функції на кінцях відрізка мають протилежні знаки на правому відрізку, $f(x_{M})\cdot f(x_{R})<0$ або $sign(f(x_{M}))\neq sign(f(x_{R}))$, то, відповідно, корінь знаходиться всередині правого відрізка $[x_{M},x_{R}]$. Тоді візьмемо правий відрізок присвоєнням $x_{L}=x_{M}$, і повторимо описану процедуру до досягнення необхідної точності $\varepsilon _{f(x)}$ по осі $y$.

За кількість ітерацій $N$ поділ навпіл здійснюється $N$ раз, тому довжина кінцевого відрізка в $2^{N}$ разів менше довжини вихідного відрізка.

Існує схожий метод, але з критерієм зупинки обчислень $\varepsilon _{x}$ по осі $x$, в цьому методі обчислення тривають до тих пір, поки, після чергового поділу навпіл, новий відрізок більше заданої точності по осі $x$: $(x_{R}-x_{L})>\varepsilon _{x}$. У цьому методі відрізок на осі $x$ може досягти заданої величини $\varepsilon _{x}$, а значення функцій $f(x)$ (особливо крутих) на осі $y$ можуть дуже далеко стояти від нуля, при пологих же функціях $f(x)$ цей метод призводить до великої кількості зайвих обчислень.

У дискретних функціях $x_{L},x_{M}$ і $x_{R}$ — це номера елементів масиву, які не можуть бути дробовими, і, в разі другого критерію зупину обчислень, різниця $(x_{R}-x_{L})$ не може бути менше $\varepsilon _{x}=1$.

Псевдокод

Нехай

• x_n — початок відрізка по х;
• x_k — кінець відрізка по х;
• x_i — середина відрізка по х;
• eps_y — необхідна точність обчислень по y (задане наближення інтервалу [x_n; x_k]: x_k — x_n до нуля).

Тоді алгоритм методу бісекції можна записати в псевдокоді наступним чином:

1. Початок.
2.     Введення x_n, x_k, eps_y.
3.     Якщо F(x_n) = 0, то висновок (корінь рівняння — x_n).
4.     Якщо F(x_k) = 0, то висновок (корінь рівняння — x_k).
5.     Поки x_k — x_n > eps_y повторювати:
6.         dx := (x_k — x_n)/2
7.         x_i := x_n + dx;
8.         якщо sign(F(x_n)) ≠ sign(F(x_i)), то x_k := x_i;
9.         інакше x_n := x_i.
10.     кінець повторювати
11.     Висновок (Знайдено корінь рівняння — x_i з точністю по y — eps_y).
12. Кінець.

Пошук значення кореня монотонної дискретної функції

Пошук найбільш наближеного до кореня значення в монотонної дискретної функції, заданої таблично і записаної в масиві, полягає в розбитті масиву навпіл (на дві частини), виборі з двох нових частин тієї частини, в якій значення елементів масиву змінюють знак шляхом порівняння знаків серединного елемента масиву зі знаком граничного значення і повторенні алгоритму для половини в якій значення елементів масиву змінюють знак.

Нехай змінні ліваГраниця і праваГраниця містять, відповідно, ліву лівГран и праву правГран межі масиву, в якій знаходиться наближення до кореня. Дослідження починається з розбиття масиву навпіл (на дві частини) шляхом знаходження номера середнього елемента масиву середина .

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

Наприклад, якщо довжина масиву дорівнює 1023, то після першого порівняння область звужується до 511 елементів, а після другого — до 255. Т.о. для пошуку наближення до кореня в масиві з 1023 елементів досить 10 проходів (ітерацій).

Псевдокод:

ліваГраниця = лівГран
праваГраниця = правГран
while (праваГраниця - ліваГраниця > 1) {
   довжинаВідрізка = правГран - лівГран
   половинаВідрізка = int(довжинаВідрізка / 2)
   середина = ліваГраниця + половинаВідрізка
   if (sign(масив[ліваГраниця]) ≠ sign(масив[середина]))
      праваГраниця = середина
   else
      ліваГраниця = середина
}
printf середина

Див. також

• Лінійний пошук
• Двійковий пошук
• Метод дихотомії
• Метод золотого перетину
• Тернарний пошук
• Метод Ньютона

Джерела

• Волков Е. А. Глава 4. Методы решения нелинейных уравнений и систем. § 26. Метод деления отрезка пополам // Численные методы. — Учеб. пособие для вузов. — 2-е изд., испр. — М. : Наука, 1987. — С. 190.
• Burden, Richard L.; Faires, J. Douglas (1985), 2.1 The Bisection Algorithm, Numerical Analysis (вид. 3rd), PWS Publishers, ISBN 0-87150-857-5

Посилання

• Рішення рівнянь методом бісекції онлайн
• Метод бісекції на сервері застосування Mathcad.
• Метод бісекції Mathcad, Maple, Matlab, Mathematica
• Використання методу бісекції в програмуванні вільно поширювана програма для обчислення ізоелектричної точки.