ALBERT

Note: Contents 1. Introduction 1.1 Historical Background 1.2 Some Examples of Spectral Methods 1.2.1 A Fourier Galerkin Method for the Wave Equation 1.2.2 A Chebyshev Collocation Method for the Heat Equation 1.2.3 A Legendre Galerkin with Numerical Integration (G-NI) Method for the Advection-Diffusion-Reaction Equation 1.2.4 A Legendre Tau Method for the Poisson Equation 1.2.5 Basic Aspects of Galerkin, Collocation, G-NI and Tau Methods 1.3 Three-Dimensional Applications in Fluids: A Look Ahead 2. Polynomial Approximation 2.1 The Fourier System 2.1.1 The Continuous Fourier Expansion 2.1.2 The Discrete Fourier Expansion 2.1.3 Differentiation 2.1.4 The Gibbs Phenomenon 2.2 Orthogonal Polynomials in (−1, 1) 2.2.1 Sturm-Liouville Problems 2.2.2 Orthogonal Systems of Polynomials 2.2.3 Gauss-Type Quadratures and Discrete Polynomial Transforms 2.3 Legendre Polynomials 2.3.1 Basic Formulas 2.3.2 Differentiation 2.3.3 Orthogonality, Diagonalization and Localization 2.4 Chebyshev Polynomials 2.4.1 Basic Formulas 2.4.2 Differentiation 2.5 Jacobi Polynomials 2.6 Approximation in Unbounded Domains 2.6.1 Laguerre Polynomials and Laguerre Functions 2.6.2 Hermite Polynomials and Hermite Functions 2.7 Mappings for Unbounded Domains 2.7.1 Semi-Infinite Intervals 2.7.2 The Real Line 2.8 Tensor-Product Expansions 2.8.1 Multidimensional Mapping 2.9 Expansions on Triangles and Related Domains 2.9.1 Collapsed Coordinates and Warped Tensor-Product Expansions 2.9.2 Non-Tensor-Product Expansions 2.9.3 Mappings 3. Basic Approaches to Constructing Spectral Methods 3.1 Burgers Equation 3.2 Strong and Weak Formulations of Differential Equations 3.3 Spectral Approximation of the Burgers Equation 3.3.1 Fourier Galerkin 3.3.2 Fourier Collocation 3.3.3 Chebyshev Tau 3.3.4 Chebyshev Collocation 3.3.5 Legendre G-NI 3.4 Convolution Sums 3.4.1 Transform Methods and Pseudospectral Methods 3.4.2 Aliasing Removal by Padding or Truncation 3.4.3 Aliasing Removal by Phase Shifts 3.4.4 Aliasing Removal for Orthogonal Polynomials 3.5 Relation Between Collocation, G-NI and Pseudospectral Methods 3.6 Conservation Forms 3.7 Scalar Hyperbolic Problems 3.7.1 Enforcement of Boundary Conditions 3.7.2 Numerical Examples 3.8 Matrix Construction for Galerkin and G-NI Methods 3.8.1 Matrix Elements 3.8.2 An Example of Algebraic Equivalence between G-NI and Collocation Methods 3.9 Polar Coordinates 3.10 Aliasing Effects 4. Algebraic Systems and Solution Techniques 4.1 Ad-hoc Direct Methods 4.1.1 Fourier Approximations 4.1.2 Chebyshev Tau Approximations 4.1.3 Galerkin Approximations 4.1.4 Schur Decomposition and Matrix Diagonalization 4.2 Direct Methods 4.2.1 Tensor Products of Matrices 4.2.2 Multidimensional Stiffness and Mass Matrices 4.2.3 Gaussian Elimination Techniques 4.3 Eigen-Analysis of Spectral Derivative Matrices 4.3.1 Second-Derivative Matrices 4.3.2 First-Derivative Matrices 4.3.3 Advection-Diffusion Matrices 4.4 Preconditioning 4.4.1 Fundamentals of Iterative Methods for Spectral Discretizations 4.4.2 Low-Order Preconditioning of Model Spectral Operators in One Dimension 4.4.3 Low-Order Preconditioning in Several Dimensions 4.4.4 Spectral Preconditioning 4.5 Descent and Krylov Iterative Methods for Spectral Equations 4.5.1 Multidimensional Matrix-Vector Multiplication 4.5.2 Iterative Methods 4.6 Spectral Multigrid Methods 4.6.1 One-Dimensional Fourier Multigrid Model Problem 4.6.2 General Spectral Multigrid Methods 4.7 Numerical Examples of Direct and Iterative Methods 4.7.1 Fourier Collocation Discretizations 4.7.2 Chebyshev Collocation Discretizations 4.7.3 Legendre G-NI Discretizations 4.7.4 Preconditioners for Legendre G-NI Matrices 4.8 Interlude 5. Polynomial Approximation Theory 5.1 Fourier Approximation 5.1.1 Inverse Inequalities for Trigonometric Polynomials 5.1.2 Estimates for the Truncation and Best Approximation Errors 5.1.3 Estimates for the Interpolation Error 5.2 Sturm-Liouville Expansions 5.2.1 Regular Sturm-Liouville Problems 5.2.2 Singular Sturm-Liouville Problems 5.3 Discrete Norms 5.4 Legendre Approximations 5.4.1 Inverse Inequalities for Algebraic Polynomials 5.4.2 Estimates for the Truncation and Best Approximation Errors 5.4.3 Estimates for the Interpolation Error 5.4.4 Scaled Estimates 5.5 Chebyshev Approximations 5.5.1 Inverse Inequalities for Polynomials 5.5.2 Estimates for the Truncation and Best Approximation Errors 5.5.3 Estimates for the Interpolation Error 5.6 Proofs of Some Approximation Results 5.7 Other Polynomial Approximations 5.7.1 Jacobi Polynomials 5.7.2 Laguerre and Hermite Polynomials 5.8 Approximation in Cartesian-Product Domains 5.8.1 Fourier Approximations 5.8.2 Legendre Approximations 5.8.3 Mapped Operators and Scaled Estimates 5.8.4 Chebyshev and Other Jacobi Approximations 5.8.5 Blended Trigonometric and Algebraic Approximations 5.9 Approximation in Triangles and Related Domains 6. Theory of Stability and Convergence 6.1 Three Elementary Examples Revisited 6.1.1 A Fourier Galerkin Method for the Wave Equation 6.1.2 A Chebyshev Collocation Method for the Heat Equation 6.1.3 A Legendre Tau Method for the Poisson Equation 6.2 Towards a General Theory 6.3 General Formulation of Spectral Approximations to Linear Steady Problems 6.4 Galerkin, Collocation, G-NI and Tau Methods 6.4.1 Galerkin Methods 6.4.2 Collocation Methods 6.4.3 G-NI Methods 6.4.4 Tau Methods 6.5 General Formulation of Spectral Approximations to Linear Evolution Problems 6.5.1 Conditions for Stability and Convergence: The Parabolic Case 6.5.2 Conditions for Stability and Convergence: The Hyperbolic Case 6.6 The Error Equation 7. Analysis of Model Boundary-Value Problems 7.1 The Poisson Equation 7.1.1 Legendre Methods 7.1.2 Chebyshev Methods 7.1.3 Other Boundary-Value Problems 7.2 Singularly Perturbed Elliptic Equations 7.2.1 Stabilization of Spectral Methods 7.3 The Eigenvalues of Some Spectral Operators 7.3.1 The Discrete Eigenvalues for Lu = −uxx 7.3.2 The Discrete Eigenvalues for Lu = −νuxx + βux 7.3.3 The Discrete Eigenvalues for Lu = ux 7.4 The Preconditioning of Spectral Operators 7.5 The Heat Equation 7.6 Linear Hyperbolic Equations 7.6.1 Periodic Boundary Conditions 7.6.2 Nonperiodic Boundary Conditions 7.6.3 The Resolution of the Gibbs Phenomenon 7.6.4 Spectral Accuracy for Non-Smooth Solutions 7.7 Scalar Conservation Laws 7.8 The Steady Burgers Equation Appendix A. Basic Mathematical Concepts A.1 Hilbert and Banach Spaces A.2 The Cauchy-Schwarz Inequality A.3 Linear Operators Between Banach Spaces A.4 The Fr´echet Derivative of an Operator A.5 The Lax-Milgram Theorem A.6 Dense Subspace of a Normed Space A.7 The Spaces Cm(Ω), m ≥ 0 A.8 Functions of Bounded Variation and the Riemann(-Stieltjes) Integral A.9 The Lebesgue Integral and Lp-Spaces A.10 Infinitely Differentiable Functions and Distributions A.11 Sobolev Spaces and Sobolev Norms A.12 The Sobolev Inequality A.13 The Poincar´e Inequality A.14 The Hardy Inequality A.15 The Gronwall Lemma Appendix B. Fast Fourier Transforms Appendix C. Iterative Methods for Linear Systems C.1 A Gentle Approach to Iterative Methods C.2 Descent Methods for Symmetric Problems C.3 Krylov Methods for Nonsymmetric Problems Appendix D. Time Discretizations D.1 Notation and Stability Definitions D.2 Standard ODE Methods D.2.1 Leap Frog Method D.2.2 Adams-Bashforth Methods D.2.3 Adams-Moulton Methods D.2.4 Backwards-Difference Formulas D.2.5 Runge-Kutta Methods D.3 Integrating Factors D.4 Low-Storage Schemes References Index