View source for Trigonometric pseudo-spectral methods

Trigonometric pseudo-spectral methods, and spectral methods in general, are methods for solving differential and integral equations using trigonometric functions as the basis.

Suppose the boundary value problem <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302101.png" /> is to be solved for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302102.png" /> on the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302103.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302104.png" /> is a [[Differential operator|differential operator]] in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302105.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302106.png" /> is some given smooth function (cf. also [[Boundary value problem, ordinary differential equations|Boundary value problem, ordinary differential equations]]). Also, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302107.png" /> must satisfy given boundary conditions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302108.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t1302109.png" />.

As in most numerical methods, an approximate solution, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021010.png" />, is sought which is the sum of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021011.png" /> basis functions, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021012.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021013.png" />, in the form <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021014.png" />, where the coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021015.png" /> are the finite set of unknowns for the approximate solution. A  "residual equation" , formed by plugging the approximate solution into the differential equation and subtracting the right-hand side, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021016.png" />, is then minimized over the interval to find the coefficients. The difference between methods boils down to the choice of basis and how <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021017.png" /> is minimized. The basis functions should be easy to compute, be complete or represent the class of desired functions in a highly accurate manner, and be orthogonal (cf. also [[Complete system of functions|Complete system of functions]]; [[Orthogonal system|Orthogonal system]]). In spectral methods, [[Trigonometric functions|trigonometric functions]] and their relatives as well as other [[Orthogonal polynomials|orthogonal polynomials]] are used.

If the basis functions are trigonometric functions such as sines or cosines, the method is said to be a Fourier spectral method. If, instead, [[Chebyshev polynomials|Chebyshev polynomials]] are used, the method is a Chebyshev spectral method.

The method of mean weighted residuals is used to minimize <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021018.png" /> and find the unknowns coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021019.png" />. An inner product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021020.png" /> and weight function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021021.png" /> are defined, as well as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021022.png" /> test functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021023.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021024.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021026.png" />. This yields <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021027.png" /> equations for the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021028.png" /> unknowns. Pseudo-spectral methods, including Fourier pseudo-spectral and Chebyshev pseudo-spectral methods, have Dirac delta-functions (cf. also [[Dirac distribution|Dirac distribution]]) as their test functions: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021029.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021030.png" /> are interpolation or collocation points. The residual equation becomes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021031.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021032.png" />.

The [[Galerkin method|Galerkin method]] uses the basis functions as the test functions. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021033.png" /> is linear, the following matrix equation can be formed: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021034.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021036.png" />. An alternative Galerkin formulation can be found by transforming the residual equation into spectral space <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021037.png" /> and setting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021038.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021039.png" />. In using Gauss–Jacobi integration to evaluate the inner products of the Galerkin method, the integrands are interpolated at the zeros of the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021040.png" />st basis function. By using the same set of points as collocation points for a pseudo-spectral method, the two methods are made equivalent. Problems can be cast in either grid-point or spectral coefficient representation. For trigonometric bases, this result allows the complexity of computation to be reduced in many problems through the use of fast transforms.

A main difference between spectral and other methods, such as finite difference or finite element methods, is that in the latter the domain is divided into smaller subdomains in which local basis functions of low order are used. With the basis functions frozen, more accuracy is gained by decreasing the size of the subdomains. In spectral methods, the domain is not subdivided, but global basis functions of high order are used. Accuracy is gained by increasing the number and order of the basis functions.

The lower-order methods produce algebraic systems which can be represented as sparse matrices. Spectral methods usually produce full matrices. The solution then involves finding the inverse. Through the use of orthogonality and fast transforms, full matrix inversion can usually be accomplished with a complexity similar to the sparse matrices.

Boundary conditions are handled in a reasonably straightforward manner. Sometimes the boundary conditions are satisfied automatically, such as with periodicity and a Fourier method. With other types of conditions, an extra equation may be added to the system to satisfy it, or the basis functions may be modified to automatically satisfy the conditions.

The attractiveness of spectral methods is that they have a greater than algebraic convergence rate for smooth solutions. A simple finite difference approximation has a convergence <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021041.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021042.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021043.png" /> is an integer; double the number of points in the interval and the error goes down by a factor <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021044.png" />. The convergence rate of spectral methods is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021045.png" />, sometimes called exponential, infinite or spectral, stemming from the fact that convergence of a trigonometric series is geometric. If the solution is not smooth, however, spectral methods will have an algebraic convergence linked to the continuity of the solution.

Rapid convergence allows fewer unknowns to be used, but more computational processing per unknown. Hence spectral methods are particularly attractive for problem/computer matches in which memory and not computing power is the critical factor.

Multi-dimensional problems are handled by tensor-product basis functions, which are basis functions that are products of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021046.png" />-dimensional basis functions. Other [[Orthogonal polynomials|orthogonal polynomials]] can be used in pseudo-spectral methods, such as Legendre and Hermite and spherical harmonics for spherical geometries.

A disadvantage of spectral methods is that only relatively simple domains and boundaries can be handled. Spectral element methods, a combination of spectral and finite element methods, have in many cases overcome this difficulty. Another difficulty is that spectral methods are, in general, more complicated to code and require more analysis to be done prior to coding than simpler methods.

Aliasing is a phenomenon in which modes of degree higher than in the expansion are interpreted as modes that are within the range of the expansion. This occurs in, say, a problem with quadratic non-linearity where twice the range is created. If the coefficients near the upper limit are sufficiently large in magnitude, there may be a significant error associated with aliased modes. For a Fourier pseudo-spectral method, the coefficient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021047.png" /> is interpreted as a coefficient <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021048.png" />. By zeroing the upper <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021049.png" /> of the coefficients, the quadratic nonlinearity will only fill a range from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021050.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021051.png" />. This will only produce aliasing errors for modes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021052.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/t/t130/t130210/t13021053.png" />, but these are to be zeroed anyway. This  "2 / 3"  rule removes errors for one-dimensional problems with quadratic non-linearity. It is debatable, however, whether in a  "well-resolved"  simulation there is need to address aliasing errors.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J.P. Boyd,   "Chebyshev and Fourier spectral methods" , Dover  (2000)  (pdf version: http://www-personal.engin.umich.edu/~jpboyd/book_spectral2000.html)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D. Gottlieb,   S.A. Orszag,   "Numerical analysis of spectral methods: Theory and applications" , SIAM  (1977)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  C. Canuto,   M.Y. Hussaini,   A. Quarteroni,   T.A. Zang,   "Spectral methods in fluid dynamics" , Springer  (1987)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  D. Gottlieb,   M.Y. Hussaini,   S.A. Orszag,   "Theory and application of spectral methods"  R.G. Voigt (ed.)  D. Gottlieb (ed.)  M.Y. Hussaini (ed.) , ''Spectral Methods for Partial Differential Equations'' , SIAM  (1984)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  B. Fornberg,   "A practical guide to pseudospectral methods" , ''Cambridge Monographs Appl. Comput. Math.'' , '''1''' , Cambridge Univ. Press  (1996)</TD></TR></table>