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

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

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

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

Спектральные методы были разработаны Стивеном Орзагом в длинной серии статей, начиная с 1969 года, включая, помимо прочего, методы рядов Фурье для периодических задач геометрии, полиномиальные спектральные методы для конечных и неограниченных задач геометрии, псевдоспектральные методы для сильно нелинейных задач и спектральные методы. итерационные методы быстрого решения стационарных задач. Реализация спектрального метода обычно осуществляется либо с помощью коллокации , либо с помощью подхода Галеркина или Тау. Для очень маленьких задач спектральный метод уникален тем, что решения можно записать в символическом виде, что дает практическую альтернативу решениям в виде рядов для дифференциальных уравнений.

Спектральные методы могут быть менее затратными в вычислительном отношении и более простыми в реализации, чем методы конечных элементов; они проявляются лучше всего, когда требуется высокая точность в простых областях с гладкими решениями. Однако из-за своей глобальной природы матрицы, связанные с пошаговыми вычислениями, являются плотными, и эффективность вычислений быстро снижается, когда имеется много степеней свободы (за некоторыми исключениями, например, если матричные приложения могут быть записаны как преобразования Фурье ). Для более крупных задач и негладких решений конечные элементы обычно работают лучше из-за разреженных матриц и лучшего моделирования разрывов и резких изгибов.

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

Конкретный, линейный пример

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

\left({\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}\ вправо)f(x,y)=g(x,y)\quad {\text{для всех }}x,y

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

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

{\begin{aligned}f&=:\sum a_{j,k}e^{i(jx+ky)},\\[5mu]g&=:\sum b_{j,k}e^{ я(jx+ky)},\end{aligned}}

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

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

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

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

При периодических граничных условиях уравнение Пуассона имеет решение только в том случае, если b _0,0 = 0. Следовательно, мы можем свободно выбрать 0,0 _, которое будет равно среднему значению разрешения. Это соответствует выбору константы интегрирования.

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

Алгоритм

Вычислите преобразование Фурье ( b _j,k ) g .
Вычислите преобразование Фурье ( a _j,k ) f по формуле ( * ).
Вычислите f , приняв обратное преобразование Фурье ( a _j,k ).

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

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

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

Учитывая периодическую область , найдите такое, что ${\ displaystyle 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 = {\Bigl \langle }\partial _{x}\left(-{\tfrac {1}{2}}u^{ 2}+\rho\partial _{x}u\right),v{\Bigr \rangle }+\left\langle f,v\right\rangle \quad \forall v\in {\mathcal {V}}, \forall t>0

где следующее обозначение внутреннего продукта . Интегрирование по частям и использование грантов периодичности

\langle \partial _{t}u,v\rangle =\left\langle {\tfrac {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}:={\biggl \{}u:u(x,t)=\sum _{k=-N/2}^{N/2-1} {\hat {u}}_{k}(t)e^{ikx}{\biggr \}}

{\mathcal {V}}^{N}:=\operatorname {span} \left\{e^{ikx}:k\in - {\tfrac {1}{2}}N,\dots , {\tfrac {1}{2}}N-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 {\tfrac {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\{-{\tfrac {1} {2}}N,\dots ,{\tfrac {1}{2}}N-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 &={\biggl \langle }\partial _{t}\sum _{l}{\hat {u}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }={\biggl \langle }\sum _{l}\partial _{t}{\hat {u}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }=2\pi \partial _{t}{\hat {u}}_{k},\\\left\langle f,e^{ikx}\right\rangle &={\biggl \langle }\sum _{l}{\hat {f}}_{l}e^{ilx},e^{ikx}{\biggr \rangle }=2\pi {\hat {f}}_{k},{\text{ and}}\\\left\langle {\tfrac {1}{2}}u^{2}-\rho \partial _{x}u,\partial _{x}e^{ikx}\right\rangle &={\biggl \langle }{\tfrac {1}{2}}{\Bigl (}\sum _{p}{\hat {u}}_{p}e^{ipx}{\Bigr )}{\Bigl (}\sum _{q}{\hat {u}}_{q}e^{iqx}{\Bigr )}-\rho \partial _{x}\sum _{l}{\hat {u}}_{l}e^{ilx},\partial _{x}e^{ikx}{\biggr \rangle }\\&={\biggl \langle }{\tfrac {1}{2}}\sum _{p}\sum _{q}{\hat {u}}_{p}{\hat {u}}_{q}e^{i\left(p+q\right)x},ike^{ikx}{\biggr \rangle }-{\biggl \langle }\rho i\sum _{l}l{\hat {u}}_{l}e^{ilx},ike^{ikx}{\biggr \rangle }\\&=-{\tfrac {1}{2}}ik{\biggl \langle }\sum _{p}\sum _{q}{\hat {u}}_{p}{\hat {u}}_{q}e^{i\left(p+q\right)x},e^{ikx}{\biggr \rangle }-\rho k{\biggl \langle }\sum _{l}l{\hat {u}}_{l}e^{ilx},e^{ikx}{\biggr \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\{-{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-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\{-{\tfrac {1}{2}}N,\dots ,{\tfrac {1}{2}}N-1\right\},\forall t>0.

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

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

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

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