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
ontents 12 Numerical Solutions to Partial Differential Equations 713 12.1 Elliptic Partial Differential Equations 716 12.2 Parabolic Partial Differential Equations 725 12.3 Hyperbolic Partial Differential Equations 739 12. 4 An Introduction to the Finite-Element Method 746 12.5 Survey of Methods and Software 760 Bibliography 763 Answers to selected exercises 773 Index 863 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
viii Contents 12 Numerical Solutions to Partial Differential Equations 713 12.1 Elliptic Partial Differential Equations 716 12.2 Parabolic Partial Differential Equations 725 12.3 Hyperbolic Partial Differential Equations 739 12.4 An Introduction to the Finite-Element Method 746 12.5 Survey of Methods and Software 760 Bibliography 763 Answers to Selected Exercises 773 Index 863 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
Preface About the text This book was written for a sequence of courses on the theory and application of numerical approximation techniques. It is designed primarily for junior-level mathematics, science, and engineering majors who have completed at least the standard college calculus sequence Familiarity with the fundamentals of linear algebra and differential equations is useful, but there is sufficient introductory material on these topics so that courses in these subjects are not needed as prerequisite Previous editions of Numerical Analysis have been used in a wide variety of situations some cases, the mathematical analysis underlying the development of approximation techniques was given more emphasis than the methods; in others, the emphasis was re- versed. The book has been used as a core reference for beginning graduate level courses in engineering and computer science programs and in first-year courses in introductory analysis offered at international universities. We have adapted the book to fit these diverse users without compromising our original purpose To introduce modern approximation techniques to explain how, why, and when they can be expected to work, and to provide a foundation for further study of numerical The book contains sufficient material for at least a full year of study, but we expect many people to use it for only a single-term course. In such a single-term course, students learn to identify the types of problems that require numerical techniques for their solution and see examples of the error propagation that can occur when numerical methods are applied They accurately approximate the solution of problems that cannot be solved exactly and arn typical techniques for estimating error bounds for the approximations. The remainder of the text then serves as a reference for methods not considered in the course. Either the full-year or single-course treatment is consistent with the philosophy of the text irtually every concept in the text is illustrated by example, and this edition contains more than 2600 class-tested exercises ranging from elementary applications of methods and algorithms to generalizations and extensions of the theory. In addition, the exercise sets include numerous applied problems from diverse areas of engineering as well as from the physical, computer, biological, economic, and social sciences. The chosen applications clearly and concisely demonstrate how numerical techniques can be, and often must be applied in real-life situations. A number of software packages, known as Computer Algebra Systems(CAS), been developed to produce symbolic mathematical computations. Maple Mathemat and MAtLAB are predominant among these in the academic environment, and versions of these software packages are available for most common computer systems. In addition, Sage, a free open source system, is now available. This system was developed primarily Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning
Preface About the Text This book was written for a sequence of courses on the theory and application of numerical approximation techniques. It is designed primarily for junior-level mathematics, science, and engineering majors who have completed at least the standard college calculus sequence. Familiarity with the fundamentals of linear algebra and differential equations is useful, but there is sufficient introductory material on these topics so that courses in these subjects are not needed as prerequisites. Previous editions of Numerical Analysis have been used in a wide variety of situations. In some cases, the mathematical analysis underlying the development of approximation techniques was given more emphasis than the methods; in others, the emphasis was reversed. The book has been used as a core reference for beginning graduate level courses in engineering and computer science programs and in first-year courses in introductory analysis offered at international universities. We have adapted the book to fit these diverse users without compromising our original purpose: To introduce modern approximation techniques; to explain how, why, and when they can be expected to work; and to provide a foundation for further study of numerical analysis and scientific computing. The book contains sufficient material for at least a full year of study, but we expect many people to use it for only a single-term course. In such a single-term course, students learn to identify the types of problems that require numerical techniques for their solution and see examples of the error propagation that can occur when numerical methods are applied. They accurately approximate the solution of problems that cannot be solved exactly and learn typical techniques for estimating error bounds for the approximations. The remainder of the text then serves as a reference for methods not considered in the course. Either the full-year or single-course treatment is consistent with the philosophy of the text. Virtually every concept in the text is illustrated by example, and this edition contains more than 2600 class-tested exercises ranging from elementary applications of methods and algorithms to generalizations and extensions of the theory. In addition, the exercise sets include numerous applied problems from diverse areas of engineering as well as from the physical, computer, biological, economic, and social sciences. The chosen applications clearly and concisely demonstrate how numerical techniques can be, and often must be, applied in real-life situations. A number of software packages, known as Computer Algebra Systems (CAS), have been developed to produce symbolic mathematical computations. Maple®, Mathematica®, and MATLAB® are predominant among these in the academic environment, and versions of these software packages are available for most common computer systems. In addition, Sage, a free open source system, is now available. This system was developed primarily ix 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
by William Stein at the University of Washington, and was first released in February 2005 Information about sage can be found at the site http://www.sagemath.org Although there are differences among the packages, both in performance and price, all can perform standard algebra and calculus operations. The results in most of our examples and exercises have been generated using problems for which exact solutions are known, because this permits the performance of the approxi- mation method to be more easily monitored. For many numerical techniques the error analysis requires bounding a higher ordinary or partial derivative, which can be a tedious task and one that is not particularly instructive once the techniques of calculus have bee mastered. Having a symbolic computation package available can be very useful in the study of approximation techniques, because exact values for derivatives can easily be obtained. A little insight often permits a symbolic computation to aid in the bounding process as well We have chosen Maple as our standard package because of its wide academic distri- bution and because it now has a NumericalAnalysis package that contains programs that parallel the methods and algorithms in our text. However, other CAS can be substituted with only minor modifications mples and exercises have been added whenever we felt that a CAs would be of significant benefit, and we have discussed the approximation methods that CAS employ when they are unable to solve a problem exactl Algorithms and Programs In our first edition we introduced a feature that at the time was innovative and somewhat controversial. Instead of presenting our approximation techniques in a specific programmin language(FOrTRan was dominant at the time), we gave algorithms in a pseudo code that would lead to a well-structured program in a variety of languages. The programs are coded and available online in most common programming languages and CAS worksheet formats All of these are on the web site for the book. http://www.math.ysu.edu/-faires/numerical-analysis/ For each algorithm there is a program written in FORTRAN, Pascal, C, and Java. In addition, we have coded the programs using Maple, Mathematica, and MATLAB. This should ensure that a set of programs is available for most common computing systems Thie Every program is illustrated with a sample problem that is closely correlated to the text permits the program to be run initially in the language of your choice to see the form of the input and output. The programs can then be modified for other problems by making minor changes. The form of the input and output are, as nearly as possible, the same in each of the programming systems. This permits an instructor using the programs to discus them generically, without regard to the particular programming system an individual student chooses to use The programs are designed to run on a minimally configured computer and given in ASCII format for flexibility of use. This permits them to be altered using any editor or word essor that creates standard ASCll files(commonly called"Text Only "files). Extensive README files are included with the program files so that the peculiarities of the various programming systems can be individually addressed. The README files are presented both in ASCII format and as PDF files. As new software is developed, the programs will be updated and placed on the web site for the book or most of the programming systems the appropriate software is needed, such as a compiler for Pascal, FORTRAN, and C, or one of the computer algebra systems(Maple, Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning
x Preface by William Stein at the University of Washington, and was first released in February 2005. Information about Sage can be found at the site http://www.sagemath.org . Although there are differences among the packages, both in performance and price, all can perform standard algebra and calculus operations. The results in most of our examples and exercises have been generated using problems for which exact solutions are known, because this permits the performance of the approximation method to be more easily monitored. For many numerical techniques the error analysis requires bounding a higher ordinary or partial derivative, which can be a tedious task and one that is not particularly instructive once the techniques of calculus have been mastered. Having a symbolic computation package available can be very useful in the study of approximation techniques, because exact values for derivatives can easily be obtained. A little insight often permits a symbolic computation to aid in the bounding process as well. We have chosen Maple as our standard package because of its wide academic distribution and because it now has a NumericalAnalysis package that contains programs that parallel the methods and algorithms in our text. However, other CAS can be substituted with only minor modifications. Examples and exercises have been added whenever we felt that a CAS would be of significant benefit, and we have discussed the approximation methods that CAS employ when they are unable to solve a problem exactly. Algorithms and Programs In our first edition we introduced a feature that at the time was innovative and somewhat controversial. Instead of presenting our approximation techniques in a specific programming language (FORTRAN was dominant at the time), we gave algorithms in a pseudo code that would lead to a well-structured program in a variety of languages. The programs are coded and available online in most common programming languages and CAS worksheet formats. All of these are on the web site for the book: http://www.math.ysu.edu/∼faires/Numerical-Analysis/ . For each algorithm there is a program written in FORTRAN, Pascal, C, and Java. In addition, we have coded the programs using Maple, Mathematica, and MATLAB. This should ensure that a set of programs is available for most common computing systems. Every program is illustrated with a sample problem that is closely correlated to the text. This permits the program to be run initially in the language of your choice to see the form of the input and output. The programs can then be modified for other problems by making minor changes. The form of the input and output are, as nearly as possible, the same in each of the programming systems. This permits an instructor using the programs to discuss them generically, without regard to the particular programming system an individual student chooses to use. The programs are designed to run on a minimally configured computer and given in ASCII format for flexibility of use. This permits them to be altered using any editor or word processor that creates standard ASCII files (commonly called “Text Only” files). Extensive README files are included with the program files so that the peculiarities of the various programming systems can be individually addressed. The README files are presented both in ASCII format and as PDF files. As new software is developed, the programs will be updated and placed on the web site for the book. For most of the programming systems the appropriate software is needed, such as a compiler for Pascal, FORTRAN, and C, or one of the computer algebra systems (Maple, 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
Preface Mathematica, and MATLAB). The Java implementations are an exception. You need the system to run the but Java can be freely downloaded from various sites. The best way to obtain Java is to use a search engine to search on the name, choose a download site, and follow the instructions for that site New for this edition The first edition of this book was published more than 30 years ago, in the decade after major advances in numerical techniques were made to reflect the new widespread availability of omputer equipment. In our revisions of the book we have added new techniques in order to keep our treatment current. To continue this trend, we have made a number of significant Our treatment of Numerical Linear Algebra has been extensively expanded, and con stitutes one of major changes in this edition. In particular, a section on Singular Value Decomposition has been added at the end of Chapter 9. This required a complete rewrite of the early part of Chapter 9 and considerable expansion of Chapter 6 to include neces- lry material concerning symmetric and orthogonal matrices. Chapter 9 is approximately 40% longer than in the eighth edition, and contains a significant number of new examples and exercises. Although students would certainly benefit from a course in Linear Algebra before studying this material, sufficient background material is included in the book, and every result whose proof is not given is referenced to at least one commonly available All the Examples in the book have been rewritten to better emphasize the problem to be solved before the specific solution is presented. Additional steps have been added to many of the examples to explicitly show the computations required for the first steps of iteration processes. This gives the reader a way to test and debug programs the ey have written for problems similar to the examples a new item designated as an illustration has been added This is used when discussing a specific application of a method not suitable for the problem statement-solution format of the Examples The Maple code we include now follows, whenever possible, the material included in their NumericalAnalysis package. The statements given in the text are precisely what is needed for the Maple worksheet applications, and the output is given in the same font and color format that Maple produces Anumber of sections have been expanded, and some divided, to make it easier for instruc- tors to assign problems immediately after the material is presented. This is particularly true in Chapters 3, 6, 7, and 9. Numerous new historical notes have been added, primarily in the margins where they can be considered independent of the text material. Much of the current material used in Numerical Analysis was developed in middle of the 20th century, and students should b The bibliographic material has been updated to reflect new editions of books that we reference. New sources have been added that were not previously available. As always with our revisions, every sentence was examined to determine if it was phrased in a manner that best relates what is described 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
Preface xi Mathematica, and MATLAB). The Java implementations are an exception. You need the system to run the programs, but Java can be freely downloaded from various sites. The best way to obtain Java is to use a search engine to search on the name, choose a download site, and follow the instructions for that site. New for This Edition The first edition of this book was published more than 30 years ago, in the decade after major advances in numerical techniques were made to reflect the new widespread availability of computer equipment. In our revisions of the book we have added new techniques in order to keep our treatment current. To continue this trend, we have made a number of significant changes to the ninth edition. • Our treatment of Numerical Linear Algebra has been extensively expanded, and constitutes one of major changes in this edition. In particular, a section on Singular Value Decomposition has been added at the end of Chapter 9. This required a complete rewrite of the early part of Chapter 9 and considerable expansion of Chapter 6 to include necessary material concerning symmetric and orthogonal matrices. Chapter 9 is approximately 40% longer than in the eighth edition, and contains a significant number of new examples and exercises. Although students would certainly benefit from a course in Linear Algebra before studying this material, sufficient background material is included in the book, and every result whose proof is not given is referenced to at least one commonly available source. • All the Examples in the book have been rewritten to better emphasize the problem to be solved before the specific solution is presented. Additional steps have been added to many of the examples to explicitly show the computations required for the first steps of iteration processes. This gives the reader a way to test and debug programs they have written for problems similar to the examples. • A new item designated as an Illustration has been added. This is used when discussing a specific application of a method not suitable for the problem statement-solution format of the Examples. • The Maple code we include now follows, whenever possible, the material included in their NumericalAnalysis package. The statements given in the text are precisely what is needed for the Maple worksheet applications, and the output is given in the same font and color format that Maple produces. • A number of sections have been expanded, and some divided, to make it easier for instructors to assign problems immediately after the material is presented. This is particularly true in Chapters 3, 6, 7, and 9. • Numerous new historical notes have been added, primarily in the margins where they can be considered independent of the text material. Much of the current material used in Numerical Analysis was developed in middle of the 20th century, and students should be aware that mathematical discoveries are ongoing. • The bibliographic material has been updated to reflect new editions of books that we reference. New sources have been added that were not previously available. As always with our revisions, every sentence was examined to determine if it was phrased in a manner that best relates what is described. 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
xiiPreface Supplements A Student Solutions Manual and Study Guide (IsBN-10: 0-538-73351-9: ISBN-13: 978-0- 538-73351-9)is available for purchase with this edition, and contains worked-out solutions to many of the problems. The solved exercises cover all of the techniques discussed in the text, and include step-by-step instructions for working through the algorithms. The first two chapters of this Guide are available for preview on the web site for the book. Complete solutions to all exercises in the text are available to instructors in secure, customizable online format through the Cengage Solution Builder service. Adopting in- structorscansignupforaccessatwww.cengage.com/solutionbuilder.Computationresults in these solutions were regenerated for this edition using the programs on the web site to ensure compatibility among the various programming systems A set of classroom lecture slides, prepared by Professor John Carroll of Dublin City University,areavailableonthebooksinstructorcompanionwebsiteatwww.cengage com/math/burden. These slides, created using the Beamer package of LaTex, are in PDF format. They present examples, hints, and step-by-step animations of important techniques in Numerical Analysis. Possible Course Suggestions Numerical Analysis is designed to give instructors flexibility in the choice of topics as well as in the level of theoretical rigor and in the emphasis on applications. In line with these aims, we provide detailed references for results not demonstrated in the text and for the applications used to indicate the practical importance of the methods. The text references cited are those most likely to be available in college libraries, and they have been updated to reflect recent editions. We also include quotations from original research papers when we feel this material is accessible to our intended audience. All referenced material has been indexed to the appropriate locations in the text, and Library of Congress information for reference material has been included to permit easy location if searching for library material The following flowchart indicates chapter prerequisites. Most of the possible sequences that can be generated from this chart have been taught by the authors at Youngstown State University Chapter 1 Chapter 6 Chapter 3 Chapter 10 Chapter 7 Chapter 8 Chapter 4 Chapter 5 E Chapter 11 Copyright 2010 Cengage Learning. All Rights May no be copied, scanned, or duplicated, in whole or in part Due to maternally aftec the overall leaning expenence. Cengage Learning
xii Preface Supplements A Student Solutions Manual and Study Guide (ISBN-10: 0-538-73351-9; ISBN-13: 978-0- 538-73351-9) is available for purchase with this edition, and contains worked-out solutions to many of the problems. The solved exercises cover all of the techniques discussed in the text, and include step-by-step instructions for working through the algorithms. The first two chapters of this Guide are available for preview on the web site for the book. Complete solutions to all exercises in the text are available to instructors in secure, customizable online format through the Cengage Solution Builder service. Adopting instructors can sign up for access at www.cengage.com/solutionbuilder. Computation results in these solutions were regenerated for this edition using the programs on the web site to ensure compatibility among the various programming systems. A set of classroom lecture slides, prepared by Professor John Carroll of Dublin City University, are available on the book’s instructor companion web site at www.cengage. com/math/burden. These slides, created using the Beamer package of LaTeX, are in PDF format. They present examples, hints, and step-by-step animations of important techniques in Numerical Analysis. Possible Course Suggestions Numerical Analysis is designed to give instructors flexibility in the choice of topics as well as in the level of theoretical rigor and in the emphasis on applications. In line with these aims, we provide detailed references for results not demonstrated in the text and for the applications used to indicate the practical importance of the methods. The text references cited are those most likely to be available in college libraries, and they have been updated to reflect recent editions. We also include quotations from original research papers when we feel this material is accessible to our intended audience. All referenced material has been indexed to the appropriate locations in the text, and Library of Congress information for reference material has been included to permit easy location if searching for library material. The following flowchart indicates chapter prerequisites. Most of the possible sequences that can be generated from this chart have been taught by the authors at Youngstown State University. Chapter 2 Chapter 6 Chapter 3 Chapter 10 Chapter 7 Chapter 8 Chapter 9 Chapter 11 Chapter 12 Chapter 4 Chapter 5 Chapter 1 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