MATHEMATICS FOR THE MILLION
1 Error Analysis 1 11 Representation of Numbers 2 12 Roundoff Errors and Floating-Point Arithmetic 4 13 Error Propagation 9 14 Examples 21 15 Interval Arithmetic; Statistical Roundoff Estimation 27 Exercises for Chapter 1 33 References for Chapter 1 36 2 Interpolation 37 21 Interpolation by Polynomials 38 211 Theoretical Foundation: The Interpolation Formula of Lagrange 38 212 Neville’s Algorithm 40 213 Newtons Interpolation Formula: Divided Differences 43 214 The Error in Polynomial Interpolation 48 215 Hermite Interpolation 51 22 Interpolation by Rational Functions 59 221 General Properties of Rational Interpolation 59 222 Inverse and Reciprocal Differences Thiele’s Continued Fraction 64 223 Algorithms of the Neville Type 68 224 Comparing Rational and Polynomial Interpolation 73 23 Trigonometric Interpolation 74 231 Basic Facts 74 232 Fast Fourier Transforms 80 233 The Algorithms of Goertzel and Reinsch 88 234 The Calculation of Fourier Coefficients Attenuation Factors 92 24 Interpolation by Spline Functions 97 241 Theoretical Foundations 97 242 Determining Interpolating Cubic Spline Functions 101 243 Convergence Properties of Cubic Spline Functions 107 244 B-Splines 111 245 The Computation of B-Splines 117 246 Multi-Resolution Methods and B-Splines 121 Exercises for Chpater 2 134 References for Chapter2 143 3 Topics in Integration 145 31 The Integration Formulas of Newton and Cotes 146 32 Peano’s Error Representation 151 33 The Euler-Maclaurin Summation Formula 156 34 Integration by Extrapolation 160 35 About Extrapolation Methods 165 36 Gaussian Integration Methods 171 37 Integrals with Singularities 181 Exercises for Chapter 3 184 References for Chapter 3 188 4 Systems of Linear Equations 190 41 Gaussian Elimination The Triangular Decomposition of a Matrix 190 42 The Gauss-Jordan Algorithm 200 43 The Choleski Decompostion 204 44 Error Bounds 207 45 Roundoff-Error Analysis for Gaussian Elimination 215 46 Roundoff Errors in Solving Triangular Systems 221 47 Orthogonalization Techniques of Householder and Gram-Schmidt 223 48 Data Fitting 231 481 Linear Least Squares The Normal Equations 232 482 The Use of Orthogonalization in Solving Linear Least-Squares Problems 235 483 The Condition of the Linear Least-Squares Problem 236 484 Nonlinear Least-Squares Problems 241 485 The Pseudoinverse of a Matrix 243 49 Modification Techniques for Matrix Decompositions 247 410 The Simplex Method 256 411 Phase One of the Simplex Method 268 412 Appendix: Elimination Methods for Sparse Matrices 272 Exercises for Chapter 4 280 References for Chapter 4 286 5 Finding Zeros and Minimum Points by Iterative Methods 289 51 The Development of Iterative Methods 290 52 General Convergence Theorems 293 53 The Convergence of Newton’s Method in Several Variables 298 54 A Modified Newton Method 302 541 On the Convergence of Minimization Methods 303 542 Application of the Convergence Criteria to the Modified Newton Method 308 543 Suggestions for a Practical Implementation of the Modified Newton Method A Rank-One Method Due to Broyden 313 55 Roots of Polynomials Application of Newton’s Method 316 56 Sturm Sequences and Bisection Methods 328 57 Bairstow’s Method 333 58 The Sensitivity of Polynomial Roots 335 59 Interpolation Methods for Determining Roots 338 510 The ?2-Method of Aitken 344 511 Minimization Problems without Constraints 349 Exercises for Chapter 5 358 References for Chapter 5 361 6 Eigenvalue Problems 364 60 Introduction 364 61 Basic Facts on Eigenvalues 366 62 The Jordan Normal Form of a Matrix 369 63 The Frobenius Normal Form of a Matrix 375 64 The Schur Normal Form of a Matrix; Hermitian and Normal Matrices; Singular Values of Matrixes 379 65 Reduction of Matrices to Simpler Form 386 651 Reduction of a Hermitian Matrix to Tridiagonal Form: The Method of Householder 388 652 Reduction of a Hermitian Matrix to Tridiagonal or Diagonal Form: The Methods of Givens and Jacobi 394 653 Reduction of a Hermitian Matrix to Tridiagonal Form: The Method of Lanczos 398 654 Reduction to Hessenberg Form 402 66 Methods for Determining the Eigenvalues and Eigenvectors 405 661 Computation of the Eigenvalues of a Hermitian Tridiagonal Matrix 405 662 Computation of the Eigenvalues of a Hessenberg Matrix The Method of Hyman 407 663 Simple Vector Iteration and Inverse Iteration of Wielandt 408 664 The LR and QR Methods 415 665 The Practical Implementation of the QR Method 425 67 Computation of the Singular Values of a Matrix 436 68 Generalized Eigenvalue Problems 440 69 Estimation of Eigenvalues 441 Exercises for Chapter 6 455 References for Chapter 6 462 7 Ordinary Differential Equations 465 70 Introduction 465 71 Some Theorems from the Theory of Ordinary Differential Equations 467 72 Initial-Value Problems 471 721 One-Step Methods: Basic Concepts 471 722 Convergence of One-Step Methods 477 723 Asymptotic Expansions for the Global Discretization Error of One-Step Methods 480 724 The Influence of Rounding Errors in One-Step Methods 483 725 Practical Implementation of One-Step Methods 485 726 Multistep Methods: Examples 492 727 General Multistep Methods 495 728 An Example of Divergence 498 729 Linear Difference Equations 501 7210 Convergence of Multistep Methods 504 7211 Linear Multistep Methods 508 7212 Asymptotic Expansions of the Global Discretization Error for Linear Multistep Methods 513 7213 Practical Implementation of Multistep Methods 517 7214 Extrapolation Methods for the Solution of the Initial-Value Problem 521 7215 Comparison of Methods for Solving Initial-Value Problems 524 7216 Stiff Differential Equations 525 7217 Implicit Differential Equations Differential-Algebraic Equations 531 7218 Handling Discontinuities in Differential Equations 536 7219 Sensitivity Analysis of Initial-Value Problems 538 73 Boundary-Value Problems 539 730 Introduction 539 731 The Simple Shooting Method 542 732 The Simple Shooting Method for Linear Boundary-Value Problems 548 733 An Existence and Uniqueness Theorem for the Solution of Boundary-Value Problems 550 734 Difficulties in the Execution of the Simple Shooting Method 552 735 The Multiple Shooting Method 557 736 Hints for the Practical Implementation of the Multiple Shooting Method 561 737 An Example: Optimal Control Program for a Lifting Reentry Space Vehicle 565 738 Advanced Techniques in Multiple Shooting 572 739 The Limiting Case m??of the Multiple Shooting Method (General Newton’s Method, Quasilinearization) 577 74 Difference Methods 582 75 Variational Methods 586 76 Comparison of the Methods for Solving Boundary-Value Problems for Ordinary Differential Equations 596 77 Variational Methods for Partial Differential Equations The Finite-Element Method 600 Exercises for Chapter 7 607 References for Chapter 7 613 8 Iterative Methods for the Solution of Large Systems of Linear Equations Additional Methods 619 80 Introduction 619 81 General Procedures for the Construction of Iterative Methods 621 82 Convergence Theorems 623 83 Relaxation Methods 629 84 Applications to Difference Methods—An Example 639 85 Block Iterative Methods 645 86 The ADI-Method of Peaceman and Rachford 647 8,7 Krylov Space Methods for Solving Linear Equations 657 871 The Conjugate-Gradient Method of Hestenes and Stiefel 658 872 The GMRES Algorithm 667 873 The Biorthogonalization Method of Lanczos and the QMR algorithm 680 874 The Bi-CG and BI-CGSTAB Algorithms 686 88 Buneman’s Algorithm and Fourier Methods for Solving the Discretized Poisson Equation 691 89 Multigrid Methods 702 810 Comparison of Iterative Methods 712 Exercises for Chapter 8 719 References for Chapter 8 727