3.10 An Introduction to Spectral Methods
61
as can be proven by using the well-known formula for the summation of
geometric series. The set of values of q is somewhat arbitrary; changing the
index from q to q f lN, where 1 is an integer, produces no change in the value
Of e%ik q X . at the grid points. This property is known as aliasing; aliasing is a
common and important source of error in numerical solutions of non-linear
differential equations, including ones that do not use spectral methods. We
shall say more about it in Chap. 9.
What makes these series useful is that Eq. (3.54) can be used to interpolate f (x). We simply replace the discrete variable xi by the continuous
variable x; f (x) is then defined for all x, not just the grid points. Now the
choice of the range of q becomes very important. Different sets of q produce
different interpolants; the best choice is the set which gives the smoothest
interpolant, which is the one used in Eq. (3.54). (The set -N/2 + 1,. . . , N/2
is as good a choice as the one selected.) Having defined the interpolant, we
can differentiate it to produce a Fourier series for the derivative:
N/2-1
- df = x ik, f(k,) eikqx ,
dx q=-N/2
which shows that the Fourier coefficient of d f /dx is ik, f (k,). This provides
a method of evaluating the derivative:
Given f (xi), use Eq. (3.55) to compute its Fourier coefficients f(k,);
Compute the Fourier coefficients of g =d f /dx;
tj(kq) =ikqf(kq);
Evaluate the series (3.56) to obtain g =d f /dx at the grid points.
Several points need to be noted.
The method is easily generalized to higher derivatives; for example, the
Fourier coefficient of d2 f /dx2 is -kif(kq).
a The error in the computed derivative decreases exponentially with N when
the number of grid points N is large if f(x) is periodic in x. This makes
spectral methods much more accurate than finite difference methods for
large N ; however, for small N , this may not be the case. The definition of
'large' depends on the function.
a The cost of computing the Fourier coefficients using Eq. (3.55) and/or the
inverse using Eq. (3.54), if done in the most obvious manner, scales as N2.
This would be prohibitively expensive; the method is made practical by
the existence of a fast method of computing Fourier transform (FFT) for
which the cost is proportional to N log2N.
To obtain the advantages of this particular spectral method, the function
must be periodic and the grid points uniformly spaced. These conditions
61
as can be proven by using the well-known formula for the summation of
geometric series. The set of values of q is somewhat arbitrary; changing the
index from q to q f lN, where 1 is an integer, produces no change in the value
Of e%ik q X . at the grid points. This property is known as aliasing; aliasing is a
common and important source of error in numerical solutions of non-linear
differential equations, including ones that do not use spectral methods. We
shall say more about it in Chap. 9.
What makes these series useful is that Eq. (3.54) can be used to interpolate f (x). We simply replace the discrete variable xi by the continuous
variable x; f (x) is then defined for all x, not just the grid points. Now the
choice of the range of q becomes very important. Different sets of q produce
different interpolants; the best choice is the set which gives the smoothest
interpolant, which is the one used in Eq. (3.54). (The set -N/2 + 1,. . . , N/2
is as good a choice as the one selected.) Having defined the interpolant, we
can differentiate it to produce a Fourier series for the derivative:
N/2-1
- df = x ik, f(k,) eikqx ,
dx q=-N/2
which shows that the Fourier coefficient of d f /dx is ik, f (k,). This provides
a method of evaluating the derivative:
Given f (xi), use Eq. (3.55) to compute its Fourier coefficients f(k,);
Compute the Fourier coefficients of g =d f /dx;
tj(kq) =ikqf(kq);
Evaluate the series (3.56) to obtain g =d f /dx at the grid points.
Several points need to be noted.
The method is easily generalized to higher derivatives; for example, the
Fourier coefficient of d2 f /dx2 is -kif(kq).
a The error in the computed derivative decreases exponentially with N when
the number of grid points N is large if f(x) is periodic in x. This makes
spectral methods much more accurate than finite difference methods for
large N ; however, for small N , this may not be the case. The definition of
'large' depends on the function.
a The cost of computing the Fourier coefficients using Eq. (3.55) and/or the
inverse using Eq. (3.54), if done in the most obvious manner, scales as N2.
This would be prohibitively expensive; the method is made practical by
the existence of a fast method of computing Fourier transform (FFT) for
which the cost is proportional to N log2N.
To obtain the advantages of this particular spectral method, the function
must be periodic and the grid points uniformly spaced. These conditions