Scientific Computing : An Introductory Survey

by Heath, Michael T.

• ISBN13: 9780070276840
• ISBN10: 0070276846
• Edition: 1st
• Format: Hardcover
• Copyright: 1996-12-01
• Publisher: McGraw-Hill Higher Education

Table of Contents

Preface	xv
Notation	xix
Scientific Computing	1	(34)
Introduction	1	(1)
General Strategy
Approximations in Scientific Computation	2	(6)
Sources of Approximation
Data Error and Computational Error
Truncation Error and Rounding Error
Absolute Error and Relative Error
Sensitivity and Conditioning
Backward Error Analysis
Stability and Accuracy
Computer Arithmetic	8	(12)
Floating-Point Numbers
Normalization
Properties of Floating-Point Systems
Rounding
Machine Precision
Subnormals and Gradual Underflow
Exceptional Values
Floating-Point Arithmetic
Cancellation
Mathematical Software	20	(5)
Mathematical Software Libraries
Scientific Computing Environments
Practical Advice on Software
Historical Notes and Further Reading	25	(10)
Systems of Linear Equations	35	(46)
Linear Systems	35	(2)
Singularity and Nonsingularity
Solving Linear Systems	37	(15)
Triangular Linear Systems
Elementary Elimination Matrices
Gaussian Elimination and LU Factorization
Pivoting
Implementation of Gaussian Elimination
Complexity of Solving Linear Systems
Gauss-Jordan Elimination
Solving Modified Problems
Norms and Condition Numbers	52	(4)
Vector Norms
Matrix Norms
Condition Number of a Matrix
Accuracy of Solutions	56	(5)
Residual of a Solution
Estimating Accuracy
Improving Accuracy
Special Types of Linear Systems	61	(4)
Symmetric Positive Definite Systems
Symmetric Indefinite Systems
Band Systems
Iterative Methods for Linear Systems	65	(1)
Software for Linear Systems	65	(3)
LINPACK and LAPACK
Basic Linear Algebra Subprograms
Historical Notes and Further Reading	68	(13)
Linear Least Squares	81	(32)
Data Fitting	81	(1)
Linear Least Squares	82	(2)
Normal Equations Method	84	(4)
Orthogonality
Normal Equations Method
Augmented System Method
Orthogonalization Methods	88	(13)
Triangular Least Squares Problems
Orthogonal Transformations
QR Factorization
Householder Transformations
Givens Rotations
Gram-Schmidt Orthogonalization
Rank Deficiency
Column Pivoting
Comparison of Methods	101	(1)
Software for Linear Least Squares	102	(1)
Historical Notes and Further Reading	103	(10)
Eigenvalues and Singular Values	113	(36)
Eigenvalues and Eigenvectors	113	(6)
Nonuniquences
Characteristic Polynomial
Properties of Eigenvalue Problems
Similarity Transformations
Conditioning of Eigenvalue Problems
Methods for Computing All Eigenvalues	119	(5)
Characteristic Polynomial
Jacobi Method for Symmetric Matrices
QR Iteration
Preliminary Reduction
Methods for Computing Selected Eigenvalues	124	(9)
Power Method
Normalization
Geometric Interpretation
Shifts
Deflation
Inverse Iteration
Rayleigh Quotient
Rayleigh Quotient Iteration
Lanczos Method for Symmetric Matrices
Spectrum-Slicing Methods for Symmetric Matrices
Generalized Eigenvalue Problems	133	(1)
Singular Values	134	(3)
Singular Value Decomposition
Applications of SVD
Software for Eigenvalues and Singular Values	137	(2)
Historical Notes and Further Reading	139	(10)
Nonlinear Equations	149	(30)
Nonlinear Equations	149	(3)
Solutions of Nonlinear Equations
Convergence Rates of Iterative Methods
Nonlinear Equations in One Dimension	152	(12)
Bisection Method
Fixed-Point Iteration
Newton's Method
Secant Method
Inverse Interpolation
Linear Fractional Interpolation
Safeguarded Methods
Zeros of Polynomials
Systems of Nonlinear Equations	164	(6)
Fixed-Point Iteration
Newton's Method
Secant Updating Methods
Broyden's Method
Robust Newton-Like Methods
Software for Nonlinear Equations	170	(1)
Historical Notes and Further Reading	171	(8)
Optimization	179	(35)
Optimization Problems	179	(3)
Local versus Global Optimization
Relationship to Nonlinear Equations
Accuracy of Solutions
One-Dimensional Optimization	182	(5)
Golden Section Search
Successive Parabolic Interpolation
Newton's Method
Safeguarded Methods
Multidimensional Unconstrained Optimization	187	(8)
Direct Search Methods
Steepest Descent Method
Newton's Method
Quasi-Newton Methods
Secant Updating Methods
Conjugate Gradient Method
Truncated Newton Methods
Nonlinear Least Squares	195	(3)
Gauss-Newton Method
Levenberg-Marquardt Method
Constrained Optimization	198	(5)
Linear Programming
Software for Optimization	203	(1)
Historical Notes and Further Reading	204	(10)
Interpolation	214	(25)
Interpolation	214	(3)
Purposes for Interpolation
Interpolation versus Approximation
Choice of Interpolating Function
Basis Functions
Polynomial Interpolation	217	(11)
Evaluating Polynomials
Lagrange Interpolation
Newton Interpolation
Orthogonal Polynomials
Interpolating a Function
High-Degree Polynomial Interpolation
Placement of Interpolation Points
Piecewise Polynomial Interpolation	228	(5)
Hermite Cubic Interpolation
Cubic Spline Interpolation
Hermite Cubic versus Cubic Spline Interpolation
B-splines
Software for Interpolation	233	(1)
Software for Special Functions
Historical Notes and Further Reading	234	(5)
Numerical Integration and Differentiation	239	(30)
Numerical Quadrature	239	(1)
Quadrature Rules
Newton-Cotes Quadrature	240	(5)
Newton-Cotes Quadrature Rules
Method of Undetermined Coefficients
Error Estimation
Polynomial Degree
Gaussian Quadrature	245	(4)
Gaussian Quadrature Rules
Change of Interval
Gauss-Kronrod Quadrature Rules
Composite and Adaptive Quadrature	249	(2)
Composite Quadrature Rules
Automatic and Adaptive Quadrature
Other Integration Problems	251	(2)
Integrating Tabular Data
Infinite Intervals
Double Integrals
Multiple Integrals
Integral Equations	253	(3)
Numerical Differentiation	256	(2)
Finite Difference Approximations
Automatic Differentiation
Richardson Extrapolation	258	(2)
Software for Numerical Integration and Differentiation	260	(1)
Historical Notes and Further Reading	261	(8)
Initial Value Problems for Ordinary Differential Equations	269	(32)
Ordinary Differential Equations	269	(4)
Initial Value Problems
Higher-Order ODEs
Stable and Unstable ODEs
Numerical Solution of ODEs	273	(3)
Euler's Method
Accuracy and Stability	276	(4)
Order of Accuracy
Stability of a Numerical Method
Stepsize Control
Implicit Methods	280	(2)
Stiff Differential Equations	282	(2)
Survey of Numerical Methods for ODEs	284	(8)
Taylor Series Methods
Runge-Kutta Methods
Extrapolation Methods
Multistep Methods
Multivalue Methods
Software for ODE Initial Value Problems	292	(1)
Historical Notes and Further Reading	293	(8)
Boundary Value Problems for Ordinary Differential Equations	301	(14)
Boundary Value Problems	301	(1)
Shooting Method	302	(2)
Superposition Method	304	(1)
Finite Difference Method	305	(1)
Finite Element Method	306	(4)
Eigenvalue Problems	310	(1)
Software for ODE Boundary Value Problems	311	(1)
Historical Notes and Further Reading	311	(4)
Partial Differential Equations	315	(42)
Partial Differential Equations	315	(1)
Classification of Partial Differential Equations
Time-Dependent Problems	316	(9)
Semidiscrete Methods Using Finite Differences
Semidiscrete Methods Using Finite Elements
Fully Discrete Methods
Implicit Finite Difference Methods
Hyperbolic versus Parabolic Problems
Time-Independent Problems	325	(2)
Finite Difference Methods
Finite Element Methods
Direct Methods for Sparse Linear Systems	327	(4)
Sparse Factorization Methods
Fast Direct Methods
Iterative Methods for Linear Systems	331	(12)
Stationary Iterative Methods
Jacobi Method
Gauss-Seidel Method
Successive Over-Relaxation
Conjugate Gradient Method
Rate of Convergence
Multigrid Methods
Comparison of Methods	343	(3)
Software for Partial Differential Equations	346	(2)
Software for Initial Value Problems
Software for Boundary Value Problems
Software for Sparse Linear Systems
Historical Notes and Further Reading	348	(9)
Fast Fourier Transform	357	(17)
Trigonometric Interpolation	357	(5)
Continuous Fourier Transform
Fourier Series
Discrete Fourier Transform
FFT Algorithm	362	(4)
Limitations of the FFT
Applications of DFT	366	(2)
Fast Polynomial Multiplication
Wavelets	368	(1)
Software for FFT	369	(1)
Historical Notes and Further Reading	369	(5)
Random Numbers and Stochastic Simulation	374	(13)
Stochastic Simulation	374	(1)
Randomness and Random Numbers	375	(1)
Random Number Generators	376	(2)
Congruential Generators
Fibonacci Generators
Nonuniform Distributions
Quasi-Random Sequences	378	(1)
Software for Generating Random Numbers	379	(1)
Historical Notes and Further Reading	379	(8)
Bibliography	387	(12)
Index	399