Spectral methods are a class of techniques used in
applied mathematics
Applied mathematics is the application of mathematics, mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and Industrial sector, industry. Thus, applied mathematics is a ...
and
scientific computing
Computational science, also known as scientific computing, technical computing or scientific computation (SC), is a division of science, and more specifically the Computer Sciences, which uses advanced computing capabilities to understand and s ...
to numerically solve certain
differential equations. The idea is to write the solution of the differential equation as a sum of certain "
basis functions" (for example, as a
Fourier series
A Fourier series () is an Series expansion, expansion of a periodic function into a sum of trigonometric functions. The Fourier series is an example of a trigonometric series. By expressing a function as a sum of sines and cosines, many problems ...
which is a sum of
sinusoids) 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
Finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat tran ...
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
In mathematics, the support of a real-valued function f is the subset of the function domain of elements that are not mapped to zero. If the domain of f is a topological space, then the support of f is instead defined as the smallest closed ...
). 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. However, there are no known three-dimensional single-domain spectral
shock capturing results (shock waves are not smooth).
[pp 235, Spectral Methods](_blank)
evolution to complex geometries and applications to fluid dynamics, By Canuto, Hussaini, Quarteroni and Zang, Springer, 2007. 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) and
optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
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 method for ODEs. Eigenvalue problems for ODEs are similarly converted to matrix eigenvalue problems .
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
In corpus linguistics, a collocation is a series of words or terms that co-occur more often than would be expected by chance. In phraseology, a collocation is a type of compositional phraseme, meaning that it can be understood from the words t ...
or a
Galerkin or a
Tau
Tau (; uppercase Τ, lowercase τ or \boldsymbol\tau; ) is the nineteenth letter of the Greek alphabet, representing the voiceless alveolar plosive, voiceless dental or alveolar plosive . In the system of Greek numerals, it has a value of 300 ...
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.
Spectral methods can be computationally less expensive and easier to implement than finite element methods; they shine best when high accuracy is sought in simple domains with smooth solutions. However, because of their global nature, the matrices associated with step computation are dense and computational efficiency will quickly suffer when there are many degrees of freedom (with some exceptions, for example if matrix applications can be written as
Fourier transform
In mathematics, the Fourier transform (FT) is an integral transform that takes a function as input then outputs another function that describes the extent to which various frequencies are present in the original function. The output of the tr ...
s). For larger problems and nonsmooth solutions, finite elements will generally work better due to sparse matrices and better modelling of discontinuities and sharp bends.
Examples of spectral methods
A concrete, linear example
Here we presume an understanding of basic multivariate
calculus
Calculus is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithmetic operations.
Originally called infinitesimal calculus or "the ...
and
Fourier series
A Fourier series () is an Series expansion, expansion of a periodic function into a sum of trigonometric functions. The Fourier series is an example of a trigonometric series. By expressing a function as a sum of sines and cosines, many problems ...
. If
is a known, complex-valued function of two real variables, and g is periodic in x and y (that is,
) then we are interested in finding a function ''f''(''x'',''y'') so that
:
where the expression on the left denotes the second partial derivatives of ''f'' in ''x'' and ''y'', respectively. This is the
Poisson equation
Poisson's equation is an elliptic partial differential equation of broad utility in theoretical physics. For example, the solution to Poisson's equation is the potential field caused by a given electric charge or mass density distribution; with th ...
, and can be physically interpreted as some sort of heat conduction problem, or a problem in potential theory, among other possibilities.
If we write ''f'' and ''g'' in Fourier series:
:
and substitute into the differential equation, we obtain this equation:
:
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
which is an explicit formula for the Fourier coefficients ''a''
''j'',''k''.
With periodic boundary conditions, the
Poisson equation
Poisson's equation is an elliptic partial differential equation of broad utility in theoretical physics. For example, the solution to Poisson's equation is the potential field caused by a given electric charge or mass density distribution; with th ...
possesses a solution only if ''b''
0,0 = 0. Therefore, we can freely choose ''a''
0,0 which will be equal to the mean of the resolution. This corresponds to choosing the integration constant.
To turn this into an algorithm, only finitely many frequencies are solved for. This introduces an error which can be shown to be proportional to
, where
and
is the highest frequency treated.
Algorithm
# Compute the Fourier transform (''b
j,k'') of ''g''.
# Compute the Fourier transform (''a
j,k'') of ''f'' via the formula ().
# Compute ''f'' by taking an inverse Fourier transform of (''a
j,k'').
Since we're only interested in a finite window of frequencies (of size ''n'', say) this can be done using a
fast Fourier transform
A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). A Fourier transform converts a signal from its original domain (often time or space) to a representation in ...
algorithm. Therefore, globally the algorithm runs in
Nonlinear example
We wish to solve the forced, transient, nonlinear
Burgers' equation using a spectral approach.
Given
on the periodic domain
, find
such that
:
where ρ is the viscosity coefficient. In weak conservative form this becomes
:
where following
inner product
In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, ofte ...
notation.
Integrating by parts and using periodicity grants
:
To apply the Fourier–
Galerkin method, choose both
:
and
:
where
. This reduces the problem to finding
such that
:
Using the
orthogonality
In mathematics, orthogonality is the generalization of the geometric notion of '' perpendicularity''. Although many authors use the two terms ''perpendicular'' and ''orthogonal'' interchangeably, the term ''perpendicular'' is more specifically ...
relation
where
is the
Kronecker delta
In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:
\delta_ = \begin
0 &\text i \neq j, \\
1 &\ ...
, we simplify the above three terms for each
to see
:
Assemble the three terms for each
to obtain
:
Dividing through by
, we finally arrive at
:
With Fourier transformed initial conditions
and forcing
, 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
In mathematics (in particular, functional analysis), convolution is a operation (mathematics), mathematical operation on two function (mathematics), functions f and g that produces a third function f*g, as the integral of the product of the two ...
, and there are several transform-based techniques for evaluating it efficiently. See the references by Boyd and Canuto et al. for more details.
A relationship with the spectral element method
One can show that if
is infinitely differentiable, then the numerical algorithm using Fast Fourier Transforms will converge faster than any polynomial in the grid size h. That is, for any n>0, there is a
such that the error is less than
for all sufficiently small values of
. We say that the spectral method is of order
, for every n>0.
Because a
spectral element method is a
finite element method
Finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat tran ...
of very high order, there is a similarity in the convergence properties. However, whereas the spectral method is based on the eigendecomposition of the particular boundary value problem, the finite element method does not use that information and works for arbitrary
elliptic boundary value problems.
See also
*
Finite element method
Finite element method (FEM) is a popular method for numerically solving differential equations arising in engineering and mathematical modeling. Typical problem areas of interest include the traditional fields of structural analysis, heat tran ...
*
Gaussian grid
*
Pseudo-spectral method
*
Spectral element method
*
Galerkin method
*
Collocation method
References
* Bengt Fornberg (1996) ''A Practical Guide to Pseudospectral Methods.'' Cambridge University Press, Cambridge, UK
Chebyshev and Fourier Spectral Methodsby John P. Boyd.
* Canuto C.,
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)
A Spectral Element Method for the Navier–Stokes Equations with Improved Accuracy 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
* J. Hesthaven, S. Gottlieb and D. Gottlieb (2007) "Spectral methods for time-dependent problems", Cambridge UP, Cambridge, UK
* Steven A. Orszag (1969) ''Numerical Methods for the Simulation of Turbulence'', Phys. Fluids Supp. II, 12, 250–257
*
* Jie Shen, Tao Tang and Li-Lian Wang (2011) "Spectral Methods: Algorithms, Analysis and Applications" (Springer Series in Computational Mathematics, V. 41, Springer),
* 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.
{{DEFAULTSORT:Spectral Method
Numerical analysis
Numerical differential equations