Applied Mathematics - Numerical Mathematics

【实例简介】Applied Mathematics - Numerical Mathematics

【实例截图】

【核心代码】

Contents
Part I Getting Started
1 Foundations of Matrix Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 Operations with Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.1 Inverse of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.3.2 Matrices and Linear Mappings . . . . . . . . . . . . . . . . . . . 8
1.3.3 Operations with Block-Partitioned Matrices . . . . . . . 9
1.4 Trace and Determinant of a Matrix . . . . . . . . . . . . . . . . . . . . . . 10
1.5 Rank and Kernel of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.6 Special Matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.1 Block Diagonal Matrices . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6.2 Trapezoidal and Triangular Matrices . . . . . . . . . . . . . . 12
1.6.3 Banded Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8 Similarity Transformations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.9 The Singular Value Decomposition (SVD) . . . . . . . . . . . . . . . . 17
1.10 Scalar Product and Norms in Vector Spaces . . . . . . . . . . . . . . 18
1.11 Matrix Norms. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
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 Definite, 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 . . . . . . . . . . . . . . . . . . . . . . . 42
X Contents
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 . . . . . . . 59
3.1 Stability Analysis of Linear Systems . . . . . . . . . . . . . . . . . . . . . 60
3.1.1 The Condition Number of a Matrix . . . . . . . . . . . . . . . 60
3.1.2 Forward a priori Analysis. . . . . . . . . . . . . . . . . . . . . . . . 62
3.1.3 Backward a priori Analysis . . . . . . . . . . . . . . . . . . . . . . 65
3.1.4 A posteriori Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2 Solution of Triangular Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.2.1 Implementation of Substitution Methods . . . . . . . . . . 67
3.2.2 Rounding Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . 69
3.2.3 Inverse of a Triangular Matrix . . . . . . . . . . . . . . . . . . . 70
3.3 The Gaussian Elimination Method (GEM) and LU
Factorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.3.1 GEM as a Factorization Method . . . . . . . . . . . . . . . . . 73
3.3.2 The Effect of Rounding Errors . . . . . . . . . . . . . . . . . . . 78
3.3.3 Implementation of LU Factorization . . . . . . . . . . . . . . 78
3.3.4 Compact Forms of Factorization. . . . . . . . . . . . . . . . . . 80
3.4 Other Types of Factorization. . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.4.1 LDM T Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
3.4.2 Symmetric and Positive Definite Matrices: The
Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.4.3 Rectangular Matrices: The QR Factorization. . . . . . . 84
3.5 Pivoting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.6 Computing the Inverse of a Matrix . . . . . . . . . . . . . . . . . . . . . . 91
3.7 Banded Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.7.1 Tridiagonal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.7.2 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.8 Block Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.8.1 Block LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.8.2 Inverse of a Block-partitioned Matrix . . . . . . . . . . . . . 97
3.8.3 Block Tridiagonal Systems. . . . . . . . . . . . . . . . . . . . . . . 98
3.9 Sparse Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Contents XI
3.9.1 The Cuthill-McKee Algorithm . . . . . . . . . . . . . . . . . . . 102
3.9.2 Decomposition into Substructures . . . . . . . . . . . . . . . . 103
3.9.3 Nested Dissection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.10 Accuracy of the Solution Achieved Using GEM. . . . . . . . . . . . 106
3.11 An Approximate Computation of K(A) . . . . . . . . . . . . . . . . . . 108
3.12 Improving the Accuracy of GEM . . . . . . . . . . . . . . . . . . . . . . . . 112
3.12.1 Scaling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
3.12.2 Iterative Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
3.13 Undetermined Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.14 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
3.14.1 Nodal Analysis of a Structured Frame. . . . . . . . . . . . . 117
3.14.2 Regularization of a Triangular Grid . . . . . . . . . . . . . . . 120
3.15 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4 Iterative Methods for Solving Linear Systems . . . . . . . . . . . . 125
4.1 On the Convergence of Iterative Methods . . . . . . . . . . . . . . . . . 125
4.2 Linear Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
4.2.1 Jacobi, Gauss-Seidel and Relaxation Methods . . . . . . 128
4.2.2 Convergence Results for Jacobi and Gauss-Seidel
Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
4.2.3 Convergence Results for the Relaxation Method . . . . 132
4.2.4 A priori Forward Analysis . . . . . . . . . . . . . . . . . . . . . . . 133
4.2.5 Block Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
4.2.6 Symmetric Form of the Gauss-Seidel and SOR
Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
4.2.7 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 137
4.3 Stationary and Nonstationary Iterative Methods. . . . . . . . . . . 138
4.3.1 Convergence Analysis of the Richardson Method . . . 139
4.3.2 Preconditioning Matrices . . . . . . . . . . . . . . . . . . . . . . . . 141
4.3.3 The Gradient Method. . . . . . . . . . . . . . . . . . . . . . . . . . . 148
4.3.4 The Conjugate Gradient Method . . . . . . . . . . . . . . . . . 152
4.3.5 The Preconditioned Conjugate Gradient Method . . . 158
4.3.6 The Alternating-Direction Method. . . . . . . . . . . . . . . . 160
4.4 Methods Based on Krylov Subspace Iterations . . . . . . . . . . . . 160
4.4.1 The Arnoldi Method for Linear Systems. . . . . . . . . . . 164
4.4.2 The GMRES Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.4.3 The Lanczos Method for Symmetric Systems. . . . . . . 168
4.5 The Lanczos Method for Unsymmetric Systems . . . . . . . . . . . 170
4.6 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.6.1 A Stopping Test Based on the Increment . . . . . . . . . . 174
4.6.2 A Stopping Test Based on the Residual . . . . . . . . . . . 175
4.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
4.7.1 Analysis of an Electric Network . . . . . . . . . . . . . . . . . . 176
4.7.2 Finite Difference Analysis of Beam Bending. . . . . . . . 178
4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
XII Contents
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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
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. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
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 . . 203
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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
5.6.5 Implementation of Transformation Matrices. . . . . . . . 212
5.7 The QR Iteration with Shifting Techniques . . . . . . . . . . . . . . . 214
5.7.1 The QR Method with Single Shift . . . . . . . . . . . . . . . . 215
5.7.2 The QR Method with Double Shift . . . . . . . . . . . . . . . 217
5.8 Computing the Eigenvectors and the SVD of a Matrix . . . . . 220
5.8.1 The Hessenberg Inverse Iteration . . . . . . . . . . . . . . . . . 220
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. . . . . . . . . . . . . . . . . . . . . 223
5.9.1 Computing the Generalized Real Schur Form . . . . . . 224
5.9.2 Generalized Real Schur Form of Symmetric-Definite
Pencils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
5.10 Methods for Eigenvalues of Symmetric Matrices . . . . . . . . . . . 226
5.10.1 The Jacobi Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
5.10.2 The Method of Sturm Sequences . . . . . . . . . . . . . . . . . 229
5.11 The Lanczos Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
5.12 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
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
Contents XIII
Part III Around Functions and Functionals
6 Rootfinding for Nonlinear Equations. . . . . . . . . . . . . . . . . . . . . . 247
6.1 Conditioning of a Nonlinear Equation . . . . . . . . . . . . . . . . . . . . 248
6.2 A Geometric Approach to Rootfinding . . . . . . . . . . . . . . . . . . . 250
6.2.1 The Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . 250
6.2.2 The Methods of Chord, Secant and Regula Falsi
and Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . 253
6.2.3 The Dekker-Brent Method. . . . . . . . . . . . . . . . . . . . . . . 259
6.3 Fixed-point Iterations for Nonlinear Equations . . . . . . . . . . . . 260
6.3.1 Convergence Results for Some Fixed-point
Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
6.4 Zeros of Algebraic Equations. . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
6.4.1 The Horner Method and Deflation . . . . . . . . . . . . . . . . 265
6.4.2 The Newton-Horner Method . . . . . . . . . . . . . . . . . . . . . 266
6.4.3 The Muller Method. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269
6.5 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
6.6 Post-processing Techniques for Iterative Methods . . . . . . . . . . 275
6.6.1 Aitken’s Acceleration . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
6.6.2 Techniques for Multiple Roots . . . . . . . . . . . . . . . . . . . 278
6.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
6.7.1 Analysis of the State Equation for a Real Gas . . . . . 280
6.7.2 Analysis of a Nonlinear Electrical Circuit . . . . . . . . . . 281
6.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
7 Nonlinear Systems and Numerical Optimization . . . . . . . . . . 285
7.1 Solution of Systems of Nonlinear Equations . . . . . . . . . . . . . . . 286
7.1.1 Newton’s Method and Its Variants. . . . . . . . . . . . . . . . 286
7.1.2 Modified Newton’s Methods . . . . . . . . . . . . . . . . . . . . . 288
7.1.3 Quasi-Newton Methods . . . . . . . . . . . . . . . . . . . . . . . . . 292
7.1.4 Secant-like Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
7.1.5 Fixed-point Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
7.2 Unconstrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298
7.2.1 Direct Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 300
7.2.2 Descent Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 305
7.2.3 Line Search Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 307
7.2.4 Descent Methods for Quadratic Functions . . . . . . . . . 309
7.2.5 Newton-like Methods for Function Minimization. . . . 311
7.2.6 Quasi-Newton Methods . . . . . . . . . . . . . . . . . . . . . . . . . 312
7.2.7 Secant-like methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
7.3 Constrained Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
7.3.1 Kuhn-Tucker Necessary Conditions for Nonlinear
Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318
7.3.2 The Penalty Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319
XIV Contents
7.3.3 The Method of Lagrange Multipliers . . . . . . . . . . . . . . 321
7.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325
7.4.1 Solution of a Nonlinear System Arising from
Semiconductor Device Simulation . . . . . . . . . . . . . . . . 325
7.4.2 Nonlinear Regularization of a Discretization Grid. . . 328
7.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
8 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.1 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
8.1.1 The Interpolation Error . . . . . . . . . . . . . . . . . . . . . . . . . 335
8.1.2 Drawbacks of Polynomial Interpolation on Equally
Spaced Nodes and Runge’s Counterexample . . . . . . . 336
8.1.3 Stability of Polynomial Interpolation. . . . . . . . . . . . . . 337
8.2 Newton Form of the Interpolating Polynomial . . . . . . . . . . . . . 339
8.2.1 Some Properties of Newton Divided Differences . . . . 341
8.2.2 The Interpolation Error Using Divided Differences . . 343
8.3 Barycentric Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . 344
8.4 Piecewise Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 346
8.5 Hermite-Birkoff Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
8.6 Extension to the Two-Dimensional Case . . . . . . . . . . . . . . . . . . 351
8.6.1 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 351
8.6.2 Piecewise Polynomial Interpolation . . . . . . . . . . . . . . . 352
8.7 Approximation by Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
8.7.1 Interpolatory Cubic Splines . . . . . . . . . . . . . . . . . . . . . . 357
8.7.2 B-splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
8.8 Splines in Parametric Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365
8.8.1 B´ ezier Curves and Parametric B-splines . . . . . . . . . . . 367
8.9 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
8.9.1 Finite Element Analysis of a Clamped Beam . . . . . . . 370
8.9.2 Geometric Reconstruction Based on Computer
Tomographies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
8.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
9 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
9.1 Quadrature Formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
9.2 Interpolatory Quadratures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
9.2.1 The Midpoint or Rectangle Formula . . . . . . . . . . . . . . 381
9.2.2 The Trapezoidal Formula . . . . . . . . . . . . . . . . . . . . . . . . 383
9.2.3 The Cavalieri-Simpson Formula . . . . . . . . . . . . . . . . . . 385
9.3 Newton-Cotes Formulae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386
9.4 Composite Newton-Cotes Formulae . . . . . . . . . . . . . . . . . . . . . . 392
9.5 Hermite Quadrature Formulae . . . . . . . . . . . . . . . . . . . . . . . . . . 394
9.6 Richardson Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 396
9.6.1 Romberg Integration. . . . . . . . . . . . . . . . . . . . . . . . . . . . 397
9.7 Automatic Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
Contents XV
9.7.1 Nonadaptive Integration Algorithms . . . . . . . . . . . . . . 400
9.7.2 Adaptive Integration Algorithms . . . . . . . . . . . . . . . . . 402
9.8 Singular Integrals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
9.8.1 Integrals of Functions with Finite Jump
Discontinuities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406
9.8.2 Integrals of Infinite Functions . . . . . . . . . . . . . . . . . . . . 407
9.8.3 Integrals over Unbounded Intervals . . . . . . . . . . . . . . . 409
9.9 Multidimensional Numerical Integration . . . . . . . . . . . . . . . . . . 411
9.9.1 The Method of Reduction Formula . . . . . . . . . . . . . . . 411
9.9.2 Two-Dimensional Composite Quadratures . . . . . . . . . 413
9.9.3 Monte Carlo Methods for Numerical Integration. . . . 416
9.10 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
9.10.1 Computation of an Ellipsoid Surface . . . . . . . . . . . . . . 417
9.10.2 Computation of the Wind Action on a
Sailboat Mast. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
9.11 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 421
Part IV Transforms, Differentiation and Problem Discretization
10 Orthogonal Polynomials in Approximation Theory. . . . . . . . 425
10.1 Approximation of Functions by Generalized Fourier Series . . 425
10.1.1 The Chebyshev Polynomials . . . . . . . . . . . . . . . . . . . . . 427
10.1.2 The Legendre Polynomials. . . . . . . . . . . . . . . . . . . . . . . 428
10.2 Gaussian Integration and Interpolation . . . . . . . . . . . . . . . . . . . 429
10.3 Chebyshev Integration and Interpolation . . . . . . . . . . . . . . . . . 433
10.4 Legendre Integration and Interpolation . . . . . . . . . . . . . . . . . . . 436
10.5 Gaussian Integration over Unbounded Intervals. . . . . . . . . . . . 438
10.6 Programs for the Implementation of Gaussian
Quadratures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
10.7 Approximation of a Function in the Least-Squares Sense. . . . 441
10.7.1 Discrete Least-Squares Approximation . . . . . . . . . . . . 442
10.8 The Polynomial of Best Approximation . . . . . . . . . . . . . . . . . . 443
10.9 Fourier Trigonometric Polynomials. . . . . . . . . . . . . . . . . . . . . . . 445
10.9.1 The Gibbs Phenomenon . . . . . . . . . . . . . . . . . . . . . . . . . 449
10.9.2 The Fast Fourier Transform . . . . . . . . . . . . . . . . . . . . . 450
10.10 Approximation of Function Derivatives . . . . . . . . . . . . . . . . . . . 452
10.10.1 Classical Finite Difference Methods . . . . . . . . . . . . . . . 452
10.10.2 Compact Finite Differences . . . . . . . . . . . . . . . . . . . . . . 454
10.10.3 Pseudo-Spectral Derivative . . . . . . . . . . . . . . . . . . . . . . 458
10.11 Transforms and Their Applications . . . . . . . . . . . . . . . . . . . . . . 460
10.11.1 The Fourier Transform . . . . . . . . . . . . . . . . . . . . . . . . . . 460
10.11.2 (Physical) Linear Systems and Fourier Transform. . . 463
10.11.3 The Laplace Transform . . . . . . . . . . . . . . . . . . . . . . . . . 465
10.11.4 The Z-Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467
XVI Contents
10.12 The Wavelet Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
10.12.1 The Continuous Wavelet Transform. . . . . . . . . . . . . . . 468
10.12.2 Discrete and Orthonormal Wavelets . . . . . . . . . . . . . . 471
10.13 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
10.13.1 Numerical Computation of Blackbody Radiation . . . 472
10.13.2 Numerical Solution of Schrödinger Equation . . . . . . . 474
10.14 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 476
11 Numerical Solution of Ordinary Differential Equations. . . . 479
11.1 The Cauchy Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
11.2 One-Step Numerical Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
11.3 Analysis of One-Step Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 483
11.3.1 The Zero-Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484
11.3.2 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 486
11.3.3 The Absolute Stability . . . . . . . . . . . . . . . . . . . . . . . . . . 489
11.4 Difference Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
11.5 Multistep Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
11.5.1 Adams Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
11.5.2 BDF Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
11.6 Analysis of Multistep Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 502
11.6.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
11.6.2 The Root Conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
11.6.3 Stability and Convergence Analysis for Multistep
Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505
11.6.4 Absolute Stability of Multistep Methods . . . . . . . . . . 509
11.7 Predictor-Corrector Methods. . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
11.8 Runge-Kutta (RK) Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
11.8.1 Derivation of an Explicit RK Method . . . . . . . . . . . . . 521
11.8.2 Stepsize Adaptivity for RK Methods . . . . . . . . . . . . . . 521
11.8.3 Implicit RK Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
11.8.4 Regions of Absolute Stability for RK Methods . . . . . 525
11.9 Systems of ODEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 526
11.10 Stiff Problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
11.11 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
11.11.1 Analysis of the Motion of a Frictionless Pendulum . . 531
11.11.2 Compliance of Arterial Walls . . . . . . . . . . . . . . . . . . . . 532
11.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
12 Two-Point Boundary Value Problems . . . . . . . . . . . . . . . . . . . . . 539
12.1 A Model Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
12.2 Finite Difference Approximation. . . . . . . . . . . . . . . . . . . . . . . . . 541
12.2.1 Stability Analysis by the Energy Method . . . . . . . . . . 542
12.2.2 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
12.2.3 Finite Differences for Two-Point Boundary Value
Problems with Variable Coefficients. . . . . . . . . . . . . . . 548
Contents XVII
12.3 The Spectral Collocation Method. . . . . . . . . . . . . . . . . . . . . . . . 550
12.4 The Galerkin Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 552
12.4.1 Integral Formulation of Boundary Value Problems . . 552
12.4.2 A Quick Introduction to Distributions . . . . . . . . . . . . 554
12.4.3 Formulation and Properties of the Galerkin
Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555
12.4.4 Analysis of the Galerkin Method . . . . . . . . . . . . . . . . . 556
12.4.5 The Finite Element Method . . . . . . . . . . . . . . . . . . . . . 558
12.4.6 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . 564
12.4.7 Spectral Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
12.5 Advection-Diffusion Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 568
12.5.1 Galerkin Finite Element Approximation . . . . . . . . . . . 569
12.5.2 The Relationship between Finite Elements and
Finite Differences; the Numerical Viscosity . . . . . . . . 572
12.5.3 Stabilized Finite Element Methods . . . . . . . . . . . . . . . 574
12.6 A Quick Glance at the Two-Dimensional Case . . . . . . . . . . . . 580
12.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583
12.7.1 Lubrication of a Slider . . . . . . . . . . . . . . . . . . . . . . . . . . 583
12.7.2 Vertical Distribution of Spore Concentration over
Wide Regions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584
12.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
13 Parabolic and Hyperbolic Initial Boundary Value
Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
13.1 The Heat Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589
13.2 Finite Difference Approximation of the Heat Equation . . . . . 591
13.3 Finite Element Approximation of the Heat Equation . . . . . . . 593
13.3.1 Stability Analysis of the θ-Method. . . . . . . . . . . . . . . . 595
13.4 Space-Time Finite Element Methods for the Heat
Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
13.5 Hyperbolic Equations: A Scalar Transport Problem . . . . . . . . 604
13.6 Systems of Linear Hyperbolic Equations . . . . . . . . . . . . . . . . . . 607
13.6.1 The Wave Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 608
13.7 The Finite Difference Method for Hyperbolic Equations . . . . 609
13.7.1 Discretization of the Scalar Equation . . . . . . . . . . . . . 610
13.8 Analysis of Finite Difference Methods . . . . . . . . . . . . . . . . . . . . 611
13.8.1 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
13.8.2 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
13.8.3 The CFL Condition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613
13.8.4 Von Neumann Stability Analysis . . . . . . . . . . . . . . . . . 615
13.9 Dissipation and Dispersion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
13.9.1 Equivalent Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . 619
13.10 Finite Element Approximation of Hyperbolic Equations . . . . 624
13.10.1 Space Discretization with Continuous and
Discontinuous Finite Elements . . . . . . . . . . . . . . . . . . . 625
XVIII Contents
13.10.2 Time Discretization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
13.11 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
13.11.1 Heat Conduction in a Bar . . . . . . . . . . . . . . . . . . . . . . . 630
13.11.2 A Hyperbolic Model for Blood Flow Interaction
with Arterial Walls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
13.12 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 632
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
Index of MATLAB Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649