Quarteroni / Sacco / Saleri Numerical Mathematics

1. Auflage 2000
ISBN: 978-0-387-22750-4
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 720 Seiten

Numerical mathematics is the branch of mathematics that 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. Other disciplines, such as physics, the natural and biological sciences, engineering, and economics and the financial sciences frequently give rise to problems that need scientific 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.

One of the purposes of this book is to provide the mathematical foundations of numerical methods, to analyze their basic theoretical properties (stability, accuracy, computational complexity) and demonstrate their performances on examples and counterexamples which outline their pros and cons. This is done using the MATLAB software environment which is user-friendly and widely adopted. Within any specific class of problems, the most appropriate scientific computing algorithms are reviewed, their theoretical analyses are carried out and the expected results are verified on a MATLAB computer implementation. Every chapter is supplied with examples, exercises and applications of the discussed theory to the solution of real-life problems.

This book is addressed to senior undergraduate and graduate students with particular focus on degree courses in Engineering, Mathematics, Physics and Computer Sciences. The attention which is paid to the applications and the related development of software makes it valuable also for researchers and users of scientific computing in a large variety of professional fields.

In this second edition, the readability of pictures, tables and program headings have been improved. Several changes in the chapters on iterative methods and on polynomial approximation have also been added.

Written for:
Graduate students, researchers

Keywords:
Matlab
calculation of matrices
linear algebra
numerical analysis

Autoren/Hrsg.

Quarteroni, Alfio

Sacco, Riccardo

Saleri, Fausto

Inhaltsverzeichnis

1;Preface;7
2;Contents;10
3;1 Foundations of Matrix Analysis;20
3.1;1.1 Vector Spaces;20
3.2;1.2 Matrices;22
3.3;1.3 Operations with Matrices;24
3.4;1.4 Trace and Determinant of a Matrix;27
3.5;1.5 Rank and Kernel of a Matrix;28
3.6;1.6 Special Matrices;29
3.7;1.7 Eigenvalues and Eigenvectors;31
3.8;1.8 Similarity Transformations;33
3.9;1.9 The Singular Value Decomposition (SVD);35
3.10;1.10 Scalar Product and Norms in Vector Spaces;36
3.11;1.11 Matrix Norms;40
3.12;1.12 Positive De.nite, Diagonally Dominant and M- matrices;46
3.13;1.13 Exercises;49
4;2 Principles of Numerical Mathematics;52
4.1;2.1 Well-posedness and Condition Number of a Problem;52
4.2;2.2 Stability of Numerical Methods;56
4.3;2.3 A priori and a posteriori Analysis;60
4.4;2.4 Sources of Error in Computational Models;62
4.5;2.5 Machine Representation of Numbers;64
4.6;2.6 Exercises;73
5;3 Direct Methods for the Solution of Linear Systems;76
5.1;3.1 Stability Analysis of Linear Systems;77
5.2;3.2 Solution of Triangular Systems;84
5.3;3.3 The Gaussian Elimination Method (GEM) and LU Factorization;87
5.4;3.4 Other Types of Factorization;98
5.5;3.5 Pivoting;104
5.6;3.6 Computing the Inverse of a Matrix;108
5.7;3.7 Banded Systems;109
5.8;3.8 Block Systems;112
5.9;3.9 Sparse Matrices;116
5.10;3.10 Accuracy of the Solution Achieved Using GEM;122
5.11;3.11 An Approximate Computation of K(A);125
5.12;3.12 Improving the Accuracy of GEM;128
5.13;3.13 Undetermined Systems;131
5.14;3.14 Applications;134
5.15;3.15 Exercises;140
6;4 Iterative Methods for Solving Linear Systems;142
6.1;4.1 On the Convergence of Iterative Methods;142
6.2;4.2 Linear Iterative Methods;145
6.3;4.3 Stationary and Nonstationary Iterative Methods;155
6.4;4.4 Methods Based on Krylov Subspace Iterations;178
6.5;4.5 The Lanczos Method for Unsymmetric Systems;187
6.6;4.6 Stopping Criteria;190
6.7;4.7 Applications;193
6.8;4.8 Exercises;198
7;5 Approximation of Eigenvalues and Eigenvectors;201
7.1;5.1 Geometrical Location of the Eigenvalues;201
7.2;5.2 Stability and Conditioning Analysis;204
7.3;5.3 The Power Method;210
7.4;5.4 The QR Iteration;218
7.5;5.5 The Basic QR Iteration;219
7.6;5.6 The QR Method for Matrices in Hessenberg Form;221
7.7;5.7 The QR Iteration with Shifting Techniques;233
7.8;5.8 Computing the Eigenvectors and the SVD of a Matrix;239
7.9;5.9 The Generalized Eigenvalue Problem;242
7.10;5.10 Methods for Eigenvalues of Symmetric matrices;245
7.11;5.11 The Lanczos Method;251
7.12;5.12 Applications;253
7.13;5.13 Exercises;258
8;6 Rootfinding for Nonlinear Equations;262
8.1;6.1 Conditioning of a Nonlinear Equation;263
8.2;6.2 A Geometric Approach to Root.nding;265
8.3;6.3 Fixed-point Iterations for Nonlinear Equations;274
8.4;6.4 Zeros of Algebraic Equations;278
8.5;6.5 Stopping Criteria;286
8.6;6.6 Post-processing Techniques for Iterative Methods;289
8.7;6.7 Applications;293
8.8;6.8 Exercises;296
9;7 Nonlinear Systems and Numerical Optimization;298
9.1;7.1 Solution of Systems of Nonlinear Equations;299
9.2;7.2 Unconstrained Optimization;311
9.3;7.3 Constrained Optimization;328
9.4;7.4 Applications;336
9.5;7.5 Exercises;342
10;8 Polynomial Interpolation;344
10.1;8.1 Polynomial Interpolation;345
10.2;8.2 Newton Form of the Interpolating Polynomial;350
10.3;8.3 Piecewise Lagrange Interpolation;355
10.4;8.4 Hermite-Birko. Interpolation;358
10.5;8.5 Extension to the Two-Dimensional Case;360
10.6;8.6 Approximation by Splines;365
10.7;8.7 Splines in Parametric Form;374
10.8;8.8 Applications;379
10.9;8.9 Exercises;385
11;9 Numerical Integration;388
11.1;9.1 Quadrature Formulae;388
11.2;9.2 Interpolatory Quadratures;390
11.3;9.3 Newton-Cotes Formulae;395
11.4;9.4 Composite Newton-Cotes Formulae;400
11.5;9.5 Hermite Quadrature Formulae;403
11.6;9.6 Richardson Extrapolation;404
11.7;9.7 Automatic Integration;408
11.8;9.8 Singular Integrals;415
11.9;9.9 Multidimensional Numerical Integration;419
11.10;9.10 Applications;425
11.11;9.11 Exercises;429
12;10 Orthogonal Polynomials in Approximation Theory;432
12.1;10.1 Approximation of Functions by Generalized Fourier Series;432
12.2;10.2 Gaussian Integration and Interpolation;436
12.3;10.3 Chebyshev Integration and Interpolation;441
12.4;10.4 Legendre Integration and Interpolation;443
12.5;10.5 Gaussian Integration over Unbounded Intervals;445
12.6;10.6 Programs for the Implementation of Gaussian Quadratures;446
12.7;10.7 Approximation of a Function in the Least- Squares Sense;448
12.8;10.8 The Polynomial of Best Approximation;450
12.9;10.9 Fourier Trigonometric Polynomials;452
12.10;10.10 Approximation of Function Derivatives;459
12.11;10.11 Transforms and Their Applications;467
12.12;10.12 The Wavelet Transform;475
12.13;10.13 Applications;480
12.14;10.14 Exercises;484
13;11 Numerical Solution of Ordinary Di . erential Equations;486
13.1;11.1 The Cauchy Problem;486
13.2;11.2 One-Step Numerical Methods;489
13.3;11.3 Analysis of One-Step Methods;490
13.4;11.4 Di.erence Equations;499
13.5;11.5 Multistep Methods;504
13.6;11.6 Analysis of Multistep Methods;509
13.7;11.7 Predictor-Corrector Methods;519
13.8;11.8 Runge-Kutta (RK) Methods;525
13.9;11.9 Systems of ODEs;534
13.10;11.10 Sti. Problems;536
13.11;11.11 Applications;538
13.12;11.12 Exercises;544
14;12 Two-Point Boundary Value Problems;548
14.1;12.1 A Model Problem;548
14.2;12.2 Finite Di.erence Approximation;550
14.3;12.3 The Spectral Collocation Method;559
14.4;12.4 The Galerkin Method;561
14.5;12.5 Advection-Di.usion Equations;577
14.6;12.6 A Quick Glance to the Two-Dimensional Case;589
14.7;12.7 Applications;592
14.8;12.8 Exercises;595
15;13 Parabolic and Hyperbolic Initial Boundary Value Problems;597
15.1;13.1 The Heat Equation;597
15.2;13.2 Finite Di.erence Approximation of the Heat Equation;600
15.3;13.3 Finite Element Approximation of the Heat Equation;602
15.4;13.4 Space-Time Finite Element Methods for the Heat Equation;609
15.5;13.5 Hyperbolic Equations: A Scalar Transport Problem;613
15.6;13.6 Systems of Linear Hyperbolic Equations;615
15.7;13.7 The Finite Di.erence Method for Hyperbolic Equations;618
15.8;13.8 Analysis of Finite Di.erence Methods;621
15.9;13.9 Dissipation and Dispersion;627
15.10;13.10 Finite Element Approximation of Hyperbolic Equations;634
15.11;13.11 Applications;639
15.12;13.12 Exercises;641
16;References;643
17;Index of MATLAB Programs;658
18;Index;661

Leseproben

5 Approximation of Eigenvalues and Eigenvectors (p. 183)

In this chapter we deal with approximations of the eigenvalues and eigenvectors of a matrix A ¸ Cn×n. Two main classes of numerical methods exist to this purpose, partial methods, which compute the extremal eigenvalues of A (that is, those having maximum and minimum module), or global methods, which approximate the whole spectrum of A.

It is worth noting that methods which are introduced to solve the matrix eigenvalue problem are not necessarily suitable for calculating the matrix eigenvectors. For example, the power method (a partial method, see Section 5.3) provides an approximation to a particular eigenvalue/eigenvector pair. The QR method (a global method, see Section 5.5) instead computes the real Schur form of A, a canonical form that displays all the eigenvalues of A but not its eigenvectors. These eigenvectors can be computed, starting from the real Schur form of A, with an extra amount of work, as described in Section 5.8.2.

Finally, some ad hoc methods for dealing e.ectively with the special case where A is a symmetric (n × n) matrix are considered in Section 5.10.

5.1 Geometrical Location of the Eigenvalues

Since the eigenvalues of A are the roots of the characteristic polynomial pA(?) (see Section 1.7), iterative methods must be used for their approximation when n ¡Ý 5. Knowledge of eigenvalue location in the complex plane can thus be helpful in accelerating the convergence of the process.