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

Метод бісекції або метод поділу відрізка навпіл — найпростіший чисельний метод для вирішення нелінійних рівнянь виду 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.

Посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.