Numerical Analysis

1 Numerical AnalysisNumerical AnalysisL. Ridgway ScottPRINCETON UNIVERSITY PRESSPRINCETON AND OXFORDC opyrightc 2011 by Princeton University PressPublished by Princeton University Press, 41 William Street,Princeton, New Jersey 08540In the United Kingdom: Princeton University Press, 6 OxfordStreet,Woodstock, Oxfordshire OX20 Rights ReservedLibrary of Congress Control Number: 2010943322 ISBN: 978-0-691-14686-7 British Library Cataloging-in-Publication Data is availableThe publisher would like to acknowledge the author of this volume for type-setting this book using LATEX and Dr. Janet Englund and Peter Scott forproviding the cover photographPrinted on acid-free paper Printed in the United States of America10 9 8 7 6 5 4 3 2 1 DedicationTo the memory of Ed Conway1who, along with his colleagues at TulaneUniversity, provided a stable, adaptive, and inspirational starting point formy Daire Conway, III (1937 1985) was a student of Eberhard Friedrich FerdinandHopf at the University of Indiana.

2 Hopf was a student of Erhard Schmidt and Issai 1. Numerical Finding Analyzing Heron s Where to An unstable General roots: effects of Solutions13 Chapter 2. Nonlinear Fixed-point Particular Complex Error More Solutions30 Chapter 3. Linear Gaussian Triangular More Solutions50 Chapter 4. Direct Direct Caution about Banded More Solutions63viiiCONTENTSC hapter 5. Vector Normed vector Proving the triangle Relations between Inner-product More Solutions79 Chapter 6. Schur Convergent Powers of Solutions95 Chapter 7. Nonlinear Functional iteration for Newton s Limiting behavior of Newton s Mixing More Solutions114 Chapter 8.

3 Iterative Stationary iterative General Necessary conditions for More Solutions131 Chapter 9. Conjugate Minimization Conjugate Gradient Optimal approximation of Comparing iterative More Solutions149 CONTENTSixChapter 10. Polynomial Local approximation: Taylor s Distributed approximation: Norms in infinite-dimensional More Solutions163 Chapter 11. Chebyshev and Hermite Error term Chebyshev basis Lebesgue Generalized More Solutions180 Chapter 12. Approximation Best approximation by Weierstrass and Least Piecewise polynomial Adaptive More Solutions199 Chapter 13.

4 Numerical Interpolatory Peano kernel Gregorie-Euler-Maclaurin Other quadrature More Solutions224 Chapter 14. Eigenvalue Eigenvalue Gershgorin s Solving How not to Reduction to Hessenberg More Solutions240xCONTENTSC hapter 15. Eigenvalue Power Inverse Singular value Comparing More Solutions256 Chapter 16. Ordinary Differential Basic theory of Existence and uniqueness of Basic discretization Convergence of discretization More Solutions271 Chapter 17. Higher-order ODE Discretization Higher-order Convergence Backward differentiation More Solutions291 Chapter 18. Floating Floating-point Errors in solving More Solutions308 Chapter 19.

5 Notation309 Bibliography311 Index323 Preface ..by faith and faith alone, embrace, believing where wecannot prove, fromIn Memoriamby Alfred Lord Ten-nyson, a memorial to Arthur Analysis provides the foundations for a major paradigm shiftin what we understand as an acceptable answer to a scientific or techni-cal question. In classical calculus we look for answers like sinx, that is,answers composed of combinations of names of functions thatare presumes we can evaluate such an expression as needed, and indeednumerical Analysis has enabled the development of pocket calculators andcomputer software to make this routine. But Numerical Analysis has donemuch more than this.

6 We will see that far more complex functions, defined, , only implicitly, can be evaluated just as easily and with the same tech-nology. This makes the search for answers in classical calculus obsolete inmany cases. This new paradigm comes at a cost: developing stable, con-vergent algorithms to evaluate functions is often more difficult than moreclassical Analysis of these functions. For this reason, thesubject is still be-ing actively developed. However, it is possible to present many importantideas at an elementary level, as is done there are many good books on Numerical Analysis at the graduatelevel, including general texts [47, 134] as well as more specialized texts.

7 Wereference many of the latter at the ends of chapters where we suggest fur-ther reading in particular areas. At a more introductory level, the recenttrend has been to provide texts accessible to a wide audience. The bookby Burden and Faires [28] has been extremely successful. It is a tribute tothe importance of the field of Numerical Analysis that such books and others[131] are so popular. However, such books intentionally diminish the roleof advanced mathematics in the subject of Numerical Analysis . As a result, Numerical Analysis is frequently presented as an elementary subject. As acorollary, most students miss exposure to Numerical Analysis as a mathemat-ical subject.

8 We hope to provide an books written some decades ago addressed specifically a mathe-matical audience, , [80, 84, 86]. These books remain valuable references,but the subject has changed substantially in the have intentionally introduced concepts from various parts of mathe-matics as they arise naturally. In this sense, this book is aninvitation tostudy more deeply advanced topics in mathematics. It may require a shortdetour to understand completely what is being said regarding operator the-xiiPREFACEory in infinite-dimensional vector spaces or regarding algebraic concepts liketensors and flags. Numerical Analysis provides, in a way thatis accessible toadvanced undergraduates, an introduction to many of the advanced conceptsof modern have assumed that the general style of a course using this book willbe to prove theorems.

9 Indeed, we have attempted to facilitate a Moore2method style of learning by providing a sequence of steps tobe verified asexercises. This has also guided the set of topics to some degree. We havetried to hit the interesting points, and we have kept the listof topics coveredas short as possible. Completeness is left to graduate levelcourses using thetexts we mention at the end of many prerequisites for the course are not demanding. We assume a sophis-ticated understanding of real numbers, including compactness also assume some familiarity with concepts of linear algebra, but we in-clude derivations of most results as a review. We have attempted to makethe book self-contained.

10 Solutions of many of the exercisesare the name: the term Numerical Analysis is fairly recent. A clas-sic book [170] on the topic changed names between editions, adopting the Numerical Analysis title in a later edition [171]. The origins of the part ofmathematics we now call Analysis were all Numerical , so for millennia thename Numerical Analysis would have been redundant. But Analysis laterdeveloped conceptual (non- Numerical ) paradigms, and it became useful tospecify the different areas by are many areas of Analysis in addition to Numerical , including com-plex, convex, functional, harmonic, and real. Some areas, which might havebeen given such a name, have their own names (such as probability, insteadof random Analysis ).