- •1 Основні поняття теорії похибок
- •1.1 Поняття похибки
- •1.2 Дії над наближеними числами
- •1.3 Пряма та обернена задачі теорії похибок
- •1.3 Джерела похибок обчислень
- •2 Обчислення значень функцій
- •2.1 Обчислення значень полінома. Схема Горнера
- •2.2 Наближене знаходження сум числових рядів
- •2.3 Обчислення значень аналітичної функції
- •2.4 Обчислення значень показової функції
- •2.5 Обчислення значень логарифмічної функції
- •2.6 Обчислення значень тригонометричних функцій
- •3 Розв’язування систем лінійних алгебраїчних рівнянь (слар)
- •3.1 Концепція методів
- •3.2 Метод простої ітерації
- •3.3 Метод Гаусса-Зейделя
- •4 Розв’язування нелінійних алгебраїчних та трансцендентних рівнянь
- •1. Етап відділення кореня: на цьому етапі відділяється корінь, тобто знаходиться такий відрізок, усередині якого міститься точно один корінь і з цього відрізка береться початкове наближення кореня.
- •2. Етап уточнення кореня: на цьому етапі послідовно уточнюють корінь, тобто знаходять значення із заданою точністю .
- •4.1 Відділення коренів
- •4.2 Метод половинного поділу (метод дихотомії)
- •4.3 Метод хорд (спосіб пропорційних частин)
- •4.4 Метод Ньютона (метод дотичних)
- •4.5 Комбінований метод
- •4.6 Метод ітерації
- •4.7 Метод ітерації для системи двох рівнянь
- •5 Обробка емпіричних даних
- •5.1 Інтерполяція та екстраполяція
- •5.2 Концепція інтерполяції та екстраполяції
- •5.3 Лінійна і квадратична локальні інтерполяції
- •5.4 Глобальна інтерполяція. Многочлен Лагранжа
- •5.5 Глобальна інтерполяція. Многочлен Ньютона
- •5.6 Апроксимація
- •При цьому вимагається, щоб
- •Побудуємо емпіричний точковий графік.
- •Візуальний аналіз побудови дозволяє обрати на роль апроксимуючої функції квадратичну параболу
- •6 Наближене обчислення визначених інтегралів
- •6.1 Концепція чисельного інтегрування
- •6.2 Методи прямокутників та трапецій
- •6.3 Метод Симпсона
- •6.4 Метод Монте-Карло
4.2 Метод половинного поділу (метод дихотомії)
Нехай дано рівняння
, (4.6)
де функція неперервна на і .
Для пошуку кореня рівняння (4.6), що належить відрізку , ділимо цей відрізок навпіл (на дві рівні частини). Якщо , то є коренем рівняння. Якщо , то вибираємо ту з половин чи , на кінцях якої функція має протилежні знаки. Новий звужений відрізок знову ділимо навпіл і вибираємо ту з половин чи , на кінцях якої функція має протилежні знаки, і так далі. У результаті отримаємо на деякому етапі точний корінь рівняння (4.6), або ж нескінчену послідовність вкладених один в одного відрізків таких, що
(4.7)
і
(4.8).
Для кожного фіксованого можна стверджувати, що корінь рівняння (4.6) знаходиться на відрізку . Наближеним значенням кореня можна вважати середину цього відрізка:
Похибка у цьому випадку:
.
Приймаючи значення досить великим (виконуючи досить велике число половинних поділів відрізка), можна досягнути високої точності обчислень.
Якщо корені рівняння (4.6) не відділені на відрізку , то таким способом можна знайти хоча б один з коренів рівняння (4.6), але немає гарантії, що ми знайдемо всі корені.
Метод дихотомії практично зручно застосовувати для грубого знаходження кореня даного рівняння, оскільки при збільшенні точності значно зростає об'єм обчислювальної роботи.
Зауважимо, що метод половинного поділу легко реалізується на комп'ютерах. Програма обчислення складається так, щоб машина знаходила значення лівої частини рівняння (4.6) в середині кожного з відрізків і вибирала відповідну половину його.
Приклад. Методом половинного поділу уточнити корінь рівняння , що лежить на відрізку .
Розв’язок. Послідовно маємо:
|
|
|
|
|
|
|
0 |
0 |
1 |
-1 |
1 |
|
0,5 |
1 |
0,5 |
1 |
-1,19 |
1 |
|
0,25 |
2 |
0,75 |
1 |
-0,59 |
1 |
|
0,125 |
3 |
0,75 |
0,875 |
-0,59 |
0,05 |
|
0,0625 |
4 |
0,8125 |
0,875 |
-0,304 |
0,05 |
|
0,03125 |
Приймаємо:
4.3 Метод хорд (спосіб пропорційних частин)
Розглянемо (в передумовах п. 4.2) більш швидкий спосіб знаходження кореня рівняння , що лежить на заданому відрізку , такому, що .
Нехай для визначеності і . Покладемо також, що . Тоді, замість того, щоб ділити відрізок навпіл, більш логічно розділити його у відношенні .
Геометрично метод хорд еквівалентний заміні кривої хордою, що проходить через точки та (рис. 4.3).
Рис. 4.3 Рис. 4.4
Рівняння хорди АВ:
.
Звідси, поклавши та , отримаємо:
. (4.9)
Далі, застосовуючи цей прийом до відрізка , отримаємо друге наближення кореня:
.
Продовжуючи процес далі, отримаємо формулу методу хорд:
(4.10)
Умова забезпечувала нам розташування точного значення кореня всередині відрізка на кожному етапі процесу обчислення (на кожній ітерації). Це випливає з аналізу рис. 4.3.
Якщо і (рис. 4.4), то потрібно користуватися такою формулою методу хорд (при цьому, як і раніше, вважаємо, що ):
(4.11)
Якщо , то можна розглядувати рівняння .
Узагальнюємо отримані результати:
1) нерухомим є той кінець відрізка , для якого знак функції співпадає зі знаком її другої похідної , тобто ; за приймаємо інший (протилежний до нерухомого) кінець відрізка;
2) послідовні наближення лежать по той бік від кореня , де функція має знак, протилежний знаку її другої похідної . У обох випадках кожне наступне наближення ближче до кореня , ніж попереднє .
Для оцінки точності наближення можна знову скористатися формулою:
,
де при ;
а також формулою:
.
Приклад. Знайти додатний корінь рівняння
з точністю до .
Розв’язок. Перш за все відділимо корінь. Так як
, , то .
Перша похідна:
.
Друга похідна
при .
Отже: нерухомий кінець , .
Послідовно застосовуючи формулу (4.10), матимемо:
|
|
|
|
|
0 |
1 |
-0,6 |
|
|
1 |
1,15 |
-0,173 |
|
|
2 |
1,190 |
-0,036 |
|
|
3 |
1,198 |
-0,0072 |
|
|
Так як при маємо
,
то можна оцінити похибку точніше:
.
Зауважимо, що точний корінь рівняння є .