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

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

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

Спектральные методы могут использоваться для решения обыкновенных дифференциальных уравнений (ОДУ), уравнений в частных производных (УЧП) и задач на собственные значения, включающих дифференциальные уравнения. При применении спектральных методов к зависящим от времени PDE решение обычно записывается как сумма базисных функций с зависящими от времени коэффициентами; подстановка этого в 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 и (х, 0)}$${\ Displaystyle х \ в \ влево [0,2 \ пи \ вправо)}$${\ 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} {\ шляпа {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 и \ ин {\ 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, \ точки , 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 {align} \ 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, \ частичный _ {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 {align}}}$

Соберите три члена для каждого, чтобы получить ${\ 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_ {п} <\ 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. СИАМ, Филадельфия, Пенсильвания