You are here

Numerical Analysis

Timothy Sauer
Publisher: 
Pearson
Publication Date: 
2012
Number of Pages: 
646
Format: 
Hardcover
Edition: 
2
Price: 
136.00
ISBN: 
9780321783677
Category: 
Textbook
[Reviewed by
Allen Stenger
, on
07/27/2012
]

This is a very clearly-written modern introduction to many areas of numerical analysis. It provides a good balance of power and simplicity, with enough detail that the student can do something useful with what he learns, but not complicated enough to be overwhelming for lower-level undergraduates. The prerequisites are not stated, but the book assumes some familiarity with calculus and with matrices.

In addition to the traditional topics of accurate function evaluation, interpolation, integration, differential equations, and eigenvectors, the book has substantial chapters on the newer fields of random numbers and Monte Carlo methods, Fast Fourier Transform, and data compression. The book attempts to make the subject a harmonious whole rather than a bag of tricks by including frequent sidebars explaining the connection to the five key concepts of numerical analysis: convergence, complexity, conditioning, compression, and orthogonality.

Very Good Feature: The book warns the student early and often of the dangers of round-off errors and loss of significance, explained very concretely in terms of the IEEE-754 floating-point arithmetic standard, and illustrated with trouble-prone problems.

Each chapter includes a “Reality Check”: a couple of pages on a real-world problem. The amount of detail varies a lot, and the models are taken for granted. I think these are intended primarily for motivation, but some are detailed enough to be used for class projects.

Many theorems are stated but few are proven, so this is a technique book rather than a proof book, but with very good explanations. There are copious exercises, mostly of the drill sort, but some asking for proofs. The exercises are divided into plain Exercises, that can be done by hand, and Computer Problems. The book uses Matlab to illustrate its algorithms, but this is a small part of the total exposition, and Matlab knowledge or access is not required. The end-of-chapter notes are extensive and refer the student to other textbooks and monographs as well as some original papers.


Allen Stenger is a math hobbyist and retired software developer. He is webmaster and newsletter editor for the MAA Southwestern Section and is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis. He volunteers in his spare time at MathNerds.org, a math help site that fosters inquiry learning.

Preface

0. Fundamentals

0.1 Evaluating a polynomial

0.2 Binary numbers

            0.2.1 Decimal to binary

            0.2.2 Binary to decimal

0.3 Floating point representation of real numbers

            0.3.1 Floating point formats

            0.3.2 Machine representation

            0.3.3 Addition of floating point numbers

0.4 Loss of significance

0.5 Review of calculus

0.6 Software and Further Reading

 

1. Solving Equations

1.1 The Bisection Method

            1.1.1 Bracketing a root

            1.1.2 How accurate and how fast?

1.2 Fixed point iteration

            1.2.1 Fixed points of a function

            1.2.2 Geometry of Fixed Point Iteration

            1.2.3 Linear Convergence of Fixed Point Iteration

            1.2.4 Stopping criteria

1.3 Limits of accuracy

            1.3.1 Forward and backward error

            1.3.2 The Wilkinson polynomial

            1.3.3 Sensitivity and error magnification

1.4 Newton’s Method

            1.4.1 Quadratic convergence of Newton's method

            1.4.2 Linear convergence of Newton's method

1.5 Root-finding without derivatives

            1.5.1 Secant method and variants

            1.5.2 Brent's Method

REALITY CHECK 1: Kinematics of the Stewart platform

1.6 Software and Further Reading

 

2. Systems of Equations

2.1 Gaussian elimination

            2.1.1 Naive Gaussian elimination

            2.1.2 Operation counts

2.2 The LU factorization

            2.2.1 Backsolving with the LU factorization

            2.2.2 Complexity of the LU factorization

2.3 Sources of error

            2.3.1 Error magnification and condition number

            2.3.2 Swamping

2.4 The PA=LU factorization

            2.4.1 Partial pivoting

            2.4.2 Permutation matrices

            2.4.3 PA = LU factorization

REALITY CHECK 2: The Euler-Bernoulli Beam

2.5 Iterative methods

            2.5.1 Jacobi Method

            2.5.2 Gauss-Seidel Method and SOR

            2.5.3 Convergence of iterative methods

            2.5.4 Sparse matrix computations

2.6 Methods for symmetric positive-definite matrices

            2.6.1 Symmetric positive-definite matrices

            2.6.2 Cholesky factorization

            2.6.3 Conjugate Gradient Method

            2.6.4 Preconditioning

2.7 Nonlinear systems of equations

            2.7.1 Multivariate Newton's method

            2.7.2 Broyden's method

2.8 Software and Further Reading

 

3. Interpolation

3.1 Data and interpolating functions

            3.1.1 Lagrange interpolation

            3.1.2 Newton's divided differences

            3.1.3 How many degree d polynomials pass through n points?

            3.1.4 Code for interpolation

            3.1.5 Representing functions by approximating polynomials

3.2 Interpolation error

            3.2.1 Interpolation error formula

            3.2.2 Proof of Newton form and error formula

            3.2.3 Runge phenomenon

3.3 Chebyshev interpolation

            3.3.1 Chebyshev's Theorem

            3.3.2 Chebyshev polynomials

            3.3.3 Change of interval

3.4 Cubic splines

            3.4.1 Properties of splines

            3.4.2 Endpoint conditions

3.5 Bézier curves

REALITY CHECK 3: Constructing fonts from Bézier splines

3.6 Software and Further Reading

 

4. Least Squares

4.1 Least squares and the normal equations

            4.1.1 Inconsistent systems of equations

            4.1.2 Fitting models to data

4.2 Linear and nonlinear models

            4.1.3 Conditioning of least squares

4.2 A survey of models

            4.2.1 Periodic data

            4.2.2 Data linearization

4.3 QR factorization

            4.3.1 Gram-Schmidt orthogonalization and least squares

            4.3.2 Modified Gram-Schmidt orthogonalization

            4.3.3 Householder reflectors

4.4 Generalized Minimum Residual (GMRES) Method

            4.4.1 Krylov methods

            4.4.2 Preconditioned GMRES

4.5 Nonlinear least squares

            4.5.1 Gauss-Newton method

            4.5.2 Models with nonlinear parameters

            4.5.3 Levenberg-Marquardt method

REALITY CHECK 4: GPS, conditioning and nonlinear least squares

4.6 Software and Further Reading

 

5. Numerical Differentiation and Integration

5.1 Numerical differentiation

            5.1.1 Finite difference formulas

            5.1.2 Rounding error

            5.1.3 Extrapolation

            5.1.4 Symbolic differentiation and integration

5.2 Newton-Cotes formulas for numerical integration

            5.2.1 Trapezoid rule

            5.2.2 Simpson's Rule

            5.2.3 Composite Newton-Cotes Formulas

            5.2.4 Open Newton-Cotes methods

5.3 Romberg integration

5.4 Adaptive quadrature

5.5 Gaussian quadrature

REALITY CHECK 5: Motion control in computer-aided modelling

5.6 Software and Further Reading

 

6. Ordinary Differential Equations

6.1 Initial value problems

            6.1.1 Euler's method

            6.1.2 Existence, uniqueness, and continuity for solutions

            6.1.3 First-order linear equations

6.2 Analysis of IVP solvers

            6.2.1 Local and global truncation error

            6.2.2 The explicit trapezoid method

            6.2.3 Taylor methods

6.3 Systems of ordinary differential equations

            6.3.1 Higher order equations

            6.3.2 Computer simulation: The pendulum

            6.3.3 Computer simulation: Orbital mechanics

6.4 Runge-Kutta methods and applications

            6.4.1 The Runge-Kutta family

            6.4.2 Computer simulation: The Hodgkin-Huxley neuron

            6.4.3 Computer simulation: The Lorenz equations

REALITY CHECK 6: The Tacoma Narrows Bridge

6.5 Variable step-size methods

            6.5.1 Embedded Runge-Kutta pairs

            6.5.2 Order 4/5 methods

6.6 Implicit methods and stiff equations

6.7 Multistep methods

            6.7.1 Generating multistep methods

            6.7.2 Explicit multistep methods

            6.7.3 Implicit multistep methods

6.8 Software and Further Reading

 

7. Boundary Value Problems

7.1 Shooting method

            7.1.1 Solutions of boundary value problems

            7.1.2 Shooting method implementation

REALITY CHECK 7: Buckling of a circular ring

7.2 Finite difference methods

            7.2.1 Linear boundary value problems

            7.2.2 Nonlinear boundary value problems

7.3 Collocation and the Finite Element Method

            7.3.1 Collocation

            7.3.2 Finite elements and the Galerkin method

7.4 Software and Further Reading

 

8. Partial Differential Equations

8.1 Parabolic equations

            8.1.1 Forward difference method

            8.1.2 Stability analysis of forward difference method

            8.1.3 Backward difference method

            8.1.4 Crank-Nicolson method

8.2 Hyperbolic equations

            8.2.1 The wave equation

            8.2.2 The CFL condition

8.3 Elliptic equations

            8.3.1 Finite difference method for elliptic equations

REALITY CHECK 8: Heat distribution on a cooling fin

            8.3.2 Finite element method for elliptic equations

8.4 Nonlinear partial differential equations

            8.4.1 Implicit Newton solver

            8.4.2 Nonlinear equations in two space dimensions

8.5 Software and Further Reading

 

9. Random Numbers and Applications

9.1 Random numbers

            9.1.1 Pseudo-random numbers

            9.1.2 Exponential and normal random numbers

9.2 Monte-Carlo simulation

            9.2.1 Power laws for Monte Carlo estimation

            9.2.2 Quasi-random numbers

9.3 Discrete and continuous Brownian motion

            9.3.1 Random walks

            9.3.2 Continuous Brownian motion

9.4 Stochastic differential equations

            9.4.1 Adding noise to differential equations

            9.4.2 Numerical methods for SDEs

REALITY CHECK 9: The Black-Scholes formula

9.5 Software and Further Reading

 

10. Trigonometric Interpolation and the FFT

10.1 The Fourier Transform

            10.1.1 Complex arithmetic

            10.1.2 Discrete Fourier Transform

            10.1.3 The Fast Fourier Transform

10.2 Trigonometric interpolation

            10.2.1 The DFT Interpolation Theorem

            10.2.2 Efficient evaluation of trigonometric functions

10.3 The FFT and signal processing

            10.3.1 Orthogonality and interpolation

            10.3.2 Least squares fitting with trigonometric functions

            10.3.3 Sound, noise, and filtering

REALITY CHECK 10: The Wiener filter

10.4 Software and Further Reading

 

11. Compression

11.1 The Discrete Cosine Transform

            11.1.1 One-dimensional DCT

            11.1.2 The DCT and least squares approximation

11.2 Two-dimensional DCT and image compression

            11.2.1 Two-dimensional DCT

            11.2.2 Image compression

            11.2.3 Quantization

11.3 Huffman coding

            11.3.1 Information theory and coding

            11.3.2 Huffman coding for the JPEG format

11.4 Modified DCT and audio compression

            11.4.1 Modified Discrete Cosine Transform

            11.4.2 Bit quantization

REALITY CHECK 11: A simple audio codec using the MDCT

11.5 Software and Further Reading

 

12. Eigenvalues and Singular Values

12.1 Power iteration methods

            12.1.1 Power iteration

            12.1.2 Convergence of power iteration

            12.1.3 Inverse power iteration

            12.1.4 Rayleigh quotient iteration

12.2 QR algorithm

            12.2.1 Simultaneous iteration

            12.2.2 Real Schur form and QR

            12.2.3 Upper Hessenberg form

REALITY CHECK 12: How search engines rate page quality

12.3 Singular value decomposition

            12.3.1 Finding the SVD in general

            12.3.2 Special case: symmetric matrices

12.4 Applications of the SVD

            12.4.1 Properties of the SVD

            12.4.2 Dimension reduction

            12.4.3 Compression

            12.4.4 Calculating the SVD

12.5 Software and Further Reading

 

13. Optimization

13.1 Unconstrained optimization without derivatives

            13.1.1 Golden section search

            13.1.2 Successive parabolic interpolation

            13.1.3 Nelder-Mead search

13.2 Unconstrained optimization with derivatives

            13.2.1 Newton's method

            13.2.2 Steepest descent

            13.2.3 Conjugate gradient search

            13.2.4 Nonlinear least squares

REALITY CHECK 13: Molecular conformation and numerical optimization

13.3 Software and Further Reading

 

APPENDIX

Appendix A: Matrix Algebra

A.1 Matrix fundamentals

A.2 Block multiplication

A.3 Eigenvalues and eigenvectors

A.4 Symmetric matrices

A.5 Vector calculus

 

Appendix B: Introduction to MATLAB

B.1 Starting MATLAB

B.2 MATLAB graphics

B.3 Programming in MATLAB

B.4 Flow control

B.5 Functions

B.6 Matrix operations

B.7 Animation and movies

References