Метод розподілу відрізка навпіл (метод дихотомії, метод бісекції).
2.3 Метод розподілу відрізка навпіл (метод дихотомії, метод бісекції)
Метод розподілу відрізка навпіл є найпростішим і найнадійнішим способом розв'язання нелінійного рівняння.
Нехай із попереднього аналізу відомо, що корінь рівняння (2.1) знаходиться на відрізку [a0, b0], тобто x*[a0, b0], так що f(x*) = 0.
Нехай функція f(x) безперервна на відрізку [a0, b0] і на кінцях відрізка значення різних знаків, тобто.
f(a0)f(b0) 0, або f(x0) * [a1, b1], і довжина відрізка [a1, b1] вдвічі менша, ніж довжина відрізка [a0, b0]. Вчинимо аналогічно з відрізком [a1, b1]. В результаті отримаємо або корінь x * або новий відрізок [a2, b2], і т.д. (Рис. 2.2).
Середина n-го відрізка xn = . Очевидно, що довжина відрізка [an, bn] дорівнюватиме , а тому що x * [an, bn], то
xn - x * £ £. (2.3)
Похибка методу. Оцінка (2.3) характеризує похибка способу розподілу відрізка навпіл і свідчить про швидкість збіжності: спосіб сходиться зі швидкістю геометричної прогресії, знаменник якої q = 1/2. Зауважимо, що оцінка (2.3) є апріорною.
Критерій закінчення. Зі співвідношення (2.3) випливає, що при заданій точності наближення e обчислення закінчуються, коли буде виконано нерівність bn – an log2((b0 – a0)/e) – 1. Таким чином, кількість ітерацій можна визначити заздалегідь. За наближене значення кореня береться величина xn.
Знайдемо приблизно x = з точністю = 0.01. Це завдання еквівалентне рішенню рівняння x 5 – 2 = 0, або знаходженню нуля функції f(x) = x 5 – 2. Як початковий відрізок [a0, b0] візьмемо відрізок [1, 2]. На кінцях цього відрізка функція набуває значень з різними знаками: f(1) 0.
Знайдемочисло n поділів відрізка [1, 2], необхідні досягнення необхідної точності. Маємо:
xn - x * £ = £ 10 -2 ,
n6.
Отже, пізніше 6-го поділу знайдемо з необхідної точністю, » 1.1484. Результати обчислень представлені у таблиці 2.1.