Метод конечных разностей для PDE

Каждый пиксель фильтра Лапласа в OpenCV - это конечная разность. Симуляция климата - PDE на сетке 0.5°×0.5°. Рендеринг жидкости в играх - уравнение Навье-Стокса, дискретизованное конечными разностями и решаемое на GPU.

• **Обработка изображений:** оператор Лапласа и фильтр Собеля - конечноразностные шаблоны второго порядка; cv2.Laplacian использует этот шаблон
• **Климатические модели:** атмосферные уравнения дискретизуются на сферической сетке; CFL ограничивает временной шаг по скорости звука
• **GPU-симуляция жидкости:** давление решается уравнением Пуассона на каждом кадре; CUDA-реализация разреженных матриц

Предварительные знания

• Stiff Systems

Конечноразностные шаблоны

Метод конечных разностей заменяет производные конечноразностными аппроксимациями на регулярной сетке. Производная аппроксимируется отношением конечных приращений. Порядок точности определяется тем, насколько хорошо аппроксимация воспроизводит ряд Тейлора.

**Базовые шаблоны (шаг h):** **Первая производная:** Forward: (uᵢ₊₁ − uᵢ) / h + O(h) ← первый порядок Backward: (uᵢ − uᵢ₋₁) / h + O(h) Central: (uᵢ₊₁ − uᵢ₋₁) / (2h) + O(h²) ← второй порядок **Вторая производная:** (uᵢ₋₁ − 2uᵢ + uᵢ₊₁) / h² + O(h²) ← лапласиан **Коэффициенты:** выводятся подстановкой ряда Тейлора в шаблон.

Конечные разности применяются в обработке изображений: **оператор Лапласа** ∇²I = (Iᵢ₋₁,ⱼ + Iᵢ₊₁,ⱼ + Iᵢ,ⱼ₋₁ + Iᵢ,ⱼ₊₁ − 4Iᵢ,ⱼ) / h² выделяет края. Это тот же 5-точечный шаблон лапласиана!

Уравнение теплопроводности: FTCS и Кранк-Николсон

Уравнение теплопроводности ∂u/∂t = α ∂²u/∂x² - простейшее PDE. Схема FTCS (Forward-Time Central-Space) - явная: вычисляет uⁿ⁺¹ через uⁿ. Схема Кранк-Николсон - неявная, безусловно устойчивая и второго порядка по t.

**FTCS (явная схема):** uᵢⁿ⁺¹ = uᵢⁿ + r·(uᵢ₋₁ⁿ − 2uᵢⁿ + uᵢ₊₁ⁿ) где r = α·Δt / Δx² **CFL условие устойчивости:** r ≤ 1/2 **Кранк-Николсон (неявная, O(Δt²)):** uᵢⁿ⁺¹ − r/2·(uᵢ₋₁ⁿ⁺¹ − 2uᵢⁿ⁺¹ + uᵢ₊₁ⁿ⁺¹) = uᵢⁿ + r/2·(uᵢ₋₁ⁿ − 2uᵢⁿ + uᵢ₊₁ⁿ) Трёхдиагональная система на каждом шаге - O(n) алгоритм прогонки!

Условие CFL и уравнение Пуассона 2D

Условие Куранта-Фридрихса-Леви (CFL) - ключевое ограничение явных PDE-схем. Физический смысл: числовая скорость распространения информации должна не уступать физической. Уравнение Пуассона −∇²u = f - эллиптическая PDE без временнóй зависимости: решается однократно.

**Условие CFL (для волнового уравнения):** C = c·Δt / Δx ≤ 1 где c - скорость волны, Δt - шаг по времени, Δx - шаг по пространству. **Для уравнения теплопроводности:** r = α·Δt / Δx² ≤ 1/2 **2D уравнение Пуассона:** −(∂²u/∂x² + ∂²u/∂y²) = f(x,y) Дискретизация: 5-точечный шаблон = разреженная СЛАУ размера N² × N². Для N = 1000: матрица 10⁶ × 10⁶ - только разреженные методы!

**Применение в GPU-симуляции жидкости.** Уравнение Пуассона для давления решается на каждом кадре в симуляции несжимаемой жидкости. На GPU используется итерационный солвер (мультисеточный метод) - каждая итерация выполняет разреженный SpMV параллельно на тысячах ядер.

Ключевые идеи

• **Конечные разности:** первая производная O(h) или O(h²), вторая O(h²); коэффициенты из ряда Тейлора
• **FTCS:** явная схема для теплопроводности; условие устойчивости r = αΔt/Δx² ≤ 1/2
• **Кранк-Николсон:** неявная, O(Δt²), безусловно устойчивая; трёхдиагональная СЛАУ на шаг
• **Уравнение Пуассона:** 5-точечный шаблон → разреженная СЛАУ N²×N²; только scipy.sparse!

Связанные темы

Конечные разности порождают жёсткие системы и разреженные матрицы:

• Жёсткие системы — Дискретизация PDE порождает жёсткие ОДУ; CFL - условие устойчивости явных методов
• Метод конечных элементов — МКЭ - обобщение МКР на нерегулярные сетки; те же операции сборки матрицы жёсткости

Вопросы для размышления

• Почему схема Кранк-Николсон имеет второй порядок по Δt, хотя содержит неявное и явное слагаемые?
• Как условие CFL меняется для 2D уравнения теплопроводности на квадратной сетке?
• Можно ли использовать конечные разности для обработки изображений с нерегулярными границами?

Связанные уроки

• de-07