Chebyshev & Fourier Spectral Methods

This book is a comprehensive introduction to spectral methods for solving differential equations. Although spectral methods are one of the three main families of numerical algorithms, this book is special in that it is one of only two books published in t

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 ñ 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.