next up previous contents
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)
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 up previous contents
Next: Fourier interpolant revisited on Up: The Periodic Problem -- Previous: Aliasing and spectral accuracy

Eitan Tadmor
Thu Jan 22 19:07:34 PST 1998