numerical analysis

数值分析第二版This page intentionally left blankNumerical AnalysisSECOND EDTIONTimothy sauerGeorge Mason universityPEARSONBoston Columbus Indianapolis New York San Francisco Upper Saddle River Amsterdam Cape TownDubai London Madrid Milan Munich Paris Montreal Toronto Delhi Mexico City Sao PauloSydney Hong Kong Seoul Singapore Taipei TokyoEditor in Chief: Deirdre LynchSenior acquisitions Editor: William HoffmanSponsoring Editor: Caroline CelanoEditorial assistant: Brandon rawnsleSenior Managing Editor: Karen WernholmSenior production Project Manager: Beth HoustonExecutive Marketing Manager: Jeff WeidenaarMarketing Assistant: Caitlin CraneSenior Author Support/Technology Specialist: Joe VetereRights and Permissions Advisor: Michael JoyceManufacturing Buyer: Debbie RossiDesign Manager: Andrea NixSenior designer: barbara atkinsonProduction Coordination and Composition: Integra Software Services Pvt LtdCover Designer: Karen SalzbachCover Image: Tim Ladder/CorbisPhoto credits: Page 1 Image Source: page 24 National Advanced Driving Simulator (NADS-1 Simulator) locatedat the University of lowa and owned by the National highway Safety Administration(NHTSA); page 39 Yalepage 467 Picture Alliance/Photoshot; page 495 Chris Rout/Alamy: page 505 Toni Angermayer/Phol 3.thInc; page 188 Pincasso/Shutterstock; page 243 Orhan 81/Fotolia; page 28/ UPPA/Photoshot; page 348 h ersgBabylonian Collection; page 71 Travellinglight/iStockphoto; page 138 Rosenfeld Images Ltd / Photo ReseaSpringett 04/Alamy, page 374 Bill Noll/iStockphoto; page 43/ Don Emmert/AFP/Getty Images//NewscResearchers, Inc, page 53/ Jinx photography Brands/Alamy, page 565 Phil Degginger/ AlamyMany of the designations used by manufacturers and sellers to distinguish their products are claimed astrademarks. Where those designations appear in this book, and Pearson Education was aware of a trademarkclaim, the designations have been printed in initial caps or all capsLibrary of Congress Cataloging-in-Publication DataSauer. TimNumerical analysis Timothy sauer.-2nd edp cmIncludes bibliographical references and indexISBN-13:978-0-321-78367-7ISBN-10:0-321-78367-01. Numerical analTitleQA297.S3482012518-dc232011014232Copyright o2012, 2006 Pearson Education, IncAll rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, inany form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the priorwritten permission of the publisher. Printed in the United States of America. For information on obtainingpermission for use of material in this work, please submit a written request to Pearson Education, Inc, Rightsand Contracts Department, 501 Boylston Street, Suite 900, Boston, MA O2116, fax your request to617-671-3447,ore-mailathttp://www.pearsoned.com/legal/permissions.htm12345678910EB1514131211PEARSONISBN 10:0-321-78367-0ISBN13:978-0-321-78367-7ContentsPREFACEXCHAPTERo Fundamentals0.1 Evaluating a polynomia0.2 Binary Numbers0. 2.1 Decimal to binary60.2.2 Binary to decimal0.3 Floating Point Representation of real Numbers0.3.1 Floating point formats0.3.2 Machine representation0. 3.3 Addition of floating point numbers0. 4 Loss of Significance160.5 Review of calculus19Software and further reading23CHAPTER 1 Solving Equations241.1 The Bisection Method251.1.1 Bracketing a root251.1.2 How accurate and how fast?281.2 Fixed-Point Iteration1.2.1 Fixed points of a function311.2.2 Geometry of Fixed-Point Iteration331.2.3 Linear convergence of Fixed-Point Iteration341.2.4 Stopping criteria401.3 Limits of Accuracy4313.1 Forward and backward error441.3.2 The wilkinson polynomial471.3.3 Sensitivity of root-finding1. 4 Newtons meth1.4.1 Quadratic convergence of Newtons Method531.4.2 Linear convergence of Newtons Method551.5 Root-Finding without Derivatives1.5.1 Secant method and variants611.5.2 Brent's Method64Reality Check 1: Kinematics of the stewart platform67Software and Further Reading69CHAPTER 2 Systems of Equations712.1 Gaussian Elimination2.1.1 Naive gaussian elimination722.1.2 Operation counts74viI Contents2.2 The lu factorization2.2.1 Matrix form of gaussian elimination792.2.2 Back substitution with the lu factorization82.2.3 Complexity of the LU factorization832.3 Sources of error852.3.1 Error magnification and condition number862.3.2 Swamping912. 4 The pa= lu factorization952.4.1 Partial952.4.2 Permutation matrices972. 4.3 PA= LU factorization98Reality Check 2: The Euler-Bernoulli Beam1022.5 Iterative Method10625.1 Jacobi method1062.5.2 Gauss-Seidel method and sor1082.5.3 Convergence of iterative methods1112.5.4 Sparse matrix computations1132.6 Methods for symmetric positive-defnite matrices1172.6.1 Symmetric positive-definite matrices1172.6.2 Cholesky factorization1192.6.3 Conjugate Gradient Method1212.6.4 Preconditioning126.7 Nonlinear Systems of Equation1302.7.1 Multivariate Newton 's Method1312.7.2 Broyden's Method133Software and Further Reading137CHAPTER 3 Interpolation1383.1 Data and Interpolating Functions1393.1.1 Lagrange interpolation1403. 1.2 Newton's divided differences1413.1.3 How many degree d polynomials pass through noints1443.1.4 Code for interpolation1453.1.5 Representing functions by approximating polynomials1473.2 Interpolation Error1513.2.1 Interpolation error formula1513.2.2 Proof of newton form and error formula1533.2.3 Runge phenomenon1553.3 Chebyshev Interpolation1583.3.1 Chebyshev's theorem1583.3.2 Chebyshev polynomials1603.3.3 Change of interval1623. 4 Cubic Splines1663.4.1 Properties of splines1673.4.2 Endpoint conditions1733.5 Bezier curves179Reality Check 3: Fonts from Bezier curves183Software and further reading187Contents I viiCHAPTER 4 Least Squares1884.1 Least Squares and the Normal equations1884.1.1 Inconsistent systems of equations1894.1.2 Fitting models to data1934.1.3 Conditioning of least squares1974.2 A Survey of models2014.2.1 Periodic data2014.2.2 Data linearization2034.3 QR Factorization2124.3.1 Gram-Schmidt orthogonalization and least squares2124.3.2 Modified Gram-Schmidt orthogonalization2184.3.3 Householder reflectors2204.4 Generalized Minimum Residual (GMRES)Method2254. 4.1 Krylov methods2264.4.2 Preconditioned gmres2284.5 Nonlinear Least squares2304.5.1 Gauss-Newton method2304.5.2 Models with nonlinear parameters2334.5.3 The Levenberg-Marquardt Method235Reality Check 4: GPS, Conditioning and Nonlinear least squares238Software and Further Reading242CHAPTER 5 Numerical Differentiation andIntegration2435.1 Numerical Differentiation2445.1.1 Finite difference formulas2445.1.2 Rounding error2475.1.3 Extrapolation2495.1.4 Symbolic differentiation and integration2505.2 Newton-Cotes Formulas for Numerical Integration2545.2.1 Trapezoid Rule2555.2.2 Simpson s rule2575.2.3 Composite Newton-Cotes formulas2595.2.4 Open Newton-Cotes Methods2625.3 Romberg Integration2655.4 Adaptive Quadrature2695.5 Gaussian Quadrature273Reality Check 5: Motion Control in Computer-Aided Modeling278Software and further reading280CHAPTER 6 Ordinary Differential Equations2816.1 Initial value Problems2826.1.1 Eulers method2836.1.2 Existence, uniqueness, and continuity for solutions2876.1.3 First-order linear equations2906.2 Analysis of IVP Solvers2936.2.1 Local and global truncation error293viii Contents6.2.2 The explicit Trapezoid Method2976.2.3 Taylor Methods3006.3 Systems of Ordinary Differential Equations3036.3.1 Higher order equations3046.3.2 Computer simulation: the pendulum3056.3.3 Computer simulation: orbital mechanics3096.4 Runge-Kutta Methods and Applications3146.4.1 The runge-Kutta family3146.4.2 Computer simulation: the Hodgkin-Huxley neuron3176.4.3 Computer simulation: the Lorenz equations319Reality Check 6: The Tacoma narrows bridge3226.5 Variable Step-Size Methods3256.5.1 Embedded runge-Kutta pairs3256.5.2 Order 4/5 methods3286.6 Implicit Methods and Stiff equations3326.7 Multistep Methods3366.7.1 Generating multistep methods3366.7.2 Explicit multistep methods3396.7.3 Implicit multistep methods342Software and Further reading347CHAPTER 7 Boundary Value Problems3487.1 Shooting method3497.1.1 Solutions of boundary value probler3497.1.2 Shooting Method implementation352Reality Check 7: Buckling of a Circular Ring557.2 Finite Difference methods3577.2.1 Linear boundary value problems3577.2.2 Nonlinear boundary value problems3597. 3 Collocation and the finite element method36573.1 Collocation3657.3.2 Finite elements and the galerkin method367Software and Further Reading373CHAPTER 8 Partial Differential Equations3748.1 Parabolic equations3758.1.1 Forward Difference method3758.1.2 Stability analysis of Forward Difference Method3798.1.3 Backward Difference method3808.1.4 Crank-Nicolson method3858.2 Hyperbolic Equations3938.2.1 The wave equation3938.2.2 The CfL condition3958.3 Elliptic Equations3988.3.1 Finite Difference method for elliptic equations399Reality Check 8: Heat distribution on a cooling fin4038.3.2 Finite Element Method for elliptic equations406Contents I ix8. 4 Nonlinear partial differential equations4178.4.1 Implicit Newton solver4178.4.2 Nonlinear equations in two space dimensions423Software and further reading430CHAPTER 9 Random Numbers and Applications 4319.1 Random Numbers4329.1.1 Pseudo-random numbers4329.1.2 Exponential and normal random numbers4379.2 Monte Carlo simulation4409.2.1 Power laws for monte carlo estimation4409.2.2 Quasi-random numbers4429.3 Discrete and Continuous brownian motion4469.3.1 Randealks9.3.2 Continuous brownian motion4499. 4 Stochastic Differential equations4529.4.1 Adding noise to differential equations4529.4.2 Numerical methods for sdes456Reality Check 9: The black-Scholes formula464Software and further reading465CHAPTER 10 Trigonometric Interpolation andhe fet46710.1 The Fourier transform46810.1.1 Complex arithmetic10.1.2 Discrete Fourier transform47010.1.3 The Fast Fourier transform47310.2 Trigonometric Interpolation47610.2.1 The dFT Interpolation Theorem47610.2.2 Efficient evaluation of trigonometric functions47910.3 The FFt and Signal Processing48310.3.1 Orthogonality and interpolation48310.3.2 Least squares fitting with trigonometric functions48510.3.3 Sound, noise, and filtering489Reality Check 10: The Wiener Filter492Software and Further Reading494CHAPTER 11 Compression49511.1 The discrete Cosine transform49611.1.1 One-dimensional dct49611.1.2 The DCT and least squares approximation49811.2 Two-Dimensional DCT and Image Compression50111.2.1 TWo-dimensional dct50111.2.2 Image compression50511.2.3 Quantization50811.3 Huffman Coding51411.3.1 Information theory and coding51411.3.2 Huffman coding for the JPEG format517