Introduction to Numerical Analysis

Preface 1 Introduction 1.1 Numerical Analysis 1.2 Approximation 1.3 Errors 1.4 Significant Figures 1.5 Determinacy of Functions. Error Control 1.6 Machine Errors 1.7 Random Errors 1.8 Recursive Computation 1.9 Mathematical Preliminaries 1.10 Supplementary References Problems 2 Interpolation with Divided Differences 2.1 Introduction 2.2 Linear Interpolation 2.3 Divided Differences 2.4 Second-Degree Interpolation 2.5 Newton's Fundamental Formula 2.6 Error Formulas 2.7 Iterated Interpolation 2.8 Inverse Interpolation 2.9 Supplementary References Problems 3 Lagrangian Methods 3.1 Introduction 3.2 Lagrange's Interpolation Formula 3.3 Numerical Differentiation and Integration 3.4 Uniform-spacing Interpolation 3.5 Newton-Cotes Integration Formulas 3.6 Composite Integration Formulas 3.7 Use of Integration Formulas 3.8 Richardson Extrapolation. Romberg Integration 3.9 Asympotic Behavior of Newton-Cotes Formulas 3.10 Weighting Functions. Filon Integration 3.11 Differentiation Formulas 3.12 Supplementary References Problems 4 Finite-Difference Interpolation 4.1 Introduction 4.2 Difference Notations 4.3 Newton Forward- and Backward-difference Formulas 4.4 Gaussian Formulas 4.5 Stirling's Formula 4.6 Bessel's Formula 4.7 Everett's Formulas 4.8 Use of Interpolation Formulas 4.9 Propogation of Inherent Errors 4.10 Throwback Techniques 4.11 Interpolation Series 4.12 Tables of Interpolation Coefficients 4.13 Supplementary References Problems 5 Operations with Finite Differences 5.1 Introduction 5.2 Difference Operators 5.3 Differentiation Formulas 5.4 Newtonian Integration Formulas 5.5 Newtonian Formulas for Repeated Integration 5.6 Central-Difference Integration Formulas 5.7 Subtabulation 5.8 Summation and Integration. The Euler-Maclaurin Sum Formula 5.9 Approximate Summation 5.10 Error Terms in Integration Formulas 5.11 Other Representations of Error Terms 5.12 Supplementary References Problems 6 Numerical Solution of Differential Equations 6.1 Introduction 6.2 Formulas of Open Type 6.3 Formulas of Closed Type 6.4 Start of Solution 6.5 Methods Based on Open-Type Formulas 6.6 Methods Based on Closed-Type Formulas. Prediction-Correction Methods 6.7 The Special Case F = Ay 6.8 Propagated-Error Bounds 6.9 Application to Equations of Higher Order. Sets of Equations 6.10 Special Second-order Equations 6.11 Change of Interval 6.12 Use of Higher Derivatives 6.13 A Simple Runge-Kutta Method 6.14 Runge-Kutta Methods of Higher Order 6.15 Boundary-Value Problems 6.16 Linear Characteristic-value Problems 6.17 Selection of a Method 6.18 Supplementary References Problems 7 Least-Squares Polynomial Approximation 7.1 Introduction 7.2 The Principle of Least Squares 7.3 Least-Squares Approximation over Discrete Sets of Points 7.4 Error Estimation 7.5 Orthogonal Polynomials 7.6 Legendre Approximation 7.7 Laguerre Approximation 7.8 Hermite Approximation 7.9 Chebsyshev Approximation 7.10 Properties of Orthoogonal Polynomials. Recursive Computation 7.11 Factorial Power Functions and Summation Formulas 7.12 Polynomials Orthogonal over Discrete Sets of Points 7.13 Gram Approximation 7.14 Example: Five-Point Least-Squares Approximation 7.15 Smoothing Formulas 7.16 Recursive Computation of Orthogonal Polynomials on Discrete Set of Points 7.17 Supplementary References Problems 8 Gaussian Quadrature and Related Topics 8.1 Introduction 8.2 Hermite Interpolation 8.3 Hermite Quadrature 8.4 Gaussian Quadrature 8.5 Legendre-Gauss Quadrature 8.6 Laguerre-Gauss Quadrature 8.7 Hermite-Gauss Quadrature 8.8 Chebyshev-Gauss Quadrature 8.9 Jacobi-Gauss Quadrature 8.10 Formulas with Assigned Abscissas 8.11 Radau Quadrature 8.12 Lobatto Quadrature 8.13 Convergence of Gaussian-quadrature Sequences 8.14 Chebyshev Quadrature 8.15 Algebraic Derivations 8.16 Application to Trigonometric Integrals 8.17 Supplementary References Problems 9 Approximations of Various Types 9.1 Introduction 9.2 Fourier Approximation: Continuous Domain 9.3 Fourier Approximation: Discrete Domain 9.4 Exponential Approximation 9.5 Determination of Constituent Periodicities 9.6 Optimum Polynomial Interpolation with Selected Abscissas 9.7 Chebyshev Interpolation 9.8 Economization of Polynomial Approximations 9.9 Uniform (Minimax) Polynomial Approximation 9.10 Spline Approximation 9.11 Splines with Uniform Spacing 9.12 Spline Error Estimates 9.13 A Special Class of Splines 9.14 Approximation by Continued Fractions 9.15 Rational Approximations and Continued Fractions 9.16 Determination of Convergents of Continued Fractions 9.17 Thiele's Continued-Fraction Approxmations 9.18 Uniformization of Rational Approximations 9.19 Supplementary References Problems 10 Numerical Solution of Equations 10.1 Introduction 10.2 Sets of Linear Equations 10.3 The Gauss Reduction 10.4 The Crout Reduction 10.5 Intermediate Roudoff Errors 10.6 Determination of the Inverse Matrix 10.7 Inherent Errors 10.8 Tridiagonal Sets of Equations 10.9 Iterative Methods and Relaxation 10.10 Iterative Methods for Nonlinear Equations 10.11 The Newton-Raphson Method 10.12 Iterative Methods of Higher Order 10.13 Sets of Nonlinear Equations 10.14 Iterated Synthetic Division of Polynomials. Lin's Method 10.15 Determinacy of Zeros of Polynomials 10.16 Bernoulli's Iteration 10.17 Graeffe's Root-squaring Technique 10.18 Quadratic Factors. Lin's Quadratic Method 10.19 Bairstow Iteration 10.20 Supplementary References Problems Appendixes A Justification of the Crout Reduction B Bibliography C Directory of Methods Index