Spectral method: Difference between revisions

Revision as of 04:30, 17 January 2023

Latest revision as of 08:40, 9 July 2025

(24 intermediate revisions by 5 users not shown)

Line 1:

{{Short description|Class of methods used in numerical analysis and scientific computing to solve ODE/PDE}}

{{More footnotes|date=August 2013}}

'''Spectral methods''' are a class of techniques used in [[applied mathematics]] and [[scientific computing]] to numerically solve certain [[differential equation]]s. The idea is to write the solution of the differential equation as a sum of certain "[[basis function]]s" (for example, as a [[Fourier series]] which is a sum of [[Sine wave|sinusoid]]s) and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.

Spectral methods and [[finite -element method]]s are closely related and built on the same ideas; the main difference between them is that spectral methods use basis functions that are generally nonzero over the whole ___domain, while finite element methods use basis functions that are nonzero only on small subdomains ([[compact support]]). Consequently, spectral methods connect variables ''globally'' while finite elements do so ''locally''. Partially for this reason, spectral methods have excellent error properties, with the so-called "exponential convergence" being the fastest possible, when the solution is [[Smooth function|smooth]]. However, there are no known three-dimensional single -___domain spectral [[shock capturing]] results (shock waves are not smooth).<ref name="CHQZ">[https://books.google.com/books?id=7COgEw5_EBQC pp 235, Spectral Methods]: evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007.</ref> In the finite -element community, a method where the degree of the elements is very high or increases as the grid parameter ''h'' increases is sometimes called a [[spectral -element method]].

Spectral methods can be used to solve [[differential equations]] (PDEs, ODEs, eigenvalue, etc) <ref>{{cite journal |last1=Muradova |first1=Aliki D. |title=The spectral method and numerical continuation algorithm for the von Kármán problem with postbuckling behaviour of solutions |journal=Adv Comput Math |year=2008 |volume=29 |issue=2 |pages=179–206, 2008 |doi=10.1007/s10444-007-9050-7|hdl=1885/56758 |s2cid=46564029 |hdl-access=free }}</ref> and [[optimization problem]]s. When applying spectral methods to time-dependent PDEs, the solution is typically written as a sum of basis functions with time-dependent coefficients; substituting this in the PDE yields a system of ODEs in the coefficients which can be solved using any [[numerical methods for ordinary differential equations|numerical method for ODEs]].<ref>{{cite journal |last1=Muradova |first1=Aliki D. |title=A time spectral method for solving the nonlinear dynamic equations of a rectangular elastic plate |journal=Journal of Engineering Mathematics |year=2015 |volume=92 |pages=83–101, 2015 |doi=10.1007/s10665-014-9752-z }}</ref> Eigenvalue problems for ODEs are similarly converted to matrix eigenvalue problems {{Citation needed|date=August 2013}}.

Spectral methods were developed in a long series of papers by [[Steven Orszag]] starting in 1969 including, but not limited to, Fourier series methods for periodic geometry problems, polynomial spectral methods for finite and unbounded geometry problems, pseudospectral methods for highly nonlinear problems, and spectral iteration methods for fast solution of steady-state problems. The implementation of the spectral method is normally accomplished either with [[collocation method|collocation]] or a [[Galerkin method|Galerkin]] or a [[Tau method|Tau]] approach . For very small problems, the spectral method is unique in that solutions may be written out symbolically, yielding a practical alternative to series solutions for differential equations.

Line 24 ⟶ 25:

If we write ''f'' and ''g'' in Fourier series:

:<math>f=:\sum a_begin{j,kalign}e^{i(jx+ky)}</math>

:<math>gf&=:\sum b_a_{j,k}e^{i(jx+ky)}</math>, \\[5mu]

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

\end{align}</math>

and substitute into the differential equation, we obtain this equation:

:<math>\sum -a_{j,k}(j^2+k^2)e^{i(jx+ky)}=\sum b_{j,k}e^{i(jx+ky)}.</math>

We have exchanged partial differentiation with an infinite sum, which is legitimate if we assume for instance that ''f'' has a continuous second derivative. By the uniqueness theorem for Fourier expansions, we must then equate the Fourier coefficients term by term, giving

Line 57 ⟶ 60:

:<math>\partial_{t} u + u \partial_{x} u = \rho \partial_{xx} u + f \quad \forall x\in\left[0,2\pi\right), \forall t>0</math>

where &rho; is the [[viscosity]] coefficient. In weak conservative form this becomes

:<math>\left\langle \partial_{t} u , v \right\rangle = \leftBigl\langle \partial_x \left(-\frac{1}{2}tfrac12 u^2 + \rho \partial_{x} u\right) , v \rightBigr\rangle + \left\langle f, v \right\rangle \quad \forall v\in \mathcal{V}, \forall t>0</math>

where following [[inner product space|inner product]] notation. [[integration by parts|Integrating by parts]] and using periodicity grants

:<math>\langle \partial_{t} u , v \rangle = \left\langle \frac{1}{2}tfrac12 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.</math>

To apply the Fourier–[[Galerkin method]], choose both

:<math>\mathcal{U}^N := \leftbiggl\{ u : u(x,t)=\sum_{k=-N/2}^{N/2-1} \hat{u}_{k}(t) e^{i k x}\rightbiggr\}</math>

and

:<math>\mathcal{V}^N :=\operatorname{span}\left\{ e^{i k x} : k\in -\tfrac12 N/2,\dots,N/2\tfrac12N - 1\right\}</math>

where <math>\hat{u}_k(t):=\frac{1}{2\pi}\langle u(x,t), e^{i k x} \rangle</math>. This reduces the problem to finding <math>u\in\mathcal{U}^N</math> such that

:<math>\langle \partial_{t} u , e^{i k x} \rangle = \left\langle \frac{1}{2}tfrac12 u^2 - \rho \partial_{x} u , \partial_x e^{i k x} \right\rangle + \left\langle f, e^{i k x} \right\rangle \quad \forall k\in \left\{ -N/2\tfrac12N,\dots,N/2\tfrac12N-1 \right\}, \forall t>0.</math>

Using the [[orthogonality]] relation <math>\langle e^{i l x}, e^{i k x} \rangle = 2 \pi \delta_{lk}</math> where <math>\delta_{lk}</math> is the [[Kronecker delta]], we simplify the above three terms for each <math>k</math> to see

:<math>

\begin{align}

\left\langle \partial_{t} u , e^{i k x}\right\rangle &= \leftbiggl\langle \partial_{t} \sum_{l} \hat{u}_{l} e^{i l x} , e^{i k x} \rightbiggr\rangle = \leftbiggl\langle \sum_{l} \partial_{t} \hat{u}_{l} e^{i l x} , e^{i k x} \rightbiggr\rangle = 2 \pi \partial_t \hat{u}_k,

\\

\left\langle f , e^{i k x} \right\rangle &= \leftbiggl\langle \sum_{l} \hat{f}_{l} e^{i l x} , e^{i k x}\rightbiggr\rangle= 2 \pi \hat{f}_k, \text{ and}

\\

\left\langle

\frac{1}{2}tfrac12 u^2 - \rho \partial_{x} u

,

\partial_x e^{i k x}

\right\rangle

&=

\leftbiggl\langle

\frac{1}{2}tfrac12

\leftBigl(\sum_{p} \hat{u}_p e^{i p x}\rightBigr)

\leftBigl(\sum_{q} \hat{u}_q e^{i q x}\rightBigr)

- \rho \partial_x \sum_{l} \hat{u}_l e^{i l x}

,

\partial_x e^{i k x}

\rightbiggr\rangle

\\

&=

\leftbiggl\langle

\frac{1}{2}tfrac12

\sum_{p} \sum_{q} \hat{u}_p \hat{u}_q e^{i \left(p+q\right) x}

,

i k e^{i k x}

\rightbiggr\rangle

-

\leftbiggl\langle

\rho i \sum_{l} l \hat{u}_l e^{i l x}

,

i k e^{i k x}

\rightbiggr\rangle

\\

&=

-\frac{tfrac12 i k}{2}

\leftbiggl\langle

\sum_{p} \sum_{q} \hat{u}_p \hat{u}_q e^{i \left(p+q\right) x}

,

e^{i k x}

\rightbiggr\rangle

- \rho k

\leftbiggl\langle

\sum_{l} l \hat{u}_l e^{i l x}

,

e^{i k x}

\rightbiggr\rangle

\\

&=

Line 130 ⟶ 133:

- 2\pi\rho{}k^2\hat{u}_k

+ 2 \pi \hat{f}_k

\quad k\in\left\{ -N/2\tfrac12N,\dots,N/2\tfrac12N-1 \right\}, \forall t>0.

</math>

Dividing through by <math>2\pi</math>, we finally arrive at

Line 139 ⟶ 142:

- \rho{}k^2\hat{u}_k

+ \hat{f}_k

\quad k\in\left\{ -N/2\tfrac12N,\dots,N/2\tfrac12N-1 \right\}, \forall t>0.

</math>

With Fourier transformed initial conditions <math>\hat{u}_{k}(0)</math> and forcing <math>\hat{f}_{k}(t)</math>, this coupled system of ordinary differential equations may be integrated in time (using, e.g., a [[Runge Kutta]] technique) to find a solution. The nonlinear term is a [[convolution]], and there are several transform-based techniques for evaluating it efficiently. See the references by Boyd and Canuto et al. for more details.

Line 162 ⟶ 165:

* [http://www-personal.umich.edu/~jpboyd/BOOK_Spectral2000.html Chebyshev and Fourier Spectral Methods] by John P. Boyd.

* Canuto C., [[M. Yousuff Hussaini|Hussaini M. Y.]], Quarteroni A., and Zang T.A. (2006) ''Spectral Methods. Fundamentals in Single Domains.'' Springer-Verlag, Berlin Heidelberg

* Javier de Frutos, Julia Novo (2000): [httphttps://epubs.siam.org/sam-bindoi/dbq/article10.1137/35198S0036142999351984 A Spectral Element Method for the Navier–Stokes Equations with Improved Accuracy]

* [http://cdm.unimo.it/home/matematica/funaro.daniele/bube.htm Polynomial Approximation of Differential Equations], by Daniele Funaro, Lecture Notes in Physics, Volume 8, Springer-Verlag, Heidelberg 1992

* D. Gottlieb and S. Orzag (1977) "Numerical Analysis of Spectral Methods : Theory and Applications", SIAM, Philadelphia, PA

Line 170 ⟶ 173:

* Jie Shen, Tao Tang and Li-Lian Wang (2011) "Spectral Methods: Algorithms, Analysis and Applications" (Springer Series in Computational Mathematics, V. 41, Springer), {{ISBN|354071040X}}

* Lloyd N. Trefethen (2000) ''Spectral Methods in MATLAB.'' SIAM, Philadelphia, PA

* Muradova A. D. (2008) "The spectral method and numerical continuation algorithm for the von Kármán problem with postbuckling behaviour of solutions", Advances in Computational Mathematics, 29, pp. 179–206, https://doi.org/10.1007/s10444-007-9050-7.

* Muradova A. D. (2015) "A time spectral method for solving the nonlinear dynamic equations of a rectangular elastic plate", Journal of Engineering Mathematics, 92, pp. 83–101, https://doi.org/10.1007/s10665-014-9752-z.

{{Numerical PDE}}