МІНІСТЕРСТВО ОСТВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ "ЛЬВІВСЬКА ПОЛІТЕХНІКА"
МЕТОДИ ЧИСЕЛЬНОГО РОЗВЯЗУВАННЯ
ДИФЕРЕНЦІАЛЬНИХ РІВНЯНЬ
Інструкція до лабораторної роботи № 6
з курсу: "Комп’ютерні методи дослідження інформаційних процесів та систем"
для студентів спеціальності 6.1601
"Інформаційна безпека"
Затверджено
на засіданні кафедри
«Захист інформації»
Протокол № __ від...
Львів – 2007
Методи чисельного розв’язування диференціальних рівнянь: Інструкція до лабораторної роботи №6 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів спеціальності 6.1601 "Інформаційна безпека" / Укл.: Л.В.Мороз, З.М.Стрілецький, В.М.Іванюк - Львів: НУЛП, 2007.- 19 с.
Укладачі: Леонід Васильович Мороз, к.т.н., доц.
Зеновій Михайлович Стрілецький, к.т.н., доц.
Віталій Миколайович Іванюк, асист.
Відповідальний за випуск: І.Я. Тишик, ст.вик.
Рецензенти: В.Б. Дудикевич, д.т.н., проф.,
В.В. Хома, д.т.н., проф.
Мета роботи – ознайомлення з методами чисельного інтегрування диференційних рівнянь.
ВСТУП
Диференціальним називається рівняння, в яке входять похідні невідомої функції.
Приклад:
(1)
(2)
Диференціальне рівняння (ДР), що містить лише одну незалежну змінну і похідні за нею, називають звичайними (ДР). Це, наприклад, рівняння (1). ДР, що містить декілька незалежних змінних і похідні за ними, називають рівняння в частинних похідних
Порядком ДР називається найвищий порядок похідної (або диференціалу), який входить в рівняння. Звичайне ДР (ЗДР) -го порядку в загальному випадку має незалежну змінну, невідому функцію та її похідні (або диференціал) до -го порядку включно:
(3)
- незалежна змінна;
- невідома функція (залежна змінна);
- похідні цієї функції.
Диференціальне рівняння -го порядку, розв’язане відносно старшої похідної, може бути записано у вигляді:
(4)
Щоб розв’язати ЗДР, необхідно мати значення залежної змінної та (або) її похідних при деяких значення незалежної змінної.
Якщо ці значення задані при одному значенні незалежної змінної - така задача називається задачею з початковими умовами або задачею Коші.
Якщо ці значення задаються при або більше значеннях незалежної змінної - задача називається крайовою.
Значення залежної змінної та її похідних називаються ще додатковими умовами, котрі в задачі Коші називаються початковими, а в крайовій задачі - граничними.
Задача Коші
Задача Коші формулюється так:
Нехай задане ДР
(5)
з початковими умовами . Потрібно знайти функцію , що задовольняє дане рівняння, та початкову умову. Для одержання чисельний розв’язку цієї задачі спочатку обчислюють значення похідної, а потім задаючи малий приріст , переходять до нової точки

Положення нової точки визначають за нахилом кривої, обчисленому з допомогою ДР. Таким чином, графік чисельного розв’язку являє собою послідовність коротких прямолінійних відрізків, якими апроксимується істинна крива . Сам чисельний метод визначає порядок дій при переході від даної точки кривої до наступної.
Існують дві групи методів розв’язування задачі Коші.
Однокрокові методи. В них для знаходження наступної точки на кривій потрібна інформація лише про попередній крок. (Однокроковими є метод Ейлера та методи Руте-Кутта.)
Багатокрокові (або методи прогнозування та коригування). Для знаходження наступної точки кривої вимагається інформація більш ніж про одну з попередніх точок. До них належать методи Адамса, Мілна, Хеммінга.
Це чисельні методи розв’язування ДР. Вони дають розв’язок у вигляді таблиці значень.
Метод Ейлера
Однокрокові методи призначені для розв’язування диференціальних рівнянь першого порядку виду
(6)
Метод Ейлера є найпростішим методом розв’язування задачі Коші. Він дозволяє інтегрувати ДР першого порядку. Точність його не велика.
- настільки мале, що значення функції мало відрізняється від лінійної функції
- тангенс кута нахилу дотичної в точці


Тобто крива заміняється дотичними. Рух відбувається не по інтегральній кривій, а по відрізках дотичної .
Метод Ейлера базується на розкладі функції в ряд Тейлора в околі точки

(7)
Якщо мале, то, члени розкладу, що містять в собі і т.д. є малими високих порядків і ними можна знехтувати.
Тоді (8)
Похідну знаходимо з рівняння (6), підставивши в нього початкову умову. Таким чином можна знайти наближене значення залежної змінної при малому зміщенні від початкової точки. Цей процес можна продовжувати, використовуючи співвідношення.
,
роблячи як завгодно багато кроків.
Похибка методу має порядок , оскільки відкинуті члени, що містять в другій і вище степенях.
Недолік методу Ейлера - нагромадження похибок, а також збільшення об’ємів обчислень при виборі малого кроку з метою забезпечення заданої точності.
В методі Ейлера на всьому інтервалі тангенс кута нахилу дотичної приймається незмінним і рівним . Очевидно, що це призводить до похибки, оскільки кути нахилу дотичної в точках та різні. Точність методу можна суттєво підвищити, якщо покращити апроксимацію похідної.
Це можна зробити, якщо, наприклад, використати середнє значення похідної на початку та в кінці інтервалу.
Модифікований метод Ейлера
В модифікованому методі Ейлера (метод Ейлера з перерахунком) спочатку обчислюється значення функції в наступній точці за звичайним методом Ейлера.
(9)
Воно використовується для обчислення наближеного значення похідної в кінці інтервалу .
Обчисливши середнє між цим значенням похідної та її значенням на початку інтервалу, знайдемо більш точне значення :
(10)
Цей прийом ілюструється на рисунку.

В обчислювальній практиці використовується також метод Ейлера-Коші з ітераціями:
знаходиться грубе початкове наближення (за звичайним методом Ейлера)

будується ітераційний процес
(14)
Ітерації продовжують до тих пір, доки два послідовні наближення не співпадуть з заданою похибкою . Якщо після декількох ітерацій співпадіння нема, то потрібно зменшити крок .

Тобто в модифікованому методі Ейлера, в методі Ейлера-Коші з ітераціями спочатку (на першому етапі) знаходиться наближення для , а потім воно вже коригується за формулами (10) або (14).
Метод Рунге – Кутта четвертого порядку
Метод Рунге-Кутта об’єднує ціле сімейство методів розв’язування диференціальних рівнянь першого порядку. Найбільш часто використовується метод четвертого порядку.
В методі Рунге-Кутта значення
функції , як і в методі Ейлера, визначається за формулою
(1)
Якщо розкласти функцію в ряд Тейлора і обмежитись членами до включно, то приріст можна записати у вигляді
(11)
Замість того, щоб обчислювати члени ряду за формулою (11) в методі Рунге-Кутта використовують наступні формули.




Це метод четвертого порядку точності.
Похибка на кожному кроці має порядок . Таким чином метод Рунге-Кутта забезпечує значно вищу точність ніж метод Ейлера, однак вимагає більшого об’єму обчислень в порівнянні з методом Ейлера. Це досить часто дозволяє збільшити крок .
Деколи зустрічається інша форма представлення методу Рунге-Кутта 4-го порядку точності.





В більшості стандартних програм ЕОМ найчастіше використовується (схема) метод четвертого порядку (Рунге-Кутта).
Методи з автоматичною зміною кроку
Застосовуються в тому випадку, якщо розв’язок потрібно одержати із заданою точністю. При високій точності (похибка ) автоматична зміна кроку забезпечує зменшення загального числа кроків в декілька разів (особливо при розв’язках у вигляді кривих, що сильно відрізняються крутизною).
Метод Рунге-Кутта з автоматичною зміною кроку
Після обчислення з кроком всі обчислення виконуються повторно з кроком . Після цього порівнюються результати, отримані в точці хn+1 з кроком і . Якщо модуль різниці менший , то обчислення продовжуються з кроком , в іншому випадку крок зменшують. Якщо нерівність дуже сильна, то крок збільшують.

Маємо
- значення незалежної змінної в точці
- значення функції в точці
- значення функції в точці , обчислене з кроком
- значення функції в точці , обчислене з кроком
- значення функції , обчислене з кроком
1) Якщо

обчислення повторюються з кроком і т.д., доки не виконається умова .
2) Якщо виконується ця умова, то можливі два варіанти, в залежності від значення K, де K – ознака поділу кроку.
Початкове значенняі залишається таким після першого поділу кроку на два. Надалі, якщо крок ділиться, то K приймає значення одиниці.
а) Якщо , то навіть коли виконалась умова , крок не змінюється, тобто лишається тим самим (обчислення далі проводяться з попереднім кроком).
б) Якщо і виконалась умова , тоді .
В обох випадках а) і б) результат виводиться на друк.
Метод Рунге-Кутта-Мерсона з автоматичною зміною кроку
Метод дозволяє оцінити похибку на кожному кроці інтегрування. Похибка інтегрування має порядок . При цьому не потрібно зберігати в пам’яті обчислення значень функцій на кроці і для оцінки похибки - перевага порівняно з методом Рунге-Кутта з автоматичною зміною кроку.
Алгоритм методу
1. Задаємо число рівнянь , похибку , початковий крок інтегрування , початкові умови .
2. За допомогою п’яти циклів з керуючою змінною обчислюємо коефіцієнти


3. Знаходимо значення


та похибку
4. Перевіряємо виконання умов

Можливі випадки:
а) Якщо перша умова не виконується, тобто , то ділимо крок на 2 та повторюємо обчислення з п.2, встановивши початкові значення .
б) Якщо виконується перша та друга умови, значення та виводяться на друк.
Якщо друга умова не виконується, крок збільшується вдвічі і тоді обчислення знову повторюється з п.2 (нема потреби обчислювати при малому кроці).
Треба відмітити, що похибка на кожному кроці методу Рунге-Кутта-Мерсона оцінюється приблизно. При розв’язуванні нелінійних ДР істинна похибка може відрізнятися в декілька разів від заданої .
, де .
- крок поділити на 2 і повернутися на початок.
для всіх рівнянь: виводимо на друк , а крок збільшуємо удвічі.
Метод Рунге-Кутта-Фельдберга з автоматичною зміною кроку
Це метод четвертого порядку, дає більш точну оцінку похибки (порівняно з методом Рунге-Кутта-Мерсона) на кожному кроці і реалізується послідовним циклічним обчисленням за наступними формулами:







Похибка

Якщо
а) , крок зменшується в двічі
б) Якщо , крок збільшується вдвічі.
Час розрахунку для однієї точки удвічі більший, ніж для методу Рунге-Кутта-Мерсона.
Загальна характеристика однокрокових методів
1) Щоб одержати інформацію в наступній точці, потрібно мати дані лише в одній попередній точці. Цю властивість деколи називають “самостартування”.
2) В основі всіх однокрокових методів лежить розклад функцій в ряд Тейлора, в якому зберігаються члени, котрі містять в степені до включно. Ціле число називають порядком методу. Похибка на кроці має порядок .
3) Всі однокрокові методи не потребують дійсного обчислення похідних - обчислюється лише сама функція. Однак можуть бути потрібні її значення в декількох проміжних точках, що викликає додаткові затрати машинного часу.
4) Властивість “самостартування” дозволяє легко змінювати значення кроку .
Методи прогнозу і корекції
Деякі звичайні диференціальні рівняння не вирішуються ні одним із розглянутих методів.
Для обчислення положення нової точки використовується інформація про декілька раніше отриманих точок. Для цього використовуються дві так звані формули прогнозу і корекції. Схеми алгоритмів для таких методів приблизно однакові, а самі методи відрізняються лише формулами.
Оскільки в цих методах використовується інформація про декілька раніше отримані точки, то на відміну від однокрокових методів вони не мають властивості самостартування. Тому, перед тим як застосовувати метод прогнозу і корекції, необхідно обчислити вихідні дані з допомогою якого-небудь однокрокового методу.
Обчислення виконують таким чином. Спочатку за формулою прогнозу та початковими значеннями змінних визначають значення . Верхній індекс (0) означає, що прогнозоване значення є одним із послідовності значень уп +1, розташованих в порядку зростання точності. За прогнозованим значенням з допомогою диференціального рівняння:
)
знаходимо похідну:

Ця похідна підставляється у формулу корекції для обчислення уточненого значення . В свою чергу використовується для одержання більш точного значення похідної:

Якщо це значення похідної недостатньо близьке до попереднього, то воно вводиться у формулу корекції і ітераційний процес продовжується. Якщо ж похідна змінюється в припустимих межах, то значення використовується для обчислення остаточного значення , яке і виводиться на друк. Після цього процес повторюється - робиться наступний крок, на якому обчислюється .
Метод Мілна
На етапі прогнозу використовується формула Мілна.
, (12)
а на етапі корекції - формула Сімпсона
(13)
Останні члени в обох формулах в ітераційному процесі не використовуються і служать лише для оцінки помилок. Метод Мілна відносять до методів четвертого порядку точності, оскільки в ньому відкинуті члени, які містять в 5 і більш високих степенях. Потрібно мати на увазі, що для користування формулою (12) необхідно попередньо одним із однокрокових методів визначити і значення похідних .
Похибка, внесена на будь-якому кроці, зростає експоненціально, тому методу Мілна властива нестійкість. Це недолік методу.
Метод Адамса
Має четвертий порядок точності. Формула прогнозу отримана на основі інтерполяційної формули Ньютона і має вигляд:
(14)
Формула корекції
(15)
На відміну від методу Мілна, похибка, внесена на кроці, не має тенденції до експоненціального зростання.
Метод Хемінга
Це стійкий метод четвертого порядку точності.
Формула прогнозу:
(16)
Формула корекції
(17)
Формула прогнозу зазвичай доповнюється формулою уточнення прогнозу:
(18)
(19)
Переваги методу Хемінга – простота і стійкість.
Характеристика методів прогнозу і корекції.
1) Для реалізації методів прогнозу і корекції необхідно мати інформацію про декілька попередніх точок, тобто ці методи не відносяться до числа самостартуючих. Для одержання вихідної інформації потрібно скористатись одним з однокрокових методів. Якщо в процесі розв’язування диференці-ального рівняння змінюється крок, то зазвичай потрібно тимчасово переходити на однокроковий метод.
2) Оскільки для методів прогнозу і корекції потрібні дані про попередні точки, то виникають підвищені вимоги до об’єму пам’яті ЕОМ.
3) Однокрокові методи і методи прогнозу і корекції можуть забезпечити приблизно однакову точність результатів. Однак, на відміну від перших другі дозволяють оцінити похибку на кроці. Тому при однокрокових методах значення кроку вибирають трохи меншим, ніж це потрібно, тому методи прогнозу і корекції є більш ефективними.
4) Застосовуючи метод Рунге – Кутта четвертого порядку точності, на кожному кроці потрібно обчислювати чотири значення функції. В той самий час для забезпечення збіжності методу прогнозу і корекції того ж порядку точності часто достатньо двох значень функції. Тому метод прогнозу і корекції потребує майже вдвічі менше машинного часу, ніж метод Рунге – Кутта такої ж точності.
2.ЗАВДАННЯ ДО ЛАБОРАТОРНОЇ РОБОТИ
Розв’язати чисельним методом звичайне диференційне рівняння.
№ п./п.
Диференційне рівняння
Початкові умови

1



2



3



4



5



6



7



8



9



10



11



12



13



14



15



2.1. Домашня підготовка до роботи
1. Ознайомитися з основними теоретичними відомостями.
2. Розробити блок-схему алгоритму методу
3.Написати програму, яка забезпечить розв’язок та виведення на екран результатів роботи. Варіанти завдань беруть за вказівкою викладача.
2.2. Робота в лабораторії
1. Ввести в комп'ютер програму згідно з отриманим завданням.
2. Здійснити відладку введеної програми, виправивши виявлені компілятором помилки.
3. Виконати програму. Текст відлагодженої програми та отримані результати оформити у звіт з лабораторної роботи.
3. ЗМIСТ ЗВIТУ
1. Мета роботи.
2. Короткі теоретичні відомості.
3. Повний текст завдання.
4. Блок-схема алгоритму програми.
5. Список ідентифікаторів констант, змінних, процедур і функцій, використаних в програмі, та їх пояснення.
6. Остаточно відлагоджений текст програми згідно з отриманим завданням.
7. Результати виконання програми.
8. Висновок.
Контрольні запитання
Як називаються додаткові умови в задачі Коші?
Як називаються додаткові умови в крайовій задачі?
Що являє собою графік чисельного розв’язку диференціального розв’язку?
В чому полягає відмінність між однокроковими і багатокроковими методами розв’язування задачі Коші?
Поясніть як знаходиться значення функції в наступній точці методом Ейлера.
Назвіть переваги і недоліки методу Ейлера.
Чим відрізняється звичайний та модифікований методи Ейлера?
Поясніть як знаходиться значення функції в наступній точці методом Ейлера-Коші з ітераціями.
Поясніть як знаходиться значення функції в наступній точці методом Руннге-Кута. Запишіть основні співвідношення.
Коли доцільно застосовувати методи з автоматичною зміною кроку?
Назвіть відомі вам методи з автоматичною змінною кроку?
СПИСОК ЛІТЕРАТУРИ
Корн Г., Корн Т. Справочник по математике для инженеров и научных работников. – М.: Наука, 1974. – 830 с.
Маликов В.Т., Кветный Р.Н. Вычислительные методы и применение ЭВМ: Учеб. пособие. – Киев: Выща шк., Головное изд-во, 1989. – 213 с.
Щуп Т. Решение инженерных задач на ЭВМ. – М.: Мир, 1982. – 235 с.
Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. – М.: Мир, 1998. –570 с.
5. Джон Г. Мэтьюз, Куртис Д. Финк Чисельнные методы. Использование Matlab. Издательский дом «Вильямс» Москва – Санкт-Петербург – Киев, 2001.
6. Коссак О., Тумашова О., Коссак О. Методи наближених обчислень: Навч.посібн. – Львів: Бак, 2003. – 168 с.