Spectral methods : fundamentals in single domains / C. Canuto ... [and others].

Format:

Book

Contributor:

Canuto, C.

Series:

Scientific computation 1434-8322

Scientific computation, 1434-8322

Language:

English

Subjects (All):

Differential equations, Partial--Numerical solutions.

Differential equations, Partial.

Numerical analysis.

Spectral theory (Mathematics).

Physical Description:

xxii, 563 pages : illustrations (partly color) ; 24 cm.

Place of Publication:

Berlin ; New York : Springer, [2006]

Summary:

Since the publication of Spectral Methods in Fluid Dynamics, spectral methods, particularly in their multidomain version, have become firmly established as a mainstream tool for scientific and engineering computation. While retaining the tight integration between the theoretical and practical aspects of spectral methods that was the hallmark of the earlier book, Canuto et al. now incorporate the many improvements in the algorithms and the theory of spectral methods that have been made since 1988.

The initial treatment Fundamentals in Single Domains discusses the fundamentals of the approximation of solutions to ordinary and partial differential equations on single domains by expansions in smooth, global basis functions. The first half of the book provides the algorithmic details of orthogonal expansions, transform methods, spectral discretization of differential equations plus their boundary conditions, and solution of the discretized equations by direct and iterative methods. The second half furnishes a comprehensive discussion of the mathematical theory of spectral methods on single domains, including approximation theory, stability and convergence, and illustrative applications of the theory to model boundary-value problems. Both the algorithmic and theoretical discussions cover spectral methods on tensor-product domains, triangles and tetrahedra. All chapters are enhanced with material on the Galerkin with numerical integration version of spectral methods. The discussion of direct and iterative solution methods is greatly expanded as are the set of numerical examples that illustrate the key properties of the various types of spectral approximations and the solution algorithms.

A companion book Evolution to Complex Geometries and Applications to Fluid Dynamics contains an extensive survey of the essential algorithmic and theoretical aspects of spectral methods for complex geometries and provides detailed discussions of spectral algorithms for fluid dynamics in simple and complex geometries.

Contents:

1.1 Historical Background 3

1.2 Some Examples of Spectral Methods 7

1.2.1 A Fourier Galerkin Method for the Wave Equation 7

1.2.2 A Chebyshev Collocation Method for the Heat Equation 11

1.2.3 A Legendre Galerkin with Numerical Integration (G-NI) Method for the Advection-Diffusion-Reaction Equation 16

1.2.4 A Legendre Tau Method for the Poisson Equation 21

1.2.5 Basic Aspects of Galerkin, Collocation, G-NI and Tau Methods 24

1.3 Three-Dimensional Applications in Fluids: A Look Ahead 25

2 Polynomial Approximation 39

2.1 The Fourier System 41

2.1.1 The Continuous Fourier Expansion 41

2.1.2 The Discrete Fourier Expansion 47

2.1.3 Differentiation 52

2.1.4 The Gibbs Phenomenon 56

2.2 Orthogonal Polynomials in (-1, 1) 68

2.2.1 Sturm-Liouville Problems 68

2.2.2 Orthogonal Systems of Polynomials 69

2.2.3 Gauss-Type Quadratures and Discrete Polynomial Transforms 70

2.3 Legendre Polynomials 75

2.3.1 Basic Formulas 75

2.3.2 Differentiation 77

2.3.3 Orthogonality, Diagonalization and Localization 81

2.4 Chebyshev Polynomials 84

2.4.1 Basic Formulas 84

2.4.2 Differentiation 87

2.5 Jacobi Polynomials 91

2.6 Approximation in Unbounded Domains 93

2.6.1 Laguerre Polynomials and Laguerre Functions 94

2.6.2 Hermite Polynomials and Hermite Functions 95

2.7 Mappings for Unbounded Domains 96

2.7.1 Semi-Infinite Intervals 96

2.7.2 The Real Line 97

2.8 Tensor-Product Expansions 98

2.8.1 Multidimensional Mapping 99

2.9 Expansions on Triangles and Related Domains 103

2.9.1 Collapsed Coordinates and Warped Tensor-Product Expansions 103

2.9.2 Non-Tensor-Product Expansions 110

2.9.3 Mappings 114

3 Basic Approaches to Constructing Spectral Methods 117

3.1 Burgers Equation 118

3.2 Strong and Weak Formulations of Differential Equations 119

3.3 Spectral Approximation of the Burgers Equation 121

3.3.1 Fourier Galerkin 122

3.3.2 Fourier Collocation 123

3.3.3 Chebyshev Tau 127

3.3.4 Chebyshev Collocation 129

3.3.5 Legendre G-NI 130

3.4 Convolution Sums 132

3.4.1 Transform Methods and Pseudospectral Methods 133

3.4.2 Aliasing Removal by Padding or Truncation 134

3.4.3 Aliasing Removal by Phase Shifts 135

3.4.4 Aliasing Removal for Orthogonal Polynomials 136

3.5 Relation Between Collocation, G-NI and Pseudospectral Methods 138

3.6 Conservation Forms 140

3.7 Scalar Hyperbolic Problems 145

3.7.1 Enforcement of Boundary Conditions 145

3.7.2 Numerical Examples 150

3.8 Matrix Construction for Galerkin and G-NI Methods 154

3.8.1 Matrix Elements 157

3.8.2 An Example of Algebraic Equivalence between G-NI and Collocation Methods 160

3.9 Polar Coordinates 162

3.10 Aliasing Effects 163

4 Algebraic Systems and Solution Techniques 167

4.1 Ad-hoc Direct Methods 169

4.1.1 Fourier Approximations 170

4.1.2 Chebyshev Tau Approximations 173

4.1.3 Galerkin Approximations 177

4.1.4 Schur Decomposition and Matrix Diagonalization 181

4.2 Direct Methods 186

4.2.1 Tensor Products of Matrices 186

4.2.2 Multidimensional Stiffness and Mass Matrices 187

4.2.3 Gaussian Elimination Techniques 192

4.3 Eigen-Analysis of Spectral Derivative Matrices 195

4.3.1 Second-Derivative Matrices 197

4.3.2 First-Derivative Matrices 200

4.3.3 Advection-Diffusion Matrices 206

4.4 Preconditioning 208

4.4.1 Fundamentals of Iterative Methods for Spectral Discretizations 209

4.4.2 Low-Order Preconditioning of Model Spectral Operators in One Dimension 211

4.4.3 Low-Order Preconditioning in Several Dimensions 227

4.4.4 Spectral Preconditioning 238

4.5 Descent and Krylov Iterative Methods for Spectral Equations 239

4.5.1 Multidimensional Matrix-Vector Multiplication 239

4.5.2 Iterative Methods 241

4.6 Spectral Multigrid Methods 242

4.6.1 One-Dimensional Fourier Multigrid Model Problem 243

4.6.2 General Spectral Multigrid Methods 246

4.7 Numerical Examples of Direct and Iterative Methods 251

4.7.1 Fourier Collocation Discretizations 251

4.7.2 Chebyshev Collocation Discretizations 253

4.7.3 Legendre G-NI Discretizations 256

4.7.4 Preconditioners for Legendre G-NI Matrices 259

4.8 Interlude 265

5 Polynomial Approximation Theory 267

5.1 Fourier Approximation 268

5.1.1 Inverse Inequalities for Trigonometric Polynomials 268

5.1.2 Estimates for the Truncation and Best Approximation Errors 269

5.1.3 Estimates for the Interpolation Error 272

5.2 Sturm-Liouville Expansions 275

5.2.1 Regular Sturm-Liouville Problems 275

5.2.2 Singular Sturm-Liouville Problems 277

5.3 Discrete Norms 279

5.4 Legendre Approximations 281

5.4.1 Inverse Inequalities for Algebraic Polynomials 281

5.4.2 Estimates for the Truncation and Best Approximation Errors 283

5.4.3 Estimates for the Interpolation Error 289

5.4.4 Scaled Estimates 290

5.5 Chebyshev Approximations 292

5.5.1 Inverse Inequalities for Polynomials 292

5.5.2 Estimates for the Truncation and Best Approximation Errors 293

5.5.3 Estimates for the Interpolation Error 296

5.6 Proofs of Some Approximation Results 298

5.7 Other Polynomial Approximations 309

5.7.1 Jacobi Polynomials 309

5.7.2 Laguerre and Hermite Polynomials 310

5.8 Approximation in Cartesian-Product Domains 312

5.8.1 Fourier Approximations 312

5.8.2 Legendre Approximations 314

5.8.3 Mapped Operators and Scaled Estimates 316

5.8.4 Chebyshev and Other Jacobi Approximations 318

5.8.5 Blended Trigonometric and Algebraic Approximations 320

5.9 Approximation in Triangles and Related Domains 323

6 Theory of Stability and Convergence 327

6.1 Three Elementary Examples Revisited 328

6.1.1 A Fourier Galerkin Method for the Wave Equation 328

6.1.2 A Chebyshev Collocation Method for the Heat Equation 329

6.1.3 A Legendre Tau Method for the Poisson Equation 334

6.2 Towards a General Theory 337

6.3 General Formulation of Spectral Approximations to Linear Steady Problems 338

6.4 Galerkin, Collocation, G-NI and Tau Methods 344

6.4.1 Galerkin Methods 345

6.4.2 Collocation Methods 351

6.4.3 G-NI Methods 360

6.4.4 Tau Methods 367

6.5 General Formulation of Spectral Approximations to Linear Evolution Problems 376

6.5.1 Conditions for Stability and Convergence: The Parabolic Case 378

6.5.2 Conditions for Stability and Convergence: The Hyperbolic Case 384

6.6 The Error Equation 396

7 Analysis of Model Boundary-Value Problems 401

7.1 The Poisson Equation 401

7.1.1 Legendre Methods 402

7.1.2 Chebyshev Methods 404

7.1.3 Other Boundary-Value Problems 409

7.2 Singularly Perturbed Elliptic Equations 409

7.2.1 Stabilization of Spectral Methods 413

7.3 The Eigenvalues of Some Spectral Operators 420

7.3.1 The Discrete Eigenvalues for Lu = -u[subscript xx] 420

7.3.2 The Discrete Eigenvalues for Lu = -vu[subscript xx] + [beta]u[subscript x] 424

7.3.3 The Discrete Eigenvalues for Lu = u[subscript x] 427

7.4 The Preconditioning of Spectral Operators 430

7.5 The Heat Equation 433

7.6 Linear Hyperbolic Equations 439

7.6.1 Periodic Boundary Conditions 439

7.6.2 Nonperiodic Boundary Conditions 445

7.6.3 The Resolution of the Gibbs Phenomenon 447

7.6.4 Spectral Accuracy for Non-Smooth Solutions 454

7.7 Scalar Conservation Laws 459

7.8 The Steady Burgers Equation 463

Appendix A Basic Mathematical Concepts 471

A.1 Hilbert and Banach Spaces 471

A.2 The Cauchy-Schwarz Inequality 473

A.3 Linear Operators Between Banach Spaces 474

A.4 The Frechet Derivative of an Operator 475

A.5 The Lax-Milgram Theorem 475

A.6 Dense Subspace of a Normed Space 476

A.7 The Spaces C[superscript m] ([Omega]), m [greater than or equal] 0 476

A.8 Functions of Bounded Variation and the Riemann(-Stieltjes) Integral 476

A.9 The Lebesgue Integral and L[superscript p]-Spaces 478

A.10 Infinitely Differentiable

Functions and Distributions 482

A.11 Sobolev Spaces and Sobolev Norms 484

A.12 The Sobolev Inequality 490

A.13 The Poincare Inequality 491

A.14 The Hardy Inequality 491

A.15 The Gronwall Lemma 492

Appendix B Fast Fourier Transforms 493

Appendix C Iterative Methods for Linear Systems 499

C.1 A Gentle Approach to Iterative Methods 499

C.2 Descent Methods for Symmetric Problems 503

C.3 Krylov Methods for Nonsymmetric Problems 508

Appendix D Time Discretizations 515

D.1 Notation and Stability Definitions 515

D.2 Standard ODE Methods 519

D.2.1 Leap Frog Method 519

D.2.2 Adams-Bashforth Methods 520

D.2.3 Adams-Moulton Methods 521

D.2.4 Backwards-Difference Formulas 524

D.2.5 Runge-Kutta Methods 524

D.3 Integrating Factors 525

D.4 Low-Storage Schemes 527.

Notes:

Includes bibliographical references (pages [529]-552) and index.

ISBN:

3540307257

OCLC:

68629287

Publisher Number:

9783540307259