    Next: Fourier interpolant revisited on Up: The Periodic Problem -- Previous: Aliasing and spectral accuracy

Fourier differentiation matrix

We observe that is nothing but the trigonometric interpolant of w(x) at the equidistant points :

This shows that is in fact a dospectral projection, which in the usual sin-cos formulation reads

Thus, trigonometric interpolation provides us with an excellent vehicle to perform approximate discretizations with high (= spectral) accuracy, of differential and integral operations. These can be easily carried out in Fourier space where the exponentials serve as eigenfunction. For example, suppose we are given the equidistant gridvalues, , of an underlying smooth (i.e., also periodic!) function . A second-order accurate discrete derivative is provided by center differencing

Note that the error in this case is, , no matter how smooth w(x) is. Similarly, fourth order approximation is given (via Richardson's extrapolation procedure) by

The pseudospectral approximation gives us an alternative procedure: construct the trigonometric interpolant

Differentiation in Fourier space amounts to simple multiplication, since the exponentials are eigenfunctions of differentiation,

and we approximate

Indeed, by our estimates we have for

which verifies the asserted spectral accuracy. Similar estimates are valid for higher derivatives. To carry out the above recipe, one proceeds as follows: starting with the vector of gridvalues, , one computes the discrete Fourier coefficients

or, in matrix formulation

then we differentiate

or in matrix formulation

and finally, we return to the ``physical'' space, calculating

or in matrix formulation

The summary of these three steps is

where represents the discrete differentiation matrix, and similarly for higher derivatives.

: Since (interpolation!) we apply . How does this compare with finite differences and finite-element type differencing?

In periodic second-order differencing we have

fourth order differencing yields

In both cases the second and fourth order differencing takes place in the physical space. The corresponding differencing matrices have finite bandwidth and this reflects the fact that these differencing methods are local. Similarly, finite-element differencing,

corresponds to a differencing matrix

We still operate in physical space with operations (tridiagonal solver) and locality is reflected by a very rapid (exponential decay) away from main diagonal. Nevertheless, if we increase the periodic center differences stencil to its limit then we end up with global pseudospectral differentiation

recall the Dirichlet kernel (2.1.33)

and its derivative,

so that

Hence (app_ps.31), (app_ps.34) give us

In this case is a full matrix whose multiplication requires operations; however, we can multiply efficiently using its spectral representation from (app_ps.30),

Multiplication by F and can be carried out by FFT which requires only operating and hence the total cost here is almost as good as standard ``local'' methods, and in addition we maintain spectral accuracy.

We have seen how the pseudospectral differentiation works in the physical space. Next, let's examine how the standard finite-difference/element differencing methods operate in the Fourier space. Again, the essential ingredient is that exponentials play the role of eigenfunctions for this type of differencing. To see this, consider for example the usual second order centered differencing, , for which we have

The term is called the ``symbol'' of center differencing. By superposition we obtain for arbitrary grid function (represented here by its trigonometric interpolant)

that

It is second-order accurate differencing since its symbol satisfies

Note that for the low modes we have error (the less significant high modes are differenced with error but their amplitudes tend rapidly to zero). Thus we have

and this estimate should be compared with the usual

The main difference between these two estimates lies in the fact that the last estimate is local, i.e., we need the smoothness of w(x) only in the neighborhood of , and not in the whole interval, . The analogue localization in the Fourier space will be dealt later.

Similarly, we have for fourth order differencing the symbol

In general, we encounter difference operators whose matrix representation, D,

is periodic and antisymmetric (here ),

Matrices satisfying the periodicity property are called circulant, and they all can be diagonalized by the unitary Fourier matrix

Indeed, with we have

and using the antisymmetry we end up with symbols

As an example, we obtain for the (linear) finite-element differencing system

This corresponds to differentiation of the forth-order Padé expansion.

In general, the symbols are trigonometric polynomials or rational functions in the ``dual variable,'' kh, which has ``exact'' representation on the grid in terms of translation operator (polynomials or rational functions), and accuracy is determined by the ability to approximate the exact differentiation symbol, ik, for , consult Figure 2.2.

Figure 2.2: The symbols of center differencing    Next: Fourier interpolant revisited on Up: The Periodic Problem -- Previous: Aliasing and spectral accuracy