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

ОбґрунтуванняРедагувати

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

Нехай безперервна функція  , тоді, якщо  , то  .

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

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

  1.   по осі  , що ближче до умови   з опису алгоритму; або
  2.  , по осі  , що може виявитися зручним в деяких випадках.

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

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

Опис алгоритмуРедагувати

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

 

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

 

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

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

 

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

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

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

 

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

 

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

 

Обчислимо значення функції   в середині відрізка  :

  • Якщо   або, в дійсних обчисленнях,  , де   — задана точність по осі  , то корінь знайдений.
  • Інакше   або, в дійсних обчисленнях,  , то розіб'ємо відрізок   на два рівних відрізка:   і  .

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

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

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

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

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

ПсевдокодРедагувати

Нехай

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

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

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

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

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

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

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

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

Псевдокод:[2]

ліваГраниця = лівГран
праваГраниця = правГран
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. 

ПосиланняРедагувати