Numerical Mathematics

by Quarteroni, Alfio; Sacco, Riccardo; Saleri, Fausto

• ISBN13: 9783540346586
• ISBN10: 3540346589
• Edition: 2nd
• Format: Hardcover
• Copyright: 2006-12-04
• Publisher: SPRINGER VERLAG

Summary

Numerical mathematics proposes, develops, analyzes and applies methods from scientific computing to several fields including analysis, linear algebra, geometry, approximation theory, functional equations, optimization and differential equations.This book provides the mathematical foundations of numerical methods and demonstrate their performance on examples, exercises and real-life applications. This is done using the MATLAB software environment, which allows an easy implementation and testing of the algorithms for any specific class of problems.The book is addressed to students in Engineering, Mathematics, Physics and Computer Sciences. The attention to applications and software development makes it valuable also for users in a wide variety of professional fields.In this second edition, the readability of pictures, tables and program headings has been improved. Several changes in the chapters on iterative methods and on polynomial approximation have also been added.

Author Biography

Alfio Quarteroni (see http://www.cirs-tm.org/researchers/researchers.php?id=319):Author of a huge amount of booksProfessor and Chair of Modelling and Scientific Computing (CMCS) at the Institute of Analysis and Scientific Computing of EPFL, Lausanne (Switzerland), since 1998. Professor of Numerical Analysis at the Politecnico di Milano (Italy) since 1989 and Scientific Director of MOX, since 2002. Research Interests :His current research involves computational fluid dynamics, modelling and simulation of haemodynamics, numerical analysis of domain decomposition methods with application to multi-physics problems. Awards and Honors :NASA Group Achievement Award for the pioneering work in Computational Fluid Dynamics as a member of the ICASE numerical analysis and algorithms group, 1992. Member of the Lombard Academy of Science (Istituto Lombardo di Scienze e Lettere) (since 1995). Chairman of the Mathematics and Computer Science RTN evaluation panel of the E.U., 1999. Co-chairman (with P.L.Lions) of the AMIF research programme of the European Science Foundation (1996-2001). Recipient of the Galileian Chair, Scuola Normale Superiore, Pisa, Italy (2001). Premio Agrumello 2003. Laurea Honoris Causa in Naval Engineering , University of Trieste, Italy, October 2003. Recipient of one of the SIAM Outstanding Paper Prize 2004 (for a paper in collaboration with A. Veneziani and P. Zunino). IACM (International Association for Computational Mechanics), Fellow Award, 2004. Member of Accademia Nazionale dei Lincei, (Italian National Academy of Sciences) 2004. President of the Evaluation Panel "Mathematics and Computer Sciences" of CIVR, 2005.

Table of Contents

Getting Started
Foundations of Matrix Analysis	p. 3
Vector Spaces	p. 3
Matrices	p. 5
Operations with Matrices	p. 6
Inverse of a Matrix	p. 7
Matrices and Linear Mappings	p. 8
Operations with Block-Partitioned Matrices	p. 9
Trace and Determinant of a Matrix	p. 10
Rank and Kernel of a Matrix	p. 11
Special Matrices	p. 12
Block Diagonal Matrices	p. 12
Trapezoidal and Triangular Matrices	p. 12
Banded Matrices	p. 13
Eigenvalues and Eigenvectors	p. 13
Similarity Transformations	p. 15
The Singular Value Decomposition (SVD)	p. 17
Scalar Product and Norms in Vector Spaces	p. 18
Matrix Norms	p. 22
Relation between Norms and the Spectral Radius of a Matrix	p. 25
Sequences and Series of Matrices	p. 26
Positive Definite, Diagonally Dominant and M-matrices	p. 27
Exercises	p. 30
Principles of Numerical Mathematics	p. 33
Well-posedness and Condition Number of a Problem	p. 33
Stability of Numerical Methods	p. 37
Relations between Stability and Convergence	p. 40
A priori and a posteriori Analysis	p. 42
Sources of Error in Computational Models	p. 43
Machine Representation of Numbers	p. 45
The Positional System	p. 45
The Floating-point Number System	p. 46
Distribution of Floating-point Numbers	p. 49
IEC/IEEE Arithmetic	p. 49
Rounding of a Real Number in its Machine Representation	p. 50
Machine Floating-point Operations	p. 52
Exercises	p. 54
Numerical Linear Algebra
Direct Methods for the Solution of Linear Systems	p. 59
Stability Analysis of Linear Systems	p. 60
The Condition Number of a Matrix	p. 60
Forward a priori Analysis	p. 62
Backward a priori Analysis	p. 65
A posteriori Analysis	p. 65
Solution of Triangular Systems	p. 66
Implementation of Substitution Methods	p. 67
Rounding Error Analysis	p. 69
Inverse of a Triangular Matrix	p. 70
The Gaussian Elimination Method (GEM) and LU Factorization	p. 70
GEM as a Factorization Method	p. 73
The Effect of Rounding Errors	p. 78
Implementation of LU Factorization	p. 78
Compact Forms of Factorization	p. 80
Other Types of Factorization	p. 81
LDM[superscript T] Factorization	p. 81
Symmetric and Positive Definite Matrices: The Cholesky Factorization	p. 82
Rectangular Matrices: The QR Factorization	p. 84
Pivoting	p. 87
Computing the Inverse of a Matrix	p. 91
Banded Systems	p. 92
Tridiagonal Matrices	p. 93
Implementation Issues	p. 94
Block Systems	p. 96
Block LU Factorization	p. 97
Inverse of a Block-partitioned Matrix	p. 97
Block Tridiagonal Systems	p. 98
Sparse Matrices	p. 99
The Cuthill-McKee Algorithm	p. 102
Decomposition into Substructures	p. 103
Nested Dissection	p. 105
Accuracy of the Solution Achieved Using GEM	p. 106
An Approximate Computation of K(A)	p. 108
Improving the Accuracy of GEM	p. 112
Scaling	p. 112
Iterative Refinement	p. 113
Undetermined Systems	p. 114
Applications	p. 117
Nodal Analysis of a Structured Frame	p. 117
Regularization of a Triangular Grid	p. 120
Exercises	p. 123
Iterative Methods for Solving Linear Systems	p. 125
On the Convergence of Iterative Methods	p. 125
Linear Iterative Methods	p. 128
Jacobi, Gauss-Seidel and Relaxation Methods	p. 128
Convergence Results for Jacobi and Gauss-Seidel Methods	p. 130
Convergence Results for the Relaxation Method	p. 132
A priori Forward Analysis	p. 133
Block Matrices	p. 134
Symmetric Form of the Gauss-Seidel and SOR Methods	p. 135
Implementation Issues	p. 137
Stationary and Nonstationary Iterative Methods	p. 138
Convergence Analysis of the Richardson Method	p. 139
Preconditioning Matrices	p. 141
The Gradient Method	p. 148
The Conjugate Gradient Method	p. 152
The Preconditioned Conjugate Gradient Method	p. 158
The Alternating-Direction Method	p. 160
Methods Based on Krylov Subspace Iterations	p. 160
The Arnoldi Method for Linear Systems	p. 164
The GMRES Method	p. 167
The Lanczos Method for Symmetric Systems	p. 168
The Lanczos Method for Unsymmetric Systems	p. 170
Stopping Criteria	p. 173
A Stopping Test Based on the Increment	p. 174
A Stopping Test Based on the Residual	p. 175
Applications	p. 175
Analysis of an Electric Network	p. 176
Finite Difference Analysis of Beam Bending	p. 178
Exercises	p. 180
Approximation of Eigenvalues and Eigenvectors	p. 183
Geometrical Location of the Eigenvalues	p. 183
Stability and Conditioning Analysis	p. 186
A priori Estimates	p. 187
A posteriori Estimates	p. 190
The Power Method	p. 192
Approximation of the Eigenvalue of Largest Module	p. 192
Inverse Iteration	p. 195
Implementation Issues	p. 196
The QR Iteration	p. 199
The Basic QR Iteration	p. 201
The QR Method for Matrices in Hessenberg Form	p. 203
Householder and Givens Transformation Matrices	p. 203
Reducing a Matrix in Hessenberg Form	p. 207
QR Factorization of a Matrix in Hessenberg Form	p. 209
The Basic QR Iteration Starting from Upper Hessenberg Form	p. 209
Implementation of Transformation Matrices	p. 212
The QR Iteration with Shifting Techniques	p. 214
The QR Method with Single Shift	p. 215
The QR Method with Double Shift	p. 217
Computing the Eigenvectors and the SVD of a Matrix	p. 220
The Hessenberg Inverse Iteration	p. 220
Computing the Eigenvectors from the Schur Form of a Matrix	p. 221
Approximate Computation of the SVD of a Matrix	p. 222
The Generalized Eigenvalue Problem	p. 223
Computing the Generalized Real Schur Form	p. 224
Generalized Real Schur Form of Symmetric-Definite Pencils	p. 225
Methods for Eigenvalues of Symmetric Matrices	p. 226
The Jacobi Method	p. 226
The Method of Sturm Sequences	p. 229
The Lanczos Method	p. 233
Applications	p. 236
Analysis of the Buckling of a Beam	p. 236
Free Dynamic Vibration of a Bridge	p. 238
Exercises	p. 240
Around Functions and Functionals
Rootfinding for Nonlinear Equations	p. 247
Conditioning of a Nonlinear Equation	p. 248
A Geometric Approach to Rootfinding	p. 250
The Bisection Method	p. 250
The Methods of Chord, Secant and Regula Falsi and Newton's Method	p. 253
The Dekker-Brent Method	p. 259
Fixed-point Iterations for Nonlinear Equations	p. 260
Convergence Results for Some Fixed-point Methods	p. 263
Zeros of Algebraic Equations	p. 264
The Horner Method and Deflation	p. 265
The Newton-Horner Method	p. 266
The Muller Method	p. 269
Stopping Criteria	p. 273
Post-processing Techniques for Iterative Methods	p. 275
Aitken's Acceleration	p. 275
Techniques for Multiple Roots	p. 278
Applications	p. 280
Analysis of the State Equation for a Real Gas	p. 280
Analysis of a Nonlinear Electrical Circuit	p. 281
Exercises	p. 283
Nonlinear Systems and Numerical Optimization	p. 285
Solution of Systems of Nonlinear Equations	p. 286
Newton's Method and Its Variants	p. 286
Modified Newton's Methods	p. 288
Quasi-Newton Methods	p. 292
Secant-like Methods	p. 292
Fixed-point Methods	p. 295
Unconstrained Optimization	p. 298
Direct Search Methods	p. 300
Descent Methods	p. 305
Line Search Techniques	p. 307
Descent Methods for Quadratic Functions	p. 309
Newton-like Methods for Function Minimization	p. 311
Quasi-Newton Methods	p. 312
Secant-like methods	p. 313
Constrained Optimization	p. 315
Kuhn-Tucker Necessary Conditions for Nonlinear Programming	p. 318
The Penalty Method	p. 319
The Method of Lagrange Multipliers	p. 321
Applications	p. 325
Solution of a Nonlinear System Arising from Semiconductor Device Simulation	p. 325
Nonlinear Regularization of a Discretization Grid	p. 328
Exercises	p. 330
Polynomial Interpolation	p. 333
Polynomial Interpolation	p. 333
The Interpolation Error	p. 335
Drawbacks of Polynomial Interpolation on Equally Spaced Nodes and Runge's Counterexample	p. 336
Stability of Polynomial Interpolation	p. 337
Newton Form of the Interpolating Polynomial	p. 339
Some Properties of Newton Divided Differences	p. 341
The Interpolation Error Using Divided Differences	p. 343
Barycentric Lagrange Interpolation	p. 344
Piecewise Lagrange Interpolation	p. 346
Hermite-Birkoff Interpolation	p. 349
Extension to the Two-Dimensional Case	p. 351
Polynomial Interpolation	p. 351
Piecewise Polynomial Interpolation	p. 352
Approximation by Splines	p. 355
Interpolatory Cubic Splines	p. 357
B-splines	p. 361
Splines in Parametric Form	p. 365
Bezier Curves and Parametric B-splines	p. 367
Applications	p. 370
Finite Element Analysis of a Clamped Beam	p. 370
Geometric Reconstruction Based on Computer Tomographies	p. 374
Exercises	p. 375
Numerical Integration	p. 379
Quadrature Formulae	p. 379
Interpolatory Quadratures	p. 381
The Midpoint or Rectangle Formula	p. 381
The Trapezoidal Formula	p. 383
The Cavalieri-Simpson Formula	p. 385
Newton-Cotes Formulae	p. 386
Composite Newton-Cotes Formulae	p. 392
Hermite Quadrature Formulae	p. 394
Richardson Extrapolation	p. 396
Romberg Integration	p. 397
Automatic Integration	p. 400
Nonadaptive Integration Algorithms	p. 400
Adaptive Integration Algorithms	p. 402
Singular Integrals	p. 406
Integrals of Functions with Finite Jump Discontinuities	p. 406
Integrals of Infinite Functions	p. 407
Integrals over Unbounded Intervals	p. 409
Multidimensional Numerical Integration	p. 411
The Method of Reduction Formula	p. 411
Two-Dimensional Composite Quadratures	p. 413
Monte Carlo Methods for Numerical Integration	p. 416
Applications	p. 417
Computation of an Ellipsoid Surface	p. 417
Computation of the Wind Action on a Sailboat Mast	p. 418
Exercises	p. 421
Transforms, Differentiation and Problem Discretization
Orthogonal Polynomials in Approximation Theory	p. 425
Approximation of Functions by Generalized Fourier Series	p. 425
The Chebyshev Polynomials	p. 427
The Legendre Polynomials	p. 428
Gaussian Integration and Interpolation	p. 429
Chebyshev Integration and Interpolation	p. 433
Legendre Integration and Interpolation	p. 436
Gaussian Integration over Unbounded Intervals	p. 438
Programs for the Implementation of Gaussian Quadratures	p. 439
Approximation of a Function in the Least-Squares Sense	p. 441
Discrete Least-Squares Approximation	p. 442
The Polynomial of Best Approximation	p. 443
Fourier Trigonometric Polynomials	p. 445
The Gibbs Phenomenon	p. 449
The Fast Fourier Transform	p. 450
Approximation of Function Derivatives	p. 452
Classical Finite Difference Methods	p. 452
Compact Finite Differences	p. 454
Pseudo-Spectral Derivative	p. 458
Transforms and Their Applications	p. 460
The Fourier Transform	p. 460
(Physical) Linear Systems and Fourier Transform	p. 463
The Laplace Transform	p. 465
The Z-Transform	p. 467
The Wavelet Transform	p. 468
The Continuous Wavelet Transform	p. 468
Discrete and Orthonormal Wavelets	p. 471
Applications	p. 472
Numerical Computation of Blackbody Radiation	p. 472
Numerical Solution of Schrodinger Equation	p. 474
Exercises	p. 476
Numerical Solution of Ordinary Differential Equations	p. 479
The Cauchy Problem	p. 479
One-Step Numerical Methods	p. 482
Analysis of One-Step Methods	p. 483
The Zero-Stability	p. 484
Convergence Analysis	p. 486
The Absolute Stability	p. 489
Difference Equations	p. 492
Multistep Methods	p. 497
Adams Methods	p. 500
BDF Methods	p. 502
Analysis of Multistep Methods	p. 502
Consistency	p. 502
The Root Conditions	p. 504
Stability and Convergence Analysis for Multistep Methods	p. 505
Absolute Stability of Multistep Methods	p. 509
Predictor-Corrector Methods	p. 511
Runge-Kutta (RK) Methods	p. 518
Derivation of an Explicit RK Method	p. 521
Stepsize Adaptivity for RK Methods	p. 521
Implicit RK Methods	p. 523
Regions of Absolute Stability for RK Methods	p. 525
Systems of ODEs	p. 526
Stiff Problems	p. 528
Applications	p. 530
Analysis of the Motion of a Frictionless Pendulum	p. 531
Compliance of Arterial Walls	p. 532
Exercises	p. 536
Two-Point Boundary Value Problems	p. 539
A Model Problem	p. 539
Finite Difference Approximation	p. 541
Stability Analysis by the Energy Method	p. 542
Convergence Analysis	p. 546
Finite Differences for Two-Point Boundary Value Problems with Variable Coefficients	p. 548
The Spectral Collocation Method	p. 550
The Galerkin Method	p. 552
Integral Formulation of Boundary Value Problems	p. 552
A Quick Introduction to Distributions	p. 554
Formulation and Properties of the Galerkin Method	p. 555
Analysis of the Galerkin Method	p. 556
The Finite Element Method	p. 558
Implementation Issues	p. 564
Spectral Methods	p. 566
Advection-Diffusion Equations	p. 568
Galerkin Finite Element Approximation	p. 569
The Relationship between Finite Elements and Finite Differences; the Numerical Viscosity	p. 572
Stabilized Finite Element Methods	p. 574
A Quick Glance at the Two-Dimensional Case	p. 580
Applications	p. 583
Lubrication of a Slider	p. 583
Vertical Distribution of Spore Concentration over Wide Regions	p. 584
Exercises	p. 586
Parabolic and Hyperbolic Initial Boundary Value Problems	p. 589
The Heat Equation	p. 589
Finite Difference Approximation of the Heat Equation	p. 591
Finite Element Approximation of the Heat Equation	p. 593
Stability Analysis of the [theta]-Method	p. 595
Space-Time Finite Element Methods for the Heat Equation	p. 601
Hyperbolic Equations: A Scalar Transport Problem	p. 604
Systems of Linear Hyperbolic Equations	p. 607
The Wave Equation	p. 608
The Finite Difference Method for Hyperbolic Equations	p. 609
Discretization of the Scalar Equation	p. 610
Analysis of Finite Difference Methods	p. 611
Consistency	p. 612
Stability	p. 612
The CFL Condition	p. 613
Von Neumann Stability Analysis	p. 615
Dissipation and Dispersion	p. 618
Equivalent Equations	p. 619
Finite Element Approximation of Hyperbolic Equations	p. 624
Space Discretization with Continuous and Discontinuous Finite Elements	p. 625
Time Discretization	p. 627
Applications	p. 630
Heat Conduction in a Bar	p. 630
A Hyperbolic Model for Blood Flow Interaction with Arterial Walls	p. 630
Exercises	p. 632
References	p. 635
Index of MATLAB Programs	p. 645
Index	p. 649
Table of Contents provided by Ingram. All Rights Reserved.