Chebyshev & Fourier Spectral Methods

1. Introduction.- 1. Series Expansions.- 2. Choice of Basis Functions.- 3. Comparison with Finite Element Methods.- 4. Boundary Conditions.- 5. The Two Kingdoms: Non-Interpolating and Pseudospectral Families of Methods.- 6. Accuracy and Efficiency.- 7. Examples.- 2. Convergence Theory.- 1. Introduction.- 2. Fourier Series.- 3. Orders of Convergence.- 4. An Upper Bound on the Truncation Error.- 5. Integration-By-Parts-Bound on Fourier Coefficients.- 6. Asymptotic Calculation of Coefficients: Power Series.- 7. Asymptotic Calculation of Coefficients: Fourier Series.- 8. Model Functions for Fourier Series.- 9. Convergence Theory for Chebyshev Polynomials.- 10. Algebraically-Converging Chebyshev Series: Functions with Singularities at the Endpoints.- 11. Summary.- 3. Galerkin's Method & Inner Products.- 1. Mean Weighted Residual Methods.- 2. General Properties of Basis Functions: Completeness.- 3. Properties of Basis Functions: Inner Product & Orthogonality.- 4. Galerkin's Method.- 5. Galerkin's Method: Case Studies.- 6. Galerkin's Method & Separation of Variables.- 7. Galerkin's in Quantum Theory: Heisenberg Matrix Mechanics.- 8. Galerkin's Method Today.- 4. Interpolation, Collocation & All That.- 1. Introduction.- 2. Polynomial Interpolation.- 3. Gaussian Integration & Pseudospectral Grids.- 4. Pseudospectral: Galerkin's Method via Gaussian Quadrature.- 5. Pseudospectral Errors for Trigonometric & Chebyshev Polynomials.- 6. The Envelope of the Interpolation Error.- 5. Cardinal Functions.- 1. Introduction.- 2. Whittaker Cardinal or "Sinc" Functions.- 3. Cardinal Functions for Trigonometric Interpolation.- 4. Cardinal Functions for Orthogonal Polynomials.- 5. Transformations and Interpolation.- 6. Pseudospectral Methods for Boundary Value Problems.- 1. Introduction.- 2. Choice of Basis Set.- 3. Boundary Conditions: Behavioral & Numerical.- 4. "Boundary-Bordering" for "Numerical" Boundary Conditions.- 5. "Basis Recombination" & "Homogenization of Boundary Conditions".- 6. The Cardinal Function Basis.- 7. The Interpolation Grid.- 8. Computing the Basis Functions & Their Derivatives.- 9. Special Problems of Higher Dimensions: Indexing.- 10. Special Problems of Higher Dimensions: Boundary Conditions, Singular Matrices & Over-Determined.- 11. Special Problems in Higher Dimensions: Corner Singularities.- 12. Matrix Methods.- 13. Checking.- 14. Summary.- Table 6-1. A Sample FORTRAN Program for Solving a Two-Point Boundary Value Problem.- 7. Symmetry & Parity.- 1. Introduction.- 2. Parity.- 3. Other Discrete Symmetries.- 4. Apple-Slicing, Axisymmetric & Hemispheric Models.- 5. Continuous Symmetries.- Table 7-1. Symmetry Classes for Trigonometric Functions.- 8. Explicit Time-Integration Methods.- 1. Introduction.- 2. Differential Equations with Variable Coefficients.- 3. Linear and Nonlinear.- 9. Practical Matters.- 1. Introduction.- 2. Partial Summation in Two or More Dimensions.- 3. The Fast Fourier Transform.- 4. Rules-of-Thumb.- 5. Boundary Layers.- 6. Endpoint versus Interior Singularities.- 7. Aliasing and the 3/2's Rule.- Table 9-1. RMS errors for the One-Dimensional Wave Equation.- 10. "Fractional Steps" Time Integration: Splitting and Its Cousins.- 1. Introduction.- 2. Diffusion Equation: Analytical and Numerical Background.- 3. The Method of Fractional Steps for the Diffusion Equ.- 4. Pitfalls in Splitting:Boundary Conditions & Consistency.- 5. Operator Theory of Time-Stepping Methods.- 6. Splitting the Navier-Stokes Equation.- 7. Rigid Boundaries, Incompressible Flow, and Splitting, I: The Over-Specified Pressure-Poisson Equation.- 8. Rigid Boundaries, Incompressible Flow, and Splitting, II: "Parabolic" & "Elliptic" Schemes & Numerical Boundary Layers.- 9. Rigid Boundaries, Incompressible Flow, and Splitting, III: Fractional Step-Coupling Boundary Conditions.- 10. Summary.- 11. Case Studies of Time Integration.- 1. Introduction.- 2. Three-Dimensional Periodic Turbulence: Brachet.- 3. Stellar Convection in Annular Shell: Glatzmaier.- 4. Plasma Physics in a Torus (Fusion Reactor): Schnack.- 5. Plane Poiseuille and Couette Flow: Orszag & Kells.- 6. Splitting & Separable Operators: Pipe Poiseuille Flow.- 7. Complex Geometry and Variable Coefficients: Zang.- 12. Iterative Methods for Solving Matrix Equations.- 1. Introduction.- 2. Stationary One-Step Iterations & the Richardson/Euler Iteration.- 3. Chebyshev Acceleration.- 4. Pre-conditioning: Finite Difference.- 5. Computing the Iterates: FFT & Matrix Multiplication.- 6. Alternative Pre-Conditionings for Partial Differential Equations.- 7. Multigrid: An Overview.- 8. The Minimum Residual Richardson's (MRR) Method.- 9. The Delves-Freeman "Asymptotically Diagonal" Preconditioned Iteration.- 10. Direct Methods for Separable PDE's.- 11. Recursion & Formal Integration: Clenshaw's Algorithm.- 12. Positive Definite & Indefinite Pseudospectral Matrices.- 13. Nonlinear Iterations & Preconditioned Newton Flow.- 14. Summary & Proverbs.- Table 12-1. Stationary One-Step Iterative Methods.- Table 12-2. Extreme Eigenvalues for the Chebyshev Discretization of the 2D Poisson equation.- Table 12-3. Condition Number n for Preconditioned Chebyshev Operator in Two Dimensions.- Table 12-4. The Upper 8 x 8 Block of a Fourier-Galerkin Matrix.- Table 12-5. Rescaled Upper Left 12 x 12 Block of an "Asymptotically Diagonal" Galerkin Matrix.- 13. The Many Uses of Coordinate Transformation.- 1. Introduction.- 2. Programming Chebyshev Methods.- 3. The General Theory of Coordinate Transformations.- 4. Mapping and Infinite and Semi-Infinite Intervals.- 5. Using Mapping to Resolve Endpoint & Coordinate Singularities.- 6. Eigenvalue Problems with Interior Singularities: Detours in the Complex Plane.- 7. Periodic Problems with Concentrated Amplitude & the Arctan/Tan Transformation.- 8. Two-Dimensional Maps & Singularity-Subtraction for Corner Branch Points.- 9. Adaptive Methods.- Table 13-1. A FORTRAN Subroutine for Computing Tn(x) and Its First Four Derivatives.- Table 13-2. The First Ten Eigenvalues of a Sturm-Liouville Problem with an Interior Pole for Different N.- 14. Methods for Unbounded Intervals.- 1. Introduction.- 2. Whittaker Cardinal or "Sinc" Expansions.- 3. Hermite functions.- 4. Algebraically Mapped Chebyshev Polynomials: TBn(y).- 5. Behavioral versus Numerical Boundary Conditions.- 6. Expansions for Functions Which Decay Algebraically With y or Asymptote to a Constant.- 7. Numerical Examples for Rational Chebyshev Functions: TBn(y).- 8. Rational Chebyshev Functions on y ? [0,?]: TLn(y).- 9. Numerical Examples: Chebyshev Methods on a Semi-Infinite Interval.- 10. Methods for f(y) Which Oscillate Without Exponential Decay at Infinity.- 11. Summary.- Table 14-1. The Rational Chebyshev Function: TBn(y).- Table 14-2. Examples of Functions Which Asymptote to a Constant or Decay Algebraically with the Corresponding Rational Basis Functions.- Table 14-3. The Spectral Coefficients for the Rational Series for the Yoshida Ocean Jet for Various N.- 15. Spherical Coordinates.- 1. Introduction.- 2. Icosahedral Grids and the Radiolaria.- 3. The Parity Factor: Sphere versus Torus.- 4. The Pole Problem.- 5. Spherical Harmonics: An Overview.- 6. The Spherical Harmonics Addition Theorem & Equiareal Resolution.- 7. Spherical Harmonics and Physics.- 8. Asymptotic Approximations I: Polar-Cap & Bessel Functions.- 9. Asymptotic Approximations II: High Zonal Wavenumber & Hermite Functions.- 10. Alternatives to Spherical Harmonics: Parity-Modified Fourier Series & Robert Functions.- 11. Transformation of the Horizontal Velocities.- 12. Semi-Implicit Spherical Harmonic Methods for the Shallow Water Wave Equations.- 13. Vector Basis Functions: Vector Spherical Harmonics & Hough Functions.- 14. Cylindrical, Toroidal and Polar Coordinates.- 15. Elliptic & Elliptic Cylinder Coordinates.- Table 15-1. An Illustration of Triangular Truncation.- 16. Special Tricks.- 1. Introduction.- 2. Sideband Truncation.- 3. Shock-Capturing & Shock-Fitting.- 4. Sum-Acceleration Methods.- 5. Special Basis Functions, I: Corner Singularities.- 6. Special Basis Functions, II: Wave Scattering.- 7. Special Basis Functions, III: Polynomial-Plus-Fourier Series for Non-Periodic Functions.- Table 16-1. The Exact & Numerical Reflection Coefficients for Quantum Scattering of a Plane Wave.- 17. Analytical Applications and Symbolic Manipulation.- 1. Introduction.- 2. Strategy: Interpolating versus Non-Interpolating Methods & the Choice of Basis Functions.- 3. Strategy, II: "Polynomialization" & "Rationalization".- 4. Implementing Spectral Methods in an Algebraic Manipulation Language.- 5. Examples.- 6. Open Problems.- Table 17-1. Listing of REDUCE ODE-BVP Legendre-Galerkin Code.- Table 17-2. The Maximum Pointwise Errors in the 4-Term Legendre Approximation.- Table 17-3. A Comparison of Legendre-Based Rational Approximation with the Power Series for the Airy Function.- Table 17-4. A REDUCE program to Derive the Two Equations in Two Unknowns for the Finlayson Nonlinear Diffusion Equ.- Table 17-5. Maximum Pointwise Errors for One and Two Point Collocation Solutions to Nonlinear Diffusion Equ.- 18. The Tau-Method.- 1. Introduction.- 2. Tau-Approximation for a Rational Function.- 3. Tau-Method for Differential Equations.- 4. Canonical Polynomials.- 5. Nomenclature Revisited.- 19. Domain Decomposition Methods.- 1. Introduction.- 2. Notation.- 3. Connecting the Subdomains: Patching.- 4. The Weak Coupling of Elemental Solutions: the Key to Efficiency.- 5. Variational Principles.- 6. Choice of Basis & Grid: Cardinal versus Orthogonal Polynomial, Chebyshev versus Legendre, Interior versus Extrema-and-Endpoints Grid.- 7. Patching versus Variational Formalism.- 8. Matrix Inversion.- 9. The Influence Matrix Method.- 10. Two-Dimensional Mappings & Sectorial Elements.- 11. Prospectus.- Appendix A. A Bestiary of Basis Functions.- 0. Trigonometric Basis Functions: Fourier Series.- 4. Gegenbauer Polynomials.- 5. Laguerre Functions.- 6. Hermite Functions.- Table A-1. Flow Chart on Choice of Basis Functions.- Fig. A-1. Regions of Convergence of Basis Sets in the Complex Plane.- Appendix B. Matrix Methods.- 1. Gaussian Elimination & LU Decomposition.- 2. Block-Banded Elimination: the "Lindzen-Kuo" Algorithm.- 3. Block and "Bordered" Matrices: the Fadeev-Fadeeva Factorization.- 4. Global Methods for Linear Eigenvalue Problems: The QR algorithm & the Pseudospectral Method.- Table B-1. Operation Counts for Banded Matrices.- Appendix C. The Newton-Kantorovich Method for Nonlinear Boundary and Eigenvalue Problems 1. Introduction.- 2. Examples.- 3. Eigenvalue Problems.- 4. Summary.- Appendix D. The Continuation Method.- 1. Introduction.- 2. Examples.- 3. Initialization Strategies.- 4. Limit Points.- 5. Bifurcation Points.- 6. Pseudoarclength Continuation.- Appendix E. Mapping Transformations.- Table E-1 [General Mapping].- Table E-2 [y = cos(x)].- Table E-3 [y = arccos(x)].- Table E-4 [y = L cot(x)].- Table E-8. [y = L arctanh(x)].- 2. Derivative Boundary Conditions.- Appendix F. Cardinal Functions.- 1. Introduction.- 2. General Fourier Series: Endpoint Grid.- 3. Fourier Cosine Series: Endpoint Grid.- 4. Fourier Sine Series: Endpoint Grid.- 5. Sinc(x): Whittaker Cardinal Functions.- 6. Chebyshev Polynomials: Extrema & Endpoints Grid.- 7. Chebyshev Polynomials: Interior Grid.- 8. Legendre Polynomials: Extrema & Endpoints Grid.- 9. Cosine Cardinal Functions on the Interior [Rectangle Rule or Roots] Grid.- 10. Sine Cardinal Functions on the Interior [Rectangle Rule or Roots] Grid.- Appendix G. Minimization of the Square of the Residual (Least Squares) for Solving Differential Equations via Nonlinear Degrees of Freedom.- 1. Introduction.- 2. Newton's Method.- 3. Linear Least-Squares Fitting and the Neglect of the Second Derivative.- 4. Evaluating the Second Derivatives for the Hessian Matrix.- 5. Steepest Descent.- 6. Convexity, Positive Definiteness, and Conditions for a Minimum.- 7. Approximations that Depend Nonlinearly on the Free Parameters.- 8. Nonlinear Approximation to the KdV Soliton: A Worked Example.- Errata.