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
京公网安备 11010102004214号