Перегляд вихідного коду сторінки Метод бісекції

{{distinguish|двійковий пошук}}
{{distinguish|Дихотомія}}

'''Метод бісекції''' '''або метод поділу [[відрізок|відрізка]] навпіл'''&nbsp;— найпростіший [[Чисельні методи|чисельний метод]] для вирішення [[Лінійна_функція#Нелінійні_функції|нелінійних рівнянь]] виду ''f''(''x'')=0. Передбачається тільки безперервність функції ''f''(''x''). Пошук ґрунтується на [[Теорема Больцано — Коші|теоремі про проміжні значення]].

== Обґрунтування ==
Алгоритм заснований на наступному наслідку з [[Теорема Больцано — Коші|теореми Больцано&nbsp;— Коші]]:
{{теорема|1=Нехай [[безперервна функція]] <math>f(x)\in\mathrm{C}([a,\;b])</math>, тоді, якщо <math>sign(f(a)) \ne sign(f(b))</math>, то <math>\exist c\in[a,\;b]:\;f(c)=0</math>.}}
Таким чином, якщо ми шукаємо нуль, то на кінцях відрізка функція повинна бути протилежних знаків. Розділимо відрізок навпіл і візьмемо ту з половинок, на кінцях якої функція як і раніше приймає значення протилежних знаків. Якщо значення функції в серединній точці виявилося потрібним нулем, то процес завершується.

Точність обчислень задається одним з двох способів:
# <math>\varepsilon_{f(x)}</math> по осі <math>y</math>, що ближче до умови <math>f(x)=0</math> з опису алгоритму; або
# <math>\varepsilon_x</math>, по осі <math>x</math>, що може виявитися зручним в деяких випадках.
Процедуру слід продовжувати до досягнення заданої точності.

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

== Опис алгоритму ==
Завдання полягає в знаходженні коренів [[Лінійна_функція#Нелінійні_функції|нелінійного рівняння]]
<center><math>f(x)=0. \qquad ( 1 )</math></center>
Для початку ітерацій необхідно знати відрізок <math>[x_L,x_R]</math> значень <math>x</math>, на кінцях якого функція приймає значення протилежних знаків.
Протилежність знаків значень функції на кінцях відрізка можна визначити багатьма способами. Один з безлічі цих способів&nbsp;— множення значень функції на кінцях відрізка і визначення знака похідної шляхом порівняння результату множення з нулем:
<center><math>f(x_L)\cdot f(x_R)<0, \qquad ( 2.1 )</math></center>
в дійсних обчисленнях такий спосіб перевірки протилежності знаків при крутих функціях призводить до передчасного [[Арифметичне переповнення|переповнення]].

Для усунення переповнення і зменшення витрат часу, тобто для збільшення швидкодії, на деяких програмно-комп'ютерних комплексах протилежність знаків значень функції на кінцях відрізка потрібно визначати за формулою:
<center><math>sign(f(x_L)) \ne sign(f(x_R)), \qquad ( 2.2 )</math></center>
так як одна операція порівняння двох знаків двох чисел вимагає меншого часу ніж дві операції: множення двох чисел (особливо з плаваючою комою і подвійною довжиною) і порівняння результату з нулем. При даному порівнянні, значення функції <math>f(x)</math> в точках <math>x_L</math> і <math>x_R</math> можна не обчислювати, досить обчислити тільки знаки функції <math>f(x)</math> в цих точках, що вимагає меншого машинного часу.

З безперервності функції <math>f(x)</math> і умови (2.2) випливає, що на відрізку <math>[x_L,x_R]</math> існує хоча б один корінь рівняння (в разі не [[Монотонна функція|монотонної функції]] <math>f(x)</math> функція має кілька коренів і метод призводить до знаходження одного з них).

Знайдемо значення <math>x</math> в середині відрізка:
<center><math>x_M=(x_L+x_R)/2,  \qquad ( 3 )</math></center>
в дійсних обчисленнях, для зменшення числа операцій, на початку, поза циклом, обчислюють довжину відрізка за формулою:
: <math>x_D=(x_R-x_L),</math>
а в циклі обчислюють довжину чергових нових відрізків за формулою: <math>x_D=x_D/2</math> і нову середину за формулою:
: <math>x_M=x_L+x_D.</math>
Обчислимо значення функції <math>f(x_M)</math> в середині відрізка <math>x_M</math>:
* Якщо <math>f(x_M)=0</math> або, в дійсних обчисленнях, <math>|f(x_M)|\leq\varepsilon_{f(x)}</math>, де <math>\varepsilon_{f(x)}
</math>&nbsp;— задана точність по осі <math>y</math>, то корінь знайдений.
* Інакше <math>f(x_M)\ne 0</math> або, в дійсних обчисленнях, <math>|f(x_M)|>\varepsilon_{f(x)}</math>, то розіб'ємо відрізок <math>[x_L,x_R]</math> на два рівних відрізка: <math>[x_L,x_M]</math> і <math>[x_M,x_R]</math>.

Тепер знайдемо новий відрізок, на якому функція змінює знак:
* Якщо значення функції на кінцях відрізка мають протилежні знаки на лівому відрізку, <math>f(x_L)\cdot f(x_M)<0</math> або <math>sign(f(x_L)) \ne sign(f(x_M))</math>, то, відповідно, корінь знаходиться всередині лівого відрізка <math>[x_L,x_M]</math>. Тоді візьмемо лівий відрізок присвоєнням <math>x_R=x_M</math>, і повторимо описану процедуру до досягнення необхідної точності <math>\varepsilon_{f(x)}</math> по осі <math>y</math>.
* Інакше значення функції на кінцях відрізка мають протилежні знаки на правому відрізку, <math>f(x_M)\cdot f(x_R)<0</math> або <math>sign(f(x_M)) \ne sign(f(x_R))</math>, то, відповідно, корінь знаходиться всередині правого відрізка <math>[x_M,x_R]</math>. Тоді візьмемо правий відрізок присвоєнням <math>x_L=x_M</math>, і повторимо описану процедуру до досягнення необхідної точності <math>\varepsilon_{f(x)}</math> по осі <math>y</math>.

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

Існує схожий метод, але з критерієм зупинки обчислень <math>\varepsilon_x</math> по осі <math>x</math><ref>Ю. Губарь, [http://www.intuit.ru/studies/courses/2260/156/lecture/2284?page=2#sect2 Курс «Введение в математическое моделирование» Лекция 4: Численные методы решения нелинейных уравнений]: Метод половинного деления // [[Интуит.ру]], 15.03.2007</ref>, в цьому методі обчислення тривають до тих пір, поки, після чергового поділу навпіл, новий відрізок більше заданої точності по осі <math>x</math>: <math>(x_R-x_L)>\varepsilon_x</math>. У цьому методі відрізок на осі <math>x</math> може досягти заданої величини <math>\varepsilon_x</math>, а значення функцій <math>f(x)</math> (особливо крутих) на осі <math>y</math> можуть дуже далеко стояти від нуля, при пологих же функціях <math>f(x)</math> цей метод призводить до великої кількості зайвих обчислень.

У дискретних функціях <math>x_L, x_M</math> і <math>x_R</math>&nbsp;— це номера елементів масиву, які не можуть бути дробовими, і, в разі другого критерію зупину обчислень, різниця <math>(x_R-x_L)</math> не може бути менше <math>\varepsilon_x=1</math>.

== Псевдокод ==
Нехай
* x<sub>n</sub>&nbsp;— початок відрізка по х;
* x<sub>k</sub>&nbsp;— кінець відрізка по х;
* x<sub>i</sub>&nbsp;— середина відрізка по х;
* eps<sub>y</sub>&nbsp;— необхідна точність обчислень по '''y''' (задане наближення інтервалу [x<sub>n</sub>; x<sub>k</sub>]: x<sub>k</sub>&nbsp;— x<sub>n</sub> до нуля).

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

# Початок.
#     Введення x<sub>n</sub>, x<sub>k</sub>, eps<sub>y</sub>.
#     Якщо F(x<sub>n</sub>) = 0, то висновок (корінь рівняння&nbsp;— x<sub>n</sub>).
#     Якщо F(x<sub>k</sub>) = 0, то висновок (корінь рівняння&nbsp;— x<sub>k</sub>).
#     Поки x<sub>k</sub>&nbsp;— x<sub>n</sub> > eps<sub>y</sub> повторювати:
#         dx := (x<sub>k</sub>&nbsp;— x<sub>n</sub>)/2
#         x<sub>i</sub> := x<sub>n</sub> + dx;
#         якщо sign(F(x<sub>n</sub>)) ≠ sign(F(x<sub>i</sub>)), то x<sub>k</sub> := x<sub>i</sub>;
#         інакше x<sub>n</sub> := x<sub>i</sub>.
#     кінець повторювати
#     Висновок (Знайдено корінь рівняння&nbsp;— x<sub>i</sub> з точністю по y&nbsp;— eps<sub>y</sub>).
# Кінець.

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

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

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

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

[[Псевдокод (мова опису алгоритмів)|Псевдокод]]:<ref>{{Harvnb|Burden|Faires|1985|p=29}}</ref>
<syntaxhighlight lang="C">
ліваГраниця = лівГран
праваГраниця = правГран
while (праваГраниця - ліваГраниця > 1) {
   довжинаВідрізка = правГран - лівГран
   половинаВідрізка = int(довжинаВідрізка / 2)
   середина = ліваГраниця + половинаВідрізка
   if (sign(масив[ліваГраниця]) ≠ sign(масив[середина]))
      праваГраниця = середина
   else
      ліваГраниця = середина
}
printf середина
</syntaxhighlight>

== Див. також ==
* [[Лінійний пошук]]
* [[Двійковий пошук]]
* [[Дихотомія|Метод дихотомії]]
* [[Метод золотого перетину]]
* [[Тернарний пошук]]
* [[Метод Ньютона]]

== Примітки ==
{{reflist}}

== Джерела ==
* {{книга |автор=Волков Е. А. |заголовок=Численные методы |видання=Учеб. пособие для вузов. — 2-е изд., испр. |місце=М. |видавництво=Наука |рік=1987 |сторінок=248 |частина=Глава 4. Методы решения нелинейных уравнений и систем. §&nbsp;26. Метод деления отрезка пополам |сторінки=190}}
* {{Citation | last1=Burden | first1=Richard L. | last2=Faires | first2=J. Douglas | title=Numerical Analysis | publisher=PWS Publishers | edition=3rd | isbn=0-87150-857-5 | year=1985 | chapter=2.1 The Bisection Algorithm | url-access=registration | url=https://archive.org/details/numericalanalys00burd }}

== Посилання ==
{{Вікіпідручник | Програмні реалізації методу бисекции | Програмні реалізації методу бисекции}}
* [http://millerbird.site11.com/Math/bisection.php Рішення рівнянь методом бісекції онлайн]
* [http://twt.mpei.ac.ru/mas/worksheets/Bisection.mcd Метод бісекції] на сервері застосування Mathcad.
* [http://numericalmethods.eng.usf.edu/topics/bisection_method.html Метод бісекції] Mathcad, Maple, Matlab, Mathematica
* [https://web.archive.org/web/20130429005222/http://isoelectric.ovh.org/ Використання методу бісекції в програмуванні] вільно поширювана програма для обчислення [[Ізоелектрична точка|ізоелектричної точки]].

[[Категорія:Чисельні методи розв'язування рівнянь]]
[[Категорія:Статті з прикладами коду мовою C]]