Preface xi Algorithms As in previous editions,we give a detailed,structured algorithm without program listing for each method in the text.The algorithms are in a form that can be coded,even by those with limited programming experience. This edition cudes a disk containing progr the algor ams for solutions to r esentative exer- The Maple and Mathema in MATLAB枣 a,as well a a comnputer software package that is wi y used for linear algebra applica systems. A Student Study Guide is available with this edition that illustrates the calls required for these programs,which is useful for those with limited programming experience.The study guide also contains worked-out solutions to many of the problems. Brooks/Cole can provide instructors with an Instructor's Manual that provides an- book.Com tion sults in the nstructor' were reg ed for this editio using the programs on lisk to ensure com patibi ty am ong the va ous programming systems The algorithms in the text lead to programs that give correct results for the examples and exercises in the text,but no attempt was made to write general-purpose professional software.Specifically,the algorithms are not always written in a form that leads to the mosf efficient program in terms of either time or storage requirements.When a conflict occurred between writing an extremely efficient algorithm and writing a slightly different one that better illustrates the important features of the method.the latter path was invariably taken About the Program Disk The CD on the inside back cover of the book contains the book ograms for all the algorithms in 11 in both the S)and ble udy Gu uide fo r the book (PDE ats For each algoithm there is a C.Fortran,Maple,Ma B,and Pascal program,and for some of these systems there are multiple programs that depend on the particular version of the software that is being run.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 pro- grams can then be modified for other problems by making minor changes.The form of the nput and output are,as nearly as possible,the same in e ach of the p n ins structor using th e ally. without regard to the particular progra studer t uses quired is a computer running MS-DOS,Windows,or the Macintosh operating system You will,however,need appropriate software,such as a compiler for Pascal,Fortran,and C.or one of the computer algebra systems (Maple,Mathematica,and MATLAB).There
xi Preface are six subdirectories on the disk,one for each of the computer languages and the accom panying data files. All of the programs are given as ASCII files or worksheets.They can be altered using any editor or word processor that creates a standard ASCI file.(These are also commonly called"Text Only"files.) Extensive README files are included with the program files so that the peculiarities of the various are pre and as PDF files.As new software is developed,the Suggested Course Outlines Numerical Analysis is designed to allow instructors flexibility in the choice of topics. well as in the level of theoretical rigor and in the emphasis on applicatio In line wit these aims,we provide detailed references for the results that are not demonstrate the text and for the applications that are used to indicate the practical importance of the methods.The text references cited are those most likely to be available in college libraries and have been updated to reflect the most recent edition at the time this book was placed into production.We also include quotations from original research papers when we feel this material is accessible to our intended audience The following flowchart indic pter quisites.The only deviation from this chart is described in the the 6r of S ction 3 4 Most of the possible sequences that can be generated from ve been taught by the authors at Youngstown State University. Chapter 6 Chapter 7 Chapter 8 Chapter 4 Chapter 5 Chapter Chapter 12
Preface xili Acknowledgments aa communicate are taken very seriously;we have tried to include all the suggestions that are in line with the philosophy of the book,and are extremely grateful to all those that have taken the time to contact us and inform us of improvements we can make in subsequent versions. We would particularly like to thank the following.whose efforts we greatly appreciate. Glen Granzow,Idaho State University Jose Miguel,Universidad Peruana Cayetano Heredia,Lima,Peru John M.Neuberger,Northern Arizona University L.G.de Pillis,Harvey Mudd College We want especially to thank our friend and former student Jim Baglama of Ball State University.Jim agreed to be an extensive reviewer for this edition and was particularly helpful in updating our survey sections and references to software.It is most gratifying to see one's students move through the profession. Also moving through his profession.but in a completly different manner,is our Editor and Publisher Gar y has been ar outstanding ma ager of our projects and al friend.We will ss his directic assista this opporunity to wish all the best in his upcoming retirement from Brooks/Cole As has been our practice in past editions of the book,we have used student help at Youngstown State University in preparing the seventh edition.Our able assistant for this edition was Laurie Marinelli,whom we thank for all her work.We would also like to express gratitude to our colleagues on the faculty and administration of Youngstown State University for providing us the opportunity and facilities to compiete this project. Finally,we would like to thank all those who have used and adopted the various edi tions of Nu rical Analysis over the ears.it has been wonderful to hear from so many and facult wwe hope osure to the study of nu rical is.If you edino ftre eitions of the bo ents studying nume analy e ments.We can be contacted by electronic mail at the addresses listed below. Richard L.Burden burden@math.ysu.edu J.Douglas Faires faires@math.ysu.edu
Contents Mathematical Preliminaries 1 11 Review of Caleulus 2 12 Roundoff Errors and Computer Arithmetic 18 1.3 Algorithms and Convergence 31 1.4 Numerical Software 40 Solutions of Equations in One Variable 47 2.1 The Bisection Method 48 2.2 Fixed-Point Iteration 55 Newton's Method 66 Error Analysis for Iterative Methods 78 25 Accelerating Convergence 86 2.6 Zeros of Polynomials and Miller's Method 91 2.7 Survey of Methods and Software 101 Interpolation and Polynomial Approximation 104 3.1 Interpolation and the Lagrange Polynomia!107 32 Divided Differences 122 33 Hermite Interpolation 133 3.4 Cubic Spline Interpolation 141 35 Parametric Curves 156 3.6 Survey of Methods and Software 163
vi Contents 4 Numerical Differentiation and Integration 166 4.1 Numerical Differentiation 167 4.2 Richardson's Extrapolation 178 Elements of Numerical [ntegration 18( Composite Numerical Integration 196 4.5 Romberg Integration 207 46 Adaptive Quadrature Methods 213 Gaussian Quadrature 220 4.8 Multiple Integrals 227 40 Improper Integrals 241 4.10 rvey of Methods and Software 247 5 Initial-Value Problems for Ordinary Differential Equations 249 The Elementary Theory of Initial-Value Problems 251 5.2 Euler's Method 256 Higher-Order Taylor Methods 266 Runge-Kutta Methods 272 5.5 Error Control and the Runge-Kutta-Fehlberg Method 282 5 6 Multisten Methods 280 5.7 Variable Step-Size Multistep Methods 30 5.8 Extrapolation Methods 307 50 Higher-Order Equations and Systems of Differential Equations 313 510 Stability 324 5.11 Stiff Differential Equations 334 5.12 Survey of Methods and Software 342 Direct Methods for Solving Linear Systems 344 Linear Systems of Equations 345 Pivoting Strategies 359 6.3 Linear Algebra and Matrix Inversion 370 64 The Determinant of a matrix 383 6.5 Matrix Factorization 388 6.6 Special Types of Matrices 398 6.7 Survey of Methods and Software 413