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

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

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

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

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

прояснить

]} .

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

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

Линейный пример

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

\left({\frac {\partial ^{2}}{\partial x^{2}}}+{\frac {\partial ^{2}}{\partial y^{2}}}\right)f(x,y)=g(x,y)

для всех x,y

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

Если мы запишем f и g в виде рядов Фурье

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

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

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

\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 . Таким образом, мы можем свободно выбрать a _{0

,

0} . Это соответствует выбору константы интегрирования.

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

Алгоритм

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

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

\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.

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

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

и

{\mathcal {V}}^{N}:={\text{ span}}\left\{e^{ikx}:k\in -N/2,\dots ,N/2-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 {\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.

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

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

Собираем три члена для каждого $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\{-N/2,\dots ,N/2-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\{-N/2,\dots ,N/2-1\right\},\forall t>0.

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

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

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

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

См. также

Примечания

, с. 285.

Литература

Claudio Canuto, M. Yousuff Hussaini, Alfio Quarteroni, Thomas A. Zang. . — Springer, 2007. — (Scientific Computation). — ISBN 978-3-540-30727-3 .
Bengt Fornberg. A Practical Guide to Pseudospectral Methods. — Cambridge, UK: Cambridge University Press, 1996. — (Cambridge monographs on applied and computational mathematics). — ISBN 0-521-49582-2 .
John P. Boyd. . — Mineola, New York: Dover Publications, Inc., 2000.
Canuto C., Hussaini M. Y., Quarteroni A., Zang T.A. Spectral Methods. Fundamentals in Single Domains. — Berlin Heidelberg: Springer-Verlag, 2006. — (Scientific Computation). — ISBN 3-540-30725-7 .
Javier de Frutos, Julia Novo. // Applied Numerical Mathematics. — 2000. — Т. 33 , вып. 1 . — С. 217-223 . — doi : .
Daniele Funaro. . — Heidelberg: Springer-Verlag, 1992. — Т. 8. — (Lecture Notes in Physics). — ISBN 3-540-55230-8 .
D. Gottlieb, S. Orzag. Numerical Analysis of Spectral Methods: Theory and Applications. — Philadelphia, PA: SIAM, 1977.
J. Hesthaven, S. Gottlieb, D. Gottlieb. Spectral methods for time-dependent problems. — Cambridge, UK: Cambridge University Press, 2007. — (Cambridge monographs on applied and computational mathematics). — ISBN 0-521-79211-8 .
Steven A. Orszag. Numerical Methods for the Simulation of Turbulence // Phys. Fluids Supp. II. — 1969. — Вып. 12 . — С. 250-257 .
Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. // Numerical Recipes: The Art of Scientific Computing. — 3rd. — New York: Cambridge University Press, 2007. — ISBN 978-0-521-88068-8 .
Lloyd N. Trefethen. Spectral Methods in MATLAB. — Philadelphia, PA: SIAM, 2000.