# Numerical Analysis, 3rd edition

Published by Pearson (October 30, 2017) © 2018

**Timothy Sauer**George Mason University

## eTextbook

- Anytime, anywhere learning with the Pearson+ app
- Easy-to-use search, navigation and notebook
- Simpler studying with flashcards

- Hardcover, paperback or looseleaf edition
- Affordable rental option for select titles
- Free shipping on looseleafs and traditional textbooks

**The most readable and relevant numerical analysis text is now infused with web links at point-of-use.**

** Numerical Analysis, 3rd Edition** is written for students of engineering, science, mathematics, and computer science who have completed elementary calculus and matrix algebra. The book covers both standard topics and some of the more advanced numerical methods used by computational scientists and engineers, while maintaining a level appropriate for undergraduates.

Students learn to construct and explore algorithms for solving science and engineering problems while situating these algorithms in a landscape of some potent and far-reaching principles. Specifically, the author cultivates a grasp of the fundamental concepts that permeate numerical analysis, including convergence, complexity, conditioning, compression, orthogonality, and its competing concerns of accuracy and efficiency.

MATLAB^{®} software is used both for exposition of algorithms and as a suggested platform for student assignments and projects. The **3rd Edition **is web enhanced, with over 200 short URLs that take students beyond the book to useful digital resources created to support their use of the text.

**Structured to move from foundational, elementary ideas at the outset to more sophisticated concepts**later in the text.contains enough content for a two-semester course, but can also be used for a one-semester course with judicious choice of topics.*Numerical Analysis*

**Spotlights**throughout the text highlight the five major ideas of numerical analysis:**convergence, complexity, conditioning, compression,**and**orthogonality.**

- These Spotlights comment on the topic at hand and make informal connections to other expressions of the same concept elsewhere in the book, helping students synthesize new material with what they already know.

**The well-received Reality Check feature**appears in each chapter to provide extended examples of the way numerical methods lead to solutions of important technological problems, making the topics immediately relevant.

**MATLAB**giving students and instructors guidance on using this important software tool.^{®}expositions appear throughout the text,

Appendix B is a short MATLAB tutorial that can be used as a first introduction to students who have not used MATLAB, or as a reference to students already familiar with the software.

**NEW! Short URLs in the text margins**(235 total) take students directly to relevant content to support their use of the textbook, including:**MATLAB Code**(goo.gl/VxzXyw): Longer instances of MATLAB code are available for students in *.m format.**Solutions to Selected Exercises**(goo.gl/2j5gI7): In previous editions a Student Solutions Manual was available for purchase separately. The 3rd Edition gives students access to solutions for selected exercises online at no extra charge.**Additional examples**(goo.gl/lFQb0B): Each section of the 3rd Edition is enhanced with extra new examples, designed to reinforce the text exposition and to ease the reader's transition to active solution of exercises and computer problems. The worked-out solutions of these examples, more than one hundred in total, are available online. Some of the solutions are in video format (created by the author).The homepage for all web content supporting the text is goo.gl/zQNJeP.

**NEW! Several dozen new exercises and computer problems**have been added to the 3rd Edition.

**Short URLs in the text margins**(235 total) take students directly to relevant content to support their use of the textbook, including:**MATLAB Code**(goo.gl/VxzXyw): Longer instances of MATLAB code are available for students in *.m format.**Solutions to Selected Exercises**(goo.gl/2j5gI7): In previous editions a Student Solutions Manual was available for purchase separately. The 3rd Edition gives students access to solutions for selected exercises online at no extra charge.**Additional examples**(goo.gl/lFQb0B): Each section of the 3rd Edition is enhanced with extra new examples, designed to reinforce the text exposition and to ease the reader's transition to active solution of exercises and computer problems. The worked-out solutions of these examples, more than one hundred in total, are available online. Some of the solutions are in video format (created by the author).The homepage for all web content supporting the text is goo.gl/zQNJeP.

**More detailed discussion of several key concepts**includes theory of polynomial interpolation, multi-step differential equation solvers, boundary value problems, and the singular value decomposition, among others.

**The Reality Check on audio compression**in Chapter 11 has been refurbished and simplified, and other MATLAB codes have been added and updated throughout the text.

**Several dozen new exercises and computer problems**have been added to the 3rd Edition.

**CHAPTER 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 formats0.3.2 Machine representation

0.3.3 Addition of floating point numbers

0.4 Loss of Significance

0.5 Review of Calculus

Software and Further Reading

**CHAPTER 1 Solving Equations**

1.1 The Bisection Method

1.1.1 Bracketing a root1.1.2 How accurate and how fast?

1.2 Fixed-Point Iteration

1.2.1 Fixed points of a function1.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 error1.3.2 The Wilkinson polynomial

1.3.3 Sensitivity of root-finding

1.4 Newton’s Method

1.4.1 Quadratic convergence of Newton’s Method1.4.2 Linear convergence of Newton’s Method

1.5 Root-Finding without Derivatives

1.5.1 Secant Method and variants1.5.2 Brent’s Method

Reality Check 1: Kinematics of the Stewart platform

Software and Further Reading

CHAPTER 2

2.1 Gaussian Elimination

2.1.1 Naive Gaussian elimination2.1.2 Operation counts

2.2 The LU Factorization

2.2.1 Matrix form of Gaussian elimination2.2.2 Back substitution with the LU factorization

2.2.3 Complexity of the LU factorization

2.3 Sources of Error

2.3.1 Error magnification and condition number2.3.2 Swamping

2.4 The PA = LU Factorization

2.4.1 Partial pivoting2.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 Method2.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 matrices2.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 Method2.7.2 Broyden’s Method

Software and Further Reading

**CHAPTER 3 Interpolation**

3.1 Data and Interpolating Functions

3.1.1 Lagrange interpolation3.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 formula3.2.2 Proof of Newton form and error formula

3.2.3 Runge phenomenon

3.3 Chebyshev Interpolation

3.3.1 Chebyshev’s theorem3.3.2 Chebyshev polynomials

3.3.3 Change of interval

3.4 Cubic Splines

3.4.1 Properties of splines3.4.2 Endpoint conditions

3.5 Bézier Curves

Reality Check 3: Fonts from Bézier curves

Software and Further Reading

**CHAPTER 4 Least Squares**

4.1 Least Squares and the Normal Equations

4.1.1 Inconsistent systems of equations4.1.2 Fitting models to data

4.1.3 Conditioning of least squares

4.2 A Survey of Models

4.2.1 Periodic data4.2.2 Data linearization

4.3 QR Factorization

4.3.1 Gram–Schmidt orthogonalization and least squares4.3.2 Modified Gram–Schmidt orthogonalization

4.3.3 Householder reflectors

4.4 Generalized Minimum Residual (GMRES) Method

4.4.1 Krylov methods4.4.2 Preconditioned GMRES

4.5 Nonlinear Least Squares

4.5.1 Gauss–Newton Method4.5.2 Models with nonlinear parameters

4.5.3 The Levenberg–Marquardt Method

Reality Check 4: GPS, Conditioning, and Nonlinear Least Squares

Software and Further Reading

**CHAPTER 5 Numerical Differentiation and Integration**

5.1 Numerical Differentiation

5.1.1 Finite difference formulas5.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 Rule5.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 Modeling

Software and Further Reading

**CHAPTER 6 Ordinary Differential Equations**

6.1 Initial Value Problems

6.1.1 Euler’s Method6.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 error6.2.2 The explicit Trapezoid Method

6.2.3 Taylor Methods

6.3 Systems of Ordinary Differential Equations

6.3.1 Higher order equations6.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 family6.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 pairs6.5.2 Order 4/5 methods

6.6 Implicit Methods and Stiff Equations

6.7 Multistep Methods

6.7.1 Generating multistep methods6.7.2 Explicit multistep methods

6.7.3 Implicit multistep methods

Software and Further Reading

**CHAPTER 7 Boundary Value Problems**

7.1 Shooting Method

7.1.1 Solutions of boundary value problems7.1.2 Shooting Method implementation

Reality Check 7: Buckling of a Circular Ring

7.2 Finite Difference Methods

7.2.1 Linear boundary value problems7.2.2 Nonlinear boundary value problems

7.3 Collocation and the Finite Element Method

7.3.1 Collocation7.3.2 Finite elements and the Galerkin Method

Software and Further Reading

**CHAPTER 8 Partial Differential Equations**

8.1 Parabolic Equations

8.1.1 Forward Difference Method8.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 equation8.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 equations8.4 Nonlinear partial differential equations

8.4.1 Implicit Newton solver8.4.2 Nonlinear equations in two space dimensions

Software and Further Reading

**CHAPTER 9 Random Numbers and Applications**

9.1 Random Numbers

9.1.1 Pseudo-random numbers9.1.2 Exponential and normal random numbers

9.2 Monte Carlo Simulation

9.2.1 Power laws for Monte Carlo estimation9.2.2 Quasi-random numbers

9.3 Discrete and Continuous Brownian Motion

9.3.1 Random walks9.3.2 Continuous Brownian motion

9.4 Stochastic Differential Equations

9.4.1 Adding noise to differential equations9.4.2 Numerical methods for SDEs

Reality Check 9: The Black–Scholes Formula

Software and Further Reading

**CHAPTER 10 Trigonometric Interpolation and the FFT**

10.1 The Fourier Transform

10.1.1 Complex arithmetic10.1.2 Discrete Fourier Transform

10.1.3 The Fast Fourier Transform

10.2 Trigonometric Interpolation

10.2.1 The DFT Interpolation Theorem10.2.2 Efficient evaluation of trigonometric functions

10.3 The FFT and Signal Processing

10.3.1 Orthogonality and interpolation10.3.2 Least squares fitting with trigonometric functions

10.3.3 Sound, noise, and filtering

Reality Check 10: The Wiener Filter

Software and Further Reading

**CHAPTER 11 Compression**

11.1 The Discrete Cosine Transform

11.1.1 One-dimensional DCT11.1.2 The DCT and least squares approximation

11.2 Two-Dimensional DCT and Image Compression

11.2.1 Two-dimensional DCT11.2.2 Image compression

11.2.3 Quantization

11.3 Huffman Coding

11.3.1 Information theory and coding11.3.2 Huffman coding for the JPEG format

11.4 Modified DCT and Audio Compression

11.4.1 Modified Discrete Cosine Transform11.4.2 Bit quantization

Reality Check 11: A Simple Audio Codec

Software and Further Reading

**CHAPTER 12 Eigenvalues and Singular Values**

12.1 Power Iteration Methods

12.1.1 Power Iteration12.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 iteration12.2.2 Real Schur form and the QR algorithm

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 general12.3.2 Special case: symmetric matrices

12.4 Applications of the SVD

12.4.1 Properties of the SVD12.4.2 Dimension reduction

12.4.3 Compression

12.4.4 Calculating the SVD

Software and Further Reading

**CHAPTER 13 Optimization**

13.1 Unconstrained Optimization without Derivatives

13.1.1 Golden Section Search13.1.2 Successive parabolic interpolation

13.1.3 Nelder–Mead search

13.2 Unconstrained Optimization with Derivatives

13.2.1 Newton’s Method13.2.2 Steepest Descent

13.2.3 Conjugate Gradient Search

Reality Check 13: Molecular Conformation and Numerical Optimization

Software and Further Reading

**Appendix A**

A.1 Matrix Fundamentals

A.2 Systems of linear equations

A.3 Block Multiplication

A.4 Eigenvalues and Eigenvectors

A.5 Symmetric Matrices

A.6 Vector Calculus

**Appendix B**

B.1 Starting MATLAB

B.2 Graphics

B.3 Programming in MATLAB

B.4 Flow Control

B.5 Functions

B.6 Matrix Operations

B.7 Animation and Movies

ANSWERS TO SELECTED EXERCISES

BIBLIOGRAPHY

INDEX

**Timothy Sauer **earned his Ph.D. in mathematics at the University of California–Berkeley in 1982, and is currently a professor at George Mason University. He has published articles on a wide range of topics in applied mathematics, including dynamical systems, computational mathematics, and mathematical biology.

Need help? Get in touch