Numerical Mathematics (eBook)

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

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.