Numerical Analysis (Second Edition)
Walter GautschiNumerical AnalysisSecond Edition
Walter GautschiDepartment of Computer SciencesPurdue University250 N. University StreetWest Lafayette, IN 47907-2066wgautschi@purdue.eduISBN 978-0-8176-8258-3e-ISBN 978-0-8176-8259-0DOI 10.1007/978-0-8176-8259-0Springer New York Dordrecht Heidelberg LondonLibrary of Congress Control Number: 2011941359Mathematics Subject Classification (2010): 65-01, 65D05, 65D07, 65D10, 65D25, 65D30, 65D32,65H04, 65H05, 65H10, 65L04, 65L05, 65L06, 65L10c Springer Science Business Media, LLC 1997, 2012 All rights reserved. This work may not be translated or copied in whole or in part without the writtenpermission of the publisher (Springer ScienceCBusiness Media, LLC, 233 Spring Street, New York,NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use inconnection with any form of information storage and retrieval, electronic adaptation, computer software,or by similar or dissimilar methodology now known or hereafter developed is forbidden.The use in this publication of trade names, trademarks, service marks, and similar terms, even if they arenot identified as such, is not to be taken as an expression of opinion as to whether or not they are subjectto proprietary rights.Printed on acid-free paperwww.birkhauser-science.com
TOERIKA
Preface to the Second EditionIn this second edition, the outline of chapters and sections has been preserved. Thesubtitle “An Introduction”, as suggested by several reviewers, has been deleted. Thecontent, however, is brought up to date, both in the text and in the notes. Manypassages in the text have been either corrected or improved. Some biographicalnotes have been added as well as a few exercises and computer assignments. Thetypographical appearance has also been improved by printing vectors and matricesconsistently in boldface types.With regard to computer language in illustrations and exercises, we now adoptuniformly Matlab. For readers not familiar with Matlab, there are a number ofintroductory texts available, some, like Moler [2004], Otto and Denier [2005],Stanoyevitch [2005] that combine Matlab with numerical computing, others, likeKnight [2000], Higham and Higham [2005], Hunt, Lipsman and Rosenberg [2006],and Driscoll [2009], more exclusively focused on Matlab.The major novelty, however, is a complete set of detailed solutions to all exercisesand machine assignments. The solution manual is available to instructors uponrequest at the publisher’s website . Selected solutions are also included in the text to give students an idea ofwhat is expected. The bibliography has been expanded to reflect technical advancesin the field and to include references to new books and expository accounts. As aresult, the text has undergone an expansion in size of about 20%.West Lafayette, IndianaNovember 2011Walter Gautschivii
Preface to the First EditionThe book is designed for use in a graduate program in Numerical Analysis thatis structured so as to include a basic introductory course and subsequent morespecialized courses. The latter are envisaged to cover such topics as numericallinear algebra, the numerical solution of ordinary and partial differential equations,and perhaps additional topics related to complex analysis, to multidimensionalanalysis, in particular optimization, and to functional analysis and related functionalequations. Viewed in this context, the first four chapters of our book could serve asa text for the basic introductory course, and the remaining three chapters (whichindeed are at a distinctly higher level) could provide a text for an advanced courseon the numerical solution of ordinary differential equations. In a sense, therefore,the book breaks with tradition in that it does no longer attempt to deal with allmajor topics of numerical mathematics. It is felt by the author that some of thecurrent subdisciplines, particularly those dealing with linear algebra and partialdifferential equations, have developed into major fields of study that have attaineda degree of autonomy and identity that justifies their treatment in separate booksand separate courses on the graduate level. The term “Numerical Analysis” asused in this book, therefore, is to be taken in the narrow sense of the numericalanalogue of Mathematical Analysis, comprising such topics as machine arithmetic,the approximation of functions, approximate differentiation and integration, and theapproximate solution of nonlinear equations and of ordinary differential equations.What is being covered, on the other hand, is done so with a view towardstressing basic principles and maintaining simplicity and student-friendliness as faras possible. In this sense, the book is “An Introduction”. Topics that, even thoughimportant and of current interest, require a level of technicality that transcends thebounds of simplicity striven for, are referenced in detailed bibliographic notes at theend of each chapter. It is hoped, in this way, to place the material treated in propercontext and to help, indeed encourage, the reader to pursue advanced modern topicsin more depth.A significant feature of the book is the large collection of exercises thatare designed to help the student develop problem-solving skills and to provideinteresting extensions of topics treated in the text. Particular attention is given toix
xPreface to the First Editionmachine assignments, where the student is encouraged to implement numericaltechniques on the computer and to make use of modern software packages.The author has taught the basic introductory course and the advanced course onordinary differential equations regularly at Purdue University for the last 30 yearsor so. The former, typically, was offered both in the fall and spring semesters, to amixed audience consisting of graduate (and some good undergraduate) students inmathematics, computer science, and engineering, while the latter was taught only inthe fall, to a smaller but also mixed audience. Written notes began to materialize inthe 1970s, when the author taught the basic course repeatedly in summer courses onMathematics held in Perugia, Italy. Indeed, for some time, these notes existed onlyin the Italian language. Over the years, they were progressively expanded, updated,and transposed into English, and along with that, notes for the advanced course weredeveloped. This, briefly, is how the present book evolved.A long gestation period such as this, of course, is not without dangers, themost notable one being a tendency for the material to become dated. The authortried to counteract this by constantly updating and revising the notes, adding newerdevelopments when deemed appropriate. There are, however, benefits as well: overtime, one develops a sense for what is likely to stand the test of time and whatmay only be of temporary interest, and one selects and deletes accordingly. Anotherbenefit is the steady accumulation of exercises and the opportunity to have themtested on a large and diverse student population.The purpose of academic teaching, in the author’s view, is twofold: to transmitknowledge, and, perhaps more important, to kindle interest and even enthusiasmin the student. Accordingly, the author did not strive for comprehensiveness –even within the boundaries delineated – but rather tried to concentrate on what isessential, interesting and intellectually pleasing, and teachable. In line with this,an attempt has been made to keep the text uncluttered with numerical examples andother illustrative material. Being well aware, however, that mastery of a subject doesnot come from studying alone but from active participation, the author providedmany exercises, including machine projects. Attributions of results to specificauthors and citations to the literature have been deliberately omitted from the bodyof the text. Each chapter, as already mentioned, has a set of appended notes thathelp the reader to pursue related topics in more depth and to consult the specializedliterature. It is here where attributions and historical remarks are made, and wherecitations to the literature – both textbook and research – appear.The main text is preceded by a prologue, which is intended to place the book inproper perspective. In addition to other textbooks on the subject, and informationon software, it gives a detailed list of topics not treated in this book, but definitelybelonging to the vast area of computational mathematics, and it provides amplereferences to relevant texts. A list of numerical analysis journals is also included.The reader is expected to have a good background in calculus and advancedcalculus. Some passages of the text require a modest degree of acquaintance withlinear algebra, complex analysis, or differential equations. These passages, however,can easily be skipped, without loss of continuity, by a student who is not familiarwith these subjects.
Preface to the First EditionxiIt is a pleasure to thank the publisher for showing interest in this book andcooperating in producing it. The author is also grateful to Soren Jensen and ManilSuri, who taught from this text, and to an anonymous reader; they all made manyhelpful suggestions on improving the presentation. He is particularly indebted toProf. Jensen for substantially helping in preparing the exercises to Chap. 7. Theauthor further acknowledges assistance from Carl de Boor in preparing the notes toChap. 2 and to Werner C. Rheinboldt for helping with the notes to Chap. 4. Last butnot least, he owes a measure of gratitude to Connie Wilson for typing a preliminaryversion of the text and to Adam Hammer for assisting the author with the moreintricate aspects of LaTeX.West Lafayette, IndianaJanuary 1997Walter Gautschi
ContentsPrologue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xixP1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xixP2Numerical Analysis Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiP3Textbooks and Monographs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiP3.1 Selected Textbooks on Numerical Analysis . . . . . . . . . . . . . . . . xxiP3.2 Monographs and Books on Specialized Topics . . . . . . . . . . . . . xxiiiP4Journals. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxvi1 Machine Arithmetic and Related Matters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1 Real Numbers, Machine Numbers, and Rounding . . . . . . . . . . . . . . . . .1.1.1 Real Numbers. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.2 Machine Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.3 Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2 Machine Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.1 A Model of Machine Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . .1.2.2 Error Propagation in Arithmetic Operations:Cancellation Error . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3 The Condition of a Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.1 Condition Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.3.2 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.4 The Condition of an Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.5 Computer Solution of a Problem; Overall Error . . . . . . . . . . . . . . . . . . .1.6 Notes to Chapter 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises and Machine Assignments to Chapter 1 . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Machine Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Selected Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Selected Solutions to Machine Assignments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1223577811131624272831313944482 Approximation and Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1 Least Squares Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.1 Inner Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.1.2 The Normal Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55595961xiii
xivContents2.1.3 Least Squares Error; Convergence. . . . . . . . . . . . . . . . . . . . . . . . .2.1.4 Examples of Orthogonal Systems . . . . . . . . . . . . . . . . . . . . . . . . . .2.2 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.1 Lagrange Interpolation Formula: Interpolation Operator . .2.2.2 Interpolation Error. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.4 Chebyshev Polynomials and Nodes . . . . . . . . . . . . . . . . . . . . . . . .2.2.5 Barycentric Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.6 Newton’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.7 Hermite Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.2.8 Inverse Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3 Approximation and Interpolation by Spline Functions . . . . . . . . . . . . .2.3.1 Interpolation by Piecewise Linear Functions . . . . . . . . . . . . . . .2.3.2 A Basis for S01 . / . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.3 Least Squares Approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.4 Interpolation by Cubic Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.5 Minimality Properties of Cubic Spline Interpolants . . . . . . . .2.4 Notes to Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises and Machine Assignments to Chapter 2 . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Machine Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Selected Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Selected Solutions to Machine Assignments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81341381503 Numerical Differentiation and Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1 Numerical Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.1 A General Differentiation Formula for UnequallySpaced Points . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.2 Examples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.1.3 Numerical Differentiation with Perturbed Data . . . . . . . . . . . .3.2 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.1 The Composite Trapezoidal and Simpson’s Rules . . . . . . . . . .3.2.2 (Weighted) Newton–Cotes and Gauss Formulae. . . . . . . . . . .3.2.3 Properties of Gaussian Quadrature Rules . . . . . . . . . . . . . . . . . . .3.2.4 Some Applications of the Gauss Quadrature Rule . . . . . . . . .3.2.5 Approximation of Linear Functionals: Methodof Interpolation vs. Method of UndeterminedCoefficients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.2.6 Peano Representation of Linear Functionals . . . . . . . . . . . . . . .3.2.7 Extrapolation Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3.3 Notes to Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Exercises and Machine Assignments to Chapter 3 . . . . . . . . . . . . . . . . . . . . . . . .Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Machine Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Selected Solutions to Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Selected Solutions to Machine Assignments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14219232
Contentsxv4 Nonlinear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.1 A Transcendental Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.2 A Two-Point Boundary Value Problem . . . . . . . . . . . . . . . . . . . .4.1.3 A Nonlinear Integral Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.1.4 s-Orthogonal Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.2 Iteration, Convergence, and Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3 The Methods of Bisection and Sturm Sequences . . . . . . . . . . . . . . . . . . .4.3.1 Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.3.2 Method of Sturm Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.4 Method of False Position . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.5 Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.6 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.7 Fixed Point Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.8 Algebraic Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.8.1 Newton’s Method Applied to an Algebraic Equation . . . . . .4.8.2 An Accelerated Newton Method for Equationswith Real Roots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.9 Systems of Nonlinear Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.9.1 Contraction Mapping Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4.9.2 Newton’s Method for Systems of Equations . . . . .
Preface to the First Edition The book is designed for use in a graduate program in Numerical Analysis that is structured so as to include a basic introductory course and subsequent more specialized courses. The latter are envisaged to cover such topics as numerical linear algebra, the numerical solution of ordinary and partial differential .
RP 2K, Second Edition RP 2L, Third Edition RP 2M, First Edition Bul 2N, First Edition RP 2P, Second Edition RP 2Q, Second Edition RP 2R, First Edition RP 2T, First Edition Bul 2U, First Edition Bul 2V, First Edition Spec 2W, First Edition RP 2X, First Edition, with Supp 1 Spec 2Y, First Edition
“numerical analysis” title in a later edition [171]. The origins of the part of mathematics we now call analysis were all numerical, so for millennia the name “numerical analysis” would have been redundant. But analysis later developed conceptual (non-numerical) paradigms, and it became useful to specify the different areas by names.
BIOS INSTANT NOTES Series Editor: B.D. Hames, School of Biochemistry and Microbiology, University of Leeds, Leeds, UK Biology Animal Biology, Second Edition Biochemistry, Third Edition Bioinformatics Chemistry for Biologists, Second Edition Developmental Biology Ecology, Second Edition Genetics, Second Edition Immunology, Second Edition
the numerical solution of second-order optimization methods. Next step development of Numerical Multilinear Algebra for the statistical analysis of multi-way data, the numerical solution of partial di erential equations arising from tensor elds, the numerical solution of higher-order optimization methods.
numerical solutions. Emphasis will be placed on standing the under basic concepts behind the various numerical methods studied, implementing basic numerical methods using the MATLAB structured programming environment, and utilizing more sophisticated numerical methods provided as built-in
Fifth Edition 1977–1978 Sixth Edition 1979–1980 Seventh Edition 1981–1982 Eighth Edition 1983–1986 Ninth Edition 1987–1988 Tenth Edition 1989–1990 Eleventh Edition 1991–1992 Twelfth Edition 1993–1994 Thirteenth Edition 1995–1996 Fourteenth Edition 1997–1998 Fifteenth Edition
Fractions and Numerical Fluency 7-3 specifically on identifying the Number, Operation, and Quantitative Reasoning as well as the Patterns, Relationships, and Algebraic Thinking TEKS that directly affects numerical fluency. Materials: Fractions and Numerical Fluency Slides 76-96, Numerical Fluency PowerPoint Handout 1-Graphic Organizer (page 7-14)
Weight of pile above scour level Wp1 220.893 kN Weight of pile below scour level Wp2 301.548 kN Tota l ultimate resistance of pile Qsf Qb – Wp2 8717.452 kN Allowable load (8717.452 / F.S.) – Wp1 3266 kN. From above calculations, Required depth 26.03m below design seabed level E.G.L. ( ) 1.15 m CD . International Journal of Engineering Trends and Technology (IJETT) – Volume .
