Chapter 1
Preliminaries
Contents
1.1 Some basic ideas of spectral methods 2
1.2 Orthogonal polynomials 6
1.3 Chebyshev and Legendre polynomials 15
1.4 Jacobi polynomials and generalized Jacobi polynomials 23
1.5 Fast Fourier transform 27
1.6 Several popular time discretization methods 38
1.7 Iterative methods and preconditioning 48
1.8 Error estimates of polynomial approximations 61
In this chapter， we present some preliminary materials which will be used throughout the book. The first section set the stage for the introduction of spectral methods. In Sections 1.2—1.4， we present some basic properties of orthogonal polynomials， which play an essential role in spectral methods， and introduce the notion of generalized Jacobi polynomials. Since much of the success and popularity of spectral methods can be attributed to the invention of Fast Fourier Transform (FFT)， an algorithmic description of the FFT is presented in Section 1.5. In the next two sections， we collect some popular time discretization schemes and iterative schemes which will be frequently used in the book. In the last section， we present a concise error analysis for several projection operators which serves as the basic ingredients for the error analysis of spectral methods.
1.1 Some basic ideas of spectral methods
Comparison with the finite element method
Computational efficiency
Fourier spectral method
Phase error
Finite Difference (FD) methods approximate derivatives of a function by local arguments such as ， where his 3， small grid spacing)-these methods are typically designed to be exact for polynomials of low orders. This approach is very reasonable: since the derivative is a local property of a function，it makes little sense (and is costly) to invoke many function values far away from the point of interest.
In contrast， spectral methods are global. The traditional way to introduce them starts by approximating the function as a sum of very smooth basis functions:
where the are polynomials or trigonometric functions. In practice， there are many feasible choices of the basis functions， such as:
In this section， we will describe some basic ideas of spectral methods. For ease of exposition， we consider the Fourier spectral method (i.e. the basis functions are chosen as elkx). We begin with the periodic heat equation， starting at time 0 from：
(1.1.1)
with a periodic boundary condition. Since the exact solution u is periodic， it can be written as an infinite Fourier series. The approximate solution UN can be expressed as a finite series. It is
where each afe(t) is to be determined.
Comparison with the finite element method
We may compare the spectral method (before actually describing it) to the finite element method. One difference is this: the trial functions 丁k in the finite element method are usually 1 at the mesh-point， Xk = kh with， and 0 at the other mesh-points， whereas elkx is nonzero everywhere. That is not such an important distinction. We could produce from the exponentials an interpolating function like Tfe， which is zero at all mesh-points except at:
(1.1.2)
(1.1.3)
Of course it is not a piecewise polynomial; that distinction is genuine. A consequence of this difference is the following:
Each function spreads over the whole solution interval， whereask is zero in all elements not containing The stiffness matrix is sparse for the finite element method; in the spectral method it is full.
The computational efficiency
Since the matrix associated with the spectral method is full， the spectral method seems more time-consuming than finite differences or finite elements. In fact， the spectral method had not been used widely for a long time. The main reason is the expensive cost in computational time. However， the discovery of the Fast Fourier Transform (FFT) by Cooley and Tukey[33] solves this problem. We will describe the Cooley-Tukey algorithm in Chapter 5. The main idea is the following.
Then for any N-dimensional vector， the usual N2 operations in computing are reduced to N log2 N. The significant improvement can be seen from the following table:
The Fourier spectral method
Unlike finite differences or finite elements， which replace the right-hand side by differences at nodes，the spectral method uses exactly. In the spectral method， there is no Ax. The derivatives with respect to space variables are computed explicitly and correctly.
The Fourier approximation uN is a combination of oscillations elkx up to frequency and we simply differentiate them; hence
Since frequencies are uncoupled， we have ， which gives
where the values afe(0) are determined by using the initial function:
It is an easy matter to show that
Therefore， the error goes to zero very rapidly as N becomes reasonably large. The convergence rate is determined by the integral term
展开
