Scientific Computing: An Introductory Survey
Table of Contents
Chapter 1 – Scientific Computing
- 1.1 Introduction
- 1.1.1 Computational Problems
- 1.1.2 General Strategy
- 1.2 Approximations in Scientific Computation
- 1.2.1 Sources of Approximation
- 1.2.2 Absolute Error and Relative Error
- 1.2.3 Data Error and Computational Error
- 1.2.4 Truncation Error and Rounding Error
- 1.2.5 Forward and Backward Error
- 1.2.6 Sensitivity and Conditioning
- 1.2.7 Stability and Accuracy
- 1.3 Computer Arithmetic
- 1.3.1 Floating-Point Numbers
- 1.3.2 Normalization
- 1.3.3 Properties of Floating-Point Systems
- 1.3.4 Rounding
- 1.3.5 Machine Precision
- 1.3.6 Subnormals and Gradual Underflow
- 1.3.7 Exceptional Values
- 1.3.8 Floating-Point Arithmetic
- 1.3.9 Cancellation
- 1.3.10 Other Arithmetic Systems
- 1.3.11 Complex Arithmetic
- 1.4 Mathematical Software
- 1.4.1 Mathematical Software Libraries
- 1.4.2 Scientific Computing Environments
- 1.4.3 Extended Arithmetic Packages
- 1.4.4 Practical Advice on Software
- 1.5 Historical Notes and Further Reading
Chapter 2 – Systems of Linear Equations
- 2.1 Linear Systems
- 2.2 Existence and Uniqueness
- 2.3 Sensitivity and Conditioning
- 2.3.1 Vector Norms
- 2.3.2 Matrix Norms
- 2.3.3 Matrix Condition Number
- 2.3.4 Error Bounds
- 2.3.5 Residual
- 2.4 Solving Linear Systems
- 2.4.1 Problem Transformations
- 2.4.2 Triangular Linear Systems
- 2.4.3 Elementary Elimination Matrices
- 2.4.4 Gaussian Elimination and LU Factorization
- 2.4.5 Pivoting
- 2.4.6 Implementation of Gaussian Elimination
- 2.4.7 Complexity of Solving Linear Systems
- 2.4.8 Gauss-Jordan Elimination
- 2.4.9 Solving Modified Problems
- 2.4.10 Improving Accuracy
- 2.5 Special Types of Linear Systems
- 2.5.1 Symmetric Positive Definite Systems
- 2.5.2 Symmetric Indefinite Systems
- 2.5.3 Banded Systems
- 2.6 Iterative Methods for Linear Systems
- 2.7 Software for Linear Systems
- 2.7.1 LINPACK and LAPACK
- 2.7.2 Basic Linear Algebra Subprograms
- 2.8 Historical Notes and Further Reading
Chapter 3 – Linear Least Squares
- 3.1 Linear Least Squares Problems
- 3.2 Existence and Uniqueness
- 3.2.1 Normal Equations
- 3.2.2 Orthogonality and Orthogonal Projectors
- 3.3 Sensitivity and Conditioning
- 3.4 Problem Transformations
- 3.4.1 Normal Equations
- 3.4.2 Augmented System Method
- 3.4.3 Orthogonal Transformations
- 3.4.4 Triangular Least Squares Problems
- 3.4.5 QR Factorization
- 3.5 Orthogonalization Methods
- 3.5.1 Householder Transformations
- 3.5.2 Givens Rotations
- 3.5.3 Gram-Schmidt Orthogonalization
- 3.5.4 Rank Deficiency
- 3.6 Singular Value Decomposition
- 3.6.1 Other Applications of SVD
- 3.7 Comparison of Methods
- 3.8 Software for Linear Least Squares
- 3.9 Historical Notes and Further Reading
Chapter 4 – Eigenvalue Problems
- 4.1 Eigenvalues and Eigenvectors
- 4.2 Existence and Uniqueness
- 4.2.1 Characteristic Polynomial
- 4.2.2 Multiplicity and Diagonalizability
- 4.2.3 Eigenspaces and Invariant Subspaces
- 4.2.4 Properties of Matrices and Eigenvalue Problems
- 4.2.5 Localizing Eigenvalues
- 4.3 Sensitivity and Conditioning
- 4.4 Problem Transformations
- 4.4.1 Diagonal, Triangular, and Block Triangular Forms
- 4.5 Computing Eigenvalues and Eigenvectors
- 4.5.1 Power Iteration
- 4.5.2 Inverse Iteration
- 4.5.3 Rayleigh Quotient Iteration
- 4.5.4 Deflation
- 4.5.5 Simultaneous Iteration
- 4.5.6 QR Iteration
- 4.5.7 Krylov Subspace Methods
- 4.5.8 Jacobi Method
- 4.5.9 Bisection or Spectrum Slicing
- 4.5.10 Divide-and-Conquer
- 4.5.11 Relatively Robust Representation
- 4.5.12 Comparison of Methods
- 4.6 Generalized Eigenvalue Problems
- 4.7 Computing the Singular Value Decomposition
- 4.8 Software for Eigenvalue Problems
- 4.9 Historical Notes and Further Reading
Chapter 5 – Nonlinear Equations
- 5.1 Nonlinear Equations
- 5.2 Existence and Uniqueness
- 5.3 Sensitivity and Conditioning
- 5.4 Convergence Rates and Stopping Criteria
- 5.5 Nonlinear Equations in One Dimension
- 5.5.1 Interval Bisection
- 5.5.2 Fixed-Point Iteration
- 5.5.3 Newton's Method
- 5.5.4 Secant Method
- 5.5.5 Inverse Interpolation
- 5.5.6 Linear Fractional Interpolation
- 5.5.7 Safeguarded Methods
- 5.5.8 Zeros of Polynomials
- 5.6 Systems of Nonlinear Equations
- 5.6.1 Fixed-Point Iteration
- 5.6.2 Newton's Method
- 5.6.3 Secant Updating Methods
- 5.6.4 Robust Newton-Like Methods
- 5.7 Software for Nonlinear Equations
- 5.8 Historical Notes and Further Reading
Chapter 6 – Optimization
- 6.1 Optimization Problems
- 6.2 Existence and Uniqueness
- 6.2.1 Convexity
- 6.2.2 Unconstrained Optimality Conditions
- 6.2.3 Constrained Optimality Conditions
- 6.3 Sensitivity and Conditioning
- 6.4 Optimization in One Dimension
- 6.4.1 Golden Section Search
- 6.4.2 Successive Parabolic Interpolation
- 6.4.3 Newton's Method
- 6.4.4 Safeguarded Methods
- 6.5 Multidimensional Unconstrained Optimization
- 6.5.1 Direct Search
- 6.5.2 Steepest Descent
- 6.5.3 Newton's Method
- 6.5.4 Quasi-Newton Methods
- 6.5.5 Secant Updating Methods
- 6.5.6 Conjugate Gradient Method
- 6.5.7 Truncated or Inexact Newton Methods
- 6.6 Nonlinear Least Squares
- 6.6.1 Gauss-Newton Method
- 6.6.2 Levenberg-Marquardt Method
- 6.7 Constrained Optimization
- 6.7.1 Sequential Quadratic Programming
- 6.7.2 Penalty and Barrier Methods
- 6.7.3 Linear Programming
- 6.8 Software for Optimization
- 6.9 Historical Notes and Further Reading
Chapter 7 – Interpolation
- 7.1 Interpolation
- 7.2 Existence, Uniqueness, and Conditioning
- 7.3 Polynomial Interpolation
- 7.3.1 Monomial Basis
- 7.3.2 Lagrange Interpolation
- 7.3.3 Newton Interpolation
- 7.3.4 Orthogonal Polynomials
- 7.3.5 Interpolating Continuous Functions
- 7.4 Piecewise Polynomial Interpolation
- 7.4.1 Hermite Cubic Interpolation
- 7.4.2 Cubic Spline Interpolation
- 7.4.3 B-splines
- 7.5 Software for Interpolation
- 7.5.1 Software for Special Functions
- 7.6 Historical Notes and Further Reading
Chapter 8 – Numerical Integration and Differentiation
- 8.1 Integration
- 8.2 Existence, Uniqueness, and Conditioning
- 8.3 Numerical Quadrature
- 8.3.1 Newton-Cotes Quadrature
- 8.3.2 Clenshaw-Curtis Quadrature
- 8.3.3 Gaussian Quadrature
- 8.3.4 Progressive Gaussian Quadrature
- 8.3.5 Composite Quadrature
- 8.3.6 Adaptive Quadrature
- 8.4 Other Integration Problems
- 8.4.1 Tabular Data
- 8.4.2 Improper Integrals
- 8.4.3 Double Integrals
- 8.4.4 Multiple Integrals
- 8.5 Integral Equations
- 8.6 Numerical Differentiation
- 8.6.1 Finite Difference Approximations
- 8.6.2 Automatic Differentiation
- 8.7 Richardson Extrapolation
- 8.8 Software for Numerical Integration and Differentiation
- 8.9 Historical Notes and Further Reading
Chapter 9 – Initial Value Problems for Ordinary Differential
Equations
- 9.1 Ordinary Differential Equations
- 9.2 Existence, Uniqueness, and Conditioning
- 9.3 Numerical Solution of ODEs
- 9.3.1 Euler's Method
- 9.3.2 Accuracy and Stability
- 9.3.3 Implicit Methods
- 9.3.4 Stiffness
- 9.3.5 Taylor Series Methods
- 9.3.6 Runge-Kutta Methods
- 9.3.7 Extrapolation Methods
- 9.3.8 Multistep Methods
- 9.3.9 Multivalue Methods
- 9.4 Software for ODE Initial Value Problems
- 9.5 Historical Notes and Further Reading
Chapter 10 – Boundary Value Problems for Ordinary Differential
Equations
- 10.1 Boundary Value Problems
- 10.2 Existence, Uniqueness, and Conditioning
- 10.3 Shooting Method
- 10.4 Finite Difference Method
- 10.5 Collocation Method
- 10.6 Galerkin Method
- 10.7 Eigenvalue Problems
- 10.8 Software for ODE Boundary Value Problems
- 10.9 Historical Notes and Further Reading
Chapter 11 – Partial Differential Equations
- 11.1 Partial Differential Equations
- 11.2 Time-Dependent Problems
- 11.2.1 Semidiscrete Methods
- 11.2.2 Fully Discrete Methods
- 11.3 Time-Independent Problems
- 11.3.1 Finite Difference Methods
- 11.3.2 Finite Element Methods
- 11.4 Direct Methods for Sparse Linear Systems
- 11.4.1 Sparse Factorization Methods
- 11.4.2 Fast Direct Methods
- 11.5 Iterative Methods for Linear Systems
- 11.5.1 Stationary Iterative Methods
- 11.5.2 Jacobi Method
- 11.5.3 Gauss-Seidel Method
- 11.5.4 Successive Over-Relaxation
- 11.5.5 Conjugate Gradient Method
- 11.5.6 Rate of Convergence
- 11.5.7 Multigrid Methods
- 11.6 Comparison of Methods
- 11.7 Software for Partial Differential Equations
- 11.7.1 Software for Initial Value Problems
- 11.7.2 Software for Boundary Value Problems
- 11.7.3 Software for Sparse Linear Systems
- 11.8 Historical Notes and Further Reading
Chapter 12 – Fast Fourier Transform
- 12.1 Trigonometric Interpolation
- 12.1.1 Discrete Fourier Transform
- 12.2 FFT Algorithm
- 12.2.1 Limitations of FFT
- 12.3 Applications of DFT
- 12.3.1 Fast Polynomial Multiplication
- 12.4 Wavelets
- 12.5 Software for FFT
- 12.6 Historical Notes and Further Reading
Chapter 13 – Random Numbers and Stochastic Simulation
- 13.1 Stochastic Simulation
- 13.2 Randomness and Random Numbers
- 13.3 Random Number Generators
- 13.3.1 Congruential Generators
- 13.3.2 Fibonacci Generators
- 13.3.3 Nonuniform Distributions
- 13.4 Quasi-Random Sequences
- 13.5 Software for Generating Random Numbers
- 13.6 Historical Notes and Further Reading
Bibliography
Index