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

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

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

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

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}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Квадратура

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

\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

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

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

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

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

Умножение

Умножение с функцией $V(x)$ затем выполняется в каждой точке сетки,

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

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

{\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})}}

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

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

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

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

Метод Фурье

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

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

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

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

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

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

Полиномы

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

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

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

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

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

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

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

Примечания

^ Орзаг, Стивен А. (сентябрь 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 .

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

[1]