AN INTRODUCTION TO NUMERICAL ANALYSIS Second Edition Kendall E. Atkinson University of Iowa • WILEY John Wiley & Sons Copyright© 1978, 1989, by John Wiley & Sons, Inc. All rights reserved. Published simultaneously in Canada. Reproduction or translation of any part of this work beyond that permitted by Sections 107 and 108 of the 1976 United States Copyright Act without the permission of the copyright owner is unlawful. Requests for permission or further information should be addressed to the Permissions Department, John Wiley & Sons. Library• of Congre.fs Cataloging in Publication Data: Atkinson, Kendall E. An introduction to numerical analysis/Kendall E. Atkinson.- 2nd ed. p. em. Bibliography: p. Includes index. ' ISBN 0-471-62489-6 '· 1. Numerical analysis. I. Title. QA297.A84 1988 519.4-dcl9 __ j 20 19 18 17 16 15 14 PREFACE to the first edition This introduction to numerical analysis was written for students in mathematics, the physical sciences, and engineering, at the upper undergraduate to beginning graduate level. Prerequisites for using the text are elementary calculus, linear algebra, and an introduction to differential equations. The student's level of mathematical maturity or experience with mathematics should be somewhat higher; I have found that most students do not attain the necessary level until their senior year. Finally, the student should have a knowledge of computer programming. The preferred language for most scientific programming is For tran. A truly effective use of numerical analysis in applications requires both a theoretical knowledge of the subject and computational experience with it. The theoretical knowledge should include an understanding of both the original problem being solved and of the numerical me.thods for its solution, including their derivation, error analysis, and an idea of when they will perform well or poorly. This kind of knowledge is necessary even if you are only considering using a package program from your computer center. You must still understand the program's purpose and limitations to know whether it applies to your particular situation or not. More importantly, a majority of problems cannot be solved by the simple application of a standard program. For such problems you must devise new numerical methods, and this is usually done by adapting standard numerical methods to the new situation. This requires a good theoreti cal foundation in numerical analysis, both to devise the new methods and to avoid certain numerical pitfalls that occur easily in a number of problem areas. Computational experience is also very important. It ·gives a sense of reality to most theoretical discussions; and it brings out the important difference between the exact arithmetic implicit in most theoretical discussions and the finite-length arithmetic computation, whether on a computer or a hand calculator. The use of a computer also imposes constraints on the structure of numerical methods, constraints that are not evident and that seem unnecessary from· a strictly mathematical viewpoint. For example, iterative procedures are often preferred over direct procedures because of simpler programming requirements or com puter memory size limitations, even though the direct procedure may seem simpler to explain and to use. Many numerical examples are ~ven in this text to illustrate these points, and there are a number of exercises that will give the student a variety of <...)mputational experience. ix X PREFACE TO THE FIRST EDITION The book is organized in a fairly standard manner. Topics that are simpler, both theoretically and computationally, come first; for example, rootfinding for a single nonlinear equation is covered in Chapter 2. The more sophisticated topics within numerical linear algebra are left until the last three chapters. If an instructor prefers, however, Chapters 7 through 9 on numerical linear ·algebra can be inserted at any point following Chapter 1. Chapter 1 contains a number of introductory topics, some of which the instructor may wish to postpone until later in the course. It is important, however, to cover the mathematical and notational preliminaries of Section 1.1 and the introduction to computer floating-point arithmetic given in Section 1.2 and in part of Section 1.3. The text contains more than enough material for a one-year course. In addition, introductions are given to some topics that instructors may wish to expand on from their own notes. For example, a brief introduction is given to stiff differential equations in the last part of Section 6.8 in Chapter 6; and some theoretical foundation for the least squares data-fitting problem is given in Theorem 7.5 and Problem 15 of Chapter 7. These can easily be expanded by using the references given in the respective chapters. Each chapter contains a discussion of the research literature and a bibliogra phy of some of the important books and papers on the material of the chapter. The chapters all conclude with a set of exercises. Some of these exercises are illustrations or applications of the text material, and others involve the develop ment of new material. As an aid to the student, answers and hints to selected exercises are given at the end of the book. It is important, however, for students to solve some problems in which there is no given answer against which they can check their results. This forces them to develop a variety of other means for checking their own work; and it will force them to develop some common sense or judgment as an aid in knowing whether or not their results are reasonable. I teach a one-year course covering much of the material of this book. Chapters 1 through 5 form the first semester, and Chapters 6 through 9 form the second semester. In most chapters, a number of topics can be deleted without any difficulty arising· in later chapters. Exceptions to this are Section 2.5 on linear iteration methods, Sections 3.1 to 3.3, 3.6 on interpolation theory, Section 4.4 on orthogonal polynomials, and Section 5.1 on the trapezoidal and Simpson integra tion rules. I thank Professor Herb Hethcote of the University of Iowa for his helpful advice and for having taught from an earlier rough draft of the book. I am also grateful for the advice of Professors Robert Barnhill, University of Utah, Herman Burchard, Oklahoma State University, and Robert J. Flynn, Polytechnic Institute of New York. I am very grateful to Ada Bums and Lois Friday, who did an excellent job of typing this and earlier versions of the book. I thank the many stude~ts who, over the past twelve years, enrolled in my course and used my notes and rough drafts rather than a regular text. They pointed but numerous i errors, and their difficulties with certain topics helped me in preparing better __ ___j presentations of them. The staff of John Wiley have been very helpful, and the text is much better as a result of their efforts. Finally, I thank my wife Alice for her patient and encouraging support, without which the book would probably have not been completed. Iowa City, August, 1978 Kendall E. Atkinson CONTENTS ONE ERROR: ITS SOURCES, PROPAGATION, AND ANALYSIS 3 1.1 Mathematical Preliminaries 3 1.2 Computer Representation of Numbers 11 1.3 Definitions and Sources of Error 17 1.4 Propagation of Errors 23 1.5 Errors in Summation 29 1.6 Stability in Numerical Analysis 34 Discussion of the Literature 39 Problems 43 1WO ROOTFINDING FOR NONLINEAR EQUATIONS 53 2.1 The Bisection Method 56 2.2 Newton's Method 58 2.3 The Secant Method 65 2.4 Muller's Method 73 2.5 A General Theory for One-Point Iteration Methods 76 2.6 Aitken Extrapolation for Linearly Convergent Sequences 83 2.7 The Numerical Evaluation of Multiple Roots 87 2.8 Brent's Rootfinding Algorithm 91 2.9 Roots of Polynomials 94 2.10 Systems of Nonlinear Equations 103 2.11 Newton's Method for Nonlinear Systems 108 2.12 Unconstrained Optimization 111 Discussion of the Literature 114 Problems 117 THREE INTERPOLATION THEORY 131 3.1 PolynOinial Interpolation Theory 131 3.2 Newton Divided Differences 138 xiii xiv CONTENTS 3.3 Finite Differences and Table-Oriented Interpolation Formulas 147 3.4 Errors in Data and Forward Differences 151 3.5 Further Results on Interpolation Error 154 3.6 Hermite Interpolation 159 3.7 Piecewise Polynomial Interpolation 163 3.8 Trigonometric Interpolation 176 Discussion of the Literature 183 Problems 185 FOUR APPROXIMATION OF FUNCTIONS 197 4.1 The Weierstrass Theorem and Taylor's Theorem 197 4.2 The Minimax Approximation Problem 201 4.3 The Least Squares Approximation Problem 204 4.4 Orthogonal Polynomials 207 4.5 The Least Squares Approximation Problem (continued) 216 4.6 Minimax Approximations 222 4.7 Near-Minimax Approximations 225 Discussion of the Literature 236 Problems 239 FIVE NUMERICAL INTEGRATION 249 5.1 The Trapezoidal Rule and Simpson's Rule 251 5.2 Newton-Cotes Integration Formulas 263 5.3 Gaussian Quadrature 270 5.4 Asymptotic Error Formulas and Their Applications 284 5.5 Automatic Numerical Integration 299 5.6 Singular Integrals 305 5.7 Numerical Differentiation 315 ; Discussion of the Literature 320 i' Problems 323 SIX NUMERICAL METHODS FOR ORDINARY DIFFERENTIAL EQUATIONS 333 6.1 Existence, Uniqueness, and Stability Theory 335 6.2 Euler's Method 341 6.3 Multistep Methods 357 6.4 The Midpoint Method 361 6.5 The Trapezoidal Method 366 .............. ! 6.6 A Low-Order Predictor-Corrector Algorithm 373 ' CONTENTS XV 6.7 Derivation of Higher Order Multistep Methods 381 6.8 Convergence and Stability Theory for Multistep Methods 394 6.9 Stiff Differential Equations and the Method of Lines 409 6.10 Single-Step and Runge-Kutta Methods 418 6.11 Boundary Value Problems 433 Discussion of the Literature 444 Problems 450 SEVEN LINEAR ALGEBRA 463 7.1 Vector Spaces, Matrices, and Linear Systems 463 7.2 Eigenvalues and Canonical Forms for Matrices 471 7.3 Vector and Matrix Norms 480 7.4 Convergence and Perturbation Theorems 490 Discussion of the Literature 495 Problems 496 EIGHT NUMERICAL SOLUTION OF SYSTEMS OF LINEAR EQUATIONS 507 8.1 Gaussian Elimination 508 8.2 Pivoting and Scaling in Gaussian Elimination 515 8.3 Variants of Gaussian Elimination 522 8.4 Error Analysis 529 8.5 The Residual Correction Method 540 8.6 Iteration Methods 544 8.7 Error Prediction and Acceleration 552 8.8 The Numerical Solution of Poisson's Equation 557 8.9 The Conjugate Gradient Method 562 Discussion of the Literature 569 Problems 574 NINE THE MATRIX EIGENVALUE PROBLEM 587 9.1 · Eigenvalue Location, Error, and Stability Results 588 9.2 The Power Method 602 9.3 Orthogonal Transformations Using Householder Matrices 609 9.4 The Eigenvalues of a Symmetric Tridiagonal Matrix 619 9.5 The QR Method 623 9.6 The Calculation of Eigenvectors and Inverse Iteration 628 9.7 Least Squares Solution of Linear Systems 633 Discussion of the Literature 645 Problems 648 xvi CONTENTS APPENDIX: MATHEMATICAL SOFTWARE 661 ANSWERS TO SELECTED EXERCISES 667 INDEX 683 ONE ERROR: ITS SOURCES, PROPAGATION, AND ANALYSIS The subject of numerical analysis provides computational methods for the study and solution of mathematical problems. In this text we study numerical methods for the solution of the most common mathematical problems and we analyze the errors present in these methods. Because almost all computation is now done on digital computers, we also discuss the implications of this in the implementation of numerical methods. The study of error is a central concern of numerical analysis. Most numerical methods give answers that are only approximations to the desired true solution, -and-itcisimportant to understand-and to be able, if possible, to estimate or bound the resulting error. This chapter examines the various kinds of errors that may occur in a problem. The representation of numbers in computers is examined, along with the error in computer arithmetic. General results on the propagation of errors in calculations are given, with a detailed look at error in summation procedures. Finally, the concepts of stability and conditioning of problems and numerical methods are introduced and illustrated. The first section contains mathematical preliminaries needed for the work of later chapters. 1.1 Mathematical Preliminaries This section contains a review of results from calculus, which will be used in this text. We first give some mean value theorems, and then we present and discuss Taylor's theorem, for functions of one and two variables. The section concludes with some notation that will be used in later chapters. Theorem 1.1 (Intermediate Value) Let f(x) be continuous on the finite interval a ~ x ~ b, and define m = Infimumf(x), M = Supremumj(x) asxsh asxsh Then for any number K in the interval [ m, MJ, there is at least one point ~ in [a, b) for which !(0 = r 3