Table 1: E
ors and convergence orders
F.E. E.T. E.M. RK4
h E
or Order | E
or | Order | E
or | Order | E
or | Orde
0.2 0.425E-02 -
0.1 0.222E-02 | 0.94
0.05 0.111E-02 | 1.00
0.025 | 0.556E-03 | 1.00
0.0125 | 0.288E-03 | 1.00
0.00675 | 0.144E-03 | 1.00
Numerical Analysis
T H I R D E D I T I O N
Timothy Saue
George Mason University
Director, Portfolio Management: Deirdre Lynch
Executive Editor: Jeff Weidenaa
Editorial Assistant: Jennifer Snyde
Content Producer: Tara Corpuz
Managing Producer: Scott Disanno
Producer: Jean Choe
Product Marketing Manager: Yvonne Vannatta
Field Marketing Manager: Evan St. Cy
Marketing Assistant: Jon Bryant
Senior Author Support/Technology Specialist: Joe Vetere
Manager, Rights and Permissions: Gina Cheselka
Manufacturing Buyer: Carol Melville, LSC Communications
Cover Image: Gyn9037/ Shutterstock
Text and Cover Design, Illustrations, Production Coordination, Composition:
Integra Software Services Pvt. Ltd
Copyright c© 2018, 2012, 2006 by Pearson Education, Inc. All Rights Reserved. Printed in the United States
of America. This publication is protected by copyright, and permission should be obtained from the publisher prior to any
prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical,
photocopying, recording, or otherwise. For information regarding permissions, request forms and the appropriate contacts
within the Pearson Education Global Rights & Permissions department, please visit www.pearsoned.com/permissions/.
Photo Credits: Page 1 Zsolt Biczo/ Shutterstock; Page 26 Polonio Video/ Shutterstock; Page 41 DEA PICTURE LIBRARY
Getty Images; Page 74 Redswept /Shutterstock; Page 144 Rosenfeld Images, Ltd./Photo Researchers, Inc.; Page 196
dolgachov/ 123RF; Page 253 wklzzz / 123RF; Page 293 UPPA/Photoshot; Page 366 Paul Springett 04/Alamy Stock Photo;
Page 394 iStock/Getty Images Plus; Page 453 xPACIFICA / Alamy; Page 489 Picture Alliance/Photoshot; Page 518 Chris
Rout/Alamy Stock Photo; Pages 528 & 534 Toni Angermaye
Photo Researchers, Inc.; Page 556 Jinx Photography
Brands/Alamy Stock Photo; Page 593 Astronoman /Shutterstock.
Text Credits: Page 50 J. H. Wilkinson, The perfidious polynomial, In ed. by Gene H. Golub. Studies in Numerical Analysis.
Mathematical Association of America, XXXXXXXXXX); Page 153 & Page 188 “Author-created using the software from MATLAB.
The MathWorks, Inc., Natick, Massachusetts, USA, http:
www.mathworks.com.”; Page 454 Von Neumann, John (1951).
“Various techniques used in connection with random digits.” In A. S. Householder, G. E. Forsythe, and H. H. Germond,
eds., Proceedings of Symposium on “Monte Carlo Method” held June-July 1949 in Los Angeles. Journal of Research of the
National Bureau of Standards, Applied Mathematics Series, no. 12, pp 36–38 (Washington, D.C.: USGPO, 1951) Summary
written by George E. Forsythe. Reprinted in von Neumann, John von Neumann Collected Works, ed. A. H. Taub, vol. 5
(New York: Macmillan, 1963) Vol. V, pp 768–770; Page 622 Author-created using the software from MATLAB. The
MathWorks, Inc., Natick, Massachusetts, USA, http:
www.mathworks.com.; Page 623 Author-created using the software
from MATLAB. The MathWorks, Inc., Natick, Massachusetts, USA, http:
www.mathworks.com.
PEARSON, ALWAYS LEARNING, and MYLAB are exclusive trademarks owned by Pearson Education, Inc. or its
affiliates in the U.S. and/or other countries.
Unless otherwise indicated herein, any third-party trademarks that may appear in this work are the property of thei
espective owners and any references to third-party trademarks, logos or other trade dress are for demonstrative o
descriptive purposes only. Such references are not intended to imply any sponsorship, endorsement, authorization, o
promotion of Pearson’s products by the owners of such marks, or any relationship between the owner and Pearson
Education, Inc. or its affiliates, authors, licensees or distributors.
Li
ary of Congress Cataloging-in-Publication Data
Names: Sauer, Tim, author.
Title: Numerical analysis / Timothy Sauer, George Mason University.
Description: Third edition. | Hoboken : Pearson, [2019] | Includes
ibliographical references and index.
Identifiers: LCCN XXXXXXXXXX| ISBN XXXXXXXXXXalk. paper) |
ISBN 013469645X (alk. paper)
Subjects: LCSH: Numerical analysis. | Mathematical analysis.
Classification: LCC QA297 .S XXXXXXXXXX | DDC 518–dc23
LC record available at https:
lccn.loc.gov/ XXXXXXXXXX
1 17
ISBN 10: XXXXXXXXXXX
ISBN 13: XXXXXXXXXX
www.pearsoned.com/permissions
http:
www.mathworks.com.�; Page
http:
www.mathworks.com.; Page
http:
www.mathworks.com
https:
lccn.loc.gov/ XXXXXXXXXX
Contents
PREFACE xi
CHAPTER 0 Fundamentals 1
0.1 Evaluating a Polynomial 1
0.2 Binary Numbers 5
0.2.1 Decimal to binary 6
0.2.2 Binary to decimal 7
0.3 Floating Point Representation of Real Numbers 8
0.3.1 Floating point formats 8
0.3.2 Machine representation 12
0.3.3 Addition of floating point numbers 14
0.4 Loss of Significance 17
0.5 Review of Calculus 21
Software and Further Reading 24
CHAPTER 1 Solving Equations 26
1.1 The Bisection Method 27
1.1.1 Bracketing a root 27
1.1.2 How accurate and how fast? 30
1.2 Fixed-Point Iteration 33
1.2.1 Fixed points of a function 33
1.2.2 Geometry of Fixed-Point Iteration 36
1.2.3 Linear convergence of Fixed-Point Iteration 36
1.2.4 Stopping criteria 42
1.3 Limits of Accuracy 46
1.3.1 Forward and backward e
or 46
1.3.2 The Wilkinson polynomial 49
1.3.3 Sensitivity of root-finding 50
1.4 Newton’s Method 54
1.4.1 Quadratic convergence of Newton’s Method 56
1.4.2 Linear convergence of Newton’s Method 58
1.5 Root-Finding without Derivatives 64
1.5.1 Secant Method and variants 64
1.5.2 Brent’s Method 68
Reality Check 1: Kinematics of the Stewart platform 70
Software and Further Reading 73
iv | Contents
CHAPTER 2 Systems of Equations 74
2.1 Gaussian Elimination 74
2.1.1 Naive Gaussian elimination 75
2.1.2 Operation counts 77
2.2 The LU Factorization 82
2.2.1 Matrix form of Gaussian elimination 82
2.2.2 Back substitution with the LU factorization 85
2.2.3 Complexity of the LU factorization 86
2.3 Sources of E
or 89
2.3.1 E
or magnification and condition number 89
2.3.2 Swamping 95
2.4 The PA = LU Factorization 99
2.4.1 Partial pivoting 99
2.4.2 Permutation matrices 101
2.4.3 PA = LU factorization 102
Reality Check 2: The Euler–Bernoulli Beam 107
2.5 Iterative Methods 110
2.5.1 Jacobi Method 111
2.5.2 Gauss–Seidel Method and SOR 113
2.5.3 Convergence of iterative methods 116
2.5.4 Sparse matrix computations 117
2.6 Methods for symmetric positive-definite matrices 122
2.6.1 Symmetric positive-definite matrices 122
2.6.2 Cholesky factorization 124
2.6.3 Conjugate Gradient Method 127
2.6.4 Preconditioning 132
2.7 Nonlinear Systems of Equations 136
2.7.1 Multivariate Newton’s Method 136
2.7.2 Broyden’s Method 139
Software and Further Reading 143
CHAPTER 3 Interpolation 144
3.1 Data and Interpolating Functions 145
3.1.1 Lagrange interpolation 146
3.1.2 Newton’s divided differences 147
3.1.3 How many degree d polynomials pass through n
points? 150
3.1.4 Code for interpolation 151
3.1.5 Representing functions by approximating polynomials 153
3.2 Interpolation E
or 157
3.2.1 Interpolation e
or formula 158
3.2.2 Proof of Newton form and e
or formula 159
3.2.3 Runge phenomenon 162
3.3 Chebyshev Interpolation 164
3.3.1 Chebyshev’s theorem 165
3.3.2 Chebyshev polynomials 167
3.3.3 Change of interval 169
Contents | v
3.4 Cubic Splines 173
3.4.1 Properties of splines 174
3.4.2 Endpoint conditions 180
3.5 Bézier Curves 185
Reality Check 3: Fonts from Bézier curves 190
Software and Further Reading 194
CHAPTER 4 Least Squares 196
4.1 Least Squares and the Normal Equations 196
4.1.1 Inconsistent systems of equations 197
4.1.2 Fitting models to data 201
4.1.3 Conditioning of least squares 205
4.2 A Survey of Models 208
4.2.1 Periodic data 208
4.2.2 Data linearization 211
4.3 QR Factorization 220
4.3.1 Gram–Schmidt orthogonalization and least squares 220
4.3.2 Modified Gram–Schmidt orthogonalization 227
4.3.3 Householder reflectors 228
4.4 Generalized Minimum Residual (GMRES) Method 235
4.4.1 Krylov methods 235
4.4.2 Preconditioned GMRES 237
4.5 Nonlinear Least Squares 240
4.5.1 Gauss–Newton Method 240
4.5.2 Models with nonlinear parameters 243
4.5.3 The Levenberg–Marquardt Method 245
Reality Check 4: GPS, Conditioning, and Nonlinear Least Squares 248
Software and Further Reading 251
CHAPTER 5 Numerical Differentiation and
Integration 253
5.1 Numerical Differentiation 254
5.1.1 Finite difference formulas 254
5.1.2 Rounding e
or 257
5.1.3 Extrapolation 259
5.1.4 Symbolic differentiation and integration 261
5.2 Newton–Cotes Formulas for Numerical Integration 264
5.2.1 Trapezoid Rule 265
5.2.2 Simpson’s Rule 267
5.2.3 Composite Newton–Cotes formulas 269
5.2.4 Open Newton–Cotes Methods 272
5.3 Romberg Integration 276
5.4 Adaptive Quadrature 279
5.5 Gaussian Quadrature 284
Reality Check 5:Motion Control in Computer-Aided Modeling 289
Software and Further Reading 291
vi | Contents
CHAPTER 6 Ordinary Differential Equations 293
6.1 Initial Value Problems 294
6.1.1 Euler’s Method 295
6.1.2 Existence, uniqueness, and continuity fo
solutions 300
6.1.3 First-order linear equations 303
6.2 Analysis of IVP Solvers 306
6.2.1 Local and global truncation e
or 306
6.2.2 The explicit Trapezoid Method 310
6.2.3 Taylor Methods 313
6.3 Systems of Ordinary Differential Equations 316
6.3.1 Higher order equations 317
6.3.2 Computer simulation: the pendulum 318
6.3.3 Computer simulation: o
ital mechanics 322
6.4 Runge–Kutta Methods and Applications 328
6.4.1 The Runge–Kutta family 328
6.4.2 Computer simulation: the Hodgkin–Huxley
neuron 331
6.4.3 Computer simulation: the Lorenz equations 333
Reality Check 6: The Tacoma Na
ows Bridge 337
6.5 Variable Step-Size Methods 340
6.5.1 Embedded Runge–Kutta pairs 340
6.5.2 Order 4/5 methods 342
6.6 Implicit Methods and Stiff Equations 347
6.7 Multistep Methods 351
6.7.1 Generating multistep methods 352
6.7.2 Explicit multistep methods 354
6.7.3 Implicit multistep methods 359
Software and Further Reading 365
CHAPTER 7 Boundary Value Problems 366
7.1 Shooting Method 367
7.1.1 Solutions of boundary value problems 367
7.1.2 Shooting Method implementation 370
Reality Check 7: Buckling of a Circular Ring 374
7.2 Finite Difference Methods 376
7.2.1 Linear boundary value problems 376
7.2.2 Nonlinear boundary value problems 378
7.3 Collocation and the Finite Element Method 384
7.3.1 Collocation 384
7.3.2 Finite Elements and the Galerkin Method 387
Software and Further Reading 392
Contents | vii
CHAPTER 8 Partial Differential Equations 394
8.1 Parabolic Equations 395
8.1.1 Forward Difference Method 395
8.1.2 Stability analysis of Forward Difference Method 399
8.1.3 Backward Difference Method 400
8.1.4 Crank–Nicolson Method 405
8.2 Hype
olic Equations 413
8.2.1 The wave equation 413
8.2.2 The CFL condition 415
8.3 Elliptic Equations 419
8.3.1 Finite Difference Method for elliptic equations 420
Reality Check 8: Heat Distribution on a Cooling Fin 424
8.3.2 Finite Element Method for elliptic equations 427
8.4 Nonlinear Partial Differential Equations 438
8.4.1 Implicit Newton solver 438
8.4.2 Nonlinear equations in two space dimensions 444
Software and Further Reading 451
CHAPTER 9 RandomNumbers and Applications 453
9.1 Random Numbers 454
9.1.1 Pseudo-random numbers 454
9.1.2 Exponential and normal random numbers 459
9.2 Monte Carlo Simulation 462
9.2.1 Power laws for Monte Carlo estimation 462
9.2.2 Quasi-random numbers 464
9.3 Discrete and Continuous Brownian Motion 469
9.3.1 Random walks 469
9.3.2 Continuous Brownian motion 472
9.4 Stochastic Differential Equations 474
9.4.1 Adding noise to differential equations 475
9.4.2 Numerical methods for SDEs 478
Reality Check 9: The Black–Scholes Formula 486
Software and Further Reading 488
CHAPTER 10 Trigonometric Interpolation and
the FFT 489
10.1 The Fourier Transform 490
10.1.1 Complex arithmetic 490
10.1.2 Discrete Fourier Transform 493
10.1.3 The Fast Fourier Transform 495
10.2 Trigonometric Interpolation 498
10.2.1 The DFT Interpolation Theorem 498
10.2.2 Efficient evaluation of trigonometric functions 502
10.3 The FFT and Signal Processing 505
10.3.1 Orthogonality and interpolation 506
10.3.2 Least squares fitting with trigonometric functions 508
10.3.3 Sound, noise, and filtering 512
Reality Check 10: The Wiener Filter 515
Software and Further Reading 517
viii | Contents
CHAPTER 11 Compression 518
11.1 The Discrete Cosine Transform 519
11.1.1 One-dimensional DCT 519
11.1.2 The DCT and least squares approximation 521
11.2 Two-Dimensional DCT and Image Compression 524
11.2.1 Two-dimensional DCT 524
11.2.2 Image compression 528
11.2.3 Quantization 531
11.3 Huffman Coding 538
11.3.1 Information theory and coding 538
11.3.2 Huffman coding for the JPEG format 541
11.4 Modified DCT and Audio Compression 544
11.4.1 Modified Discrete Cosine Transform 544
11.4.2 Bit quantization 550
Reality Check 11: A Simple Audio Codec 552
Software and Further Reading 555
CHAPTER 12 Eigenvalues and Singular Values 556
12.1 Power Iteration Methods 556
12.1.1 Power Iteration 557
12.1.2 Convergence of Power Iteration 559
12.1.3 Inverse Power Iteration 560
12.1.4 Rayleigh Quotient Iteration 562
12.2 QR Algorithm 564
12.2.1 Simultaneous iteration 565
12.2.2 Real Schur form and the QR algorithm 567
12.2.3 Upper Hessenberg form 570
Reality Check 12: How Search Engines Rate Page Quality 575
12.3 Singular Value Decomposition 578
12.3.1 Geometry of the SVD 578
12.3.2 Finding