A First Course in Numerical Analysis Second Edition

by Ralston, Anthony; Rabinowitz, Philip

• ISBN13: 9780486414546
• ISBN10: 048641454X
• Edition: 2nd
• Format: Paperback
• Copyright: 2001-02-06
• Publisher: Dover Publications

Summary

Outstanding text treats numerical analysis with mathematical rigor, but relatively few theorems and proofs. Oriented toward computer solutions of problems, it stresses errors in methods and computational efficiency. Problems some strictly mathematical, others requiring a computer appear at the end of each chapter.

Table of Contents

Preface to the Dover Edition	xii
Preface to the Second Edition	xiii
Notation	xvi
Introduction and Preliminaries	1	(30)
What Is Numerical Analysis?	1	(1)
Sources of Error	2	(2)
Error Definitions and Related Matters	4	(5)
Significant Digits
Error in Functional Evaluation
Norms
Roundoff Error	9	(3)
The Probabilistic Approach to Roundoff: A Particular Example
Computer Arithmetic	12	(8)
Fixed-Point Arithmetic
Floating-Point Numbers
Floating-Point Arithmetic
Overflow and Underflow
Single- and Double-Precision Arithmetic
Error Analysis	20	(2)
Backward Error Analysis
Condition and Stability	22	(9)
Bibliographic Notes	24	(1)
Bibliography	24	(1)
Problems	24	(7)
Approximation and Algorithms	31	(21)
Approximation	31	(8)
Classes of Approximating Functions
Types of Approximations
The Case for Polynomial Approximation
Numerical Algorithms	39	(3)
Functionals and Error Analysis	42	(2)
The Method of Undetermined Coefficients	44	(8)
Bibliographic Notes	46	(1)
Bibliography	46	(1)
Problems	47	(5)
Interpolation	52	(37)
Introduction	52	(2)
Lagrangian Interpolation	54	(2)
Interpolation at Equal Intervals	56	(7)
Lagrangian Interpolation at Equal Intervals
Finite Differences
The Use of Interpolation Formulas	63	(3)
Iterated Interpolation	66	(2)
Inverse Interpolation	68	(2)
Hermite Interpolation	70	(3)
Spline Interpolation	73	(5)
Other Methods of Interpolation; Extrapolation	78	(11)
Bibliographic Notes	79	(1)
Bibliography	80	(1)
Problems	81	(8)
Numerical Differentiation, Numerical Quadrature, and Summation	89	(75)
Numerical Differentiation of Data	89	(4)
Numerical Differentiation of Functions	93	(3)
Numerical Quadrature: The General Problem	96	(2)
Numerical Integration of Data
Gaussian Quadrature	98	(4)
Weight Functions	102	(2)
Orthogonal Polynomials and Gaussian Quadrature	104	(1)
Gaussian Quadrature over Infinite Intervals	105	(3)
Particular Gaussian Quadrature Formulas	108	(5)
Gauss-Jacobi Quadrature
Gauss-Chebyshev Quadrature
Singular Integrals
Composite Quadrature Formulas	113	(5)
Newton-Cotes Quadrature Formulas	118	(8)
Composite Newton-Cotes Formulas
Romberg Integration
Adaptive Integration	126	(4)
Choosing a Quadrature Formula	130	(6)
Summation	136	(28)
The Euler-Maclaurin Sum Formula
Summation of Rational Functions; Factorial Functions
The Euler Transformation
Bibliographic Notes	145	(1)
Bibliography	146	(2)
Problems	148	(16)
The Numerical Solution of Ordinary Differential Equations	164	(83)
Statement of the Problem	164	(2)
Numerical Integration Methods	166	(5)
The Method of Undetermined Coefficients
Truncation Error in Numerical Integration Methods	171	(2)
Stability of Numerical Integration Methods	173	(10)
Convergence and Stability
Propagated-Error Bounds and Estimates
Predictor-Corrector Methods	183	(12)
Convergence of the Iterations
Predictors and Correctors
Error Estimation
Stability
Starting the Solution and Changing the Interval	195	(3)
Analytic Methods
A Numerical Method
Changing the Interval
Using Predictor-Corrector Methods	198	(10)
Variable-Order-Variable-Step Methods
Some Illustrative Examples
Runge-Kutta Methods	208	(16)
Errors in Runge-Kutta Methods
Second-Order Methods
Third-Order Methods
Fourth-Order Methods
Higher-Order Methods
Practical Error Estimation
Step-Size Strategy
Stability
Comparison of Runge-Kutta and Predictor-Corrector Methods
Other Numerical Integration Methods	224	(4)
Methods Based on Higher Derivatives
Extrapolation Methods
Stiff Equations	228	(19)
Bibliographic Notes	233	(1)
Bibliography	234	(2)
Problems	236	(11)
Functional Approximation: Least-Squares Techniques	247	(38)
Introduction	247	(1)
The Principle of Least Squares	248	(3)
Polynomial Least-Squares Approximations	251	(3)
Solution of the Normal Equations
Choosing the Degree of the Polynomial
Orthogonal-Polynomial Approximations	254	(6)
An Example of the Generation of Least-Squares Approximations	260	(3)
The Fourier Approximation	263	(22)
The Fast Fourier Transform
Least-Squares Approximations and Trigonometric Interpolation
Bibliographic Notes	274	(1)
Bibliography	275	(1)
Problems	276	(9)
Functional Approximation: Minimum maximum Error Techniques	285	(47)
General Remarks	285	(2)
Rational Functions, Polynomials, and Continued Fractions	287	(6)
Pade Approximations	293	(2)
An Example	295	(4)
Chebyshev Polynomials	299	(2)
Chebyshev Expansions	301	(6)
Economization of Rational Functions	307	(4)
Economization of Power Series
Generalization to Rational Functions
Chebyshev's Theorem on Minimax Approximations	311	(4)
Constructing Minimax Approximations	315	(17)
The Second Algorithm of Remes
The Differential Correction Algorithm
Bibliographic Notes	320	(1)
Bibliography	320	(2)
Problems	322	(10)
The Solution of Nonlinear Equations	332	(78)
Introduction	332	(2)
Functional Iteration	334	(4)
Computational Efficiency
The Secant Method	338	(6)
One-Point Iteration Formulas	344	(3)
Multipoint Iteration Formulas	347	(6)
Iteration Formulas Using General Inverse Interpolation
Derivative Estimated Iteration Formulas
Functional Iteration at a Multiple Root	353	(3)
Some Computational Aspects of Functional Iteration	356	(3)
The δ Process
Systems of Nonlinear Equations	359	(8)
The Zeros of Polynomials: The Problem	367	(4)
Sturm Sequences
Classical Methods	371	(12)
Bairstow's Method
Graeffe's Root-squaring Method
Bernoulli's Method
Laguerre's Method
The Jenkins-Traub Method	383	(9)
A Newton-based Method	392	(3)
The Effect of Coefficient Errors on the Roots; Ill-conditioned Polynomials	395	(15)
Bibliographic Notes	397	(2)
Bibliography	399	(1)
Problems	400	(10)
The Solution of Simultaneous Linear Equations	410	(73)
The Basic Theorem and the Problem	410	(2)
General Remarks	412	(2)
Direct Methods	414	(16)
Gaussian Elimination
Compact Forms of Gaussian Elimination
The Doolittle, Crout, and Cholesky Algorithms
Pivoting and Equilibration
Error Analysis	430	(7)
Roundoff-Error Analysis
Iterative Refinement	437	(3)
Matrix Iterative Methods	440	(3)
Stationary Iterative Processes and Related Matters	443	(7)
The Jacobi Iteration
The Gauss-Seidel Method
Roundoff Error in Iterative Methods
Acceleration of Stationary Iterative Processes
Matrix Inversion	450	(1)
Overdetermined Systems of Linear Equations	451	(6)
The Simplex Method for Solving Linear Programming Problems	457	(8)
Miscellaneous Topics	465	(18)
Bibliographic Notes	468	(2)
Bibliography	470	(2)
Problems	472	(11)
The Calculation of Eigenvalues and Eigenvectors of Matrices	483	(66)
Basic Relationships	483	(9)
Basic Theorems
The Characteristic Equation
The Location of, and Bounds on, the Eigenvalues
Canonical Forms
The Largest Eigenvalue in Magnitude by the Power Method	492	(9)
Acceleration of Convergence
The Inverse Power Method
The Eigenvalues and Eigenvectors of Symmetric Matrices	501	(12)
The Jacobi Method
Given's Method
Householder's Method
Methods for Nonsymmetric Matrices	513	(8)
Lanczos' Method
Supertriangularization
Jacobi-Type Methods
The LR and QR Algorithms	521	(15)
The Simple QR Algorithm
The Double QR Algorithm
Errors in Computed Eigenvalues and Eigenvectors	536	(13)
Bibliographic Notes	538	(1)
Bibliography	539	(2)
Problems	541	(8)
Index	549	(8)
Hints and Answers to Problems	557