Spectral method

From Wikipedia, the free encyclopedia

You have new messages (last change).

Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain partial differential equations, often involving the use of the Fast Fourier Transform. For well-behaved problems, spectral methods have excellent error properties: The more differentiable the solution is, the better the accuracy of the method.

Partial differential equations (PDEs) describe a wide array of physical processes such as heat conduction, fluid flow, and sound propagation. In many such equations, there are underlying "basic waves" that can be used to give efficient algorithms for computing solutions to these PDEs. In a typical case, spectral methods take advantage of this fact by writing the solution as its Fourier series, substituting this series into the PDE to get a system of ODEs in the time-dependent coefficients of the trigonometric terms in the series (written in complex exponential form), and using a time-stepping method to solve those ODEs.

The difference between the spectral method and the finite element method (FEM) is the type of function that is used to approximate the solution. For the FEM, piecewise linear functions (or piecewise polynomial functions) are used. In the spectral method, the solution is approximated using harmonics (see Fourier series). In the finite difference method, the derivatives occuring in the differential operator are replaced by finite differences.

In the finite element community, a method where the degree of the elements is very high or increases as the grid parameter h decreases to zero is sometimes called a spectral method. For a discussion of this method, see spectral element method.

Contents

[edit] A concrete example

Here we presume a basic understanding of basic multivariate calculus and Fourier series. If g(x,y) is a known, complex-valued function of two real variables, and g is periodic in x and y (that is, g(x,y)=g(x+2π,y)=g(x,y+2π)) then we are interested in finding a function f(x,y) so that

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

where the expression on the left denotes the second partial derivatives of f in x and y, respectively. This is Poisson equation, and can be physically interpreted as some sort of heat conduction problem.

If we write f and g in Fourier series:

f=\sum a_{j,k}e^{ijx+iky}
g=\sum b_{j,k}e^{ijx+iky}

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

\sum -a_{j,k}(j^2+k^2)e^{ijx+iky}=\sum b_{j,k}e^{ijx+iky}

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

(*) a_{j,k}=-\frac{b_{j,k}}{j^2+k^2}

which is an explicit formula for the Fourier coefficients aj,k.

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 hn, where h = 1 / n and n is the highest frequency treated.

[edit] Algorithm

  1. Compute the Fourier transform (bj,k) of g.
  2. Compute the Fourier transform (aj,k) of f via the formula (*) and the Fourier transform of g.
  3. Compute f by taking an inverse Fourier transform of (aj,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 algorithm. Therefore, globally the algorithm runs in time O(nlogn).

[edit] A relationship with the spectral element method

One can show that if g 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 C<\infty such that the error is less than Chn for all sufficiently small values of h. We say that the spectral method is of order n, for every n>0.

Because a spectral element method is a finite element method 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 spectral element method does not use that information and works for abitrary elliptic boundary value problems.

[edit] See also

[edit] References

Retrieved from "http://en.wikipedia.org../../../s/p/e/Spectral_method.html"
In other languages