Спектральные методы

Метеорологи предсказывают погоду на 10 дней с помощью уравнений атмосферы, это PDE в 3D с миллионами переменных. Аэродинамики моделируют турбулентность вокруг крыла самолёта. В обоих случаях требуется не просто точность, а **спектральная точность**: ошибка уменьшается быстрее любой степени h при росте числа узлов. Это достигается спектральными методами, и именно поэтому многие глобальные модели атмосферы (ECMWF, NCEP) исторически были основаны на преобразовании Фурье.

• **Численная метеорология**: ECMWF до 2016 использовал спектральную модель (T1279, 1279 гармоник, разрешение ~16 км)
• **Квантовая химия**: псевдоспектральные методы для расчёта молекулярных орбиталей (DFT, density functional theory)
• **Гидродинамика**: DNS (Direct Numerical Simulation) турбулентности, самые точные симуляции используют спектральные методы

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

• Sparse Matrices
• Numerical Integration

Идея спектральных методов: глобальные базисы

FNO (Fourier Neural Operator, NVIDIA, 2020) решает уравнения в частных производных в 1000× быстрее МКЭ, используя спектральные базисные функции. Конечные разности и конечные элементы используют **локальные** базисные функции: полиномы малой степени на каждом элементе. Спектральные методы идут в другую сторону, решение аппроксимируется **глобальными** функциями высокой степени (тригонометрическими полиномами Фурье или алгебраическими полиномами Чебышёва).

Решение u(x) представляется как конечная сумма: u(x) ≈ u_N(x) = Σₖ₌₀ᴺ û_k · φ_k(x) где φ_k, базисные функции (синусы/косинусы, полиномы Чебышёва, Лежандра), û_k, спектральные коэффициенты. **Экспоненциальная сходимость** (spectral accuracy): если u(x) бесконечно гладкая, ошибка убывает как e^{-cN}, намного быстрее, чем O(h^p) для МКЭ с фиксированным порядком p.

Цена за экспоненциальную сходимость, **требование гладкости**: если решение имеет разрывы или острые пики (типично для PDE с ударными волнами), спектральные методы страдают от эффекта Гиббса. В таких случаях предпочтительнее методы высокого порядка с hp-adaptivity или специальные спектральные фильтры.

Полиномы Чебышёва: оптимальная интерполяция

Полиномы Чебышёва, «лучший» алгебраический базис для апроксимации на отрезке [-1,1]. Они минимизируют максимальную ошибку интерполяции (теорема минимакса) и решают проблему явления Рунге, сильных осцилляций при равноудалённых узлах.

Ошибка полиномиальной интерполяции в N+1 точках: |f(x) - p_N(x)| ≤ (1/(N+1)!) · max|f^{(N+1)}(ξ)| · |ω_{N+1}(x)| где ω_{N+1}(x) = ∏(x - xⱼ). Узлы Чебышёва минимизируют max|ω_{N+1}(x)| на [-1,1]: max|ω| = 1/2^N, это минимально возможное значение среди всех наборов из N+1 узлов (теорема Чебышёва о минимаксном полиноме). Для сравнения: у равноудалённых узлов max|ω| ~ 2N+1/(4e·N), экспоненциально больше!

Спектральные методы для ODE и PDE

Матрица дифференцирования Чебышёва D превращает задачу ODE/PDE в систему линейных уравнений. Коллокационный метод: подобрать коэффициенты решения так, чтобы уравнение точно выполнялось в узлах Чебышёва.

**Спектральный метод Галёркина**: подставляем u_N = Σ û_k φ_k в уравнение, требуем ортогональность невязки каждому базисному элементу. Матрицы часто разреженные для специальных базисов. **Коллокация (псевдоспектральный метод)**: требуем точного выполнения уравнения в узлах. Проще в реализации, особенно для нелинейных задач, нелинейность вычисляется поточечно в физическом пространстве. **Псевдоспектральный трюк для нелинейных PDE**: переключаться между спектральным и физическим пространствами через FFT, производные вычисляются спектрально, нелинейные члены, поточечно.

FFT в спектральных методах

Быстрое преобразование Фурье (FFT), алгоритм Кули-Тьюки (1965), вычисляет дискретное преобразование Фурье за O(N log N) вместо O(N²). Без FFT спектральные методы были бы практически бесполезны для больших N.

DFT: F_k = Σₙ fₙ · e^{-2πi·kn/N}, наивно O(N²) FFT (Cooley-Tukey): рекурсивно разбивает N-точечный DFT на два N/2-точечных DFT по чётным и нечётным индексам: F_k = F_k^{even} + e^{-2πik/N} · F_k^{odd} Т(N) = 2·T(N/2) + O(N) → T(N) = O(N log₂ N) При N = 2^m (степень двойки) алгоритм максимально эффективен. Для N = 10⁶: FFT требует ~2·10⁷ операций вместо 10¹² у наивного DFT, ускорение в 50000 раз.

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

• **Спектральные методы**: аппроксимация через глобальные базисы (Фурье, Чебышёв), экспоненциальная сходимость e^{-cN} для гладких функций
• **Узлы Чебышёва**: минимизируют максимальную ошибку интерполяции, устраняют явление Рунге, «сгущаются» у концов отрезка
• **Матрица дифференцирования D**: превращает дифференциальное уравнение в систему линейных уравнений на узлах, просто реализовать
• **FFT**: O(N log N) алгоритм для перехода между физическим и спектральным пространствами, ключ к эффективности нелинейных псевдоспектральных методов

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

Спектральные методы, расширение классических методов к высокой точности:

• МКЭ и конечные разности для PDE — Конечные разности, локальные, O(h^p). Спектральные, глобальные, экспоненциальные. Выбор зависит от гладкости решения
• Методы решения ODE — Спектральные методы для краевых задач ODE конкурируют с shooting method и конечными разностями, выигрывают при гладких решениях
• Адаптивные методы — Для негладких решений спектральный метод деградирует, именно тогда нужна hp-адаптация или конечные элементы высокого порядка

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

• Для каких физических задач спектральные методы явно превосходят конечные элементы, а для каких, уступают?
• Как бы обнаружили, что решение данной PDE «развило» разрыв в ходе вычисления, и что сделали бы с методом?
• FFT требует N = 2^m для максимальной эффективности. Как это ограничение влияет на практический выбор размера сетки?

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

• dsp-05