ELEMENTARY NUMERICAL ANALYSIS ELEMENTARY NUMERICAL ANALYSIS Third Edition KENDALL ATKINSON WEIMINHAN University of Iowa John Wiley & Sons, Inc. ASSOCIATE PUBLISHER Laurie Rosatone SENIOR MARKETING MANAGER Julie Z. Lindstrom ASSISTANT EDITOR Jennifer Battista PROGRAM ASSISTANT Stacy French SENIOR PRODUCTION EDITOR Ken Santor SENIOR DESIGNER Dawn Stanley ILLUSTRATION EDITOR Sandra Rigby This book was set in I5⅞X by Techsetters Inc. and printed and bound by R. R. Donnelley Crawfordsville. The cover was printed by Phoenix Color Corporation. This book is printed on acid free paper. ∞ Copyright © 2004 John Wiley & Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 or the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750- 4470. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., Ill River Street, Hoboken, NJ 07030, (201) 748- 6011, fax (201) 748-6008, E-Mail: [email protected]. To order books or for customer service please call 1-800-CALL WILEY (225-5945). Library of Congress Cataloging-in-Publication Data Atkinson, Kendall E. Elementary numerical analysis / Kendall Atkinson and Weimin Han.-3rd ed. p. cm. Includes bibliographical references and index. ISBN 0-471-43337-3 ) 1. Numerical analysis. I. Han, Weimin. ∏. Title. QA297.A83 2004 519.4-dc21 2003053836 To our children Elizabeth and Kathryn Elizabeth and Michael P r ef a c e This book provides an introduction to numerical analysis and is intended to be used by undergraduates in the sciences, mathematics, and engineering. The main prerequisite is a one-year course in the calculus of functions of one variable, but some familiarity with computers is also needed. With this background, the book can be used for a sophomore­ level course in numerical analysis. The last four chapters of the book present numerical methods for linear algebra, ordinary differential equations, and partial differential equa­ tions. A background in these subjects would be helpful, but these chapters include the necessary introduction to the theory of these subjects. Students taking a course in numerical analysis do so for a variety of reasons. Some will need it in studying other subjects, in research, or in their careers. Others will be taking it to broaden their knowledge of computing. When we teach this course, we have several objectives for the students. First, they should obtain an intuitive and working understanding of some numerical methods for the basic problems of numerical analysis (as specified by the chapter headings). Second, they should gain some appreciation of the concept of error and of the need to analyze and predict it. And third, they should develop some experience in the implementation of numerical methods by using a computer. This should include an appreciation of computer arithmetic and its effects. vii viii Preface The book covers most of the standard topics in a numerical analysis course, and it also explores some of the main underlying themes of the subject. Among these are the approximation of problems by simpler problems, the construction of algorithms, iteration methods, error analysis, stability, asymptotic error formulas, and the effects of machine arithmetic. Because of the level of the course, emphasis has been placed on obtaining an intuitive understanding of both the problem at hand and the numerical methods being used to solve it. The examples have been carefully chosen to develop this understanding, not just to illustrate an algorithm. Proofs are included only where they are sufficiently simple and where they add to an intuitive understanding of the result. For the computer programming, the preferred language for introductory courses in numerical analysis is Matlab. A short introduction is given in Appendix D; and the programs in the text serve as further examples. The students are encouraged to modify these programs and to use them as models for writing their own Matlab programs. When the authors teach this course, we also provide links to other sites that have online Matlab tutorials. The Matlab programs are included for several reasons. First, they illustrate the construction of algorithms. Second, they save the students time by avoiding the need to write many programs, allowing them to spend more time on experimentally learning about a numerical method. After all, the main focus of the course should be numerical analysis, not learning how to program. Third, the programs provide examples of the language Matlab and of reasonably good programming practices when using it. Of course, the students should write some programs of their own. Some of these can be simple modifications of the included programs; for example, modifying the trapezoidal rule integration code to obtain one for the midpoint rule. Other programs should be more substantial and original. All of the codes in the book, and others, are available from the book’s Website at John Wiley, at http://www.wiley.com/college/atkinson The authors also maintain a site for these codes and other course materials, at http√∕www.math.uiowa>edu∕flp∕atkinson∕ENA~Materials In addition to the Matlab programs in the text, the authors are experimenting with graphical user interfaces (GUIs) to help students explore various topics using only menus, query windows, and pushbuttons. Several of these have been written, including some to explore the creation and analysis of Taylor polynomial approximations, rootfinding, polynomial interpolation with both uniformly spaced nodes and Chebyshev nodes, and numerical integration. The GUIs are written using the Matlab GUI development envi­ ronment, and they must be run from within Matlab. These GUIs are available from the authors’ Website given above, and the authors are interested in feedback from instructors, students, and other people using the GUIs. There are exercises at the end of each section in the book. These are of several types. Some exercises provide additional illustrations of the theoretical results given in the section, and many of these exercises can be done with either a hand calculator or with Preface ix a simple computer program. Other exercises are for the purpose of further exploring the theoretical material of the section, perhaps to develop some additional theoretical results. In some sections, exercises are given that require more substantial programs; many' of these exercises can be done in conjunction with package programs like those discussed in Appendix C. The third edition of this book contains a new chapter and two new sections, and the book has been reorganized when compared to the second edition. The section on computer arithmetic has been rewritten and it now concentrates on the IEEE floating­ point format for representing numbers in computers; the section on binary arithmetic has been moved to the new Appendix E. The new sections are Section 4.7 on the least squares approximation of functions (including an introduction to Legendre polynomials), and Section 8.8 on the two-point boundary value problem. The new Chapter 9 is on numerical methods for the classic second order linear partial differential equations in two variables. In addition, a number of other parts of the text have been rewritten, and examples and many new problems have been added. In teaching a one-semester course from this textbook, the authors usually cover much of Chapters 1-6 and 8. The linear algebra material of Chapter 6 can be introduced at any point, although the authors generally leave it to the second half of the course. The material on polynomial interpolation in Chapter 4 will be needed before covering Chapters 5 and 8. The textbook contains more than enough material for a one-semester course, and an instructor has considerable leeway in choosing what to omit. We thank our colleagues at the University of Iowa for their comments on the text. We also thank the reviewers of the manuscript for their many suggestions, which were very helpful in preparing the third edition of the book. We thank Cymie Wehr for having done an excellent job of creating a K⅛X version of the second edition. It was used in preparing this third edition and it saved us a great deal of time and effort. We thank Brian Treadway for his invaluable assistance in helping us to navigate KΓβX. The staff of John Wiley have been supportive and helpful in this project, and we are grateful to them. Kendall E. Atkinson Weimin Han Iowa City, Iowa May 2003