数值数学是数学的一个分支，它提出、发展、分析并应用科学计算中的方法于若干领域，如分析学、线性代数、几何学、逼近论、函数方程、优化问题和微分方程等等。而其他领域，如物理学、自然和生物科学、工程、经济、金融科学也经常提出问题，而问题的解决同样需要科学计算。    因此可以说，数值数学是现代应用科学中具有很强相关性的不同学科的一个交叉学科，是这些学科中定性和定量分析的重要工具。    写作本书的目的之一，是给出数值方法的数学基础，分析其基本的理论性质（如稳定性、精度、计算复杂性），应用MATLAB这一界面友好并被广泛接受的软件，通过例子和反例说明其特征和优缺点。讨论每一类问题时，都评述最适合的算法，进行理论分析，并利用一个MATLAB程序验证理论结果。书中每一章都包含例子、练习，并运用所讨论的理论解决现实生活中的问题。

Contents
Preface iii
Ⅰ Getting Started 1
1. Foundations of Matrix Analysis 3
1.1 Vector Spaces 3
1.3 0perations with Matrices 7
1.3.1 Inverse of a Matrix 8
1.3.2 Matrices and Linear Mappings 9
1.3.3 0perations 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 13
1.6.3 Banded Matrices 13
1.7 Eigenvalues and Eigenvectors 14
1.8 Similarity Transformations 16
1.9 The Singular Value Decomposition (SVD) 18
1.10 Scalar Product and Norms in Vector Spaces 19
1.11 Matrix Norms 23
1.11.1 Relation between Norms and the Spectral Radius of a Matrix 27
1.11.2 Sequences and Series of Matrices 28
1.12 Positive Definite, Diagonally Dominant and M-matrices 29
1.13 Exercises 32
2. Principles of Numerical Mathematics 35
2.1 Well-posedness and Condition Number of a Problem 35
2.2 Stability of Numerical Methods 39
2.2.1 Relations between Stability and Convergence 42
2.3 A priori and a posteriori Analysis 43
2.4 Sources of Error in Computational Models 45
2.5 Machine Representation of Numbers 47
2.5.1 The Positional System 47
2.5.2 The Floating-point Number System 48
2.5.3 Distribution of Floating-point Numbers 51
2.5.4 IEC/IEEE Arithmetic 51
2.5.5 Rounding of a Real Number in its Machine Representation 52
2.5.6 Machine Floating-point Operations 54
2.6 Exercises 56
II Numerical Linear Algebra 59
3. Direct Methods for the Solution of Linear Systems61
3.1 Stability Analysis of Linear Systems 62
3.1.1 The Condition Number of a Matrix 62
3.1.2 Forward a priori Analysis 64
3.1.3 Backward a priori Analysis 67
3.1.4 A posteriori Analysis 68
3.2 Solution of Triangular Systems 69
3.2.1 Implementation of Substitution Methods 69
3.2.2 Rounding Error Analysis 71
3.2.3 Inverse of a Triangular Matrix 71
3.3 The Gaussian Elimination Method (GEM) and LU Factorization 72
3.3.1 GEM as a Factorization Method 76
3.3.2 The Effect of Rounding Errors 80
3.3.3 Implementation of LU Factorization 81
3.3.4 Compact Forms of Factorization 82
3.4 0ther Types of Factorization 83
3.4.1 LDMT Factorization 83
3.4.2 Symmetric and Positive Definite Matrices: The Cholesky Factorization 84
3.4.3 Rectangular Matrices: The QR Factorization 86
3.6 Computing the Inverse of a Matrix 93
3.7 Banded Systems 94
3.7.1 Tridiagonal Matrices 95
3.7.2 Implementation Issues 96
3.8 Block Systems 97
3.8.1 Block LU Factorization 98
3.8.2 Inverse of a Block-partitioned Matrix 98
3.8.3 Block Tridiagonal Systems 99
3.9 Sparse Matrices 101
3.9.1 The Cuthill-McKee Algorithm 102
3.9.2 Decomposition into Substructures 104
3.9.3 Nested Dissection 107
3.10 Accuracy of the Solution Achieved Using GEM 107
3.11 An Approximate Computation of K(A) 110
3.12 Improving the Accuracy of GEM 113
3.12.1 Scaling 114
3.12.2 Iterative Refinement 115
3.13 Undetermined Systems 116
3.14 Applications 119
3.14.1 Nodal Analysis of a Structured Frame 119
3.14.2 Regularization of a Triangular Grid 122
3.15 Exercises 125
4. Iterative Methods for Solving Linear Systems 127
4.1 0n the Convergence of lterative Methods 127
4.2 Linear Iterative Methods 130
4.2.1 Jacobi, Gauss-Seidel and Relaxation Methods 131
4.2.2 Convergence Results for Jacobi and Gauss-SeidelMethods 133
4.2.3 Convergence Results for the Relaxation Method 135
4.2.4 A priori Forward Analysis 136
4.2.5 Block Matrices 137
4.2.6 Symmetric Form of the Gauss-Seidel and SOR Methods 137
4.2.7 Implementation Issues 139
4.3 Stationary and Nonstationary Iterative Methods 140
4.3.1 Convergence Analysis of the Richardson Method 141
4.3.2 Preconditioning Matrices 143
4.3.3 The Gradient Method 150
4.3.4 The Conjugate Gradient Method 155
4.3.5 The Preconditioned Conjugate Gradient Method 160
4.3.6 The Alternating-Direction Method 162
4.4 Methods Based on Krylov Subspace Iterations 163
4.4.1 The Arnoldi Method for Linear Systems 166
4.4.2 The GMRES Method 169
4.4.3 The Lanczos Method for Symmetric Systems 171
4.5 The Lanczos Method for Unsymmetric Systems 172
4.6 Stopping Criteria 175
4.6.1 A Stopping Test Based on the Increment 176
4.6.2 A Stopping Test Based on the Residual 178
4.7 Applications 178
4.7.1 Analysis of an Electric Network 178
4.7.2 Finite Difference Analysis of Beam Bending 181
4.8 Exercises 183
5. Approximation of Eigenvalues and Eigenvectors 187
5.1 Geometrical Location of the Eigenvalues 187
5.2 Stability and Conditioning Analysis 190
5.2.1 A priori Estimates 190
5.2.2 A posteriori Estimates 194
5.3 The Power Method 196
5.3.1 Approximation of the Eigenvalue of Largest Module 196
5.3.2 Inverse Iteration 199
5.3.3 Implementation Issues 200
5.4 The QR Iteration 203
5.5 The Basic QR Iteration 205
5.6 The QR Method for Matrices in Hessen berg Form 207
5.6.1 Householder and Givens Transformation Matrices 208
5.6.2 Reducing a Matrix in Hessen berg Form 211
5.6.3 QR Factorization of a Matrix in Hessen berg Form 213
5.6.4 The Basic QR Iteration Starting from Upper Hessen berg Form 214
5.6.5 Implementation of Transformation Matrices 216
5.7 The QR Iteration with Shifting Techniques 218
5.7.1 The QR Method with Single Shift 219
5.7.2 The QR Method with Double Shift 221
5.8 Computing the Eigenvectors and the SVD of a Matrix 224
5.8.1 The Hessen berg lnverse Iteration 224
5.8.2 Computing the Eigenvectors from the Schur Form of a Matrix 225
5.8.3 Approximate Computation of the SVD of a Matrix 226
5.9 The Generalized Eigenvalue Problem 227
5.9.1 Computing the Generalized Real Schur Form 228
5.9.2 Generalized Real Schur Form of Symmetric-Definite Pencils 229
5.10 Methods for Eigenvalues of Symmetric Matrices 230
5.10.1 The Jacobi Method 231
5.10.2 The Method of Sturm Sequences 233
5.11 The Lanczos Method 236
5.12 Applications 239
5.12.1 Analysis of the Buckling of a Beam 239
5.12.2 Free Dynamic Vibration of a Bridge 241
III Around Functions and Functionals 249
6. Rootfinding for Nonlinear Equations251
6.1 Conditioning of a Nonlinear Equation 252
6.2 A Geometric Approach to Rootfinding 254
6.2.1 The Bisection Method 254
6.2.2 The Methods of Chord, Secant and Regula Falsi and Newton's Method 257
6.2.3 The Dekker-Brent Method 262
6.3 Fixed-point Iterations for Nonlinear Equations 263
6.3.1 Convergence Results for Some Fixed-point Methods 266
6.4 Zeros of Algebraic Equations 267
6.4.1 The Homer Method and Deflation 268
6.4.2 The Newton-Horner Method 269
6.4.3 The Muller Method 272
6.5 Stopping Criteria 275
6.6 Post-processing Techniques for Iterative Methods 278
6.6.1 Aitken's Acceleration 278
6.6.2 Techniques for Multiple Roots 280
6.7 Applications 282
6.7.1 Analysis of the State Equation for a Real Gas 282
6.7.2 Analysis of a Nonlinear Electrical Circuit 283
7. Nonlinear Systems and Numerical Optimization287
7.1 Solution of Systems of Nonlinear Equations 288
7.1.1 Newton's Method and Its Variants 289
7.1.2 Modified Newton's Methods 291
7.1.3 Quasi-Newton Methods 294
7.1.4 Secant-like Methods 294
7.1.5 Fixed-point Methods 297
7.2 Unconstrained Optimization 300
7.2.1 Direct Search Methods 301
7.2.2 Descent Methods 306
7.2.3 Line Search Techniques 308
7.2.4 Descent Methods for Quadratic Functions 310
7.2.5 Newton-like Methods for Function Minimization 313
7.2.6 Quasi-Newton Methods 314
7.2.7 Secant-like methods 315
7.3 Constrained Optimization 317
7.3.1 Kuhn-Tucker Necessary Conditions for Nonlinear Programming 319
7.3.2 The Penalty Method 321
7.3.3 The Method of Lagrange Multipliers 322
7.4.1 Solution of a Nonlinear System Arising from Semiconductor Device Simulation 325
7.4.2 Nonlinear Regularization of a Discretization Grid 329
8. Polynomiallnterpolation333
8.1 Polynomial Interpolation 334
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.3Stability of Polynomial Interpolation 338
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 Piecewise Lagrange Interpolation 344
8.4 Barycentric Lagrange Interpolation 347
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 356
8.7.1 Interpolatory Cubic Splines 357
8.7.2 B-splines 361
8.8 Splines in Parametric Form 365
8.8.1 Bezier Curves and Parametric B-splines 367
8.9 Applications 370
8.9.1 Finite Element Analysis of a Clamped Beam 371
8.9.2 Geometric Reconstruction Based on Computer To mographies 374
8.10 Exercises 376
9 Numerical Integration379
9.1 Quadrature Formulae 379
9.2 Interpolatory Quadratures 381
9.2.1The 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 391
9.5 Hermite Quadrature Formulae 394
9.6 Richardson Extrapolation 396
9.6.1 Romberg Integration 398
9.7 Automatic Integration 399
9.7.1 Non Adaptive 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 oflnfinite Functions 407
9.8.3 Integrals over Unbounded Intervals 409
9.9 Multidimensional Numericallntegration 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 Numericallntegration 415
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
IV Transforms, DifFerentiation and Problem Discretization 423
10. Orthogonal Polynomials in Approximation Theory425
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 440
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 444
10.9 Fourier Trigonometric Polynomials 445
10.9.1 The Gibbs Phenomenon 450
10.9.2 The Fast Fourier Transform 451
10.10 Approximation of Function Derivatives 452
10.10.1 Classical Finite Difference Methods 452
10.10.2 Compact Finite Differences 455
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 464
10.11.3 The Laplace Transform 466
10.11.4 The Z-Transform 467
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 473
10.13.1 Numerical Computation of Blackbody Radiation 473
10.13.2 Numerical Solution of Schrodinger Equation 474
10.14 Exercises 477
11. Numerical Solution of Ordinary Differential Equations 479
11.1 The Cauchy Problem 479
11.2 0ne-Step Numerical Methods 482
11.3 Analysis of One-Step Methods 483
11.3.1 The Zero-Stability 485
11.3.2 Convergence Analysis 487
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 503
11.6.1 Consistency 503
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 513
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 522
11.8.3 Implicit RK Methods 524
11.8.4 Regions of Absolute Stability for RK Methods 526
11.9 Systems of ODEs 527
11.10 Stiff Problems 529
11.11 Applications 532
11.11.1 Analysis of the Motion of a Frictionless Pendulum 532
11.11.2 Compliance of Arterial Walls 535
12. Two-Point Boundary Value Problems541
12.1 A Model Problem 541
12.2 Finite Difference Approximation 543
12.2.1 Stability Analysis by the Energy Method 544
12.2.2 Convergence Analysis 548
12.2.3 Finite Differences for Two-Point Boundary Value Problems with Variable Coefficients 550
12.3 The Spectral Collocation Method 552
12.4 The Galerkin Method 554
12.4.1 Integral Formulation of Boundary Value Problems 554
12.4.2 A Quick Introduction to Distributions 556
12.4.3 Formulation and Properties of the Galerkin Method 557
12.4.4 Analysis of the Galerkin Method 558
12.4.5 The Finite Element Method 560
12.4.6 Implementation Issues 566
12.4.7 Spectral Methods 569
12.5 Advection-Diffusion Equations 570
12.5.1 Galerkin Finite Element Approximation 571
12.5.2 The Relationship between Finite Elements and Finite Differences; the Numerical Viscosity 573
12.5.3 Stabilized Finite Element Methods 577
12.6 A Quick Glance at the Two-Dimensional Case 582
12.7 Applications 585
12.7.1 Lubrication of a Slider 585
12.7.2Vertical Distribution of Spore Concentration over Wide
12.8 Exercises 588
13. Parabolic and Hyperbolic Initial Boundary Value Problems 591
13.1 The Heat Equation 591
13.2 Finite Difference Approximation of the Heat Equation 594
13.3 Finite Element Approximation of the Heat Equation 596
13.3.1 Stability Analysis of the O-Method 598
13.4 Space-Time Finite Element Methods for the Heat Equation 603
13.5 Hyperbolic Equations: A Scalar Transport Problem 607
13.6 Systems of Linear Hyperbolic Equations 609
13.6.1 The Wave Equation 611
13.7 The Finite Difference Method for Hyperbolic Equations 612
13.7.1 Discretization of the Scalar Equation 612
13.8 Analysis of Finite Difference Methods 615
13.8.1 Consistency 615
13.8.3 The CFL Condition 616
13.8.4 Von Neumann Stability Analysis 618
13.9 Dissipation and Dispersion 621
13.9.1 Equivalent Equations 624
13.10 Finite Element Approximation of Hyperbolic Equations 627
13.10.1 Space Discretization with Continuous and Discontinuous Finite Elements 628
13.10.2 Time Discretization 630
13.11 Applications 632
13.11.1 Heat Conduction in a Bar 632
13.11.2 A Hyperbolic Model for Blood Flow Interaction with Arterial Walls 633
13.12 Exercises 635
References 637
Index of MATLAB Programs 653
Index 657