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

Не плутати з двійковий пошук.

Не плутати з Дихотомія.

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

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

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

Нехай ${\displaystyle f(x)\in \mathrm {C} ([a,\;b])}$, тоді, якщо ${\displaystyle sign(f(a))\neq sign(f(b))}$, то ${\displaystyle \exists c\in [a,\;b]:\;f(c)=0}$.

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

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

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

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

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

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

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

${\displaystyle f(x)=0.\qquad (1)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

1. Ю. Губарь, Курс «Введение в математическое моделирование» Лекция 4: Численные методы решения нелинейных уравнений: Метод половинного деления // , 15.03.2007
2. Burden та Faires, 1985, с. 29

Джерела

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

Посилання

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