Глосарій чисельних методів

Найпростіший явний розв’язувач ЗДР: y(t+h) = y(t) + h·f(t,y). Точність першого порядку (похибка ∝ h). Може бути нестійким для жорстких задач, якщо h не мале. Використовується в базових системах частинок, де стійкість не критична.

Спочатку оновлює швидкість (v ← v + a·dt), потім позицію за новою швидкістю (x ← x + v·dt). Зберігає енергію краще за прямий Ейлер для гамільтонових систем. Кращий за прямий Ейлер для систем «пружина-маса» та орбітальної механіки.

x(t+h) = 2x(t) - x(t-h) + a(t)·h². Оборотне в часі, точність другого порядку, явна швидкість не потрібна. Швидкісний Верле обчислює і швидкість: v(t+h) = v(t) + (a(t)+a(t+h))·h/2. Стандартний вибір для симуляцій тканини, волосся, твердих тіл.

Швидкість обчислюється зі зсувом на півкроку відносно позиції; еквівалентне Верле, але сформульоване так, що швидкість явна. Використовується в молекулярній динаміці та симуляціях N тіл. Симплектичне (зберігає площу у фазовому просторі), точність другого порядку.

Обчислює чотири оцінки похідної k1–k4 й поєднує їх як y ← y + (k1 + 2k2 + 2k3 + k4)/6 · h. Точність четвертого порядку (похибка ∝ h⁴). Потребує 4 обчислень функції на крок. Робоча конячка для хаотичних ЗДР: Лоренц, подвійний маятник, орбітальна механіка.

Розв’язувач RK з адаптивним кроком: обчислює оцінки 4-го та 5-го порядку й використовує їхню різницю як оцінку похибки для автоматичного підбору h. Більше обчислень на крок, але менше загальних кроків, коли точність змінюється вздовж траєкторії.

Явний багатокроковий метод, що повторно використовує обчислення похідної з попередніх кроків. AB 2-го порядку: y_{n+1} = y_n + (3f_n - f_{n-1})·h/2. Ефективніший за RK для гладких функцій, бо минулі обчислення переробляються.

y(t+h) = y(t) + h·f(t+h, y(t+h)). Потребує розв’язання (можливо, нелінійного) рівняння на кожному кроці. Безумовно стійкий для лінійних систем — ідеальний для жорсткої фізики (швидкі пружини, тканина з високою жорсткістю).

Замінює неперервні похідні різницевими відношеннями на регулярній сітці. Права різниця: ∂u/∂x ≈ (u_{i+1}-u_i)/h. Центральна: ≈ (u_{i+1}-u_{i-1})/(2h). Проста в реалізації, обмежена простими областями.

Поділяє область на малі елементи (трикутники, тетраедри). РЧП перетворюється у слабку форму на кожному елементі та збирається у глобальну матрицю жорсткості Ku = f. Опрацьовує складні геометрії та граничні умови. Використовується в структурному аналізі, механіці рідин.

Інтегрує РЧП по контрольних об’ємах. Потоки через межі об’ємів зберігаються точно. Кращий для законів збереження (рівняння Ейлера/Нав’є-Стокса). Використовується в CFD, теплопереносі.

Зменшує вимірність на одиницю: потрібні лише поверхневі (граничні) елементи замість об’ємних. Дуже ефективний для необмежених або зовнішніх задач (акустика, електростатика). Щільна матриця — складання O(N²) проти O(N) для FEM.

Подає розв’язок як суму глобальних базисних функцій (Фур’є, Чебишова). Експоненційна збіжність для гладких розв’язків. Використовується в симуляції турбулентності, моделюванні погоди, симуляціях океану. FFT дає змогу робити перетворення за O(N log N).

Симулює рідину, відстежуючи функції розподілу щільностей частинок на ґратці. Кожен крок: зіткнення (релаксація до Максвелла-Больцмана) + потік (зсув розподілів до сусідів). Відтворює рівняння Нав’є-Стокса в макроскопічній межі. Природно паралельний, зручний для GPU.

lerp(a, b, t) = a + t·(b - a), t ∈ [0,1]. Многочлен першого степеня, що з’єднує дві точки. Використовується скрізь: змішування анімації, семплінг текстур, покрокове підштовхування у фізиці.

Лінійна інтерполяція у двох вимірах (4 кутові вибірки → 1 результат). Використовується для вибірки з текстур, сіткової адвекції рідини. Еквівалентна lerp по рядках, потім по стовпцях.

Кубічний многочлен, заданий значеннями в кінцевих точках ТА похідними (дотичними) у них. C¹-неперервний у контрольних точках. Використовується для плавних шляхів камери, кривих анімації.

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

Поліноміальна крива, задана контрольними точками за допомогою базису Бернштейна. Кубічна Безьє: чотири контрольні точки; крива дотична до P0→P1 на початку та P2→P3 в кінці. Використовується у шляхах SVG, CSS-анімаціях, контурах шрифтів.

Інтерполяція за допомогою функцій відстані від точок даних: f(x) = Σ wᵢ · φ(‖x-xᵢ‖). Поширені ядра: ґаусове, мультиквадрик, тонкопластинний сплайн. Корисна для розкиданих даних; лежить в основі ядер SPH.

Похибка, яку вносить заміна точних похідних скінченними наближеннями. Для явного Ейлера локальна похибка апроксимації становить O(h²); глобальна накопичена похибка — O(h). Методи вищого порядку зменшують похибку апроксимації на крок.

Арифметика з рухомою комою має скінченну точність (~15–17 десяткових цифр для double). Накопичене округлення може домінувати при відніманні майже рівних чисел (катастрофічне скорочення).

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

Куранта-Фрідріхса-Леві: для явної хвилі/адвекції крок часу має задовольняти c·Δt/Δx ≤ 1 (1D). Гарантує, що інформація не пройде більш ніж одну комірку за крок. Спрямовує вибір кроку часу в симуляціях рідин і хвиль.

Штучне демпфування, що вноситься дискретизацією. Методи першого порядку (проти потоку, прямий Ейлер) сильно дисипативні; схеми високого порядку зберігають хвильові особливості довше. Корисна для стійкості, але пригнічує деталі в симуляціях турбулентності.

Підставляє анзац фур’є-моди u_j^n = g^n · exp(ikjΔx) у дискретизовану схему й перевіряє, що коефіцієнт підсилення g задовольняє |g| ≤ 1 для всіх хвильових чисел k. Стандартний інструмент для доведення стійкості скінченнорізницевих схем.

Симплектичні інтегратори (Верле, leapfrog, симплектичний Ейлер) зберігають симплектичну структуру гамільтонових систем. Повна енергія коливається навколо правильного значення, а не дрейфує, навіть у довгих симуляціях.

Прямий розв’язувач для Ax = b. Розкладає A = LU (нижня/верхня трикутні) методом виключення. O(N³) для щільних матриць N×N. Точний з точністю до округлення. Використовується для малих систем FEM.

Ітераційний розв’язувач для симетричних додатно визначених Ax = b. Збігається щонайбільше за N кроків (точна арифметика), але на практиці зазвичай значно швидше. Економний щодо пам’яті: потрібні лише добутки матриці на вектор. Стандарт для великих розріджених систем FEM.

Generalised Minimal Residual (узагальнений мінімальний залишок) — ітераційний розв’язувач для несиметричних розріджених систем. Будує підпростір Крилова та мінімізує норму залишку. Використовується для задач рідин з переважанням конвекції, де CG незастосовний.

Матриця M ≈ A, що застосовується для перетворення Ax = b → M⁻¹Ax = M⁻¹b, аби зменшити число обумовленості й прискорити ітераційну збіжність. Поширені варіанти: Якобі (діагональна M), ILU (неповне LU-розкладання), мультисіткові.

Спеціалізований метод Гаусса для тридіагональних систем. O(N) за часом і пам’яттю. Трапляється в побудові кубічних сплайнів, рівняннях теплопровідності Кранка-Ніколсона та складанні 1D FEM.

Лагранжів метод: рідина — це набір частинок. Польові величини інтерполюються за допомогою ядра W(r,h): A(x) = Σ mⱼ Aⱼ/ρⱼ · W(x-xⱼ, h). Поширені ядра: кубічний сплайн, Wendland C4. Природно опрацьовує вільні поверхні; використовується в нашій симуляції рідини.

Гранична відстань h (довжина згладжування), за межами якої ядро SPH дорівнює нулю. Більше h → плавніші, але менш деталізовані результати. Зазвичай задається 2–3 міжчастинкові відстані. Просторове хешування обмежує пошук сусідів вузлами/комірками в межах h.

Відображає комірки 3D-сітки в 1D хеш-таблицю, щоб ефективно знаходити частинки в межах заданої відстані. Зменшує пошук сусідів з O(N²) до O(N·k), де k — середня кількість сусідів у радіусі носія.

Прогнозно-коригувальний SPH та бездивергентний SPH — розв’язувачі тиску, що забезпечують нестисливість точніше за початкове рівняння стану тиску. Бездивергентний SPH також коригує дивергенцію швидкості, зменшуючи похибки об’єму на 2–3 порядки.