Numerical Analysis NINTH EDITION Richard L. burden Youngstown State University J. Douglas Faires Youngstown State University BROOKS/COLE CENGAGE Learning Australia· Brazil· Japan· Korea· Mexico· Singapore· Spain· United Kingdon· United states t materially affect the overal leaming eperience. Cengage Learning reserves the right b remove arty oomen may be suppressed from the eBook andor eChapterts). Copyright 2010 Cengage Learning. All Rights Reserved. May nox be copied, scanned, or duplicated, in whole or in part. Due to
Numerical Analysis NINTH EDITION Richard L. Burden Youngstown State University J. Douglas Faires Youngstown State University Australia • Brazil • Japan • Korea • Mexico • Singapore • Spain • United Kingdom • United States Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
, BROOKS/COLE W CENGAGE Learning Numerical A O 2011, 2005, 2001 Brooks/Cole, Cengage Learning Richard L. Burden and ]. Douglas Faires ALL RIGHTS RESERVED. No part of this work covered by the copyright herein graphic, electronic, or mechanical, including but not limited to photocopyin cording, scanning, digitizing, taping, Web distribution, information networks or information storage and retrieval systems, except as permitted under Section Senior Sponsoring Editor: Molly Taylor noor 1o8 of the 1976 United States Copyright Act, without the prior written Associate Editor: Danie/ Seibert ission of the publisher. ditorial Assistant: Shaylin Walsh Associate Media Editor: Andrew Coppola For product information and technology assistance, contact us at Senior Marketing Manager: Jennifer Pursley Jones Cengage Learning Custo oo3549706 Marketing Coordinator: Erica COnnell For permission to use material from this text or product, Marketing Communications Manager: Mary Anne Content Project Manager: Jill Clark Further permissions questions can be emailed to permissionrequest@cengage.com. Senior Rights Acquisition Specialist: Katie Huha Library of Congress Control Number: 2010922639 Production Service: Cadmus Co SBN-13:978-0-538-73351-9 Text Designer: Jay Purcell SBN1o:o53873351 Cover Designer: Wing ngan Brooks/Cole Cover Image: Spiral Vortex o Channel Center Street Boston MA o2210 Photographer: Akira Inoue USA CollectionAmanaimagesGettyimages.com Compositor: Cadmus Communications ngage Learning is a leading provider of customized learning solutions with ffice locations around the globe, including Singapore, the United Kingdom Australia, Mexico, Brazil and Japan. Locate your local office at international cengage. com/region. Cengage Learning products are represented in Canada by Nelson Education, Ltd For your course and learning solutions, visit Purchase any of our products at your local college store or at our preferred onlinestorewww.cengagebrain.com Printed in Canada 12345671413121110 Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
Numerical Analysis, Ninth Edition Richard L. Burden and J. Douglas Faires Editor-in-Chief: Michelle Julet Publisher: Richard Stratton Senior Sponsoring Editor: Molly Taylor Associate Editor: Daniel Seibert Editorial Assistant: Shaylin Walsh Associate Media Editor: Andrew Coppola Senior Marketing Manager: Jennifer Pursley Jones Marketing Coordinator: Erica O’Connell Marketing Communications Manager: Mary Anne Payumo Content Project Manager: Jill Clark Art Director: Jill Ort Senior Manufacturing Buyer: Diane Gibbons Senior Rights Acquisition Specialist: Katie Huha Production Service: Cadmus Communications Text Designer: Jay Purcell Cover Designer: Wing Ngan Cover Image: Spiral Vortex Photographer: Akira Inoue Collection: Amana images, Gettyimages.com Compositor: Cadmus Communications © 2011, 2005, 2001 Brooks/Cole, Cengage Learning ALL RIGHTS RESERVED. No part of this work covered by the copyright herein may be reproduced, transmitted, stored, or used in any form or by any means graphic, electronic, or mechanical, including but not limited to photocopying, recording, scanning, digitizing, taping, Web distribution, information networks, or information storage and retrieval systems, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without the prior written permission of the publisher. For product information and technology assistance, contact us at: Cengage Learning Customer & Sales Support, 1-800-354-9706 For permission to use material from this text or product, submit all requests online at www.cengage.com/permissions. Further permissions questions can be emailed to permissionrequest@cengage.com. Library of Congress Control Number: 2010922639 ISBN-13: 978-0-538-73351-9 ISBN-10: 0-538-73351-9 Brooks/Cole 20 Channel Center Street Boston, MA 02210 USA Cengage Learning is a leading provider of customized learning solutions with office locations around the globe, including Singapore, the United Kingdom, Australia, Mexico, Brazil and Japan. Locate your local office at international.cengage.com/region. Cengage Learning products are represented in Canada by Nelson Education, Ltd. For your course and learning solutions, visit www.cengage.com. Purchase any of our products at your local college store or at our preferred online store www.cengagebrain.com. Printed in Canada 1 2 3 4 5 6 7 14 13 12 11 10 Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
Contents Preface ix 1 Mathematical Preliminaries and Error Analysis 1 2 Round-off Errors and Computer Arithmetic 17 1.3 Algorithms and Convergence 32 1.4 Numerical Softy 41 2 Solutions of Equations in One Variable 47 2.1 The Bisection Method 48 2.2 Fixed-Point Iteration 56 2. 3 Newtons Method and Its Extensions 67 2.4 Error Analysis for Iterative Methods 79 2.6 Zeros of Polynomials and Muiller's Method 91 2.7 Survey of Methods and Software 101 3 Interpolation and Polynomial Approximation 105 nd the Lagrange Polynomial 106 3.2 Data Approximation and Neville's Method 117 3.3 Divided Differences 124 3.4 Hermite Interp 3.5 Cubic Spline Interpolation 144 6 Parame 164 3.7 Survey of Methods and Software 171 4 Numerical Differentiation and Integration 173 4.2 Richardson's Extrapolation 185 4.3 Elements of Numerical Integration 193 Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
Contents Preface ix 1 Mathematical Preliminaries and Error Analysis 1 1.1 Review of Calculus 2 1.2 Round-off Errors and Computer Arithmetic 17 1.3 Algorithms and Convergence 32 1.4 Numerical Software 41 2 Solutions of Equations in One Variable 47 2.1 The Bisection Method 48 2.2 Fixed-Point Iteration 56 2.3 Newton’s Method and Its Extensions 67 2.4 Error Analysis for Iterative Methods 79 2.5 Accelerating Convergence 86 2.6 Zeros of Polynomials and Müller’s Method 91 2.7 Survey of Methods and Software 101 3 Interpolation and Polynomial Approximation 105 3.1 Interpolation and the Lagrange Polynomial 106 3.2 Data Approximation and Neville’s Method 117 3.3 Divided Differences 124 3.4 Hermite Interpolation 136 3.5 Cubic Spline Interpolation 144 3.6 Parametric Curves 164 3.7 Survey of Methods and Software 171 4 Numerical Differentiation and Integration 173 4.1 Numerical Differentiation 174 4.2 Richardson’s Extrapolation 185 4.3 Elements of Numerical Integration 193 v Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
Contents 4.4 Composite Numerical Integration 203 4.5 Romberg Integration 213 4.6 Adaptive Quadrature Methods 220 4.7 Gaussian Quadrature 228 4.8 Multiple Integrals 235 4.9 Improper Integrals 250 4.10 Survey of Methods and Software 256 5 Initial-Value Problems for Ordinary Differentia Equations 259 5.1 The Elementary Theory of Initial-Value Problems 260 5.2 Euler's Method 266 5.3 Higher-Order Taylor Methods 276 5.4 Runge-Kutta Methods 282 5.5 Error Control and the Runge-Kutta-Fehlberg Method 293 5.6 Multistep Methods 302 5.7 Variable Step-Size Multistep Methods 315 5.9 Higher-Order Equations and Systems of Differential Equations 328 5.10 Stability 339 5.11 Stiff Differential Equations 348 5. 12 Survey of Methods and Software 355 6 Direct Methods for Solving Linear Systems 357 6.1 Linear Systems of Equations 358 6.2 Pivoting Strategies 372 6.3 Linear Algebra and matrix Inversion 381 6. 4 The Determinant of a matrix 396 6.5 Matrix Factorization 400 6.6 Special Types of Matrices 411 6.7 Survey of Methods and Software 428 Iterative Techniques in Matrix Algebra 431 7.1 Norms of vectors and matrices 432 7.2 Eigenvalues and Eigenvectors 443 7.3 The Jacobi and Gauss-Siedel Iterative Techniques 450 7.4 Relaxation Techniques for Solving Linear Systems 462 7.5 Error Bounds and Iterative Refinement 469 7.6 The Conjugate Gradient Method 479 7.7 Survey of Methods and Software 495 Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
vi Contents 4.4 Composite Numerical Integration 203 4.5 Romberg Integration 213 4.6 Adaptive Quadrature Methods 220 4.7 Gaussian Quadrature 228 4.8 Multiple Integrals 235 4.9 Improper Integrals 250 4.10 Survey of Methods and Software 256 5 Initial-Value Problems for Ordinary Differential Equations 259 5.1 The Elementary Theory of Initial-Value Problems 260 5.2 Euler’s Method 266 5.3 Higher-Order Taylor Methods 276 5.4 Runge-Kutta Methods 282 5.5 Error Control and the Runge-Kutta-Fehlberg Method 293 5.6 Multistep Methods 302 5.7 Variable Step-Size Multistep Methods 315 5.8 Extrapolation Methods 321 5.9 Higher-Order Equations and Systems of Differential Equations 328 5.10 Stability 339 5.11 Stiff Differential Equations 348 5.12 Survey of Methods and Software 355 6 Direct Methods for Solving Linear Systems 357 6.1 Linear Systems of Equations 358 6.2 Pivoting Strategies 372 6.3 Linear Algebra and Matrix Inversion 381 6.4 The Determinant of a Matrix 396 6.5 Matrix Factorization 400 6.6 Special Types of Matrices 411 6.7 Survey of Methods and Software 428 7 IterativeTechniques in Matrix Algebra 431 7.1 Norms of Vectors and Matrices 432 7.2 Eigenvalues and Eigenvectors 443 7.3 The Jacobi and Gauss-Siedel Iterative Techniques 450 7.4 Relaxation Techniques for Solving Linear Systems 462 7.5 Error Bounds and Iterative Refinement 469 7.6 The Conjugate Gradient Method 479 7.7 Survey of Methods and Software 495 Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it
8 Approximation Theory 497 1 Discrete Least Squares Approximation 498 8.2 Orthogonal Polynomials and Least Squares Approximation 510 8.3 Chebyshev Polynomials and Economization of Power Series 518 8.4 Rational Function Approximation 528 8.5 Trigonometric Polynomial Approximation 538 8.6 Fast fourier transforms 547 8.7 Survey of Methods and Software 558 9 Approximating Eigenvalues 561 9.1 Linear Algebra and Eigenvalues 562 9.2 Orthogonal Matrices and Similarity Transformations 570 9.3 The Power Method 576 9. 4 Householder's Method 593 9.5 The QR Algorithm 601 Singular Value Decomposition 614 9.7 Survey of Methods and Software 626 10 Numerical Solutions of Nonlinear Systems of quations 629 E 10.1 Fixed Points for Functions of several variables 630 10.2 Newtons Method 638 10.3 Quasi-Newton Methods 647 10.4 Steepest Descent Techniques 6.54 10.5 Homotopy and Continuation Methods 660 10.6 Survey of Methods and Software 668 11 Boundary-Value Problems for Ordinary Differential quations 671 11.1 The Linear Shooting method 672 11.2 The Shooting Method for Nonlinear Problems 678 11. 3 Finite-Difference Methods for Linear problems 684 11.4 Finite-Difference methods for Nonlinear problems 691 11. 5 The Rayleigh-Ritz Method 696 11.6 Survey of Methods and Software 711 Copyright 2010 Cengage Learning. All Rights t materially affect the overall leaming eaperience Cengage Learning reserves the right to remo rty commen may be suppressed from the eBook andor eChaptert'sh. May no be copied, scanned, or duplicated, in whole or in part Due to
Contents vii 8 ApproximationTheory 497 8.1 Discrete Least Squares Approximation 498 8.2 Orthogonal Polynomials and Least Squares Approximation 510 8.3 Chebyshev Polynomials and Economization of Power Series 518 8.4 Rational Function Approximation 528 8.5 Trigonometric Polynomial Approximation 538 8.6 Fast Fourier Transforms 547 8.7 Survey of Methods and Software 558 9 Approximating Eigenvalues 561 9.1 Linear Algebra and Eigenvalues 562 9.2 Orthogonal Matrices and Similarity Transformations 570 9.3 The Power Method 576 9.4 Householder’s Method 593 9.5 The QR Algorithm 601 9.6 Singular Value Decomposition 614 9.7 Survey of Methods and Software 626 10 Numerical Solutions of Nonlinear Systems of Equations 629 10.1 Fixed Points for Functions of Several Variables 630 10.2 Newton’s Method 638 10.3 Quasi-Newton Methods 647 10.4 Steepest Descent Techniques 654 10.5 Homotopy and Continuation Methods 660 10.6 Survey of Methods and Software 668 11 Boundary-Value Problems for Ordinary Differential Equations 671 11.1 The Linear Shooting Method 672 11.2 The Shooting Method for Nonlinear Problems 678 11.3 Finite-Difference Methods for Linear Problems 684 11.4 Finite-Difference Methods for Nonlinear Problems 691 11.5 The Rayleigh-Ritz Method 696 11.6 Survey of Methods and Software 711 Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it