- •Модуль 1 (Лекції №1-3) Розв’язання нелінійних алгебраїчних і трансцендентних рівнянь Лекція 1
- •1. Методи розв’язання нелінійних рівнянь.
- •Одне рівняння
- •2. Теоретичні положення.
- •3. Чисельні методи розв’язання нелінійних рівнянь
- •3.1 Метод половинного ділення.
- •Лекція 2
- •3.2 Метод пропорційних частин (хорд)
- •3.3 Метод Рибакова
- •Лекція 3
- •3.4 Метод Ньютона (дотичних)
- •3.5 Метод січних
- •Лекція 4-5. Початкова обробка даних
- •Лекція 6-7 Інтерполяція функцій Постановка задачі інтерполяції
- •Поліноміальна інтерполяція
- •Багатоінтервальна інтерполяція
- •Інтерполяція для випадку рівновіддалених вузлів
- •Інтерполяційні формули Ньютона
- •Інтерполяційні формули Гаусса
- •Перша інтерполяційна формула Гауса:
- •Друга інтерполяційна формула Гауса:
- •Інтерполяційна формула Стірлінга
- •Інтерполяційна формула Бесселя
- •Інтерполяція для випадку довільних вузлів. Інтерполяційна формула Лагранжа
- •Лінійних алгебраїчних рівнянь.
- •Метод гауса.
- •Метод Рунге-Кута
- •Метод а.Н. Крилова послідовних наближень
- •Метод Адамса
- •2. Розробка програми
- •2.1 Обчислювальна схема методу Рунге-Кута:
- •2.2 Обчислювальна схема методу Адамса:
- •2.3 Обчислювальна схема методу Крилова:
- •2.4 Структура програми
- •2.5 Опис роботи програми
- •2.6 Опис інтерфейсу користувача
- •2.7 Приклад роботи програми
- •Список літератури:
- •Лекція 14-15.Чисельне інтегрування функцій
- •1. Вступ. Загальні відомості про чисельні інтегрування.
- •2. Огляд методів чисельного інтегрування.
- •2.1 Метод прямокутників.
- •2.2 Метод трапецій
- •1.1.2 Метод Сімпсона (парабол)
- •1.1.3Метод Ньютона-Котеса.
- •2. Функції обчислення інтегралів у вигляді підпрограм.
- •Обчислення інтеграла за допомогою методу трапецій та парабол
- •Лекція 17. Системи диференціальних рівнянь.
- •Дифференціальні рівняння вищого порядку
- •Метод прогону.
- •Проекційні методи (на прикладі методу Гальоркіна).
- •Метод прогону.
- •Проекційні методи (на прикладі методу Гальоркіна).
3.3 Метод Рибакова
Необхідно знайти декілька дійсних коренів рівняння (1).на відрізку[a, b], причому похідна функція f’(x) на [a, b] може мати розриви першого роду.
Для розв’язання цієї задачі доцільно використати метод Рибакова. Опишемо обчислювальну схему цього методу. До початку ітераційного процесу задаємо точність , з якою потрібно отримати корені рівняння (1), і виберемо деяке число m, при умові, що max f(х)< m.
Завищення m не порушує збіжності методу, а тільки сповільнює.
Потім: 1)вважаємо x0 = a;
2)для кожного k = 1,2… ( k - номер ітерації):
обчислюємо наближення до кореня по формулі:
xk+1 = xk + f (х) /m;
- перевіряємо умову xk+1 < b,
і, якщо умова не виконується, то вважаємо, що всі корені знайдені, інакше продовжуємо обчислення;
- перевіряємо виконання умови xk+1 - xk,> , і якщо вона виконується, то повторюємо обчислення з новим k; а інакше вважаємо xk+1 одним із коренів рівняння і продовжуємо обчислення;
3) обчислюємо початкове наближення до наступного кореня по формулі x0 = xk+1+ і переходимо до п.2)
Дамо геометричну інтерпретацію розглянутого ітераційного процесу. На мал.5 зобразимо функцію y=f (х). Задано початкове наближення до кореня x0=a. Через точку (a, f(a)) проводимо пряму (тангенс кута нахилу рівний m), точку перетину цієї прямої віссю X приймаємо за перше наближення до першого кореня. Через точку (x1, f(x1)) проводимо пряму, паралельну першій.
Блок-схема алгоритму метода Рибакова:
Мал.4
ДА НЕТ ТАК
НЕТ НІ
ДА ТАК
НЕТ НІ
НІ
НЕТ НІ
ТАК
Точку перетину цією прямою з віссю X приймаємо за друге наближення до першого кореня і т.д., поки не отримаємо корінь. Відступивши від отриманого праворуч на , приступаємо до знаходження наступного кореня.
Тут змінна T (прапорець) приймає значення 1 після першого виконання умови xk+-xk,,. При цьому допоміжні змінні xl та xr запам'ятовують значення xk+1. Значення x=( xl + xr)/2 буде надруковано, якщо при новому значенні xk+1 не виконується вказана раніше умова. Інакше знову змінюється допоміжна змінна xr (набуває нового значення xk+1), а xl зберігає своє значення і знову обчислюється нове значення xk+1.
Лекція 3
3.4 Метод Ньютона (дотичних)
Метод Ньютона дуже широко використовується при побудові ітераційних алгоритмів. Його популярність пояснюється тим, що, для визначення інтервалу, в якому міститься корінь, не потрібно знаходити значення функції з протилежними знаками. Замість інтерполяції (наближення) по двом значенням функції в методі Ньютона здійснюється екстраполяція за допомогою дотичної до кривої в даній точці.
Нехай корінь рівняння f(х)=0 відділений на відрізку [a, b], причому f'(х) і f"(х) неперервні і зберігають постійні знаки на всьому відрізку [а, b].
Геометричний зміст методу Ньютона полягає в тому, що дуга кривої у=f(х) замінюється дотичною до цієї кривої (звідси і друга назва: метод дотичних).
Перший випадок. Нехай f(а)<0, f(b)>0, f'(х)>0, f'(x)>0 (мал.5а), або f(а)>0, f(b)<0, f'(х)<0, f”(х)<0 (мал.5б). Проведемо дотичну до кривої у=f(х) у точці B0(b; f(b)) і знайдемо абсцису точки перетину дотичної з віссю Ox.
Відомо, що рівняння дотичної в точці B0(b; f(b)) має вигляд:
y – f(b) = f(b)(x-b)
Вважаючи y=0, x=x1, отримаємо
x1 = b - f(b)/f(b) (5)
Тепер корінь рівняння знаходиться на відрізку [a, x1]. Застосовуючи знову метод Ньютона, проведемо дотичну до кривої в точці В1(x1; f(х1)) і отримаємо
x2 = x1 - f(х1)/ f(х1)
І взагалі
xn+1 = xn - f(хn)/ f(хn) (6)
Одержуємо послідовність близьких значень x1, x2,..., xn кожний наступний член якої ближче до кореня , ніж попередній. Однак всі xn залишаються більше істинного кореня , тобто xn - наближене значення кореня xn з надлишком.
Другий випадок. Нехай f(а)<0, f(b)>0, f'(х)>0, f”(х)<0 (мал.6а) або f(а)>0, f(b)<0, f'(х)<0, f”(х)>0 (мал.6б).
Якщо знову провести дотичну до кривої у=f(x) в точці В, то вона перетне вісь абсцис у точці, що не належить відрізку [a, b]. Тому проведемо дотичну в точці A0(a; f(a)) і запишемо її рівняння для даного випадку:
y – f(a) = f(a)(x-a)
Вважаючи у=0, x=x1, знаходимо
x1 =a- f(a)/ f(a) (7)
Корінь знаходиться тепер на відрізку [x1, b]. Застосовуючи знову метод Ньютона, проведемо дотичну в точці A1 (x1; f(x1)) і отримаємо
x2 =a- f(x1)/ f( x1)
М ал.6
І взагалі
xn+1 =a- f(xn)/ f( xn) (8)
Одержуємо послідовність близьких значень х1, х2,..., xn кожний наступний член якої ближче до істинного кореня , ніж попередній, тобто xn — близьке значення кореня з недоліком.
Порівнюючи ці формули з раніше виведеними, помічаємо, що вони відрізняються друг від друга тільки вибором початкового наближення: у першому випадку за x0 приймався кінець b відрізка, в другому — кінець a.
При виборі початкового наближення кореня необхідно керуватися наступним правилом: за вхідну точку слідує вибирати той кінець відрізка [а, b], на якому знак функції співпадає зі знаком другої похідної. У першому випадку f(b)•f”(х)>0 і початкова точка b=x0, в другому f(a)•f”(x)>0 і в якості початкового наближення беремо а=x0.
Для оцінки похибки можна користуватися загальною формулою
- xnf (хn)/m, (9)
де m = minf (х) [а x b].
Ця формула годиться і для методу хорд. У випадку, коли відрізок [а, b] настільки малий , що на ньому виконується умова
m2<2m1, де m2 = maxf (х), a m1 = minf (х) [а x b].
Точність наближення на k-ому кроку оцінюється так:
якщо xk+1 - xk <, , то - xk <2.
Якщо похідна f'(x) мало змінюється на відрізку [а, b], то для спрощення обчислень можна користуватися формулою
xn+1 = xn - f(xn)/ f( xn) (10)
тобто значення похідної в початковій точці достатньо обчислити тільки один раз. Геометрично це означає, що дотичні в точках Вn(xn; f(xn)) замінюються прямими, паралельними до дотичної, проведеної до кривої у=f(х) в точці В0(x0; f(x0)) (мал.7).
Приклад. Методом дотичних уточнити до =0.001 корінь рівняння x3+Зx2-3=0, розташований на відрізку [-2.75; -2.5].
Розв’язання. Раніше було встановлено, що f(-2.75)•f"(х)>0. Тому, щоб скористуватися методом дотичних, слід вибрати x0=-2.75. Обчислення будемо вести по формулі (10). Знаходимо f'(x0)=Зх2+6x; f'(x0)=f'(- 2.75)=6,1875.
Для зручності всі обчислення зведемо в наступну таблицю:
Таблиця 1
N
|
xп
|
x3п
|
x2п
|
3x2п
|
f(xп)
|
-f(xn)/6,1875
|
0 1 2 3 4 5
|
-2,75 -2,571 -2,545 -2,537 -2,534 -2,533 |
-20,797 -16,994 -16,484 -16,329 -16,271
|
7,5625 6,6100 6,4770 6,4364 6,4212
|
22,6875 19,8300 19,431 19,309 19,2636
|
-1,111 -0,164 -0,053 0,020 0,007
|
0,179 0,026 0,008 0,003 0,001
|
З таблиці 1 видно, що x5 - x4 <0.001, тому = x5 =-2.533.