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

Спектральные методы — это класс используемых в прикладной математике методик для численного решения некоторых дифференциальных уравнений, иногда использующих быстрое преобразование Фурье. Идея заключается в представлении решения дифференциальных уравнений как суммы некоторых «базисных функций» (например, как ряды Фурье являются суммой синусоид) с последующим выбором коэффициентов в сумме, наиболее удовлетворяющих заданным уравнениям.

Спектральные методы и методы конечных элементов тесно связаны и построены на одних и тех же идеях. Основное отличие заключается в том, что спектральные методы используют базисные функции, ненулевые во всей области определения, в то время как методы конечных элементов используют базисные функции, которые не равны нулю только в малых подобластях. Другими словами, спектральные методы предпринимают глобальный подход, в то время как методы конечных элементов используют локальный подход. Отчасти по этой причине спектральные методы имеют превосходные свойства так называемой «экспоненциальной сходимости», которая наиболее быстрая из возможных, если решение является гладким. Однако не известно трёхмерного однообластного спектрального метода сквозного счёта^[англ.] (ударная волна не гладкая)^[1]. Метод конечных элементов, в котором степень элементов очень высока или возрастает при уменьшении параметра решётки h, иногда называется методом спектрального элемента.

Спектральные методы могут быть использованы для решения обыкновенных дифференциальных уравнений (ОДУ), дифференциальных уравнений в частных производных и задач нахождения собственных значений, вовлекающих дифференциальные уравнения. Когда спектральные методы применяются к зависимым от времени дифференциальным уравнениям в частных производных, решение обычно записывается как сумма базисных функций с зависящими от времени коэффициентами. Подстановка такой суммы в дифференциальное уравнение в частных производных даёт систему обыкновенных дифференциальных уравнений от коэффициентов, которая может быть решена с помощью любого.численного метода обыкновенных дифференциальных уравнений^[англ.]. Задача нахождения собственных значений для обыкновенных дифференциальных уравнений аналогичным образом сводится к задаче нахождения собственных значений матрицы.

Спектральные методы были разработаны в серии статей Стивеном Орсага. Начиная с 1969 года они были разработаны для методов Фурье для периодических геометрических задач, полиномиальных спектральных методов для конечных и неограниченных геометрических задач, псевдоспектральных методов для сильно нелинейных задач, спектральных итерационных методов для решения задач стационарного состояния и других задач. Реализация спектрального метода обычно завершается коллокацией^[англ.]или методом Галёркина, или Тау-подходом^{[прояснить]}.

Спектральные методы вычислительно менее затратны, чем методы конечных элементов, но становятся менее точными для задач со сложными геометриями и прерывистыми коэффициентами. Это увеличение ошибки является следствием.явления Гиббса^[англ.]

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

Линейный пример

Здесь мы предполагаем понимание базового многомерного математического анализа и рядов Фурье. Если g(x,y) является известной комплексной функцией от двух вещественных переменных и g является периодической по x и по y ( g(x,y)=g(x+2π,y)=g(x,y+2π)), то мы заинтересованы в нахождении функции f(x,y), такой, что

\left({\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}\right)f(x,y)=g(x,y)

для всех x,y

где выражение слева означает вторую частную производную функции f по x и по y, соответственно. Это уравнение Пуассона и оно может быть физически проинтерпретировано как некоторый вид задачи передачи тепла или задачи в теории потенциалов среди прочих других возможностей.

Если мы запишем f и g в виде рядов Фурье

f=:\sum a_{j,k}e^{i(jx+ky)}

g=:\sum b_{j,k}e^{i(jx+ky)}

И подставим в дифференциальное уравнение, мы получим уравнение:

\sum -a_{j,k}(j^{2}+k^{2})e^{i(jx+ky)}=\sum b_{j,k}e^{i(jx+ky)}

Мы поменяли местами частичное дифференцирование с суммированием, что законно, если мы предположим, например, что f имеет непрерывную вторую производную. Согласно теореме единственности разложения Фурье, мы должны тогда приравнять коэффициенты Фурье элемент за элементом, что даёт

(*)

a_{j,k}=-{\frac {b_{j,k}}{j^{2}+k^{2}}}

что является явной формулой для коэффициентов Фурье a_j,k.

С периодическими краевыми условиями уравнение Пуассона обладает решением, только если b_0,0 = 0. Таким образом, мы можем свободно выбрать a_0,0. Это соответствует выбору константы интегрирования.

Чтобы преобразовать это в алгоритм, вычисляется только конечное число частот. Это даёт ошибку, которая, как можно показать, пропорциональна $h^{n}$ , где $h:=1/n$ и $n$ является наибольшей обрабатываемой частотой.

Алгоритм

Вычисляем преобразование Фурье (b_j,k) функции g.
Вычисляем преобразование Фурье (a_j,k) функции f через формулу (*).
Вычисляем f путём взятия обратного преобразования Фурье для (a_j,k).

Поскольку мы заинтересованы в конечном окне частот (скажем, размера n), это может быть сделано с помощью алгоритма быстрого преобразования Фурье. Поэтому, глобально, алгоритм работает за время O(n log n).

Нелинейный пример

Мы желаем решить нелинейное уравнение Бюргерса переходного процесса с помощью специального подхода.

Если дана $u(x,0)$ на периодической области $x\in \left[0,2\pi \right)$ , находим $u\in {\mathcal {U}}$ , такой, что

\partial _{t}u+u\partial _{x}u=\rho \partial _{xx}u+f\quad \forall x\in \left[0,2\pi \right),\forall t>0

где ρ является коэффициентом вязкости. Это превращается в

\left\langle \partial _{t}u,v\right\rangle =\left\langle \partial _{x}\left(-{\frac {1}{2}}u^{2}+\rho \partial _{x}u\right),v\right\rangle +\left\langle f,v\right\rangle \quad \forall v\in {\mathcal {V}},\forall t>0

где $\langle f,g\rangle :=\int _{0}^{2\pi }f(x){\overline {g(x)}}\,dx$ соответствует скалярному произведению. Интегрирование по частям и использование периодичности даёт

\langle \partial _{t}u,v\rangle =\left\langle {\frac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}v\right\rangle +\left\langle f,v\right\rangle \quad \forall v\in {\mathcal {V}},\forall t>0.

Для применения метода Фурье-Галёркина выберем

{\mathcal {U}}^{N}:=\left\{u:u(x,t)=\sum _{k=-N/2}^{N/2-1}{\hat {u}}_{k}(t)e^{ikx}\right\}

и

{\mathcal {V}}^{N}:={\text{ span}}\left\{e^{ikx}:k\in -N/2,\dots ,N/2-1\right\}

где ${\hat {u}}_{k}(t):={\frac {1}{2\pi }}\langle u(x,t),e^{ikx}\rangle$ . Это сводит задачу к поиску $u\in {\mathcal {U}}^{N}$ , такого, что

\langle \partial _{t}u,e^{ikx}\rangle =\left\langle {\frac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}e^{ikx}\right\rangle +\left\langle f,e^{ikx}\right\rangle \quad \forall k\in \left\{-N/2,\dots ,N/2-1\right\},\forall t>0.

Используя отношение ортогональности $\langle e^{ilx},e^{ikx}\rangle =2\pi \delta _{lk}$ , где $\delta _{lk}$ является дельтой Кронекера, мы упрощаем три элемента выше для каждого $k$

{\begin{aligned}\left\langle \partial _{t}u,e^{ikx}\right\rangle &=\left\langle \partial _{t}\sum _{l}{\hat {u}}_{l}e^{ilx},e^{ikx}\right\rangle =\left\langle \sum _{l}\partial _{t}{\hat {u}}_{l}e^{ilx},e^{ikx}\right\rangle =2\pi \partial _{t}{\hat {u}}_{k},\\\left\langle f,e^{ikx}\right\rangle &=\left\langle \sum _{l}{\hat {f}}_{l}e^{ilx},e^{ikx}\right\rangle =2\pi {\hat {f}}_{k},{\text{ and}}\\\left\langle {\frac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}e^{ikx}\right\rangle &=\left\langle {\frac {1}{2}}\left(\sum _{p}{\hat {u}}_{p}e^{ipx}\right)\left(\sum _{q}{\hat {u}}_{q}e^{iqx}\right)-\rho \partial _{x}\sum _{l}{\hat {u}}_{l}e^{ilx},\partial _{x}e^{ikx}\right\rangle \\&=\left\langle {\frac {1}{2}}\sum _{p}\sum _{q}{\hat {u}}_{p}{\hat {u}}_{q}e^{i\left(p+q\right)x},ike^{ikx}\right\rangle -\left\langle \rho i\sum _{l}l{\hat {u}}_{l}e^{ilx},ike^{ikx}\right\rangle \\&=-{\frac {ik}{2}}\left\langle \sum _{p}\sum _{q}{\hat {u}}_{p}{\hat {u}}_{q}e^{i\left(p+q\right)x},e^{ikx}\right\rangle -\rho k\left\langle \sum _{l}l{\hat {u}}_{l}e^{ilx},e^{ikx}\right\rangle \\&=-i\pi k\sum _{p+q=k}{\hat {u}}_{p}{\hat {u}}_{q}-2\pi \rho {}k^{2}{\hat {u}}_{k}.\end{aligned}}

Собираем три члена для каждого $k$ и получаем

2\pi \partial _{t}{\hat {u}}_{k}=-i\pi k\sum _{p+q=k}{\hat {u}}_{p}{\hat {u}}_{q}-2\pi \rho {}k^{2}{\hat {u}}_{k}+2\pi {\hat {f}}_{k}\quad k\in \left\{-N/2,\dots ,N/2-1\right\},\forall t>0.

Делим на $2\pi$ и, наконец, получаем

\partial _{t}{\hat {u}}_{k}=-{\frac {ik}{2}}\sum _{p+q=k}{\hat {u}}_{p}{\hat {u}}_{q}-\rho {}k^{2}{\hat {u}}_{k}+{\hat {f}}_{k}\quad k\in \left\{-N/2,\dots ,N/2-1\right\},\forall t>0.

С начальными условиями преобразования Фурье ${\hat {u}}_{k}(0)$ и определяя ${\hat {f}}_{k}(t)$ , эта пара обыкновенных дифференциальных уравнений может быть проинтегрирована по времени (с помощью, например, техники Рунге — Кутта) для нахождения решения. Нелинейный член является свёрткой и существует несколько техник, основанных на преобразованиях, для вычисления эффективного её вычисления.

Связь с методом спектрального элемента

Можно показать, что если $g$ бесконечно дифференцируема, то численный алгоритм, использующий быстрое преобразование Фурье, сходится быстрее, чем любой многочлен на решётке размера h. То есть для любого n>0 существует $C_{n}<\infty$ , такое, что ошибка меньше $C_{n}h^{n}$ для всех достаточно малых значений $h$ . Мы говорим, что спектральный метод имеет порядок $n$ для любого n>0.

Поскольку метод спектрального элемента является методом конечных элементов очень высокого порядка, имеется похожесть в свойствах сходимости. Однако спектральный метод основан на разложении по собственным значениям конкретной краевой задачи, а метод конечных элементов не использует эту информацию и работает для произвольных эллиптических краевых задач^[англ.].

См. также

Примечания

↑ Canuto, Hussaini, Quarteroni, Zang, 2007, с. 285.

Литература

Claudio Canuto, M. Yousuff Hussaini, Alfio Quarteroni, Thomas A. Zang. Spectral Methods: evolution to complex geometries and applications to fluid dynamics. — Springer, 2007. — (Scientific Computation). — ISBN 978-3-540-30727-3.
Bengt Fornberg. A Practical Guide to Pseudospectral Methods. — Cambridge, UK: Cambridge University Press, 1996. — (Cambridge monographs on applied and computational mathematics). — ISBN 0-521-49582-2.
John P. Boyd. Chebyshev and Fourier Spectral Methods. — Mineola, New York: Dover Publications, Inc., 2000.
Canuto C., Hussaini M. Y., Quarteroni A., Zang T.A. Spectral Methods. Fundamentals in Single Domains. — Berlin Heidelberg: Springer-Verlag, 2006. — (Scientific Computation). — ISBN 3-540-30725-7.
Javier de Frutos, Julia Novo. A Spectral Element Method for the Navier-Stokes Equations with Improved Accuracy // Applied Numerical Mathematics. — 2000. — Т. 33, вып. 1. — С. 217-223. — doi:10.1016/S0168-9274(99)00086-0.
Daniele Funaro. Polynomial Approximation of Differential Equations. — Heidelberg: Springer-Verlag, 1992. — Т. 8. — (Lecture Notes in Physics). — ISBN 3-540-55230-8.
D. Gottlieb, S. Orzag. Numerical Analysis of Spectral Methods: Theory and Applications. — Philadelphia, PA: SIAM, 1977.
J. Hesthaven, S. Gottlieb, D. Gottlieb. Spectral methods for time-dependent problems. — Cambridge, UK: Cambridge University Press, 2007. — (Cambridge monographs on applied and computational mathematics). — ISBN 0-521-79211-8.
Steven A. Orszag. Numerical Methods for the Simulation of Turbulence // Phys. Fluids Supp. II. — 1969. — Вып. 12. — С. 250-257.
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Section 20.7. Spectral Methods // Numerical Recipes: The Art of Scientific Computing. — 3rd. — New York: Cambridge University Press, 2007. — ISBN 978-0-521-88068-8.
Lloyd N. Trefethen. Spectral Methods in MATLAB. — Philadelphia, PA: SIAM, 2000.