Алгоритм наближеного обчислення кореня методом половинного ділення

Методи уточнення коренів

На даному етапі завдання полягає в одержанні наближеного значення кореня, що належить відрізку [a, b], із заданою точністю (погрішністю) e. Це означає, що обчислене значення кореня повинне відрізнятися від точного не більше ніж на величину e:

(4.1)

Процедура чисельного визначення наближених значень коренів нелінійних рівнянь, як правило, полягає у виборі початкового наближення до кореня x₀ й обчисленні по деякій формулі наступних x_1, x₂ наближень, і т.д. Кожний такий крок x_0, x_1, x₂,..., x_n називається ітерацією (від латинського iteratio – повторення), а самі методи уточнення – ітераційними методами. В результаті ітерацій утворюється послідовність наближених значень кореня, яка називається ітераційною послідовністю. Якщо ці значення з ростом k прагнуть до точного значення кореня :

(4.2)

то говорять, що ітераційний процес сходиться.

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

(4.3)

У загальному випадку цю нерівність можна представити у вигляді:

(4.4)

де q > 0 й α ≥ 1 – деякі числа, значення яких визначаються методом уточнення кореня. Від значень q і a залежить, наскільки з кожним кроком зменшується погрішність наближених значень і, відповідно, наскільки швидко можна одержати наближене значення із заданою точністю. Головним показником швидкості збіжності методу є значення a, називане порядком збіжності. При α = 1 погрішність із кожним кроком убуває лінійно, у цьому випадку говорять про лінійну збіжність. Якщо α >1, то говорять, що має місце сверхлінійна збіжність.

4.2. Уточнення кореня методом ділення відрізка навпіл (дихотомії)

Для уточнення коренів до заданої точності застосовують ітераційні методи.

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

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

Найбільш простий метод ділення відрізка навпіл має інші назви: метод половинного ділення, метод дихотомії, метод проб, метод бісекцій.

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

Нехай корінь рівняння f(x) = 0 відділений на відрізку , тобто .

Покладемо a₀=a, b₀=b, x₀=(a₀+b₀)/2. Якщо , то . Якщо , то покладемо

(4.5)

(4.6)

(4.7)

і обчислимо . Якщо , то ітераційний процес зупинимо і будемо вважати, що . Якщо , то повторюємо розрахунки за формулами (2)-(4).

З формул (2), (3) видно, що і . Тому , а отже шуканий корінь знаходиться на проміжку . При цьому має місце оцінка збіжності

. (4.8)

Звідси випливає, що кількість ітерацій, які необхідно провести для знаходження наближеного кореня рівняння (1) з заданою точністю e, задовольняє співвідношенню

. (4.9)

де [c] - ціла частина числа c.

Серед переваг даного методу слід відзначити простоту реалізації та надійність. Послідовність {x_n} збігається до кореня для довільних неперервних функцій f(x). До недоліків можна віднести невисоку швидкість збіжності методу та неможливість безпосереднього узагальнення систем нелінійних рівнянь.

Алгоритм наближеного обчислення кореня методом половинного ділення

Вихідні дані:

f (x) – функція;

ε – необхідна точність;

a, b – границі заданого інтервалу (границі пошуку кореня).

Результат: x_пр – наближений корінь рівняння f (x) = 0.

Методика розв'язання:

Крок 1. Вибрати середину відрізка як наближеного кореня.

Крок 2. Якщо , то c – шуканий корінь рівняння, на цьому припиняємо обчислення. А якщо ні, то перейти до кроку 3.

Крок 3. Точний корінь рівняння x^* відрізняється від c не більше ніж на половину довжини відрізка, тобто не більше ніж на (отримана точність). Перевіряємо умову . Якщо умова не виконується, тобто отримана точність нас не влаштовує (вона більше, ніж необхідна), то перейти до кроку 4; а якщо ні, то припинити обчислення, оскільки ми досягли необхідної точності, і наближеним коренем рівняння f (x) = 0 вважати середину c відрізка .

Крок 4. Визначити інтервал подальшого пошуку кореня. Із двох відрізків, що утворювалися при діленні, переходимо до тієї з його половин і, на кінцях якого функція приймає значення різних знаків.

Випадок 1 (рис.4.1). Корінь на відрізку . , границя b зрушується вліво – замінити b на c: b:= c.

Випадок 2 (рис.4.1). Корінь на відрізку . , границя a зрушується вправо – замінити a на c: a:= c.

Перейти до кроку 1.

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

Рис.4.1. Графічна ілюстрація методу половинного ділення.