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

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

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

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

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

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

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

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

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

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

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

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

$f(x_L)\cdot f(x_R)<0,(2.1)$

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

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

$sign(f(x_L))\ne sign(f(x_R)),(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,(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)|\le {\epsilon }_{f(x)}$, де ${\epsilon }_{f(x)}$ — задана точність по осі $y$, то корінь знайдений.
• Інакше $f(x_M)\ne 0$ або, в дійсних обчисленнях, $|f(x_M)|>{\epsilon }_{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))\ne sign(f(x_M))$, то, відповідно, корінь знаходиться всередині лівого відрізка $[x_L,x_M]$. Тоді візьмемо лівий відрізок присвоєнням $x_R=x_M$, і повторимо описану процедуру до досягнення необхідної точності ${\epsilon }_{f(x)}$ по осі $y$.
• Інакше значення функції на кінцях відрізка мають протилежні знаки на правому відрізку, $f(x_M)\cdot f(x_R)<0$ або $sign(f(x_M))\ne sign(f(x_R))$, то, відповідно, корінь знаходиться всередині правого відрізка $[x_M,x_R]$. Тоді візьмемо правий відрізок присвоєнням $x_L=x_M$, і повторимо описану процедуру до досягнення необхідної точності ${\epsilon }_{f(x)}$ по осі $y$.

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

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

У дискретних функціях $x_L,x_M$ і $x_R$ — це номера елементів масиву, які не можуть бути дробовими, і, в разі другого критерію зупину обчислень, різниця $(x_R-x_L)$ не може бути менше ${\epsilon }_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 середина

Див. також

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

Джерела

• Шаблон:Книга
• Шаблон:Citation

Посилання

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