Elementary Numerical Analysis

Preface
Contents
1. Taylor Polynomials
1.1 The Taylor Polynomial
1.2 The Error in Taylor's Polynomials
1.2.1 Infinite Series
1.3 Polynomial Evaluation
1.3.1 An Example Program
2. Error and Computer Arithmetic
2.1 Floating-Point Numbers
2.1.1 Accuracy of Floating-Point Representation
2.1.2 Rounding and Chopping
2.1.3 Consequences for Programming of Floating-Point
Arithmetic
2.2 Errors: Definitions, Sources, and Examples
2.2.1 Sources of Error
2.2.2 Loss-of-Significance Errors
2.2.3 Noise in Function Evaluation
2.2.4 Underflow and Overflow Errors
2.3 Propagation of Error
2.3.1 Propagated Error in Function Evaluation
2.4 Summation
2.4.1 Rounding versus Chopping
2.4.2 A Loop Error
2.4.3 Calculation of Inner Products
3. Rootfinding
3.1 The Bisection Method
3.1.1 Error Bounds
3.2 Newton's Method
3.2.1 Error Analysis
3.2.2 Error Estimation
3.3 Secant Method
3.3.1 Error Analysis
3.3.2 Comparison of Newton and Secant Methods
3.3.3 The MATLAB Function fzero
3.4 Fixed Point Iteration
3.4.1 Aitken Error Estimation and Extrapolation
3.4.2 Higher-Order Iteration Formulas
3.5 Ill-Behaving Rootfinding Problems
3.5.1 Stability of Roots
4. Interpolation and Approximation
4.1. Polynomial Interpolation
4.1.1 Linear Interpolation
4.1.2 Quadratic Interpolation
4.1.3 Higher-Degree Interpolation
4.1.4 Divided Differences
4.1.5 Properties of Divided Differences
4.1.6 Newton's Divided Difference Interpolation Formula
4.2 Error in Polynomial Interpolation
4.2.1 Another Error Formula
4.2.2 Behavior of the Error
4.3 Interpolation Using Spline Functions
4.3.1 Spline Interpolation
4.3.2 Construction of the Interpolating Natural Cubic Spline
4.3.3 Other Interpolating Spline Functions
4.3.4 The MATLAB Program spline
4.4 The Best Approximation Problem
4.4.1 Accuracy of the Minimax Approximation
4.5 Chebyshev Polynomials
4.5.1 The Triple Recursion Relation
4.5.2 The Minimum Size Property
4.6 A Near-Minimax Approximation Method
4.6.1 Odd and Even Functions
4.7 Least Squares Approximation
4.7.1 Legendre Polynomials
4.7.2 Solving for the Least Squares Approximation
4.7.3 Generalizations of Least Squares Approximation
5. Numerical Integration and Differentiation
5.1 The Trapezoidal and Simpson Rules
5.1.1 Simpson's Rule
5.2 Error Formulas
5.2.1 An Asymptotic Estimate of the Trapezoidal Error
5.2.2 Error Formulas for Simpson's Rule
5.2.3 Richardson Extrapolation
5.2.4 Periodic Integrands
5.3 Gaussian Numerical Integration
5.3.1 Weighted Gaussian Quadrature
5.4 Numerical Differentiation
5.4.1 Differentiation Using Interpolation
5.4.2 The Method of Undetermined Coefficients
5.4.3 Effects of Error in Function Values
6. Solution of Systems of Linear Equations
6.1 Systems of Linear Equations
6.2 Matrix Arithmetic
6.2.1 Arithmetic Operations
6.2.2 Elementary Row Operations
6.2.3 The Matrix Inverse
6.2.4 Matrix Algebra Rules
6.2.5 Solvability Theory of Linear Systems
6.3 Gaussian Elimination
6.3.1 Partial Pivoting
6.3.2 Calculation of Inverse Matrices
6.3.3 Operations Count
6.4 The LU Factorization
6.4.1 Compact Variants of Gaussian Elimination
6.4.2 Tridiagonal Systems
6.4.3 MATLAB Built-in Functions for Solving Linear Systems
6.5 Error in Solving Linear Systems
6.5.1 The Residual Correction Method
6.6 Iteration Methods
6.6.1 Jacobi Method and Gauss-Seidel Method
6.6.2 General Schema
6.6.3 The Residual Correction Method
7. Numerical Linear Algebra: Advanced Topics
7.1 Least Squares Data Fitting
7.1.1 The Linear Least Squares Approximation
7.1.2 Polynomial Least Squares Approximation
7.2 The Eigenvalue Problem
7.2.1 The Characteristic Polynomial
7.2.2 Eigenvalues for Symmetric Matrices
7.2.3 The Nonsymmetric Eigenvalue Problem
7.2.4 The Power Method
7.2.5 Convergence of the Power Method
7.2.6 MATLAB Eigenvalue Calculations
7.3 Nonlinear Systems
7.3.1 Newton's Method
7.3.2 The General Newton Method
7.3.3 A Modified Newton's Method
8. Numerical Solution of Ordinary Differential Equations
8.1 Theory of Differential Equations: An Introduction
8.1.1 General Solvability Theory
8.1.2 Stability of the Initial Value Problem
8.1.3 Direction Fields
8.2 Euler's Method
8.3 Convergence Analysis of Euler's Method
8.3.1 Asymptotic Error Analysis
8.3.2 Richardson Extrapolation
8.4 Numerical Stability, Implicit Methods
8 .4 .1 The Backward Euler Method
8.4.2 The Trapezoidal Method
8.5 Taylor and Runge-Kitta Methods
8.5.1 Runge-Kutta Methods
8.5.2 Error Prediction and Control
8.5.3 MATLAB Built-in Functions
8.6 Multistep Methods
8.7 Systems of Differential Equations
8.7.1 Higher-Order Differential Equations
8.7.2 Numerical Methods for Systems
8.8 Finite Difference Method for Two-Point Boundary Value
Problems
9. Finite Difference Method for Partial Differential Equations
9.1 The Poisson Equation
9.2 One-Dimensional Heat Equation
9.2.1 Semidiscretization
9.2.2 Explicit Full Discretization
9.2.3 Implicit Full Discretization
9.3 One-Dimensional Wave Equation
Appendix A: Mean Value Theorems
Appendix B: Mathematical Formulas
B.1 Algebra
B.2 Geometry
B.3 Trigonometry
B.4 Calculus
Appendix C: Numerical Analysis Software Packages
C.1 Commercial Packages
C.2 Public Domain Packages
C.3 Interactive Numerical Computation Environments
C.4 Symbolic Computation Environments
C.5 Literature on Mathematical Software
Appendix D: MATLAB: An Introduction
Appendix E: The Binary Number System
E.1 Conversion from Decimal to Binary
E.2 Hexadecimal Numbers
Answers to Selected Problems
Bibliography
Index