Метод Ейлера

для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації",

6.170103 "Управління інформаційною безпекою"

 

Затверджено

на засіданні кафедри

«Безпека інформаційних

технологій»

Протокол № 12 від 12.05.2011р.

 

 

Львів – 2011

Методи чисельного розв’язування диференціальних рівнянь: Методичні вказівки до лабораторної роботи №6 з курсу "Комп’ютерні методи дослідження інформаційних процесів та систем" для студентів базових напрямів 6.170101 "Безпека інформаційних і комунікаційних систем", 6.170102 "Системи технічного захисту інформації", 6.170103 "Управління інформаційною безпекою" / Укл.: Л.В. Мороз, А.Я. Горпенюк, Н.М. Лужецька - Львів: Видавництво НУ“ЛП”, 2011..- 14 с.

 

 

 

Укладачі: Л.В. Мороз, к.т.н., доц.

А.Я. Горпенюк, к.т.н., доц.

Н.М. Лужецька, асист.

 

 

Відповідальний за випуск: В.М. Максимович, д.т.н., проф.

 

 

Рецензент: В.В. Хома, д.т.н., проф.

А.Е. Лагун, к.т.н., доц.,

 

Мета роботи – ознайомлення з методами чисельного розв’язування диференційних рівнянь.

 

ВСТУП

Диференціальне рівняння (ДР), що містить лише одну незалежну змінну і похідні за нею, називають звичайними (ДР). ДР, що містить декілька незалежних змінних і похідні за ними, називають рівняння в частинних похідних.

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

(1)

- незалежна змінна;

- невідома функція (залежна змінна);

- похідні цієї функції.

Диференціальне рівняння -го порядку, розв’язане відносно старшої похідної, може бути записано у вигляді:

(2)

Щоб розв’язати ЗДР, необхідно мати значення залежної змінної та (або) її похідних при деяких значення незалежної змінної.

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

Значення залежної змінної та її похідних називаються додатковими умовами, котрі в задачі Коші називаються початковими, а в крайовій задачі - граничними.

 

Задача Коші

Задача Коші формулюється так:

Нехай задане ДР

(3)

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

Положення нової точки визначають за нахилом кривої, обчисленому з допомогою ДР. Таким чином, графік чисельного розв’язку являє собою послідовність коротких прямолінійних відрізків, якими апроксимується істинна крива . Сам чисельний метод визначає порядок дій при переході від даної точки кривої до наступної.

Існують дві групи методів розв’язування задачі Коші.

1. Однокрокові методи. В них для знаходження наступної точки на кривій потрібна інформація лише про попередній крок.

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

Всі ці методи розв’язування ДР дають розв’язок у вигляді таблиці значень.

 

Метод Ейлера

Метод Ейлера є найпростішим методом розв’язування задачі Коші. Він дозволяє інтегрувати ДР першого порядку виду.

(4)

Метод Ейлера базується на розкладі функції в ряд Тейлора в околі точки

(5)

Якщо мале, то, знехтувавши членам розкладу, що містять в собі і т.д. отримаємо

(6)

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

,

роблячи як завгодно багато кроків.

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

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

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

 

Модифікований метод Ейлера

В модифікованому методі Ейлера спочатку обчислюється значення функції в наступній точці за звичайним методом Ейлера.

(7)

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

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

(8)

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

1) знаходиться грубе початкове наближення (за звичайним методом Ейлера)

2) будується ітераційний процес

(9)

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

 

Метод Рунге – Кутта четвертого порядку

В методі Рунге-Кутта значення функції , як і в методі Ейлера, визначається за формулою

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

(10)

Замість того, щоб обчислювати члени ряду за формулою (10) в методі Рунге-Кутта використовують наступні формули.

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

Деколи зустрічається інша форма представлення методу Рунге-Кутта 4-го порядку точності.

 

Методи з автоматичною зміною кроку

Застосовуються в тому випадку, якщо розв’язок потрібно одержати із заданою точністю. При високій точності (похибка ) автоматична зміна кроку забезпечує зменшення загального числа кроків в декілька разів (особливо при розв’язках у вигляді кривих, що сильно відрізняються крутизною).

 

Метод Рунге-Кутта з автоматичною зміною кроку

Після обчислення з кроком всі обчислення виконуються повторно з кроком . Після цього порівнюються результати, отримані в точці х_{n+ 1} з кроком і . Якщо модуль різниці менший , то обчислення продовжуються з кроком , в іншому випадку крок зменшують. Якщо нерівність дуже сильна, то крок збільшують.

Маємо

- значення незалежної змінної в точці

- значення функції в точці

- значення функції в точці , обчислене з кроком

- значення функції в точці , обчислене з кроком

- значення функції , обчислене з кроком

 

1) Якщо

обчислення повторюються з кроком і т.д., доки не виконається умова .

2) Якщо виконується ця умова, то можливі два варіанти, в залежності від значення K, де K – ознака поділу кроку.

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

а) Якщо , то навіть коли виконалась умова , крок не змінюється, тобто лишається тим самим (обчислення далі проводяться з попереднім кроком).

б) Якщо і виконалась умова , тоді .

В обох випадках а) і б) результат виводиться на друк.

 

Метод Рунге-Кутта-Мерсона з автоматичною зміною кроку

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

Алгоритм методу

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

2. За допомогою п’яти циклів з керуючою змінною обчислюємо коефіцієнти

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

та похибку

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

Можливі випадки:

а) Якщо перша умова не виконується, тобто , то ділимо крок на 2 та повторюємо обчислення з п.2, встановивши початкові значення .

б) Якщо виконується перша та друга умови, значення та виводяться на друк.

Якщо друга умова не виконується, крок збільшується вдвічі і тоді обчислення знову повторюється з п.2.

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

, де .

- крок поділити на 2 і повернутися на початок.

для всіх рівнянь: виводимо на друк , а крок збільшуємо удвічі.

 

Метод Рунге-Кутта-Фельберга з автоматичною зміною кроку

Це метод четвертого порядку, дає більш точну оцінку похибки (порівняно з методом Рунге-Кутта-Мерсона) на кожному кроці і реалізується послідовним циклічним обчисленням за наступними формулами:

Похибка

Якщо

а) , крок зменшується в двічі

б) Якщо , крок збільшується вдвічі.

Час розрахунку для однієї точки удвічі більший, ніж для методу Рунге-Кутта-Мерсона.

Методи прогнозу і корекції

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

Обчислення виконують таким чином. Спочатку за формулою прогнозу та початковими значеннями змінних визначають значення . Верхній індекс (0) означає, що прогнозоване значення є одним із послідовності значень у_{п +1}, розташованих в порядку зростання точності. За прогнозованим значенням з допомогою диференціального рівняння:

знаходимо похідну:

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

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

Метод Мілна

На етапі прогнозу використовується формула Мілна.

, (11)

а на етапі корекції - формула Сімпсона

(12)

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

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