Elliptic and Parabolic

Partial Differential

Equations

Peter Knabner

Lutz Angermann

Springer

44

Texts in Applied Mathematics

Editors

J.E. Marsden

L. Sirovich

S.S. Antman

Advisors

G. Iooss

P. Holmes

D. Barkley

M. Dellnitz

P. Newton

This page intentionally left blank

Peter Knabner Lutz Angermann

Numerical Methods for

Elliptic and Parabolic Partial

Differential Equations

With 67 Figures

Peter Knabner Lutz Angermann

Institute for Applied Mathematics Institute for Mathematics

University of Erlangen University of Clausthal

Martensstrasse 3 Erzstrasse 1

D-91058 Erlangen D-38678 Clausthal-Zellerfeld

Germany Germany

knabner@am.uni-erlangen.de angermann@math.tu-clausthal.de

Series Editors

J.E. Marsden L. Sirovich

Control and Dynamical Systems, 107“81 Division of Applied Mathematics

California Institute of Technology Brown University

Pasadena, CA 91125 Providence, RI 02912

USA USA

marsden@cds.caltech.edu chico@camelot.mssm.edu

S.S. Antman

Department of Mathematics

and

Institute for Physical Science

and Technology

University of Maryland

College Park, MD 20742-4015

USA

ssa@math.umd.edu

Mathematics Subject Classification (2000): 65Nxx, 65Mxx, 65F10, 65H10

Library of Congress Cataloging-in-Publication Data

Knabner, Peter.

[Numerik partieller Differentialgleichungen. English]

Numerical methods for elliptic and parabolic partial differential equations /

Peter Knabner, Lutz Angermann.

p. cm. ” (Texts in applied mathematics ; 44)

Include bibliographical references and index.

ISBN 0-387-95449-X (alk. paper)

1. Differential equations, Partial”Numerical solutions. I. Angermann, Lutz. II. Title.

III. Series.

QA377.K575 2003

515′.353”dc21 2002044522

ISBN 0-387-95449-X Printed on acid-free paper.

™ 2003 Springer-Verlag New York, Inc.

All rights reserved. This work may not be translated or copied in whole or in part without the written

permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Avenue, New York, NY 10010,

USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with

any form of information storage and retrieval, electronic adaptation, computer software, or by similar or

dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are

not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject

to proprietary rights.

Printed in the United States of America.

987654321 SPIN 10867187

Typesetting: Pages created by the authors in 2e using Springer™s svsing6.cls macro.

www.springer-ny.com

Springer-Verlag New York Berlin Heidelberg

A member of BertelsmannSpringer Science+Business Media GmbH

Series Preface

Mathematics is playing an ever more important role in the physical and

biological sciences, provoking a blurring of boundaries between scientific

disciplines and a resurgence of interest in the modern as well as the classical

techniques of applied mathematics. This renewal of interest, both in re-

search and teaching, has led to the establishment of the series Texts in

Applied Mathematics (TAM).

The development of new courses is a natural consequence of a high level

of excitement on the research frontier as newer techniques, such as numeri-

cal and symbolic computer systems, dynamical systems, and chaos, mix

with and reinforce the traditional methods of applied mathematics. Thus,

the purpose of this textbook series is to meet the current and future needs

of these advances and to encourage the teaching of new courses.

TAM will publish textbooks suitable for use in advanced undergraduate

and beginning graduate courses, and will complement the Applied Mathe-

matical Sciences (AMS) series, which will focus on advanced textbooks and

research-level monographs.

Pasadena, California J.E. Marsden

Providence, Rhode Island L. Sirovich

College Park, Maryland S.S. Antman

This page intentionally left blank

Preface to the English Edition

Shortly after the appearance of the German edition we were asked by

Springer to create an English version of our book, and we gratefully ac-

cepted. We took this opportunity not only to correct some misprints and

mistakes that have come to our knowledge1 but also to extend the text at

various places. This mainly concerns the role of the ¬nite di¬erence and

the ¬nite volume methods, which have gained more attention by a slight

extension of Chapters 1 and 6 and by a considerable extension of Chapter

7. Time-dependent problems are now treated with all three approaches (¬-

nite di¬erences, ¬nite elements, and ¬nite volumes), doing this in a uniform

way as far as possible. This also made a reordering of Chapters 6“8 nec-

essary. Also, the index has been enlarged. To improve the direct usability

in courses, exercises now follow each section and should provide enough

material for homework.

This new version of the book would not have come into existence without

our already mentioned team of helpers, who also carried out ¬rst versions

of translations of parts of the book. Beyond those already mentioned, the

team was enforced by Cecilia David, Basca Jadamba, Dr. Serge Kr¨utle, a

Dr. Wilhelm Merz, and Peter Mirsch. Alexander Prechtel now took charge

of the di¬cult modi¬cation process. Prof. Paul DuChateau suggested im-

provements. We want to extend our gratitude to all of them. Finally, we

1 Users

of the German edition may consult

http:/

/www.math.tu-clausthal.de/˜mala/publications/errata.pdf

viii Preface to the English Edition

thank senior editor Achi Dosanjh, from Springer-Verlag New York, Inc., for

her constant encouragement.

Remarks for the Reader and the Use in Lectures

The size of the text corresponds roughly to four hours of lectures per week

over two terms. If the course lasts only one term, then a selection is nec-

essary, which should be orientated to the audience. We recommend the

following “cuts”:

Chapter 0 may be skipped if the partial di¬erential equations treated

therein are familiar. Section 0.5 should be consulted because of the notation

collected there. The same is true for Chapter 1; possibly Section 1.4 may

be integrated into Chapter 3 if one wants to deal with Section 3.9 or with

Section 7.5.

Chapters 2 and 3 are the core of the book. The inductive presenta-

tion that we preferred for some theoretical aspects may be shortened for

students of mathematics. To the lecturer™s taste and depending on the

knowledge of the audience in numerical mathematics Section 2.5 may be

skipped. This might impede the treatment of the ILU preconditioning in

Section 5.3. Observe that in Sections 2.1“2.3 the treatment of the model

problem is merged with basic abstract statements. Skipping the treatment

of the model problem, in turn, requires an integration of these statements

into Chapter 3. In doing so Section 2.4 may be easily combined with Sec-

tion 3.5. In Chapter 3 the theoretical kernel consists of Sections 3.1, 3.2.1,

3.3“3.4.

Chapter 4 presents an overview of its subject, not a detailed development,

and is an extension of the classical subjects, as are Chapters 6 and 9 and

the related parts of Chapter 7.

In the extensive Chapter 5 one might focus on special subjects or just con-

sider Sections 5.2, 5.3 (and 5.4) in order to present at least one practically

relevant and modern iterative method.

Section 8.1 and the ¬rst part of Section 8.2 contain basic knowledge of

numerical mathematics and, depending on the audience, may be omitted.

The appendices are meant only for consultation and may complete

the basic lectures, such as in analysis, linear algebra, and advanced

mathematics for engineers.

Concerning related textbooks for supplementary use, to the best of our

knowledge there is none covering approximately the same topics. Quite a

few deal with ¬nite element methods, and the closest one in spirit probably

is [21], but also [6] or [7] have a certain overlap, and also o¬er additional

material not covered here. From the books specialised in ¬nite di¬erence

methods, we mention [32] as an example. The (node-oriented) ¬nite volume

method is popular in engineering, in particular in ¬‚uid dynamics, but to

the best of our knowledge there is no presentation similar to ours in a

Preface to the English Edition ix

mathematical textbook. References to textbooks specialised in the topics

of Chapters 4, 5 and 8 are given there.

Remarks on the Notation

Printing in italics emphasizes de¬nitions of notation, even if this is not

carried out as a numbered de¬nition.

Vectors appear in di¬erent forms: Besides the “short” space vectors

x ∈ Rd there are “long” representation vectors u ∈ Rm , which describe

in general the degrees of freedom of a ¬nite element (or volume) approxi-

mation or represent the values on grid points of a ¬nite di¬erence method.

Here we choose bold type, also in order to have a distinctive feature from

the generated functions, which frequently have the same notation, or from

the grid functions.

Deviations can be found in Chapter 0, where vectorial quantities belong-

ing to Rd are boldly typed, and in Chapters 5 and 8, where the unknowns

of linear and nonlinear systems of equations, which are treated in a general

manner there, are denoted by x ∈ Rm .

Components of vectors will be designated by a subindex, creating a

double index for indexed quantities. Sequences of vectors will be supplied

with a superindex (in parentheses); only in an abstract setting do we use

subindices.

Erlangen, Germany Peter Knabner

Clausthal-Zellerfeld, Germany Lutz Angermann

January 2002

This page intentionally left blank

Preface to the German Edition

This book resulted from lectures given at the University of Erlangen“

Nuremberg and at the University of Magdeburg. On these occasions we

often had to deal with the problem of a heterogeneous audience composed

of students of mathematics and of di¬erent natural or engineering sciences.

Thus the expectations of the students concerning the mathematical accu-

racy and the applicability of the results were widely spread. On the other

hand, neither relevant models of partial di¬erential equations nor some

knowledge of the (modern) theory of partial di¬erential equations could be

assumed among the whole audience. Consequently, in order to overcome the

given situation, we have chosen a selection of models and methods relevant

for applications (which might be extended) and attempted to illuminate the

whole spectrum, extending from the theory to the implementation, with-

out assuming advanced mathematical background. Most of the theoretical

obstacles, di¬cult for nonmathematicians, will be treated in an “induc-

tive” manner. In general, we use an explanatory style without (hopefully)

compromising the mathematical accuracy.

We hope to supply especially students of mathematics with the in-

formation necessary for the comprehension and implementation of ¬nite

element/¬nite volume methods. For students of the various natural or

engineering sciences the text o¬ers, beyond the possibly already existing

knowledge concerning the application of the methods in special ¬elds, an

introduction into the mathematical foundations, which should facilitate the

transformation of speci¬c knowledge to other ¬elds of applications.

We want to express our gratitude for the valuable help that we received

during the writing of this book: Dr. Markus Bause, Sandro Bitterlich,

xii Preface to the German Edition

Dr. Christof Eck, Alexander Prechtel, Joachim Rang, and Dr. Eckhard

Schneid did the proofreading and suggested important improvements. From

the anonymous referees we received useful comments. Very special thanks

go to Mrs. Magdalena Ihle and Dr. Gerhard Summ. Mrs. Ihle transposed

the text quickly and precisely into TEX. Dr. Summ not only worked on the

original script and on the TEX-form, he also organized the complex and

distributed rewriting and extension procedure. The elimination of many

inconsistencies is due to him. Additionally he in¬‚uenced parts of Sec-

tions 3.4 and 3.8 by his outstanding diploma thesis. We also want to thank

Dr. Chistoph Tapp for the preparation of the graphic of the title and for

providing other graphics from his doctoral thesis [70].

Of course, hints concerning (typing) mistakes and general improvements

are always welcome.

We thank Springer-Verlag for their constructive collaboration.

Last, but not least, we want to express our gratitude to our families for

their understanding and forbearance, which were necessary for us especially

during the last months of writing.

Erlangen, Germany Peter Knabner

Magdeburg, Germany Lutz Angermann

February 2000

Contents

Series Preface v

Preface to the English Edition vii

Preface to the German Edition xi

0 For Example: Modelling Processes in Porous Media

with Di¬erential Equations 1

0.1 The Basic Partial Di¬erential Equation Models . . . . . 1

0.2 Reactions and Transport in Porous Media . . . . . . . . 5

0.3 Fluid Flow in Porous Media . . . . . . . . . . . . . . . . 7

0.4 Reactive Solute Transport in Porous Media . . . . . . . . 11

0.5 Boundary and Initial Value Problems . . . . . . . . . . . 14

1 For the Beginning: The Finite Di¬erence Method

for the Poisson Equation 19

1.1 The Dirichlet Problem for the Poisson Equation . . ... 19

1.2 The Finite Di¬erence Method . . . . . . . . . . . . ... 21

1.3 Generalizations and Limitations

of the Finite Di¬erence Method . . . . . . . . . . . ... 29

1.4 Maximum Principles and Stability . . . . . . . . . . ... 36

2 The Finite Element Method for the Poisson Equation 46

2.1 Variational Formulation for the Model Problem . . . . . 46

xiv Contents

2.2 The Finite Element Method with Linear Elements . ... 55

2.3 Stability and Convergence of the

Finite Element Method . . . . . . . . . . . . . . . . ... 68

2.4 The Implementation of the Finite Element Method:

Part 1 . . . . . . . . . . . . . . . . . . . . . . . . . ... 74

2.5 Solving Sparse Systems of Linear Equations

by Direct Methods . . . . . . . . . . . . . . . . . . ... 82

3 The Finite Element Method for Linear Elliptic

Boundary Value Problems of Second Order 92

3.1 Variational Equations and Sobolev Spaces . . . . . . .. 92

3.2 Elliptic Boundary Value Problems of Second Order . .. 100

3.3 Element Types and A¬ne

Equivalent Triangulations . . . . . . . . . . . . . . . .. 114

3.4 Convergence Rate Estimates . . . . . . . . . . . . . . .. 131

3.5 The Implementation of the Finite Element Method:

Part 2 . . . . . . . . . . . . . . . . . . . . . . . . . . .. 148

3.6 Convergence Rate Results in Case of

Quadrature and Interpolation . . . . . . . . . . . . . . . 155

3.7 The Condition Number of Finite Element Matrices . . . 163

3.8 General Domains and Isoparametric Elements . . . . . . 167

3.9 The Maximum Principle for Finite Element Methods . . 171

4 Grid Generation and A Posteriori Error Estimation 176

4.1 Grid Generation . . . . . . . . . . . . . . . . . . . . . . . 176

4.2 A Posteriori Error Estimates and Grid Adaptation . . . 185

5 Iterative Methods for Systems of Linear Equations 198

5.1 Linear Stationary Iterative Methods . . . . . . . . . ... 200

5.2 Gradient and Conjugate Gradient Methods . . . . . ... 217

5.3 Preconditioned Conjugate Gradient Method . . . . ... 227

5.4 Krylov Subspace Methods

for Nonsymmetric Systems of Equations . . . . . . ... 233

5.5 The Multigrid Method . . . . . . . . . . . . . . . . ... 238

5.6 Nested Iterations . . . . . . . . . . . . . . . . . . . ... 251

6 The Finite Volume Method 255

6.1 The Basic Idea of the Finite Volume Method . . . . . . . 256

6.2 The Finite Volume Method for Linear Elliptic Di¬eren-

tial Equations of Second Order on Triangular Grids . . . 262

7 Discretization Methods for Parabolic Initial Boundary

Value Problems 283

7.1 Problem Setting and Solution Concept . . . . . . . . . . 283

7.2 Semidiscretization by the Vertical Method of Lines . . . 293

Contents xv

7.3 Fully Discrete Schemes . . . . . .............. 311

7.4 Stability . . . . . . . . . . . . . .............. 315

7.5 The Maximum Principle for the

One-Step-Theta Method . . . . .............. 323

7.6 Order of Convergence Estimates .............. 330

8 Iterative Methods for Nonlinear Equations 342

8.1 Fixed-Point Iterations . . . . . . . . . . . . . . . . . . . . 344

8.2 Newton™s Method and Its Variants . . . . . . . . . . . . 348

8.3 Semilinear Boundary Value Problems for Elliptic

and Parabolic Equations . . . . . . . . . . . . . . . . . . 360

9 Discretization Methods

for Convection-Dominated Problems 368

9.1 Standard Methods and

Convection-Dominated Problems . . . . . . . . . . . . . 368

9.2 The Streamline-Di¬usion Method . . . . . . . . . . . . . 375

9.3 Finite Volume Methods . . . . . . . . . . . . . . . . . . . 383

9.4 The Lagrange“Galerkin Method . . . . . . . . . . . . . . 387

A Appendices 390

A.1 Notation . . . . . . . . . . . . . . . . . . . ........ 390

A.2 Basic Concepts of Analysis . . . . . . . . . ........ 393

A.3 Basic Concepts of Linear Algebra . . . . . ........ 394

A.4 Some De¬nitions and Arguments of Linear

Functional Analysis . . . . . . . . . . . . . ........ 399

A.5 Function Spaces . . . . . . . . . . . . . . . ........ 404

References: Textbooks and Monographs 409

References: Journal Papers 412

Index 415

This page intentionally left blank

0

For Example:

Modelling Processes in Porous

Media with Di¬erential Equations

This chapter illustrates the scienti¬c context in which di¬erential equation

models may occur, in general, and also in a speci¬c example. Section 0.1

reviews the fundamental equations, for some of them discretization tech-

niques will be developed and investigated in this book. In Sections 0.2 “