Метод бісекції або метод поділу (відрізка) навпіл — найпростіший чисельний метод для вирішення виду f(x)=0. Передбачається тільки безперервність функції f(x). Пошук ґрунтується на (теоремі про проміжні значення).
Обґрунтування
Алгоритм заснований на наступному наслідку з (теореми Больцано — Коші):
|
Таким чином, якщо ми шукаємо нуль, то на кінцях відрізка функція повинна бути протилежних знаків. Розділимо відрізок навпіл і візьмемо ту з половинок, на кінцях якої функція як і раніше приймає значення протилежних знаків. Якщо значення функції в серединній точці виявилося потрібним нулем, то процес завершується.
Точність обчислень задається одним з двох способів:
по осі
, що ближче до умови
з опису алгоритму; або
, по осі
, що може виявитися зручним в деяких випадках.
Процедуру слід продовжувати до досягнення заданої точності.
Для пошуку довільного значення досить відняти від значення функції шукане значення і шукати нуль функції що вийшла.
Опис алгоритму
Завдання полягає в знаходженні коренів
Для початку ітерацій необхідно знати відрізок значень
, на кінцях якого функція приймає значення протилежних знаків. Протилежність знаків значень функції на кінцях відрізка можна визначити багатьма способами. Один з безлічі цих способів — множення значень функції на кінцях відрізка і визначення знака похідної шляхом порівняння результату множення з нулем:
в дійсних обчисленнях такий спосіб перевірки протилежності знаків при крутих функціях призводить до передчасного (переповнення).
Для усунення переповнення і зменшення витрат часу, тобто для збільшення швидкодії, на деяких програмно-комп'ютерних комплексах протилежність знаків значень функції на кінцях відрізка потрібно визначати за формулою:
так як одна операція порівняння двох знаків двох чисел вимагає меншого часу ніж дві операції: множення двох чисел (особливо з плаваючою комою і подвійною довжиною) і порівняння результату з нулем. При даному порівнянні, значення функції в точках
і
можна не обчислювати, досить обчислити тільки знаки функції
в цих точках, що вимагає меншого машинного часу.
З безперервності функції і умови (2.2) випливає, що на відрізку
існує хоча б один корінь рівняння (в разі не монотонної функції
функція має кілька коренів і метод призводить до знаходження одного з них).
Знайдемо значення в середині відрізка:
в дійсних обчисленнях, для зменшення числа операцій, на початку, поза циклом, обчислюють довжину відрізка за формулою:
а в циклі обчислюють довжину чергових нових відрізків за формулою: і нову середину за формулою:
Обчислимо значення функції в середині відрізка
:
- Якщо
або, в дійсних обчисленнях,
, де
— задана точність по осі
, то корінь знайдений.
- Інакше
або, в дійсних обчисленнях,
, то розіб'ємо відрізок
на два рівних відрізка:
і
.
Тепер знайдемо новий відрізок, на якому функція змінює знак:
- Якщо значення функції на кінцях відрізка мають протилежні знаки на лівому відрізку,
або
, то, відповідно, корінь знаходиться всередині лівого відрізка
. Тоді візьмемо лівий відрізок присвоєнням
, і повторимо описану процедуру до досягнення необхідної точності
по осі
.
- Інакше значення функції на кінцях відрізка мають протилежні знаки на правому відрізку,
або
, то, відповідно, корінь знаходиться всередині правого відрізка
. Тоді візьмемо правий відрізок присвоєнням
, і повторимо описану процедуру до досягнення необхідної точності
по осі
.
За кількість ітерацій поділ навпіл здійснюється
раз, тому довжина кінцевого відрізка в
разів менше довжини вихідного відрізка.
Існує схожий метод, але з критерієм зупинки обчислень по осі
, в цьому методі обчислення тривають до тих пір, поки, після чергового поділу навпіл, новий відрізок більше заданої точності по осі
:
. У цьому методі відрізок на осі
може досягти заданої величини
, а значення функцій
(особливо крутих) на осі
можуть дуже далеко стояти від нуля, при пологих же функціях
цей метод призводить до великої кількості зайвих обчислень.
У дискретних функціях і
— це номера елементів масиву, які не можуть бути дробовими, і, в разі другого критерію зупину обчислень, різниця
не може бути менше
.
Псевдокод
Нехай
- xn — початок відрізка по х;
- xk — кінець відрізка по х;
- xi — середина відрізка по х;
- epsy — необхідна точність обчислень по y (задане наближення інтервалу [xn; xk]: xk — xn до нуля).
Тоді алгоритм методу бісекції можна записати в (псевдокоді) наступним чином:
- Початок.
- Введення xn, xk, epsy.
- Якщо F(xn) = 0, то висновок (корінь рівняння — xn).
- Якщо F(xk) = 0, то висновок (корінь рівняння — xk).
- Поки xk — xn > epsy повторювати:
- dx := (xk — xn)/2
- xi := xn + dx;
- якщо sign(F(xn)) ≠ sign(F(xi)), то xk := xi;
- інакше xn := xi.
- кінець повторювати
- Висновок (Знайдено корінь рівняння — xi з точністю по y — epsy).
- Кінець.
Пошук значення кореня монотонної дискретної функції
Пошук найбільш наближеного до кореня значення в монотонної дискретної функції, заданої таблично і записаної в масиві, полягає в розбитті масиву навпіл (на дві частини), виборі з двох нових частин тієї частини, в якій значення елементів масиву змінюють знак шляхом порівняння знаків серединного елемента масиву зі знаком граничного значення і повторенні алгоритму для половини в якій значення елементів масиву змінюють знак.
Нехай змінні ліваГраниця і праваГраниця містять, відповідно, ліву лівГран и праву правГран межі масиву, в якій знаходиться наближення до кореня. Дослідження починається з розбиття масиву навпіл (на дві частини) шляхом знаходження номера середнього елемента масиву середина .
Якщо знаки значень масиву масив[ліваГраниця] та масив[середина] протилежні, то наближення до кореня шукають в лівій половині масиву, тобто значенням праваГраниця стає середина і на наступній ітерації досліджується тільки ліва половина масиву. Якщо знаки значень масив[ліваГраниця] і масив[середина] однакові, то здійснюється перехід до пошуку наближення до кореня в правій половині масиву, тобто значенням змінної ліваГраниця стає середина і на наступній ітерації досліджується тільки права половина масиву. Т.о., в результаті кожної перевірки область пошуку звужується вдвічі.
Наприклад, якщо довжина масиву дорівнює 1023, то після першого порівняння область звужується до 511 елементів, а після другого — до 255. Т.о. для пошуку наближення до кореня в масиві з 1023 елементів досить 10 проходів (ітерацій).
(Псевдокод):
ліваГраниця = лівГран праваГраниця = правГран while (праваГраниця - ліваГраниця > 1) { довжинаВідрізка = правГран - лівГран половинаВідрізка = int(довжинаВідрізка / 2) середина = ліваГраниця + половинаВідрізка if (sign(масив[ліваГраниця]) ≠ sign(масив[середина])) праваГраниця = середина else ліваГраниця = середина } printf середина
Див. також
- (Лінійний пошук)
- (Двійковий пошук)
- (Метод дихотомії)
- (Метод золотого перетину)
- (Тернарний пошук)
- (Метод Ньютона)
Примітки
- Ю. Губарь, Курс «Введение в математическое моделирование» Лекция 4: Численные методы решения нелинейных уравнений: Метод половинного деления // , 15.03.2007
- 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
- вільно поширювана програма для обчислення (ізоелектричної точки).
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет