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

Эта статья включает в себя список общих ссылок , но он остается в основном непроверенным, поскольку в нем отсутствуют соответствующие встроенные ссылки . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Август 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

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

Конкретный линейный пример [ править ]

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

${\ displaystyle \ 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 в ряды Фурье:

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

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

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

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

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

(*) ${\displaystyle a_{j,k}=-{\frac {b_{j,k}}{j^{2}+k^{2}}}}$

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

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

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

Алгоритм [ править ]

1. Вычислите преобразование Фурье ( b _{j, k} ) функции g .
2. Вычислите преобразование Фурье ( a _{j, k} ) функции f по формуле (*).
3. Вычислить f , взяв обратное преобразование Фурье ( a _{j, k} ).

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

Нелинейный пример [ править ]

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

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

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

где ρ - коэффициент вязкости . В слабой консервативной форме это становится

${\displaystyle \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}$

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

${\displaystyle \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.}$

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

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

и

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

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

${\displaystyle \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.}$

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

${\displaystyle {\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}}}$

Соберите три члена для каждого, чтобы получить${\displaystyle k}$

${\displaystyle 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.}$

Разделив на , мы наконец приходим к${\displaystyle 2\pi }$

${\displaystyle \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.}$

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

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

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

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

См. Также [ править ]

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

Ссылки [ править ]

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