Solving PDEs in C++
C O M P U T A T I O N A L S C I E N C E & E N G I N E E R I N G
Computational Science and Engineering (CS&E) is widely accepted, along with theory and experiment,
as a crucial third mode of scientific investigation and engineering design. This series publishes research
monographs, advanced undergraduate- and graduate-level textbooks, and other volumes of interest to a
wide segment of the community of computational scientists and engineers.The series also includes volumes
addressed to users of CS&E methods by targeting specific groups of professionals whose work relies
extensively on computational science and engineering.
Editor-in-Chief
Omar Ghattas
University of Texas–Austin
Editorial Board
David Keyes, Associate Editor
Columbia University
Kim Baldridge
San Diego State University and
University of Zurich
Lori Freitag Diachin
Lawrence Livermore National Laboratory
Charbel Farhat
University of Colorado–Boulder
James Glimm
SUNY–Stony Brook
Teresa Head-Gordon
University of California–Berkeley and
Lawrence Berkeley National Laboratory
Rolf Jeltsch
ETH Zurich
Chris Johnson
University of Utah
Laxmikant Kale
University of Illinois
Jelena Kovacevic
Carnegie Mellon University
Habib Najm
Sandia National Laboratory
Alan Needleman
Brown University
Alex Pothen
Old Dominion University
Mary Wheeler
University of Texas–Austin
Series Volumes
Shapira,Yair, Solving PDEs in C++: Numerical Methods in a Unified Object-Oriented Approach
Solving PDEs in C++
Numerical Methods in a
Unified Object-Oriented Approach
Yair Shapira
Technion–Israel Institute of Technology
Haifa, Israel
Society for Industrial and Applied Mathematics
Philadelphia
Copyright © 2006 by the Society for Industrial and Applied Mathematics.
10 9 8 7 6 5 4 3 2 1
All rights reserved. Printed in the United States of America. No part of this book may be
reproduced, stored, or transmitted in any manner without the written permission of the
publisher. For information, write to the Society for Industrial and Applied Mathematics,
3600 University City Science Center, Philadelphia, PA 19104-2688.
The examples represented in this book have been included for their instructional value.
They have been tested with care but are not guaranteed for any particular purpose. The
publisher does not offer any warranties or representations, nor does it accept any liabilities
with respect to use of the examples.
MATLAB is a registered trademark of The MathWorks, Inc. and is used with permission.
The MathWorks does not warrant the accuracy of the text or exercises in this book.
This book’s use or discussion of MATLAB software or related products does not constitute
endorsement or sponsorship by The MathWorks of a particular pedagogical approach or
particular use of the MATLAB software. For MATLAB information, contact The MathWorks,
3 Apple Hill Drive, Natick, MA 01760-2098 USA,Tel: 508-647-7000, Fax: 508-647-7001
info@mathworks.com, www.mathworks.com
Windows is a registered trademark of Microsoft Corporation in the United States and/or
other countries.
Library of Congress Cataloging-in-Publication Data
Shapira,Yair, 1960-
Solving PDEs in C++ : numerical methods in a unified object-oriented approach / Yair
Shapira.
p. cm. — (Computational science and engineering)
Includes bibliographical references and index.
ISBN 0-89871-601-2 (pbk. : alk. paper)
1. Differential equations, Partial. 2. C++ (Computer program language) 3.
Object-oriented programming (Computer science) I.Title: Solving partial differential
equations in C++. II.Title. III. Series.
QA377.S466 2006
518’.64’02855133—dc22
2005054086
Partial royalties from the sale of this book are placed in a fund to help students
attend SIAM meetings and other SIAM-related activities.This fund is administered
by SIAM, and qualified individuals are encouraged to write directly to SIAM for
guidelines.
is a registered trademark.
i
i
i
“final3
2005/1
page v
i
Contents
List of Figures
List of Tables
Preface
Programming
I
1
xiii
xxi
xxiii
1
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . .
. . . . . .
. . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . .
. . . . .
.
. . . . .
.
. . . . . .
. . . . . .
. . . . . .
Introduction to C
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
1.10
1.11
1.12
1.13
1.14
1.15
1.16
1.17
1.18
1.19
1.20
1.21
1.22
1.23
Variables and Types . . . . .
. . . . . . .
Assignment
.
. . . . . . .
Initialization .
Conversion .
.
.
Arithmetic Operations . . . . .
Functions .
.
Printing Output
Conditions .
.
Scope of Variables . . . . .
Loops
. . . . . . .
Examples with Loops . . . . .
Example: Reversed Integer
Pointers
Arrays
. . . . .
Passing Arguments to Functions . . . . .
I/O .
.
Recursion .
Example: Binary Representation . . . . .
Example: Pascal’s Triangle . . . . .
Example: Local Maximum . . . . .
Example: Arithmetic Expression . . . . .
Example: The Exponent Function . . . . .
Exercises .
. . . . . . . .
. . . . . . .
. . . . .
. . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . .
. . . . .
. . . . .
. . . . .
. .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. .
. .
. .
. . .
.
7
7
8
8
9
9
. . . . 11
. . . . 13
. . . 14
. . . 15
. 17
. 19
. . 20
. . . . 22
. 23
. . . . . . . . . . 24
. . . . . . . 25
. . . 26
. . . . . . . . . 27
. . 29
. . 30
. . . . . . . . . 36
. . . . . . . . . 40
. . . . . . . . . . . . 43
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
. . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . .
v
i
i
i
i
i
i
vi
2
3
i
“final3
2005/1
page vi
i
Contents
. . . . . . . . . . . .
. . . . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . .
.
.
.
.
.
. .
. . . . .
. . . . .
. . . . . .
. . . . . .
. . . . . . . . .
. . . . . . . . .
. . . .
. . . .
. . .
. . . . . .
. . . . . .
. . . .
. . . .
. . . . .
. . . . . . . . .
. . . . .
. . . . . . . . .
. . . . . . . . .
Introduction to C++
.
2.1
2.2
.
2.3
2.4
2.5
2.6
2.7
2.8
2.9
2.10
2.11
2.12
2.13
2.14
2.15
2.16
2.17
2.18
2.19
2.20
2.21
2.22
2.23
.
Objects .
Classes .
.
Constructors .
Explicit Conversion . . . . .
Implicit Conversion . . . . .
The Default Copy Constructor . . . . .
Destructor
Member and Friend Functions . . . . .
References .
. .
Copy Constructor
Assignment Operators . . . . .
Operators .
Inverse Conversion . . . . .
Unary Operators . . . . .
Binary Operators . . . . .
Example: Complex Numbers . . . . .
Templates
Example: The Vector Object
Inheritance .
Example: The Matrix Object
Determinant and Inverse of a Square Matrix . . . . .
Exponent of a Square Matrix . . . . .
Exercises .
. . . . . .
. . . . .
. . . . . .
. . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. .
.
.
.
.
. .
.
.
.
.
.
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . . . .
47
. 47
. 48
. . 51
. . 53
. . 53
. 53
. . . 55
. 55
. . . 57
. . . 59
. 60
. . . . 62
. . . 63
. . . . 63
. . . . 65
. 68
. . . 72
. 75
. . . 79
. 86
. . . 88
. 90
. . . . 90
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . . .
.
.
.
.
. . . .
. . . . . .
. . . . . .
. . . . . . . .
Data Structures
3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8
3.9
3.10
3.11
3.12
Data Structures .
Templates in Data Structures
Dynamic Vectors . . . . .
Lists .
Connected Lists . . . . .
The Merging Problem . . . . .
The Ordering Problem . . . . .
. . . . . .
Vectors vs. Lists . . . . .
Two-Sided Connected Lists . . . . .
.
Trees .
.
Graphs .
.
Exercises .
. . . . . . . .
. . . . . . . . .
. . . .
.
.
. . . . . .
. . . . . .
.
.
.
.
.
.
. . . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . . .
. . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . .
. . . . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . . .
93
. 93
. 94
. . . . 94
. . . . . . 99
. . . . 102
. 108
. 110
. . . . 111
. . 112
. . . . . . 112
. 114
. . . . 115
. . . .
. . . .
. . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . .
. . . . .
. . . . . . . . . . .
. . . . .
. . . . . . . . . . .
II The Object-Oriented Approach
117
Object-Oriented Programming
4.1
4.2
4.3
Object-Oriented Language . . . . .
Example: The Graph-Coloring Problem . . . . .
Downward Implementation . . . . .
. . . . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
121
. . . 121
. . . . . 122
. . 124
4
i
i
i
i
i
i
Contents
4.4
4.5
4.6
4.7
4.8
4.9
4.10
i
“final3
2005/1
page v
i
vii
.
. . . . . .
. . . . . .
. . . . . . .
. . . . . . . . . .
The C++ Implementation . . . . .
Triangulation .
Example: The Triangle-Coloring Problem . . . . .
Downward Implementation . . . . .
Separation of Information . . . . .
Application in Numerical Schemes . . . . .
Exercises .
. . . 126
. . 128
. . . . 129
. . 130
. . . 131
. . . . . . . . 133
. . . . . . . . . . . . 134
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . .
. . . .
. . . .
.
.
5
6
. . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . .
. . . . . .
. . . . . .
Algorithms and Their Object-Oriented Implementation
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8
5.9
5.10
5.11
5.12
5.13
5.14
5.15
Ideas and Their Implementation . . . . .
Multilevel Programming . . . . .
Information and Storage . . . . .
Example: The Polynomial Object . . . .
Multiplication of Polynomials . . . . .
Calculation of a Polynomial . . . . .
Algorithms and Their Implementation . . . . .
Horner’s Algorithm . . . . .
Calculation of a Power . . . . .
Calculation of Derivatives . . . . .
The Taylor Expansion . . . . .
Derivatives of a Product . . . . .
Polynomial of Two Variables
Integration of a Polynomial
Exercises .
. . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . .
. . . . .
. . . . .
.
.
.
.
. . . . . . . . . .
. . . . . . . . . .
. . . . .
135
. . . . . . . . . . 135
. . . . 136
. . . . 137
. . 138
. 141
. . 143
. . . . . . . 143
. . 144
. 145
. . . 147
. 148
. . . . 151
. 152
. . 154
. . . . 156
. . . .
. . . .
. . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . . .
.
.
.
.
. . . .
. . . . . .
. . . . . .
. . . . . .
Object-Oriented Analysis
6.1
6.2
6.3
6.4
6.5
6.6
6.7
6.8
6.9
6.10
6.11
6.12
6.13
6.14
6.15
6.16
ODEs .
Stability in the ODE . . . . .
System of ODEs . . . . .
Stability in a System of ODEs . . . . .
Stable Invariant Subspace . . . . .
The Inhomogeneous Case . . . . .
. . . . . .
Numerical Solution . . . . .
. . . . . .
Difference Schemes . . . . .
. . . . .
The Taylor Difference Scheme
Computational Error Estimates . . . . .
Nonlinear ODEs . . . . .
Object-Oriented Analysis . . . . .
Application .
. . . . . . . . .
Taylor Scheme with Error Estimates
Asymptotic Solution . . . . .
Exercises .
. . . . . . . .
. . . . . .
. . . . . .
.
.
.
.
.
.
.
. . . . . . . . . .
. . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . .
. . . . . .
. . . . . . . . . .
. . . . .
. . . . . . . . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
. . . .
161
. . . . . . 161
. . . .
. . 162
. . . . 162
. 163
. . . 164
. . . 165
. . 165
. . 166
. . . . . . . . . . 167
. . . . . . . . . . 168
. . . . 170
. . . 170
. . . 171
. . . . . . . 172
. . 174
. . . . 176
. . . .
. . . .
i
i
i
i
i
i
i
“final3
2005/1
page vi
i
viii
III Partial Differential Equations and Their Discretization
Contents
179
7
8
9
10
. . . . . .
. . . . .
. . . . .
. . . . . . . . .
. . . . .
. . . . .
. . . . . . . . .
. . . . . . . . .
The Convection-Diffusion Equation
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
7.10
7.11
7.12
7.13
7.14
Initial-Boundary-Value Problems . . . . .
Finite Differences . . . .
. . . . . . . . .
The Upwind Scheme . . . .
Discrete Boundary Conditions . . . .
The Explicit Scheme . . . .
The Implicit Scheme . . . .
The Semi-Implicit Scheme
The Implementation . . . .
Hierarchy of Objects . . . .
List of Vectors .
The Time-Space Grid . . . . .
Difference Operators . . . . .
Two Spatial Dimensions . . . . .
Exercises .
. . . . . . . . .
. . . . . . . . .
. . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
. . . . . . . . .
. . . . .
. . . . .
. . . .
187
. . . . . . . . . 187
. . . . . . . . . . 188
. . . . . . . . . 189
. . . . .
. . . . 190
. . . . . . . . . 191
. . . . . . . . . 193
. . . . . 193
. . . . . . . . . 194
. . . . . . . . . 198
. . . . . . . . . 198
. 199
. . 201
. . . . 205
. . . . 207
. . . . .
. . . .
. . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
. . . .
Stability Analysis
8.1
8.2
8.3
8.4
8.5
Preliminaries .
Algebraic Representation . . . . .
Stability in Time Marching . . . . .
Accuracy and Adequacy . . . . .
Exercises .
. . . . . .
. . . . . .
. . . . . .
.
.
. . . . . . . . . .
. . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . .
. . . . . . . . . .
209
. . . . . . 209
. . . 211
. . 212
. . . . 214
. . . . 216
. . . . . .
. . . . . .
Nonlinear Equations
9.1
9.2
9.3
9.4
9.5
9.6
9.7
9.8
9.9
9.10
9.11
9.12
Nonlinear PDEs . . . . .
The Riemann Problem . . . . .
Conflicting Characteristic Lines . . . . .
The Godunov Scheme . . . . .
The Random-Choice Scheme . . . . .
. . . .
The N-Wave .
. . . . . . . .
Singular Perturbation . . . . .
. . . . . .
Linearization .
Adequacy in the Linearized Problem . . . . .
The Inhomogeneous Case . . . . .
. . . . . .
System of Nonlinear PDEs
Exercises .
. . . . . . . . .
. . . . . . .
. . . . . .
. . . . . .
. . . . .
. . . . .
.
.
.
.
.
. . . . . . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
. . . .
. . . . . . . . . .
219
. . . . 219
. 219
. . . . . . . . . . 220
. 222
. 225
. . . . . . . . 226
. 226
. . 228
. . . . . . . 230
. . . 232
. . 233
. . . . 235
. . . .
. . . .
. . . . . .
. . . . . . . . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . . . .
. . . . . . . .
Application in Image Processing
10.1
10.2
10.3
10.4
10.5
10.6
Digital Images .
The Denoising Problem . . . . .
The Nonlinear Diffusion Problem . . . .
The Discretization . . . . .
Linearization .
Color Images .
. . . . . . .
. . . . . . .
. . . . . .
. . . . . .
. . . . . .
.
.
237
. 237
. . . . 237
. . 238
. . . 239
. . 240
. . 240
. . . . . .
. . . . . . . . . .
. . . .
. . . . . .
. . . . . . . . . .
. . . . . . . . .
. . . . . . . . . .
. . . . .
. . . .
. . . . . . . . . .
. . . . . . . . . .
. . . .
. . . .
i
i
i
i