The Azimuth Project
Spectral methods for PDEs

Contents

Idea

Spectral methods are discrete approximation schemes for partial differential equations. They are important for the solution of the Navier-Stokes equations in meteorology and in climate models.

The basic idea of spectral methods is to choose a finite set of functions and calculate the optimal approximation of the exact solution by these functions. These basis functions are often part of an orthonormal basis of a Hilbert space, and more specifically trigonometric functions, hence the name “spectral” methods. In contrast to finite elements, spectral methods usually refer to an approximation with basis functions that don’t have a restricted support, but are “globally nontrivial”.

For parabolic equations with a notion of time, spectral methods are usually used to discretize the spatial dimensions only, not the time dimension.

Details

Introduction for Pure Functional Analysts

The following paragraph is meant as an introduction to the method for pure mathematicians with a background in functional analysis.

For illustrative purposes we will make some simplifying assumptions. Let’s assume that we have an infinite topological vector space T, its topological dual T *T^* and a (closable densely defined differential) operator

A:DTT A: D \subset T \to T

with a unique solution of the equation

A(f)=0 A(f) = 0

We omit initial and boundary conditions for the moment. In order to calculate an approximation to the exact solution ff, we need to turn the infinite dimensional problem to a finite dimensional one.

The basic idea of spectral methods is to choose a finite dimensional subspace T gT_g of T spanned by a given set of functions {g 1,...,g n}\{g_1, ..., g_n \}, which are called in this context trial, expansion or approximation functions. We are looking for the projection of the exact solution ff to the subspace T gT_g, but since we don’t know ff, we cannot calculate the exact expansion

f= k=1 nα kg k f = \sum_{k = 1}^n \alpha_k g_k

But we can test the goodness of a given approximation f α:= k=1 nα kg kf_{\alpha} := \sum_{k = 1}^n \alpha_k g_k by testing M(f α)M(f_{\alpha}) for “smallness”. This function is sometimes called the residual function.

Different spectral methods differ mainly in their interpretation of “smallness” and their strategy to determine the best approximation.

One particular “smallness” test in spectral methods is done via a choice of a finite dimensional subspace T h *T^*_h of the dual space T *T^* spanned by the elements {h 1,...,h n}\{h_1, ..., h_n \}, we then demand that

M(f α),h i=0 \langle \; M(f_{\alpha}), \; h_i \; \rangle = 0

should hold for all h iT h *h_i \in T^*_h. The “functions” h ih_i are called test or weight functions. Due to the choice of finite dimensional subspaces the problem is reduced to a finite set of (linear) algebraic equations.

Approximation with Orthonormal Functions in Hilbert Space

Often the function space is a Hilbert space and the approximation functions elements of an orthonormal base. This is the case for example if one uses Fourier series. In some cases it is possible to show that the expansion coefficients of, for example, a smooth function in an orthonormal basis decay exponentially fast. This is sometimes called exponential or spectral accuracy in the literature.

Difference of Spectral and Finite Element Methods

The only difference of spectral and finite element methods is that spectral methods use approximation functions that are not local, while finite elements uses approximation functions with support restricted to certain simple subsets of the domain of the equation one would like to solve.

As a consequence, finite elements can only handle bounded domains. It is possible to combine both approaches and get, for example, the hp-FEM.

Choice of Basis Functions

Basis functions should be easy to evaluate, both numerically or with pen-and-paper if a step of the overall calculation can and should be performed by hand.

Basis functions should be complete in the sense that the approximation gets “arbitrarily good” with increasing number of approximation functions.

To make the latter precise, one needs a measure of closeness which will usually be a norm of a Banach space of functions \| \cdot \|. Then we would like to have a relation like

lim nuu n=0 \lim_{n \to \infty} \| u - u_n \| = 0

where nn is the number of approximation functions (or, to be more precise, the dimension of the subspace of the topological vector space spanned by the approximation functions).

For practical problems, it would be nice to know that the approximation converges with a certain rate, that it is exponential, for example:

uu n=O(exp(n)) \| u - u_n \| = O(\exp(-n))

With regard to boundary conditions, there are two possibilites:

The most commonly used approximation functions are

Examples

One Dimensional Boundary Problem

We will have a look at an ordinary differential equation on the interval [1,1][-1, 1] with boundary conditions:

u xx(x 6+3x 2)u=0 u_{xx} - (x^6 + 3 x^2) u = 0

where we have written u xxu_{xx} for d 2udx 2\frac{d^2 u}{d x^2}.

The boundary conditions are:

u(1)=u(1)=0 u(-1) = u(1) = 0

This problem has an exact solution which is:

u(x)=exp(14(x 41)) u(x) = \exp{(\frac{1}{4} (x^4 - 1))}

The first step to calculate an approximate solution using the spectral method is to choose the approximation functions, in this example we choose the polynomials 1,x,x 21, x, x^2. With this choice, the approximation functions themselves don’t satisfy the boundary conditions, therefore we make another choice and choose as approximation

u a:=1+(1x 2)(a 0+a 1x+a 2x 2) u_a := 1 + (1 - x^2) (a_0 + a_1 x + a_2 x^2)

This way, the boundary conditions are satisfied independently of the approximation coefficients a 0,a 1,a 2a_0, a_1, a_2.

The residual function is of course

R(a 0,a 1,a 3;x)=d 2u adx 2(x 6+3x 2)u a R(a_0, a_1, a_3; x) = \frac{d^2 u_a}{d x^2} - (x^6 + 3 x^2) u_a

We choose as test functions three Dirac delta functions, which is equivalent to choosing three points (x 0,x 1,x 2)(x_0, x_1, x_2) such that the residual function vanishes at these points. This choice has its own name, it is called the collocation or pseudospectral method.

Choosing as collocation points the tuple (12,0,12)(- \frac{1}{2}, 0, \frac{1}{2}) leads to a system of three linear equations for the approximation coefficients, with the solution:

a 0=a 2=7843807anda 1=0 a_0 = a_2 = - \frac{784}{3807} \; \text{and} \; a_1 = 0

The resulting approximation may seem to be crude at first sight, but the following graphic shows that it is actually quite close to the exact solution already:

comparing exact solution and approximation for example

The choice of the approximation functions and of the test functions are completely arbitrary, so the follow-up question to this example is if there is any way to determine what a good choice would be.

We could have known that a 2a_2 would turn out to be zero, for example, because the problem is symmetric with respect to reflection along the y-axis. Without using this knowledge, we spent some computational effort to determine a 2a_2, which did not help in making the approximation any better.

Burgers’ Equation

More examples can be found on the page Burgers' equation.

References

A two volume introduction to the theory of the method, starting with the basics:

… and continuing with the explanation of how complex boundary conditions should be handled, with applications to CFD:

Based on the preceding introduction to the theory, the following volume concentrated on the task of implementing concrete algorithms:

An elementary introduction with special emphasis on spherical coordinates (important for GCMs):

For an application of spectral methods to global weather and climate models see: