Transcription

Walter GautschiNumerical AnalysisSecond Edition

Walter GautschiDepartment of Computer SciencesPurdue University250 N. University StreetWest Lafayette, IN [email protected] 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 . . . .