. 1
( : 95)



. . >>

Numerical Mathematics




Alfio Quarteroni
Riccardo Sacco
Fausto Saleri



Springer
Texts in Applied Mathematicsm37



Editors
J.E. Marsden
L. Sirovich
M. Golubitsky
W. J¤ger

Advisors
G. Iooss
P. Holmes
D. Barkley
M. Dellnitz
P. Newton




Springer
New York
Berlin
Heidelberg
Barcelona
Hong Kong
London
Milan
Paris
Singapore
Tokyo
Alfio QuarteroniMMRiccardo Sacco
Fausto Saleri




Numerical Mathematics


With 134 Illustrations




123
Riccardo Sacco
Alfio Quarteroni Fausto Saleri
Dipartimento di Matematica
Department of Mathematics Dipartimento di Matematica,
Politecnico di Milano
Ecole Polytechnique M“F. Enriques”
Piazza Leonardo da Vinci 32
MFe ´rale de Lausanne
´de Università degli Studi di
20133 Milan
CH-1015 Lausanne MMilano
Italy
Switzerland Via Saldini 50
ricsac@mate.polimi.it
alfio.quarteroni@epfl.ch 20133 Milan
Italy
fausto.saleri@unimi.it
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

M. Golubitsky W. J¨ ger
a
Department of Mathematics Department of Applied Mathematics
University of Houston Universit a t Heidelberg
¨
Houston, TX 77204-3476 Im Neuenheimer Feld 294
USA 69120 Heidelberg
Germany

Mathematics Subject Classification (1991): 15-01, 34-01, 35-01, 65-01

Library of Congress Cataloging-in-Publication Data
Quarteroni, Alfio.
Numerical mathematics/Alfio Quarteroni, Riccardo Sacco, Fausto Saleri.
p.Mcm. ” (Texts in applied mathematics; 37)
Includes bibliographical references and index.
ISBN 0-387-98959-5 (alk. paper)
1. Numerical analysis.MI. Sacco, Riccardo.MII. Saleri, Fausto.MIII. Title.MIV. Series.
I. Title.MMII. Series.
QA297.Q83M2000
519.4”dc21 99-059414




© 2000 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 heraf-
ter developed is forbidden.
The use of general descriptive names, trade names, trademarks, etc., in this publication, even
if the former are not especially identified, is not to be taken as a sign that such names, as
understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely
by anyone.




ISBN 0-387-98959-5nSpringer-VerlagnNew YorknBerlinnHeidelbergMSPIN 10747955
Preface




Numerical mathematics is the branch of mathematics that proposes, de-
velops, analyzes and applies methods from scienti¬c computing to several
¬elds including analysis, linear algebra, geometry, approximation theory,
functional equations, optimization and di¬erential equations. Other disci-
plines such as physics, the natural and biological sciences, engineering, and
economics and the ¬nancial sciences frequently give rise to problems that
need scienti¬c computing for their solutions.
As such, numerical mathematics is the crossroad of several disciplines of
great relevance in modern applied sciences, and can become a crucial tool
for their qualitative and quantitative analysis. This role is also emphasized
by the continual development of computers and algorithms, which make it
possible nowadays, using scienti¬c computing, to tackle problems of such
a large size that real-life phenomena can be simulated providing accurate
responses at a¬ordable computational cost.
The corresponding spread of numerical software represents an enrichment
for the scienti¬c community. However, the user has to make the correct
choice of the method (or the algorithm) which best suits the problem at
hand. As a matter of fact, no black-box methods or algorithms exist that
can e¬ectively and accurately solve all kinds of problems.
One of the purposes of this book is to provide the mathematical foun-
dations of numerical methods, to analyze their basic theoretical proper-
ties (stability, accuracy, computational complexity), and demonstrate their
performances on examples and counterexamples which outline their pros
viii Preface

and cons. This is done using the MATLAB 1 software environment. This
choice satis¬es the two fundamental needs of user-friendliness and wide-
spread di¬usion, making it available on virtually every computer.
Every chapter is supplied with examples, exercises and applications of
the discussed theory to the solution of real-life problems. The reader is
thus in the ideal condition for acquiring the theoretical knowledge that is
required to make the right choice among the numerical methodologies and
make use of the related computer programs.
This book is primarily addressed to undergraduate students, with partic-
ular focus on the degree courses in Engineering, Mathematics, Physics and
Computer Science. The attention which is paid to the applications and the
related development of software makes it valuable also for graduate stu-
dents, researchers and users of scienti¬c computing in the most widespread
professional ¬elds.
The content of the volume is organized into four parts and 13 chapters.
Part I comprises two chapters in which we review basic linear algebra and
introduce the general concepts of consistency, stability and convergence of
a numerical method as well as the basic elements of computer arithmetic.
Part II is on numerical linear algebra, and is devoted to the solution of
linear systems (Chapters 3 and 4) and eigenvalues and eigenvectors com-
putation (Chapter 5).
We continue with Part III where we face several issues about functions
and their approximation. Speci¬cally, we are interested in the solution of
nonlinear equations (Chapter 6), solution of nonlinear systems and opti-
mization problems (Chapter 7), polynomial approximation (Chapter 8) and
numerical integration (Chapter 9).
Part IV, which is the more demanding as a mathematical background, is
concerned with approximation, integration and transforms based on orthog-
onal polynomials (Chapter 10), solution of initial value problems (Chap-
ter 11), boundary value problems (Chapter 12) and initial-boundary value
problems for parabolic and hyperbolic equations (Chapter 13).
Part I provides the indispensable background. Each of the remaining
Parts has a size and a content that make it well suited for a semester
course.
A guideline index to the use of the numerous MATLAB Programs de-
veloped in the book is reported at the end of the volume. These programs
are also available at the web site address:
http://www1.mate.polimi.it/˜ calnum/programs.html
For the reader™s ease, any code is accompanied by a brief description of
its input/output parameters.
We express our thanks to the sta¬ at Springer-Verlag New York for their
expert guidance and assistance with editorial aspects, as well as to Dr.

1 MATLAB is a registered trademark of The MathWorks, Inc.
Preface ix

Martin Peters from Springer-Verlag Heidelberg and Dr. Francesca Bonadei
from Springer-Italia for their advice and friendly collaboration all along
this project.
We gratefully thank Professors L. Gastaldi and A. Valli for their useful
comments on Chapters 12 and 13.
We also wish to express our gratitude to our families for their forbearance
and understanding, and dedicate this book to them.

Lausanne, Switzerland Al¬o Quarteroni
Milan, Italy Riccardo Sacco
Milan, Italy Fausto Saleri
January 2000
Contents




Series Preface v

Preface vii

PART I: Getting Started

1. Foundations of Matrix Analysis 1
1.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Operations with Matrices . . . . . . . . . . . . . . . . . . . 5
1.3.1 Inverse of a Matrix . . . . . . . . . . . . . . . . . . 6
1.3.2 Matrices and Linear Mappings . . . . . . . . . . . 7
1.3.3 Operations with Block-Partitioned Matrices . . . . 7
1.4 Trace and Determinant of a Matrix . . . . . . . . . . . . . 8
1.5 Rank and Kernel of a Matrix . . . . . . . . . . . . . . . . 9
1.6 Special Matrices . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.1 Block Diagonal Matrices . . . . . . . . . . . . . . . 10
1.6.2 Trapezoidal and Triangular Matrices . . . . . . . . 11
1.6.3 Banded Matrices . . . . . . . . . . . . . . . . . . . 11
1.7 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . 12
1.8 Similarity Transformations . . . . . . . . . . . . . . . . . . 14
1.9 The Singular Value Decomposition (SVD) . . . . . . . . . 16
1.10 Scalar Product and Norms in Vector Spaces . . . . . . . . 17
1.11 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . 21
xii Contents

1.11.1 Relation Between Norms and the
Spectral Radius of a Matrix . . . . . . . . . . . . . 25
1.11.2 Sequences and Series of Matrices . . . . . . . . . . 26
1.12 Positive De¬nite, Diagonally Dominant and M-Matrices . 27
1.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2. Principles of Numerical Mathematics 33
2.1 Well-Posedness and Condition Number of a Problem . . . 33
2.2 Stability of Numerical Methods . . . . . . . . . . . . . . . 37
2.2.1 Relations Between Stability and Convergence . . . 40
2.3 A priori and a posteriori Analysis . . . . . . . . . . . . . . 41
2.4 Sources of Error in Computational Models . . . . . . . . . 43
2.5 Machine Representation of Numbers . . . . . . . . . . . . 45
2.5.1 The Positional System . . . . . . . . . . . . . . . . 45
2.5.2 The Floating-Point Number System . . . . . . . . 46
2.5.3 Distribution of Floating-Point Numbers . . . . . . 49
2.5.4 IEC/IEEE Arithmetic . . . . . . . . . . . . . . . . 49
2.5.5 Rounding of a Real Number in Its
Machine Representation . . . . . . . . . . . . ... 50
2.5.6 Machine Floating-Point Operations . . . . . . ... 52
2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . ... 54

PART II: Numerical Linear Algebra

3. Direct Methods for the Solution of Linear Systems 57
3.1 Stability Analysis of Linear Systems . . . . . . . . . . . . 58
3.1.1 The Condition Number of a Matrix . . . . . . . . 58
3.1.2 Forward a priori Analysis . . . . . . . . . . . . . . 60
3.1.3 Backward a priori Analysis . . . . . . . . . . . . . 63
3.1.4 A posteriori Analysis . . . . . . . . . . . . . . . . . 64
3.2 Solution of Triangular Systems . . . . . . . . . . . . . . . 65
3.2.1 Implementation of Substitution Methods . . . . . 65
3.2.2 Rounding Error Analysis . . . . . . . . . . . . . . 67
3.2.3 Inverse of a Triangular Matrix . . . . . . . . . . . 67
3.3 The Gaussian Elimination Method (GEM) and
LU Factorization . . . . . . . . . . . . . . . . . . . . . . . 68
3.3.1 GEM as a Factorization Method . . . . . . . . . . 72
3.3.2 The E¬ect of Rounding Errors . . . . . . . . . . . 76
3.3.3 Implementation of LU Factorization . . . . . . . . 77
3.3.4 Compact Forms of Factorization . . . . . . . . . . 78
3.4 Other Types of Factorization . . . . . . . . . . . . . . . . . 79
3.4.1 LDMT Factorization . . . . . . . . . . . . . . . . . 79
3.4.2 Symmetric and Positive De¬nite Matrices:
The Cholesky Factorization . . . . . . . . . . ... 80
3.4.3 Rectangular Matrices: The QR Factorization ... 82
Contents xiii

3.5 Pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.6 Computing the Inverse of a Matrix . . . . . . . . . . . . . 89
3.7 Banded Systems . . . . . . . . . . . . . . . . . . . . . . . . 90
3.7.1 Tridiagonal Matrices . . . . . . . . . . . . . . . . . 91
3.7.2 Implementation Issues . . . . . . . . . . . . . . . . 92
3.8 Block Systems . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.8.1 Block LU Factorization . . . . . . . . . . . . . . . 94
3.8.2 Inverse of a Block-Partitioned Matrix . . . . . . . 95
3.8.3 Block Tridiagonal Systems . . . . . . . . . . . . . . 95
3.9 Sparse Matrices . . . . . . . . . . . . . . . . . . . . . . . . 97
3.9.1 The Cuthill-McKee Algorithm . . . . . . . . . . . 98
3.9.2 Decomposition into Substructures . . . . . . . . . 100
3.9.3 Nested Dissection . . . . . . . . . . . . . . . . . . . 103
3.10 Accuracy of the Solution Achieved Using GEM . . . . . . 103
3.11 An Approximate Computation of K(A) . . . . . . . . . . . 106
3.12 Improving the Accuracy of GEM . . . . . . . . . . . . . . 109
3.12.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . 110
3.12.2 Iterative Re¬nement . . . . . . . . . . . . . . . . . 111
3.13 Undetermined Systems . . . . . . . . . . . . . . . . . . . . 112
3.14 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 115
3.14.1 Nodal Analysis of a Structured Frame . . . . . . . 115
3.14.2 Regularization of a Triangular Grid . . . . . . . . 118
3.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

4. Iterative Methods for Solving Linear Systems 123
4.1 On the Convergence of Iterative Methods . . . . . . . . . . 123
4.2 Linear Iterative Methods . . . . . . . . . . . . . . . . . . . 126
4.2.1 Jacobi, Gauss-Seidel and Relaxation Methods . . . 127
4.2.2 Convergence Results for Jacobi and
Gauss-Seidel Methods . . . . . . . . . . . . . . . . 129
4.2.3 Convergence Results for the Relaxation Method . 131
4.2.4 A priori Forward Analysis . . . . . . . . . . . . . . 132
4.2.5 Block Matrices . . . . . . . . . . . . . . . . . . . . 133
4.2.6 Symmetric Form of the Gauss-Seidel and
SOR Methods . . . . . . . . . . . . . . . . . . . . . 133
4.2.7 Implementation Issues . . . . . . . . . . . . . . . . 135
4.3 Stationary and Nonstationary Iterative Methods . . . . . . 136
4.3.1 Convergence Analysis of the Richardson Method . 137
4.3.2 Preconditioning Matrices . . . . . . . . . . . . . . 139
4.3.3 The Gradient Method . . . . . . . . . . . . . . . . 146
4.3.4 The Conjugate Gradient Method . . . . . . . . . . 150
4.3.5 The Preconditioned Conjugate Gradient Method . 156
4.3.6 The Alternating-Direction Method . . . . . . . . . 158
4.4 Methods Based on Krylov Subspace Iterations . . . . . . . 159
4.4.1 The Arnoldi Method for Linear Systems . . . . . . 162
xiv Contents

4.4.2 The GMRES Method . . . . . . . . . . . . . . . . 165
4.4.3 The Lanczos Method for Symmetric Systems . . . 167
4.5 The Lanczos Method for Unsymmetric Systems . . . . . . 168
4.6 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . 171
4.6.1 A Stopping Test Based on the Increment . . . . . 172
4.6.2 A Stopping Test Based on the Residual . . . . . . 174
4.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.7.1 Analysis of an Electric Network . . . . . . . . . . . 174
4.7.2 Finite Di¬erence Analysis of Beam Bending . . . . 177
4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

5. Approximation of Eigenvalues and Eigenvectors 183
5.1 Geometrical Location of the Eigenvalues . . . . . . . . . . 183
5.2 Stability and Conditioning Analysis . . . . . . . . . . . . . 186
5.2.1 A priori Estimates . . . . . . . . . . . . . . . . . . 186
5.2.2 A posteriori Estimates . . . . . . . . . . . . . . . . 190
5.3 The Power Method . . . . . . . . . . . . . . . . . . . . . . 192
5.3.1 Approximation of the Eigenvalue of
Largest Module . . . . . . . . . . . . . . . . . . . . 192
5.3.2 Inverse Iteration . . . . . . . . . . . . . . . . . . . 195
5.3.3 Implementation Issues . . . . . . . . . . . . . . . . 196
5.4 The QR Iteration . . . . . . . . . . . . . . . . . . . . . . . 200
5.5 The Basic QR Iteration . . . . . . . . . . . . . . . . . . . . 201
5.6 The QR Method for Matrices in Hessenberg Form . . . . . 203
5.6.1 Householder and Givens Transformation Matrices 204
5.6.2 Reducing a Matrix in Hessenberg Form . . . . . . 207
5.6.3 QR Factorization of a Matrix in Hessenberg Form 209
5.6.4 The Basic QR Iteration Starting from
Upper Hessenberg Form . . . . . . . . . . . . . . . 210
5.6.5 Implementation of Transformation Matrices . . . . 212
5.7 The QR Iteration with Shifting Techniques . . . . . . . . . 215
5.7.1 The QR Method with Single Shift . . . . . . . . . 215
5.7.2 The QR Method with Double Shift . . . . . . . . . 218
5.8 Computing the Eigenvectors and the SVD of a Matrix . . 221
5.8.1 The Hessenberg Inverse Iteration . . . . . . . . . . 221
5.8.2 Computing the Eigenvectors from the
Schur Form of a Matrix . . . . . . . . . . . . . . . 221
5.8.3 Approximate Computation of the SVD of a Matrix 222
5.9 The Generalized Eigenvalue Problem . . . . . . . . . . . . 224
5.9.1 Computing the Generalized Real Schur Form . . . 225
5.9.2 Generalized Real Schur Form of
Symmetric-De¬nite Pencils . . . . . . . . . . . . . 226
5.10 Methods for Eigenvalues of Symmetric Matrices . . . . . . 227
5.10.1 The Jacobi Method . . . . . . . . . . . . . . . . . 227
5.10.2 The Method of Sturm Sequences . . . . . . . . . . 230
Contents xv

5.11 The Lanczos Method . . . . . . . . . . . . . . . . . . . . . 233
5.12 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . 235
5.12.1 Analysis of the Buckling of a Beam . . . . . . . . . 236
5.12.2 Free Dynamic Vibration of a Bridge . . . . . . . . 238
5.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

PART III: Around Functions and Functionals

6. Root¬nding for Nonlinear Equations 245
6.1 Conditioning of a Nonlinear Equation . . . . . . . . . . . . 246
6.2 A Geometric Approach to Root¬nding . . . . . . . . . . . 248
6.2.1 The Bisection Method . . . . . . . . . . . . . . . . 248
6.2.2 The Methods of Chord, Secant and Regula Falsi
and Newton™s Method . . . . . . . . . . . . . . . . 251
6.2.3 The Dekker-Brent Method . . . . . . . . . . . . . 256
6.3 Fixed-Point Iterations for Nonlinear Equations . . . . . . . 257
6.3.1 Convergence Results for
Some Fixed-Point Methods . . . . . . . . . . . . . 260
6.4 Zeros of Algebraic Equations . . . . . . . . . . . . . . . . . 261
6.4.1 The Horner Method and De¬‚ation . . . . . . . . . 262
6.4.2 The Newton-Horner Method . . . . . . . . . . . . 263
6.4.3 The Muller Method . . . . . . . . . . . . . . . . . 267
6.5 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . 269
6.6 Post-Processing Techniques for Iterative Methods . . . . . 272
6.6.1 Aitken™s Acceleration . . . . . . . . . . . . . . . . 272

. 1
( : 95)



. . >>