Numerical Methods (Dover Books on Mathematics)

Practical text strikes fine balance between students' requirements for theoretical treatment and needs of practitioners, with best methods for large- and small-scale computing. Prerequisites are minimal (calculus, linear algebra, and preferably some acquaintance with computer programming). Text includes many worked examples, problems, and an extensive bibliography. 1974 edition. PREFACE CONVENTIONS 1 SOME GENERAL PRINCIPLES OF NUMERICAL CALCULATION 1.1. Introduction 1.2. Some Common Ideas and Concepts in Numerical Methods 1.3. Numerical Problems and Algorithms 1.3.1. Definitions 1.3.2. Recursive Formulas; Horner's Rule 1.3.3. An Example of Numerical Instability 2 HOW TO OBTAIN AND ESTIMATE ACCURACY IN NUMERICAL CALCULATIONS 2.1. Basic Concepts in Error Estimation 2.1.1. Introduction 2.1.2. Sources of Error 2.1.3. Absolute and Relative Errors 2.1.4. Rounding and Chopping 2.2 Propagation of Errors 2.2.1. Simple Examples of Error Analysis 2.2.2. The General Formula for Error Propagation; Maximum Error and Standard Error 2.2.3. On the Practical Application of Error Estimation 2.2.4. The Use of Experimental Perturbations 2.2.5. Automatic Control of Accuracy 2.3. Number Systems; Floating and Fixed Representation 2.3.1. The Position System 2.3.2. Floating and Fixed Representation 2.3.3. Floating Decimal Point 2.3.4. Fixed Decimal Point 2.3.5. Round-off Errors in Computation with Floating Arithmetic Operations 2.4. Backward Error Analysis; Condition Numbers 2.4.1. Backward Error Analysis 2.4.2. Condition Numbers for Problems and Algorithms 2.4.3. Geometrical Illustration of Error Analysis 3 NUMERICAL USES OF SERIES 3.1. Elementary Uses of Series 3.1.1. Simple Examples 3.1.2. Estimating the Remainder 3.1.3. Power Series 3.2. Acceleration of Convergence 3.2.1. Slowly Converging Alternating Series 3.2.2. Slowly Converging Series with Positive Terms 3.2.3. Other Simple Ways to Accelerate Convergence 3.2.4. Ill-Conditioned Series 3.2.5. Numerical Use of Divergent Series 4 APPROXIMATION OF FUNCTIONS 4.1. Basic Concepts in Approximation 4.1.1. Introduction 4.1.2. The Idea of a Function Space 4.1.3. Norms and Seminorms 4.1.4. Approximation of Functions as a Geometric Problem in Function Space 4.2. The Approximation of Functions by the Method of Least Squares 4.2.1. Statement of the Problems 4.2.2. Orthogonal Systems 4.2.3. Solution of the Approximation Problem 4.3. Polynomials 4.3.1. Basic Terminology; the Weierstrass Approximation Theorem 4.3.2. Triangle Families of Polynomials 4.3.3. A Triangle Family and Its Application to Interpolation 4.3.4. Equidistant Interpolation and the Runge Phenomenon 4.4. Orthogonal Polynomials and Applications 4.4.1. Tchebycheff Polynomials 4.4.2. Tchebycheff Interpolation and Smoothing 4.4.3. General Theory of Orthogonal Polynomials 4.4.4. Legendre Polynomials and Gram Polynomials 4.5. Complementary Observations on Polynomial Approximation 4.5.1. Summary of the Use of Polynomials 4.5.2. Some Inequalities for En(f) with Applications to the Computation of Linear Functional 4.5.3. Approximation in the Maximum Norm 4.5.4. Economization of Power Series; Standard Functions 4.5.5. Some Statistical Aspects of the Method of Least Squares 4.6. Spline Functions 5 NUMERICAL LINEAR ALGEBRA 5.1. Introduction 5.2. Basic Concepts of Linear Algebra 5.2.1. Fundamental Definitions 5.2.2. Partitioned Matrices 5.2.3. Linear Vector Spaces 5.2.4. Eigenvalues and Similarity Transformations 5.2.5. Singular-Value Decomposition and Pseudo-Inverse 5.3. Direct Methods for Solving Systems of Linear Equations 5.3.1. Triangular Systems 5.3.2. Gaussian Elimination 5.3.3. Pivoting Strategies 5.3.4. LU-Decomposition 5.3.5. Compact Schemes for Gaussian Elimination 5.3.6. Inverse Matrices 5.4. Special Matrices 5.4.1. Symmetric Positive-Definite Matrices 5.4.2. Band Matrices 5.4.3. Large-Scale Linear Systems 5.4.4. Other Sparse Matrices 5.5. Error Analysis for Linear Systems 5.5.1. An Ill-Conditioned Example 5.5.2. Vector and Matrix Norms 5.5.3. Perturbation Analysis 5.5.4. Rounding Errors in Gaussian Elimination 5.5.5. Scaling of Linear Systems 5.5.6. Iterative Improvement of a Solution 5.6. Iterative Methods 5.7. Overdetermined Linear Systems 5.7.1. The Normal Equations 5.7.2. Orthogonalization Methods 5.7.3. Improvement of Least-Squares Solutions 5.7.4. Least-Squares Problems with Linear Constraints 5.8. Computation of Eigenvalues and Eigenvectors 5.8.1. The Power Method 5.8.2. Methods Based on Similarity Transformations 5.8.3. Eigenvalues by Equation Solving 5.8.4. The QR-Algorithm 6 NONLINEAR EQUATIONS 6.1. Introduction 6.2. Initial Approximations; Starting Methods 6.2.1. Introduction 6.2.2. The Bisection Method 6.3. Newton-Raphson's Method 6.4. The Secant Method 6.4.1. Description of the Method 6.4.2. Error Analysis for the Secant Method 6.4.3. Regula Falsi 6.4.4. Other Related Methods 6.5. General Theory of Iteration Methods 6.6. Error Estimation and Attainable Accuracy in Iteration Methods 6.6.1. Error Estimation 6.6.2. Attainable Accuracy; Termination Criteria 6.7. Multiple Roots 6.8. Algebraic Equations 6.8.1. Introduction 6.8.2. Deflation 6.8.3. Ill-Conditioned Algebraic Equations 6.9. Systems of Nonlinear Equations 6.9.1. Iteration 6.9.2. Newton-Raphson's Method and Some ModiiScations 6.9.3. Other Methods 7 FINITE DIFFERENCES WITH APPLICATIONS TO NUMERICAL INTEGRATION, DIFFERENTIATION, AND INTERPOLATION 7.1. Difference Operators and Their Simplest Properties 7.2. Simple Methods for Deriving Approximation Formulas and Error Estimates 7.2.1. Statement of the Problems and Some Typical Examples 7.2.2. Repeated Richardson Extrapolation 7.3. Interpolation 7.3.1. Introduction 7.3.2. When is Linear Interpolation Sufficient? 7.3.3. Newton's General Interpolation Formula 7.3.4. Formulas for Equidistant Interpolation 7.3.5. Complementary Remarks on Interpolation 7.3.6. Lagrange's Interpolation Formula 7.3.7. Hermite Interpolation 7.3.8. Inverse Interpolation 7.4. Numerical Integration 7.4.1. The Rectangle Rule, Trapezoidal Rule, and Romberg's Method 7.4.2. The Truncation Error of the Trapezoidal Rule 7.4.3. Some Difficulties and Possibilities in Numerical Integration 7.4.4. The Euler-Maclaurin Summation Formula 7.4.5. Uses of the Euler-Maclaurin Formula 7.4.6. Other Methods for Numerical Integration 7.5. Numerical Differentiation 7.6. The Calculus of Operators 7.6.1. Operator Algebra 7.6.2. Operator Series with Applications 7.7. Functions of Several Variables 7.7.1. Working with One Variable at a Time 7.7.2. Rectangular Grids 7.7.3. Irregular Triangular Grids 8 DIFFERENTIAL EQUATIONS 8.1. Theoretical Background 8.1.1. Initial-Value Problems for Ordinary Differential Equations 8.1.2. Error Propagation 8.1.3. Other Differential Equation Problems 8.2. Euler's Method, with Repeated Richardson Extrapolation 8.3. Other Methods for Initial-Value Problems in Ordinary Differential Equations 8.3.1. The Modified Midpoint Method 8.3.2. The Power-Series Method 8.3.3. Runge-Kutta Methods 8.3.4. Implicit Methods 8.3.5. Stiff Problems 8.3.6. Control of Step Size 8.3.7. A Finite-Difference Method for a Second-Order Equation 8.4. Orientation on Boundary and Eigenvalue Problems for Ordinary Differential Equations 8.4.1. Introduction 8.4.2. The Shooting Method 8.4.3. The Band Matrix Method 8.4.4. Numerical Example of an Eigenvalue Problem 8.5. Difference Equations 8.5.1. Homogeneous Linear Difference Equations with Constant Coefficients 8.5.2. General Linear Difference Equations 8.5.3. Analysis of a Numerical Method with the Help of a Test Problem 8.5.4. Linear Multistep Methods 8.6. Partial Differential Equations 8.6.1. Introduction 8.6.2. An Example of an Initial-Value Problem 8.6.3. An Example of a Boundary-Value Problem 8.6.4. Methods of Undetermined Coefficients and Variational Methods 8.6.5. Finite-Element Methods 8.6.6. Integral Equations 9 FOURIER METHODS 9.1. Introduction 9.2. Basic Formulas and Theorems in Fourier Analysis 9.2.1. Functions of One Variable 9.2.2. Functions of Several Variables 9.3. Fast Fourier Analysis 9.3.1. An Important Special Case 9.3.2. Fast Fourier Analysis, General Case 9.4. Periodic Continuation of a Nonperiodic Function 9.5. The Fourier Integral Theorem 10 OPTIMIZATION 10.1. Statement of the Problem, Definitions, and Normal Form 10.2. The Simplex Method 10.3. Duality 10.4. The Transportation Problem and Some Other Optimization Problems 10.5. Nonlinear Optimization Problems 10.5.1. Basic Concepts and Introductory Examples 10.5.2. Line Search 10.5.3. Algorithms for Unconstrained Optimization 10.5.4. Overdetermined Nonlinear Systems 10.5.5. Constrained Optimization 11 THE MONTE CARLO METHOD AND SIMULATION 11.1. Introduction 11.2. Random Digits and Random Numbers 11.3. Applications; Reduction of Variance 11.4. Pseudorandom Numbers 12 SOLUTIONS TO PROBLEMS 13 BIBLIOGRAPHY AND PUBLISHED ALGORITHMS 13.1. Introduction 13.2. General Literature in Numerical Analysis 13.3. Tables, Collections of Formulas, and Problems 13.4. Error Analysis and Approximation of Functions 13.5. Linear Algebra and Nonlinear Systems of Equations 13.6. Interpolation, Numerical Integration, and Numerical Treatment of Differential Equations 13.7. Optimization; Simulation 13.8. Reviews, Abstracts and Other Periodicals 13.9. Survey of Published Algorithms Index by Subject to Algorithms, 1960-1970 APPENDIX TABLES INDEX 'Substantial, detailed and rigorous... readers for whom the book is intended are admirably served.'— MathSciNet (Mathematical Reviews on the Web), American Mathematical Society.Practical text strikes fine balance between students'requirements for theoretical treatment and needs of practitioners, with best methods for large- and small-scale computing. Prerequisites are minimal (calculus, linear algebra, and preferably some acquaintance with computer programming). Text includes many worked examples, problems, and an extensive bibliography.