Чисельні методи для звичайних диференціальних рівнянь — чисельні методи для знаходження наближених розв'язків звичайних диференціальних рівнянь. Їх застосування також іноді називають «чисельним інтегруванням», хоча частіше цей термін вживають для обчислення інтегралів.
Багато диференціальних рівнянь неможливо розв'язати точно. Однак для практичних цілей – наприклад, в інженерії – часто достатньо чисельного наближення до розв'язку. Тоді стають в нагоді алгоритми для обчислення такого наближення. Альтернативним методом є використання методів математичного аналізу для отримання розв'язку у вигляді ряду.
Звичайні диференціальні рівняння зустрічаються в багатьох наукових дисциплінах, зокрема у фізиці, хімії, біології та економіціChicone, C. (2006). Ordinary differential equations with applications (Vol. 34). Springer Science & Business Media.. Крім того, деякі методи перетворюють диференціальні рівняння з частинними похідними на звичайні диференціальні рівняння, які потім теж необхідно розв'язати.
Задача Диференціальне рівняння першого порядку — це вигляду
де є функцією , а початкова умова — якийсь заданий вектор. Перший порядок рівняння означає, що в рівнянні з'являється лише перша похідна від y, а вищі похідні відсутні.
Без втрати загальності для систем вищого порядку, ми обмежимося диференціальними рівняннями першого порядку, оскільки звичайне диференціальне рівняння вищого порядку можна перетворити на більшу систему рівнянь першого порядку шляхом введення додаткових змінних. Наприклад, рівняння другого порядку можна переписати як два рівняння першого порядку: та
У цьому розділі ми описуємо лише чисельні методи для задач з початковими умовами та зазначаємо, що крайові задачі вимагають іншого набору інструментів. У крайових задачах значення y задані в більш ніж одній точці. Через це для розв'язання крайової задачі необхідно використовувати спеціальні методи, наприклад, метод стрільби (та його варіанти) або глобальні методи, такі як метод скінченних різницьLeVeque, R. J. (2007). Finite difference methods for ordinary and partial differential equations: steady-state and time-dependent problems (Vol. 98). SIAM., методи ГальоркінаSlimane Adjerid and Mahboub Baccouch (2010) Galerkin methods. Scholarpedia, 5(10):10056. або методи колокації.
Теорема Пікара-Лінделёфа стверджує, що існує єдиний розв'язок, за умови, що f задовільняє критерію Ліпшиця.
Методи Чисельні методи розв'язання задачі з початковими умовами першого порядку часто поділяють на дві великі категоріїGriffiths, D. F., & Higham, D. J. (2010). Numerical methods for ordinary differential equations: initial value problems. Springer Science & Business Media.: лінійні багатокрокові методи та методи Рунге-Кутти. Подальший поділ можна здійснити, розділивши методи на явні та неявні. Наприклад, неявні лінійні багатокрокові методи включають методи Адамса — Моултона та , тоді як неявні методи Рунге — Кутти включають діагонально неявний метод Рунге — Кутти ()Alexander, R. (1977). Diagonally implicit Runge–Kutta methods for stiff ODE’s. SIAM Journal on Numerical Analysis, 14(6), 1006-1021.Cash, J. R. (1979). Diagonally implicit Runge-Kutta formulae with error estimates. IMA Journal of Applied Mathematics, 24(3), 293-301., однодіагонально неявний метод Рунге-Кутти ()Ferracina, L., & Spijker, M. N. (2008). Strong stability of singly-diagonally-implicit Runge–Kutta methods. Applied Numerical Mathematics, 58(11), 1675-1686. та чисельні методи Гаусса-РадауEverhart, E. (1985). An efficient integrator that uses Gauss-Radau spacings. In International Astronomical Union Colloquium (Vol. 83, pp. 185–202). Cambridge University Press. (засновані на квадратурі ГаусаWeisstein, Eric W. "Gaussian Quadrature." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GaussianQuadrature.html). Явні приклади з лінійних багатокрокових методів включають методи Адамса — Башфорта, а будь-який метод Рунге — Кутти з таблицею Бутчера нижнього трикутного виду є явним. Грубе емпіричне правило вказує, що жорсткі диференціальні рівняння вимагають використання неявних схем, тоді як нежорсткі задачі можна ефективніше розв'язувати за допомогою явних схем.
Так звані є узагальненням двох вищезгаданих великих класів методівButcher, J. C. (1987). The numerical analysis of ordinary differential equations: Runge-Kutta and general linear methods. Wiley-Interscience..
Метод Ейлера
Для будь-якої точки кривої можна знайти наближене значення наступної точки на кривій, перемістившися на невелику відстань вздовж лінії, дотичної до кривої.
Починаючи з диференціального рівняння (), замінимо похідну y′ наближеною скінченною різницею
Після перегрупування це дає наступну формулу:
Використання () дає:
Цю формулу зазвичай застосовують таким чином. Вибираємо крок h та будуємо послідовність Ми позначаємо через чисельну оцінку точного розв'язку . Керуючись (), ми обчислюємо ці оцінки за такою рекурсивною схемою
Цей метод Ейлера (або прямий Ейлера вперед, на відміну від зворотного методу Ейлера, який буде описано нижче) названий на честь Леонарда Ейлера, який описав його в 1768 році.
Метод Ейлера є прикладом явного методу. Це означає, що нове значення yn+1 визначається з точки зору вже відомих величин, таких як yn.
Зворотний метод Ейлера Якщо замість () використовувати наближення
отримуємо зворотний метод Ейлера:
Зворотний метод Ейлера є неявним методом, тобто нам потрібно розв'язати рівняння, щоб знайти yn+1. Для досягнення цієї мети часто використовують метод простої ітерації або деяку модифікацію методу Ньютона — Рафсона.
Розв'язання цього рівняння потребує більше часу, ніж явні методи, і цю вартість необхідно враховувати під час вибору методу. Перевага неявних методів, таких як (), полягає в тому, що вони зазвичай стійкіші для розв'язання жорстких рівнянь, а це означає, що можна використовувати більший крок h.
Метод експоненціального інтегратора першого порядку Експоненціальні інтегратори описують великий клас інтеграторів, які нещодавно зазнали значного розвитку This is a modern and extensive review paper for exponential integrators. Вони існують щонайменше з 1960-х років.
Замість () ми припускаємо, що диференціальне рівняння або має вигляд
або його локально лінеаризували відносно фонового стану для отримання лінійного члена і нелінійний члену .
Експоненціальні інтегратори будують шляхом множення () на та точного інтегрування результату на певному інтервалі часу :
Це інтегральне рівняння є точним, але воно не визначає інтеграл.
Експоненціальний інтегратор першого порядку можна реалізувати, вважаючи сталим протягом усього інтервалу часу:
Узагальнення Метод Ейлера часто недостатньо точний. Точніше кажучи, він має лише 1-й порядок (поняття порядку пояснено нижче). Це спонукало математиків шукати методи вищого порядку.
Одна з можливостей полягає в тому, щоб використовувати не лише попередньо обчислене значення yn для визначення yn+1, але й зробити розв'язок залежним від більшої кількості минулих значень. Це призводить до так званого багатокрокового методу. Можливо, найпростішим є метод перекроковування, який має 2-й порядок та (грубо кажучи) спирається на два минулі значення.
Майже всі практичні багатокрокові методи належать до сімейства лінійних багатокрокових методів, які мають вигляд
Інша можливість полягає у використанні більшої кількості точок в інтервалі Це призводить до появи сімейства методів Рунге-Кутти, названих на честь Карла Рунге та Мартіна Кутти. Один з їхніх методів четвертого порядку є особливо популярним.
Додаткові можливості Гарна реалізація будь-якого з цих методів розв'язання звичайного диференціального рівняння передбачає більше, ніж просто застосування формули з якимось кроком за часом.
Часто неефективно постійно використовувати один і той самий розмір кроку, тому були розроблені методи зі змінним розміром кроку. Зазвичай розмір кроку вибирають таким чином, щоб (локальна) похибка на крок була нижчою за певний рівень допуску. Це означає, що методи також повинні робити оцінку локальної похибки.
Розширенням цієї ідеї є динамічний вибір між різними методами різного порядку (це називається методом змінного порядку). Методи, засновані на екстраполяції РічардсонаBrezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier., такі як алгоритм Булірша-ШтераMonroe, J. L. (2002). Extrapolation and the Bulirsch-Stoer algorithm. Physical Review E, 65(6), 066116.Kirpekar, S. (2003). Implementation of the Bulirsch Stoer extrapolation method. Department of Mechanical Engineering, UC Berkeley/California. часто використовують для побудови різних методів різного порядку.
Інші бажані характеристики включають:
щільний вихід: прості для обчислень чисельні наближення для всього інтервалу інтегрування, а не лише в точках t0, t1, t2, … локалізація подій: знаходження моментів часу, коли, наприклад, певна функція обертається на нуль. Зазвичай це вимагає чисельного розв'язання нелінійних рівнянь для знаходження коренів. підтримка паралельних обчислень. при використанні для інтегрування за часом, .
Альтернативні методи Багато методів не підпадають під обговорену тут класифікацію. Деякі класи альтернативних методів:
багатопохідні методи (), які використовують не лише функцію f, але й її похідні. Цей клас включає методи Ерміта — Обрешкова та Фельберга, а також такі методи, як Nurminskii, E. A., & Buryi, A. A. (2011). Parker-Sochacki method for solving systems of ordinary differential equations using graphics processors. Numerical Analysis and Applications, 4(3), 223. або метод Бичкова — Щербакова, які рекурсивно обчислюють коефіцієнти ряду Тейлора розв'язку y. методи для звичайних диференціальних рівнянь другого порядку. Ми казали, що всі звичайні диференціальні рівняння вищого порядку можна перетворити на звичайні диференціальні рівняння першого порядку виду (1). Хоча це, безумовно, правда, це може бути не найкращим способом дій. Зокрема, методи Ністрема працюють безпосередньо з рівняннями другого порядку. Hairer, E., Lubich, C., & Wanner, G. (2006). Geometric numerical integration: structure-preserving algorithms for ordinary differential equations (Vol. 31). Springer Science & Business Media.Hairer, E., Lubich, C., & Wanner, G. (2003). Geometric numerical integration illustrated by the Störmer–Verlet method. Acta Numerica, 12, 399-450. спеціально розроблені для спеціальних класів звичайних диференціальних уравнень (наприклад, для розв'язання рівнянь Гамільтона). Вони забезпечують дотримання чисельним розв'язком правильної геометрії цих рівнянь. — це сімейство методів інтегрування звичайних диференціальних рівнянь, заснованих на ідеї квантування станів. Вони ефективні при моделюванні розріджених систем з частими розривами.
Паралельні в часі методи Деякі задачі з початковими умовами вимагають інтегрування з такою високою часовою роздільною здатністю або протягом таких тривалих часових інтервалів, що застосування класичних методів з послідовними часовими кроками стає неможливим (наприклад, у задачах чисельного прогнозування погоди, моделювання плазми та молекулярної динаміки). У відповідь на ці виклики були розроблені методи паралельні у часі (), щоб скоротити час виконання моделювання за рахунок використання паралельних обчислень.
Перші паралельні у часі методи були запропоновані в 1960-х роках, але спочатку вони не привертали уваги дослідників, бо необхідні для них архітектури паралельних обчислень ще не були розповсюджені. Зі збільшенням обчислювальної потужності інтерес до них відродився на початку 2000-х років з розробкою , гнучкого, простого у використанні алгоритму PinT, який підходить для вирішення широкого спектра задач з початковими умовами. Поява екзафлопових обчислень призвела до того, що алгоритми PinT стали привертати дедалі більшу увагу дослідників і розроблялися таким чином, щоб вони могли використовувати найпотужніші суперкомп'ютери світу. Популярності набули такі методи, як Parareal, PFASST, ParaDiag та MGRIT.
Аналіз