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

Класс аналитических процессов решения уравнений в частных производных

Псевдоспектральные методы , ^[1] также известные как методы представления дискретных переменных (DVR), представляют собой класс численных методов , используемых в прикладной математике и научных вычислениях для решения уравнений в частных производных . Они тесно связаны со спектральными методами , но дополняют базис дополнительным псевдоспектральным базисом, который позволяет представлять функции на квадратурной сетке ^{[ необходимо определение ]} . Это упрощает оценку некоторых операторов и может значительно ускорить вычисления при использовании быстрых алгоритмов, таких как быстрое преобразование Фурье .

Мотивация конкретным примером

Возьмем задачу начального значения

${\displaystyle i{\frac {\partial }{\partial t}}\psi (x,t)={\Bigl [}-{\frac {\partial ^{2}}{\partial x^{2}}}+V(x){\Bigr ]}\psi (x,t),\qquad \qquad \psi (t_{0})=\psi _{0}}$

с периодическими условиями . Этот конкретный пример представляет собой уравнение Шрёдингера для частицы в потенциале , но структура более общая. Во многих практических уравнениях в частных производных есть член, который включает в себя производные (например, вклад кинетической энергии) и умножение на функцию (например, потенциал). ${\displaystyle \psi (x+1,t)=\psi (x,t)}$ ${\displaystyle V(x)}$

В спектральном методе решение разлагается по подходящему набору базисных функций, например плоских волн, ${\displaystyle \psi }$

${\displaystyle \psi (x,t)={\frac {1}{\sqrt {2\pi }}}\sum _{n}c_{n}(t)e^{2\pi inx}.}$

Вставка и приравнивание одинаковых коэффициентов дает систему обыкновенных дифференциальных уравнений для коэффициентов:

${\displaystyle i{\frac {d}{dt}}c_{n}(t)=(2\pi n)^{2}c_{n}+\sum _{k}V_{n-k}c_{k},}$

где элементы вычисляются с помощью явного преобразования Фурье ${\displaystyle V_{n-k}}$

${\displaystyle V_{n-k}=\int _{0}^{1}V(x)\ e^{2\pi i(k-n)x}dx.}$

Тогда решение будет получено путем усечения разложения до базисных функций и поиска решения для . Обычно это делается численными методами , такими как методы Рунге-Кутты . Для численного решения правая часть обыкновенного дифференциального уравнения должна вычисляться повторно на разных временных шагах. На этом этапе у спектрального метода возникает серьезная проблема с потенциальным членом . ${\displaystyle N}$ ${\displaystyle c_{n}(t)}$ ${\displaystyle V(x)}$

В спектральном представлении умножение на функцию преобразуется в векторно-матричное умножение, которое масштабируется как . Кроме того, элементы матрицы необходимо вычислить явно, прежде чем можно будет решить дифференциальное уравнение для коэффициентов, что требует дополнительного шага. ${\displaystyle V(x)}$ ${\displaystyle N^{2}}$ ${\displaystyle V_{n-k}}$

В псевдоспектральном методе этот член оценивается по-другому. Учитывая коэффициенты , обратное дискретное преобразование Фурье дает значение функции в дискретных точках сетки . В этих точках сетки функция затем умножается и результат преобразуется обратно Фурье. Это дает новый набор коэффициентов , которые используются вместо матричного произведения . ${\displaystyle c_{n}(t)}$ ${\displaystyle \psi }$ ${\displaystyle x_{j}=2\pi j/N}$ ${\displaystyle \psi '(x_{i},t)=V(x_{i})\psi (x_{i},t)}$ ${\displaystyle c'_{n}(t)}$ ${\displaystyle \sum _{k}V_{n-k}c_{k}(t)}$

Можно показать, что оба метода имеют одинаковую точность. Однако псевдоспектральный метод позволяет использовать быстрое преобразование Фурье, которое масштабируется как и, следовательно, значительно более эффективно, чем матричное умножение. Кроме того, функцию можно использовать напрямую, без вычисления каких-либо дополнительных интегралов. ${\displaystyle O(N\ln N)}$ ${\displaystyle V(x)}$

Техническое обсуждение

Более абстрактно, псевдоспектральный метод имеет дело с умножением двух функций и как часть уравнения в частных производных. Для упрощения обозначений зависимость от времени опущена. Концептуально он состоит из трех этапов: ${\displaystyle V(x)}$ ${\displaystyle f(x)}$

1. ${\displaystyle f(x),{\tilde {f}}(x)=V(x)f(x)}$разлагаются по конечному набору базисных функций (это спектральный метод ).
2. Для заданного набора базисных функций ищется квадратура, которая преобразует скалярные произведения этих базисных функций во взвешенную сумму по узлам сетки.
3. Произведение рассчитывается путем умножения в каждой точке сетки. ${\displaystyle V,f}$

Расширение в основе

Функции можно разложить в конечном базисе как ${\displaystyle f,{\tilde {f}}}$ ${\displaystyle \{\phi _{n}\}_{n=0,\ldots ,N}}$

${\displaystyle f(x)=\sum _{n=0}^{N}c_{n}\phi _{n}(x)}$

${\displaystyle {\tilde {f}}(x)=\sum _{n=0}^{N}{\tilde {c}}_{n}\phi _{n}(x)}$

Для простоты пусть базис будет ортогональным и нормализованным, используя внутренний продукт с соответствующими границами . Коэффициенты затем получаются по формуле ${\displaystyle \langle \phi _{n},\phi _{m}\rangle =\delta _{nm}}$ ${\displaystyle \langle f,g\rangle =\int _{a}^{b}f(x){\overline {g(x)}}dx}$ ${\displaystyle a,b}$

${\displaystyle c_{n}=\langle f,\phi _{n}\rangle }$

${\displaystyle {\tilde {c}}_{n}=\langle {\tilde {f}},\phi _{n}\rangle }$

Тогда немного вычислений даст результат

${\displaystyle {\tilde {c}}_{n}=\sum _{m=0}^{N}V_{n-m}c_{m}}$

с . Это составляет основу спектрального метода. Чтобы отличить базис от квадратурного, расширение иногда называют представлением конечного базиса (FBR). ${\displaystyle V_{n-m}=\langle V\phi _{m},\phi _{n}\rangle }$ ${\displaystyle \phi _{n}}$

Квадратура

Для заданного базиса и количества базисных функций можно попытаться найти квадратуру, т. е. набор точек и весов такой, что ${\displaystyle \{\phi _{n}\}}$ ${\displaystyle N+1}$ ${\displaystyle N+1}$

${\displaystyle \langle \phi _{n},\phi _{m}\rangle =\sum _{i=0}^{N}w_{i}\phi _{n}(x_{i}){\overline {\phi _{m}(x_{i})}}\qquad \qquad n,m=0,\ldots ,N}$

Особыми примерами являются квадратура Гаусса для полиномов и дискретное преобразование Фурье для плоских волн. Следует подчеркнуть, что точки сетки и веса являются функцией базиса и числа . ${\displaystyle x_{i},w_{i}}$ ${\displaystyle N}$

Квадратура позволяет альтернативное числовое представление функции через ее значение в точках сетки. Это представление иногда называют представлением дискретных переменных (DVR) и полностью эквивалентно разложению в базисе. ${\displaystyle f(x),{\tilde {f}}(x)}$

${\displaystyle f(x_{i})=\sum _{n=0}^{N}c_{n}\phi _{n}(x_{i})}$

${\displaystyle c_{n}=\langle f,\phi _{n}\rangle =\sum _{i=0}^{N}w_{i}f(x_{i}){\overline {\phi _{n}(x_{i})}}}$

Умножение

Затем умножение на функцию выполняется в каждой точке сетки, ${\displaystyle V(x)}$

${\displaystyle {\tilde {f}}(x_{i})=V(x_{i})f(x_{i}).}$

Обычно это вводит дополнительное приближение. Чтобы убедиться в этом, мы можем вычислить один из коэффициентов : ${\displaystyle {\tilde {c}}_{n}}$

${\displaystyle {\tilde {c}}_{n}=\langle {\tilde {f}},\phi _{n}\rangle =\sum _{i}w_{i}{\tilde {f}}(x_{i}){\overline {\phi _{n}(x_{i})}}=\sum _{i}w_{i}V(x_{i})f(x_{i}){\overline {\phi _{n}(x_{i})}}}$

Однако при использовании спектрального метода тот же коэффициент будет равен . Таким образом, псевдоспектральный метод вводит дополнительное приближение ${\displaystyle {\tilde {c}}_{n}=\langle Vf,\phi _{n}\rangle }$

${\displaystyle \langle Vf,\phi _{n}\rangle \approx \sum _{i}w_{i}V(x_{i})f(x_{i}){\overline {\phi _{n}(x_{i})}}.}$

Если произведение можно представить с помощью заданного конечного набора базисных функций, приведенное выше уравнение является точным благодаря выбранной квадратуре. ${\displaystyle Vf}$

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

Метод Фурье

Если на систему наложены периодические граничные условия с периодом , базисные функции могут порождаться плоскими волнами: ${\displaystyle [0,L]}$

${\displaystyle \phi _{n}(x)={\frac {1}{\sqrt {L}}}e^{-\imath k_{n}x}}$

с , где – функция потолка . ${\displaystyle k_{n}=(-1)^{n}\lceil n/2\rceil 2\pi /L}$ ${\displaystyle \lceil \cdot \rceil }$

Квадратура для обрезания при задается дискретным преобразованием Фурье . Точки сетки расположены на равном расстоянии друг от друга, с интервалом , а постоянные веса равны . ${\displaystyle n_{\text{max}}=N}$ ${\displaystyle x_{i}=i\Delta x}$ ${\displaystyle \Delta x=L/(N+1)}$ ${\displaystyle w_{i}=\Delta x}$

Для обсуждения ошибки обратите внимание, что произведение двух плоских волн снова является плоской волной с . Таким образом, качественно, если функции могут быть достаточно точно представлены с помощью базисных функций, псевдоспектральный метод дает точные результаты при использовании базисных функций. ${\displaystyle \phi _{a}+\phi _{b}=\phi _{c}}$ ${\displaystyle c\leq a+b}$ ${\displaystyle f(x),V(x)}$ ${\displaystyle N_{f},N_{V}}$ ${\displaystyle N_{f}+N_{V}}$

Разложение по плоским волнам часто имеет низкое качество и требует сходимости многих базисных функций. Однако преобразование между базовым расширением и сеточным представлением можно выполнить с помощью быстрого преобразования Фурье , которое масштабируется как . Как следствие, плоские волны являются одним из наиболее распространенных расширений, встречающихся при использовании псевдоспектральных методов. ${\displaystyle N\ln N}$

Полиномы

Другое распространенное расширение - классические полиномы. Здесь используется квадратура Гаусса , которая утверждает, что всегда можно найти веса и точки такие, что ${\displaystyle w_{i}}$ ${\displaystyle x_{i}}$

${\displaystyle \int _{a}^{b}w(x)p(x)dx=\sum _{i=0}^{N}w_{i}p(x_{i})}$

справедливо для любого многочлена степени или меньше. Обычно весовая функция и диапазоны выбираются для конкретной задачи и приводят к одной из различных форм квадратуры. Чтобы применить это к псевдоспектральному методу, мы выбираем базисные функции , которые являются полиномом степени со свойством ${\displaystyle p(x)}$ ${\displaystyle 2N+1}$ ${\displaystyle w(x)}$ ${\displaystyle a,b}$ ${\displaystyle \phi _{n}(x)={\sqrt {w(x)}}P_{n}(x)}$ ${\displaystyle P_{n}}$ ${\displaystyle n}$

${\displaystyle \int _{a}^{b}w(x)P_{n}(x)P_{m}(x)dx=\delta _{mn}.}$

В этих условиях образуют ортонормированный базис относительно скалярного произведения . Этот базис вместе с квадратурными точками затем можно использовать для псевдоспектрального метода. ${\displaystyle \phi _{n}}$ ${\displaystyle \langle f,g\rangle =\int _{a}^{b}f(x){\overline {g(x)}}dx}$

Для обсуждения ошибки обратите внимание, что если она хорошо представлена ​​базисными функциями и хорошо представлена ​​полиномом степени , их произведение можно разложить по первым базисным функциям, и псевдоспектральный метод даст точные результаты для такого числа базисные функции. ${\displaystyle f}$ ${\displaystyle N_{f}}$ ${\displaystyle V}$ ${\displaystyle N_{V}}$ ${\displaystyle N_{f}+N_{V}}$

Такие полиномы естественным образом встречаются в некоторых стандартных задачах. Например, квантовый гармонический осциллятор идеально разлагается в полиномах Эрмита, а полиномы Якоби можно использовать для определения связанных функций Лежандра, обычно появляющихся в задачах вращения.

Примечания

1. Орзаг, Стивен А. (сентябрь 1972 г.). «Сравнение псевдоспектрального и спектрального приближения». Исследования по прикладной математике . 51 (3): 253–259. дои : 10.1002/sapm1972513253.

Рекомендации

• Орзаг, Стивен А. (1969). «Численные методы моделирования турбулентности». Физика жидкостей . 12 (12): II-250. дои : 10.1063/1.1692445.
• Готлиб, Дэвид; Орзаг, Стивен А. (1989). Численный анализ спектральных методов: теория и приложения (5-е печатное изд.). Филадельфия, Пенсильвания: Общество промышленной и прикладной математики. ISBN 978-0898710236.
• Хестхавен, Ян С.; Готлиб, Сигал ; Готлиб, Дэвид (2007). Спектральные методы для нестационарных задач (1-е изд.). Кембридж [ua]: Cambridge Univ. Нажимать. ISBN 9780521792110.
• Цзе Шен, Тао Тан и Ли-Лиан Ван (2011) «Спектральные методы: алгоритмы, анализ и приложения» (серия Спрингера по вычислительной математике, т. 41, Springer), ISBN 354071040X . 
• Трефетен, Ллойд Н. (2000). Спектральные методы в MATLAB (3-е изд.). Филадельфия, Пенсильвания: СИАМ. ISBN 978-0-89871-465-4.
• Форнберг, Бенгт (1996). Практическое руководство по псевдоспектральным методам . Кембридж: Издательство Кембриджского университета. ISBN 9780511626357.
• Бойд, Джон П. (2001). Спектральные методы Чебышева и Фурье (2-е изд., перераб. изд.). Минеола, Нью-Йорк: Dover Publications. ISBN 978-0486411835.
• Фунаро, Даниэле (1992). Полиномиальная аппроксимация дифференциальных уравнений. Берлин: Springer-Verlag. ISBN 978-3-540-46783-0.
• де Фрутос, Хавьер; Ново, Юлия (январь 2000 г.). «Метод спектрального элемента для уравнений Навье-Стокса с повышенной точностью». SIAM Journal по численному анализу . 38 (3): 799–819. дои : 10.1137/S0036142999351984.
• Клаудио, Кануто; М. Юсуф, Хуссаини; Альфио, Квартерони ; Томас А., Занг (2006). Основы спектральных методов в отдельных областях . Берлин: Springer-Verlag. ISBN 978-3-540-30726-6.
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 20.7. Спектральные методы». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN 978-0-521-88068-8.