. 1
( : 59)



. . >>

Numerical Methods for
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 “

. 1
( : 59)



. . >>