Scientific Computing: An Introductory Survey

Engineering at Illinois Engineering at Illinois

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