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

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

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

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

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

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

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

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

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

$\left({\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}\right)f(x,y)=g(x,y)\quad {\text{for all }}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^{i(jx+ky)},\end{aligned}}$

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

$\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. Следовательно, мы можем свободно выбрать 0,0 _, которое будет равно среднему значению разрешения. Это соответствует выбору константы интегрирования.

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

Алгоритм

1. Вычислите преобразование Фурье ( b _j,k ) g .
2. Вычислите преобразование Фурье ( a _j,k ) f по формуле ( * ).
3. Вычислите 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 ={\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.$

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

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

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

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

См. также

• Метод конечных элементов
• Гауссова сетка
• Псевдоспектральный метод
• Метод спектральных элементов
• Метод Галёркина
• Метод коллокации

Ссылки

• Бенгт Форнберг (1996) Практическое руководство по псевдоспектральным методам. Издательство Кембриджского университета, Кембридж, Великобритания
• Чебышева и спектральные методы Фурье Джона П. Бойда.
• Кануто К., Хуссаини М.Ю. , Квартерони А. и Занг Т.А. (2006) Спектральные методы. Основы работы с отдельными доменами. Шпрингер-Верлаг, Берлин Гейдельберг
• Хавьер де Фрутос, Джулия Ново (2000): Метод спектральных элементов для уравнений Навье – Стокса с повышенной точностью
• Полиномиальная аппроксимация дифференциальных уравнений , Даниэле Фунаро, Конспект лекций по физике, том 8, Springer-Verlag, Гейдельберг, 1992 г.
• Д. Готлиб и С. Орзаг (1977) «Численный анализ спектральных методов: теория и приложения», SIAM, Филадельфия, Пенсильвания
• Дж. Хестхавен, С. Готлиб и Д. Готлиб (2007) «Спектральные методы для нестационарных задач», Кембриджский университет, Кембридж, Великобритания
• Стивен А. Орзаг (1969) Численные методы моделирования турбулентности , Phys. Доп. жидкости. II, 12, 250–257
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 20.7. Спектральные методы» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 .
• Цзе Шен, Тао Тан и Ли-Лиан Ван (2011) «Спектральные методы: алгоритмы, анализ и приложения» (серия Спрингера по вычислительной математике, т. 41, Springer), ISBN   354071040X
• Ллойд Н. Трефетен (2000) Спектральные методы в MATLAB. СИАМ, Филадельфия, Пенсильвания