# Scientific Computing: An Introductory Survey

##### 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.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