Time-Dependent Problems and Difference Methods E-Book

Bertil Gustafsson

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Serie: Wiley Series in Pure and Applied Mathematics
• Sprache: Englisch

Seitenzahl: 497

Veröffentlichungsjahr: 2013

Beschreibung

Praise for the First Edition ". . . fills a considerable gap in the numerical analysis literature by providing a self-contained treatment . . . this is an important work written in a clear style . . . warmly recommended to any graduate student or researcher in the field of the numerical solution of partial differential equations." --SIAM Review Time-Dependent Problems and Difference Methods, Second Edition continues to provide guidance for the analysis of difference methods for computing approximate solutions to partial differential equations for time-dependent problems. The book treats differential equations and difference methods with a parallel development, thus achieving a more useful analysis of numerical methods. The Second Edition presents hyperbolic equations in great detail as well as new coverage on second-order systems of wave equations including acoustic waves, elastic waves, and Einstein equations. Compared to first-order hyperbolic systems, initial-boundary value problems for such systems contain new properties that must be taken into account when analyzing stability. Featuring the latest material in partial differential equations with new theorems, examples, and illustrations,Time-Dependent Problems and Difference Methods, Second Edition also includes: * High order methods on staggered grids * Extended treatment of Summation By Parts operators and their application to second-order derivatives * Simplified presentation of certain parts and proofs Time-Dependent Problems and Difference Methods, Second Edition is an ideal reference for physical scientists, engineers, numerical analysts, and mathematical modelers who use numerical experiments to test designs and to predict and investigate physical phenomena. The book is also excellent for graduate-level courses in applied mathematics and scientific computations.

Leseprobe

Table of Contents

series

Title Page

Copyright

Part I: Problems with Periodic Solutions

Preface

Preface to the First Edition

Chapter 1: Model Equations

1.1 Periodic Gridfunctions and Difference Operators

1.2 First-Order Wave Equation, Convergence, and Stability

1.3 Leap-frog scheme

1.4 Implicit Methods

1.5 Truncation Error

1.6 Heat Equation

1.7 Convection–Diffusion Equation

1.8 Higher Order Equations

1.9 Second-Order Wave Equation

1.10 Generalization to Several Space Dimensions

Chapter 2: Higher Order Accuracy

2.1 Efficiency of Higher Order Accurate Difference Approximations

2.2 Time Discretization

Chapter 3: Well-Posed Problems

3.1 Introduction

3.2 Scalar Differential Equations with Constant Coefficients in One Space Dimension

3.3 First-Order Systems with Constant Coefficients in One Space Dimension

3.4 Parabolic Systems with Constant Coefficients in One Space Dimension

3.5 General Systems with Constant Coefficients

3.6 General Systems with Variable Coefficients

3.7 Semibounded Operators with Variable Coefficients

3.8 Stability and Well-Posedness

3.9 The Solution Operator and Duhamel's Principle

3.10 Generalized Solutions

3.11 Well-Posedness of Nonlinear Problems

3.12 The Principle of a Priori Estimates

3.13 The Principle of Linearization

Chapter 4: Stability and Convergence for Difference Methods

4.1 The Method of Lines

4.2 General Fully Discrete Methods

4.3 Splitting Methods

Chapter 5: Hyperbolic Equations and Numerical Methods

5.1 Systems with Constant Coefficients in One Space Dimension

5.2 Systems with Variable Coefficients in One Space Dimension

5.3 Systems with Constant Coefficients in Several Space Dimensions

5.4 Systems with Variable Coefficients in Several Space Dimensions

5.5 Approximations with Constant Coefficients

5.6 Approximations with Variable Coefficients

5.7 The Method of Lines

5.8 Staggered Grids

Chapter 6: Parabolic Equations And Numerical Methods

6.1 General Parabolic Systems

6.2 Stability For Difference Methods

Chapter 7: Problems with Discontinuous Solutions

7.1 Difference Methods for Linear Hyperbolic Problems

7.2 Method of Characteristics

7.3 Method of Characteristics in Several Space Dimensions

7.4 Method of Characteristics on a Regular Grid

7.5 Regularization Using Viscosity

7.6 The Inviscid Burgers’ Equation

7.7 The Viscous Burgers’ Equation and Traveling Waves

7.8 Numerical Methods for Scalar Equations Based on Regularization

7.9 Regularization for Systems of Equations

7.10 High Resolution Methods

Part II Initial_Boundary Value Problems

Chapter 8: The Energy Method For Initial–Boundary Value Problems

8.1 Characteristics And Boundary Conditions For Hyperbolic Systems In One Space Dimension

8.2 Energy Estimates For Hyperbolic Systems In One Space Dimension

8.3 Energy Estimates For Parabolic Differential Equations In One Space Dimension

8.4 Stability And Well-Posedness For General Differential Equations

8.5 Semibounded Operators

8.6 Quarter-Space Problems In More Than One Space Dimension

Chapter 9: The Laplace Transform Method for First-Order Hyperbolic Systems

9.1 A Necessary Condition for Well-Posedness

9.2 Generalized Eigenvalues

9.3 The Kreiss Condition

9.4 Stability in the Generalized Sense

9.5 Derivative Boundary Conditions for First-Order Hyperbolic Systems

Chapter 10: Second-Order Wave Equations

10.1 The Scalar Wave Equation

10.3 General Systems of Wave Equations

10.4 A Modified Wave Equation

10.5 The Elastic Wave Equations

10.6 Einstein's Equations and General Relativity

Chapter 11: The Energy Method for Difference Approximations

11.1 Hyperbolic problems

11.2 Parabolic Problems

11.3 Stability, Consistency, and Order of Accuracy

11.4 SBP Difference Operators

Chapter 12: The Laplace Transform Method For Difference Approximations

12.1 Necessary Conditions for Stability

12.2 Sufficient Conditions for Stability

12.3 Stability in the Generalized Sense for Hyperbolic Systems

12.4 An Example That Does Not Satisfy The Kreiss Condition But is Stable in the Generalized Sense

12.5 The Convergence Rate

Chapter 13: The Laplace Transform Method for Fully Discrete Approximations

13.1 General theory for approximations of hyperbolic systems

13.2 The Method of Lines and Stability in the Generalized Sense

Appendix A: Fourier Series and Trigonometric Interpolation

A.1 Some Results from the Theory of Fourier Series

A.2 Trigonometric Interpolation

A.3 Higher Dimensions

Appendix B: Fourier And Laplace Transform

B.1 Fourier Transform

B.2 Laplace Transform

Appendix C: Some results from linear algebra

Appendix D: SBP Operators

Diagonal -norm

Full -norm

References

Index

Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.

Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permission.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Gustafsson, Bertil, 1939-

Time-dependent problems and difference methods / Bertil Gustafsson, Heinz-Otto Kreiss, Joseph

Oliger.

pages cm

``Published simultaneously in Canada''--Title page verso.

Includes bibliographical references and index.

ISBN 978-0-470-90056-7 (cloth)

1. Differential equations, Partial- Numerical solutions. I. Kreiss, H. (Heinz-Otto) II. Oliger, Joseph, 1941--III. Title.

QA374.G974 2013

515'.353- dc23

2013000327

Part I

Problems With Periodic Solutions

Preface

In the first edition of this book, it was assumed that the partial differential equations (PDEs) are of the form , where is a differential operator of any order in space. Particular emphasis was given to hyperbolic first-order systems. Wave propagation problems most often come in the form , where is a differential operator of second order. Such differential equations can be rewritten as first-order systems, which is then used for discretization and computation. However, the original second-order form might be more convenient for computation and is often used. When it comes to initial–boundary value problems, it turns out that there are new properties to take into account when analyzing stability for second-order systems. This is discussed in Chapter 10.

A short section on staggered grids in Chapter 5 is also new, as well as an extension of SBP (summation by parts) operators in Section 11.4, including second-order derivatives and SAT (simultaneous approximation term) methods for implementation. There is also a new Appendix D containing the explicit form of a number of SBP operators.

Even if new parts have been included, this second edition is shorter than the original one. The reason is that we have tried to simplify certain parts. For example, in the discussion of difference methods in Chapter 4, we have emphasized explicit one-step methods to avoid the more complicated notation that comes with general multistep methods. We have also left out some of the detailed derivations and proofs in Chapters 5, 6, and 12. Furthermore, the Laplace transform methods for analysis of initial–boundary value problems is now limited to hyperbolic problem, where its strength is more pronounced.

Acknowledgments

The authors want to thank Barbro Kreiss for her assistance in preparing the manuscript of Chapter 10.

Preface to the First Edition

In this preface, we discuss the material to be covered, the point of view we take, and our emphases. Our primary goal is to discuss material relevant to the derivation and analysis of numerical methods for computing approximate solutions to partial differential equations for time-dependent problems arising in the sciences and engineering. It is our intention that this book should be useful for graduate students interested in applied mathematics and scientific computation as well as physical scientists and engineers whose primary interests are in carrying out numerical experiments to investigate physical behavior and test designs.

We carry out a parallel development of material for differential equations and numerical methods. Our motivation for this approach is twofold: the usual treatment of partial differential equations does not follow the lines that are most useful for the analysis of numerical methods, and the derivation of numerical methods is increasingly utilizing and benefiting from following the detailed development for the differential equations.

Most of our development and analysis is for linear equations, whereas most of the calculations done in practice are for nonlinear problems. However, this is not so fruitless as it may sound. If the nonlinear problem of interest has a smooth solution, then it can be linearized about this solution and the solution of the nonlinear problem will be a solution of the linearized problem with a perturbed forcing function. Errors of numerical approximations for the nonlinear problem can thus be estimated locally, and justified in terms of the linearized equations. A problem often arises in this scenario; the mathematical properties required to guarantee that the solution is smooth a priori may not be known or verifiable. So we often perform calculations whose results we cannot justify a priori. In this situation, we can proceed rationally, if not rigorously, by using a method that we could justify for the corresponding linearized problems and can be justified a posteriori, at least in principle, if the obtained solution satisfies certain smoothness properties. The smoothness properties of our computed solutions can be observed to experimentally verify the needed smoothness requirements and justify our computed results a posteriori. However, this procedure is not without its limitations. There are many problems that do not have smooth solutions. There are genuinely nonlinear phenomena, such as shocks, rarefaction waves, and nonlinear instability, that we must study in a nonlinear framework, and we discuss such issues separately. There are a few general results for nonlinear problems that generally are justifications of the linearization procedure mentioned above and that we include when available.

The material covered in this book emphasizes our own interests and work. In particular, our development of hyperbolic equations is more complete and detailed than our development of parabolic equations and equations of other types. Similarly,we emphasize the construction and analysis of finite difference methods, although we do discuss Fourier methods. We devote a considerable portion of this book to initial boundary value problems and numerical methods for them. This is the first book to contain much of this material and quite a lot of it has been redone for this presentation. We also tend to emphasize the sufficient results needed to justify methods used in applications rather than necessary results, and to stress error bounds and estimates which are valid for finite values of the discretization parameters rather than statements about limits.

We have organized this book in two parts: Part I discusses problems with periodic solutions and Part II discusses initial-boundary-value problems. It is simpler and more clear to develop the general concepts and to analyze problems and methods for the periodic boundary problems where the boundaries can essentially be ignored and Fourier series or trigonometric interpolants can be used. This same development is often carried out elsewhere for the Cauchy, or pure initial-value, problem. These two treatments are dual to each other, one relying upon Fourier series and the other upon Fourier integrals. We have chosen periodic boundary problems, because we are, in this context, dealing with a finite, computable method without any complications arising from the infinite domains of the corresponding Cauchy problems. Periodic boundary problems do arise naturally in many physical situations such as flows in toroids or on the surface of spheres; for example, the separation of periodic boundary and initial-boundary-value problems is also natural, because the results for initial-boundary-value problems often take the following form: If the problem or method is good for the periodic boundary problem and if some additional conditions are satisfied, then the problem or method is good for a corresponding initial-boundary-value problem. So an analysis and understanding of the corresponding periodic boundary problem is often a necessary condition for results for more general problems.

In Part I, we begin with a discussion in Chapter 1 of Fourier series and trigonometric interpolation, which is central to this part of the book. In Chapter 2, we discuss model equations for convection and diffusion. Throughout the book, we often rely upon a model equation approach to our material. Equations typifying various phenomena, such as convection, diffusion, and dispersion, that distinguish the difficulties inherent in approximating equations of different types are central to our analysis and development. Difference methods are first introduced in this chapter and discussed in terms of the model equations. In Chapter 3, we consider the efficiencies of using higher order accurate methods, which, in a natural limit, lead to the Fourier or pseudospectral method. The concept of a well-posed problem is introduced in Chapter 4 for general linear and nonlinear problems for partial differential equations. The general stability and convergence theory for difference methods is presented in Chapter 5. Sections are devoted to the tools and techniques needed to establish stability for methods for linear problems with constant coefficients and then for those with variable coefficients. Splitting methods are introduced, and their analysis is carried out. These methods are very useful for problems in several space dimensions and to take advantageof special solution techniques for particular operators. The chapter closes with a discussion of stability for nonlinear problems. Chapters 6 and 7 are devoted to specific results and methods for hyperbolic and parabolic equations, respectively. Nonlinear problems with discontinuous solutions, in particular, hyperbolic conservation laws with shocks and numerical methods for them are discussed in Chapter 8, which concludes Part I of the book and our basic treatment of partial differential equations and methods in the periodic boundary setting.

Part II is devoted to the discussion of the initial boundary value problem for partial differential equations and numerical methods for these problems. Chapter 9 discusses the energy method for initial-boundary-value problem for hyperbolic and parabolic equations. Chapter 10 discusses Laplace transform techniques for these problems. Chapter 11 treats stability for difference approximations using the energy method and follows the treatment of the differential equations in Chapter 9. Chapter 12 follows from Chapter 10 in terms of development–here the Laplace transform is used for difference approximations. This treatment is carried out for the semidiscretized problem: Only the spacial part of the operator is discretized. Finally, the fully discretized problem is treated in Chapter 13 using the Laplace transform. The so-called “normal mode analysis” technique is used and developed in these last two chapters. In particular, sufficient stability conditions for the fully discretized problem are obtained in terms of stability results for the semidiscretized problem, which are much easier to obtain.

Acknowledgments

The authors gratefully acknowledge the assistance we have gotten from our students and colleagues who have worked through various versions of this material and have supplied us with questions and suggestions that have been very helpful. We want to give special thanks to Barbro Kreiss and Mary Washburn who have expertly handled the preparation of our manuscript and have carried out most of the computations we have included. Their patience and good humor through our many versions and revisions is much appreciated. Pelle Olsson has gone over our manuscript carefully with us and a number of sections have been improved by his suggestions.

Finally, we acknowledge the Office of Naval Research and the National Aeronautics and Space Administration for their support of our work.

Chapter 1

Model Equations

In this chapter, we examine several model equations to introduce some basic properties of differential equations and difference approximations by example. Generalizations of these ideas are discussed throughout the remainder of this book.

1.1 Periodic Gridfunctions and Difference Operators

Let , where is a natural number, denote a grid interval. A grid on the -axis is defined to be the set of gridpoints

A discrete, possibly complex valued, function defined on the grid is called a gridfunction (see Figure 1.1.1). Here, we are only interested in -periodic gridfunctions, that is,

Clearly, the product and sum of gridfunctions are again gridfunctions. Their gridvalues are

We denote the set of all -periodic gridfunctions by . If , then uv, .

Figure 1.1.1 A gridfunction.

We now introduce difference operators. They play a fundamental role throughout the book. We start with the translation operator . It is defined by

If , then . Powers of are defined recursively,

Thus,

1.1.1

The inverse also exists and

If we define by , then Eq. (1.1.1 ) holds for all integers . is a linear operator and

The forward, backward, and central difference operators are defined by

1.1.2

respectively. In particular, consider these operators acting on the functions . Then, we have for all

1.1.3

Thus,

1.1.4

Consequently, one says that and are first-order accurate approximations of because the error is proportional to . is second-order accurate.

Higher derivatives are approximated by products of the above operators. For example,

In particular,

1.1.5

Therefore,

and is a second-order accurate approximation of . Note that all of the above operators commute, because they are all defined in terms of powers of .

We need to define norms for finite-dimensional vector spaces and discuss some of their properties. We begin with the usual Euclidean inner product and norm. Consider the -dimensional vector space consisting of all where , are complex numbers. We denote the conjugate transpose of by ( if is real). The inner product and norm are defined by

1.1.6

respectively. The inner product is a bilinear form that satisfies the following equalities:

1.1.7

The following inequalities hold:

1.1.8

Let be a complex matrix. Then, its transpose is denoted by and its conjugate transpose by . The Euclidean norm of the matrix is defined by

where the norm on the right-hand side is the vector norm defined above. If and are matrices, then

1.1.9

If the scalar and vector satisfy , then is an eigenvalue of and is the corresponding eigenvector. The spectral radius, , of a matrix is defined by

where the are the eigenvalues of . The spectral radius satisfies the inequality

1.1.10

We next define a scalar product and norm for our periodic gridfunctions of length . For fixed and , these functions form a vector space. However, we are interested in these functions as and . The Euclidean inner product and norm defined above would not necessarily be finite in this limit, so we must use a different definition.

We define a discrete scalar product and norm for periodic gridfunctions by

1.1.11

respectively.

The scalar product is also a bilinear form and satisfies the same equalities as the Euclidean inner product for vectors in Eq. (1.1.7 ):

1.1.12

The following inequalities also hold in analogy with Eq. (1.1.8 ):

1.1.13

For periodic functions defined everywhere, the scalar product and norm are defined by

A function with finite norm is called an function.

If are the projections of continuous functions onto the grid, then

converge to the scalar product and norm. Therefore, the above-mentioned inequalities are also valid for the scalar product and norm applied to functions. Because any function can be approximated arbitrarily well by a function, they are valid for all functions as well.

The norm of an operator is defined in the usual way,

From this definition, it follows that . Thus,

implies

1.1.14

Also,

that is,

The general inequalities

1.1.15

give us

Actually, these inequalities for the norms of , and can be replaced by equalities. For , we define and obtain

which yields

1.1.16

Using the same gridfunction again, we get

1.1.17

For , we choose (where ) and obtain

so

1.1.18

We now consider systems of partial differential equations and consequently need to define a norm and scalar product for vector-valued gridfunctions . Let and be two such vector-valued gridfunctions, then we define

1.1.19

The properties shown in Eqs. (1.1.12 ) and (1.1.13 ) are still valid. We can also generalize the second inequality in Eq. (1.1.13 ) when is replaced by an matrix . If is a constant matrix, we have

1.1.20

If is a matrix-valued gridfunction, then

1.1.21

Exercises

1.1.1 Derive estimates for

where .

1.1.2 Both the difference operators and approximate , but they have different norms. Explain why this is not a contradiction.

1.1.3 Compute .

1.2 First-Order Wave Equation, Convergence, and Stability

The equation is the simplest hyperbolic equation; the general definition of the class of hyperbolic equations is given in Section 3.3. We consider the initial value problem

1.2.1

where is a smooth -periodic function. To begin, we assume that the initial function

consists of one wave. The integer is called the wave number or the frequency. We try to find a solution of the same type

1.2.2

with . Substituting Eq. (1.2.2 ) into Eq. (1.2.1 ) yields an initial value problem for the ordinary differential equation