Уточнення коренів. Метод проб

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

Другий етап – уточнення коренів, тобто доведення їх до заданого ступеня точності.

Дано рівняння , де – неперервна функція. Треба знайти корінь цього рівняння з точністю до ε, де ε – деяке додатне достатньо мале число.

Вважатимемо, що корінь відділений і знаходиться на відрізку [а, b], тобто має місце нерівність Числа а і b є наближеними значеннями кореня відповідно з недостачею і з надлишком. Похибка цих наближень не перевищує довжини відрізка b – а. Якщо , то бажана точність обчислень досягнута, і за наближене значення кореня можна прийняти або а, або b. Але якщо , то бажана точність обчислень не досягнута і необхідно звузити інтервал, в якому знаходиться корінь , тобто підібрати такі числа і , щоб виконувалася нерівність і При обчислення треба зупинити і за наближене значення кореня з точністю до ε прийняти або або Треба відмітити, що значення кореня буде більш точним, коли за наближене значення кореня прийняті не кінці відрізка і а середина цього відрізка, тобто Помилка при цьому не буде перевищувати величину

Метод проб. Нехай дано рівняння , де – неперервна функція, і корінь відділений на відрізку [а, b], тобто , при чому . Треба знайти корінь цього рівняння з точністю до ε (рис. 8).

Метод половинного ділення. Метод проб у такому вигляді, як описаний вище на ЕОМ не застосовується. Для складання програми і проведення розрахунків на ЕОМ метод проб застосовується у вигляді так званого метода половинного ділення, який в літературі з числових методів можна знайти під назвою "метод дихотомії".

Нехай корінь ξ рівняння , де – неперервна функція, і корінь відділений на відрізку [а, b], тобто , при чому . Треба знайти корінь цього рівняння з точністю до ε.

Як і раніше, візьмемо на відрізку [а, b] проміжну точку а₁, однак не довільним чином, а так щоб вона знаходилася в середині відрізка, тобто Ця точка розділить [а, b] на два відрізки [а, а₁] і [а₁, b], довжина яких дорівнює (рис. 9). Якщо , то а₁ буде коренем рівняння . Якщо ж , то з двох відрізків [а, а₁] і [а₁, b], що утворилися, вибирають той, на кінцях якого функція приймає значення протилежних знаків. Ітераційний процес продовжують за схемою, розглянутою вище, до тих пір поки не буде знайдено корінь рівняння з заданою точністю, або інакше – поки відрізок [а, b] не стане меншим за ε.

Треба відмітити, що функція розраховується з деякою похибкою ε₁. З цих двох відрізків вибираємо той, на кінцях якого функція приймає значення з протилежними знаками. У нашому прикладі і , тому вибираємо відрізок [а₁, b].

Процес ділення відрізка навпіл продовжують до тих пір, коли на якомусь n-му етапі або середина буде коренем рівняння (випадок, який рідко зустрічаються на практиці), або буде отриманий відрізок такий, що і (число n вказує на кількість проведених ділень). Числа a_n і b_n – корні рівняння з точністю до ε. За наближене значення кореня треба взяти , причому похибка не буде перевищувати

Зазначимо, що при практичній програмній реалізації методу половинного ділення (методу дихотомії) замість розрахунку добутку , пов’язаного з визначенням однаковості або різниці знаків функції в точках a і b, доцільно скористатися стандартною підпрограмою-функцією SIGN(X) , яка в тому чи іншому вигляді присутня в усіх алгоритмічних мовах. Значення, що видається цією підпрограмою-функцією, відповідає наступному математичному визначенню:

Подібна заміна в алгоритмі методу половинного ділення обґрунтовується тим, що при наближенні точок a і b до кореню рівняння при розрахунку добутку може статися зникнення порядку внаслідок малості співмножників. Тому використання знакової функції є переважним.

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

Метод хорд

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

Процес уточнення кореня закінчується, коли відстань між черговими наближеннями буде менше заданої похибки ε₁

або коли значення функції попадуть в область шуму, тобто

Рівняння прямої лінії, що проходить через точки і має вигляд

Коефіцієнти k і c рівняння цієї прямої визначають наступним чином

Розв’язавши цю систему рівнянь, отримують

Точку перетину прямої з віссю абсцис знаходять, прирівнюючи до нуля

або

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