Transcription
Numerical Analysis
Numerical AnalysisL. Ridgway ScottPRINCETON UNIVERSITY PRESSPRINCETON AND OXFORD
Copyright c 2011 by Princeton University PressPublished by Princeton University Press, 41 William Street,Princeton, New Jersey 08540In the United Kingdom: Princeton University Press, 6 Oxford Street,Woodstock, Oxfordshire OX20 1TWpress.princeton.eduAll Rights ReservedLibrary of Congress Control Number: 2010943322ISBN: 978-0-691-14686-7British Library Cataloging-in-Publication Data is availableThe publisher would like to acknowledge the author of this volume for typesetting 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 98 76 54 32 1
DedicationTo the memory of Ed Conway1 who, along with his colleagues at TulaneUniversity, provided a stable, adaptive, and inspirational starting point formy career.1 Edward Daire Conway, III (1937–1985) was a student of Eberhard Friedrich FerdinandHopf at the University of Indiana. Hopf was a student of Erhard Schmidt and Issai Schur.
ContentsPrefacexiChapter 1. Numerical Algorithms1.11.21.31.41.51.61.7Finding rootsAnalyzing Heron’s algorithmWhere to startAn unstable algorithmGeneral roots: effects of floating-pointExercisesSolutionsChapter 2. Nonlinear Equations2.12.22.32.42.52.62.7Fixed-point iterationParticular methodsComplex rootsError propagationMore readingExercisesSolutionsChapter 3. Linear Systems3.13.23.33.43.53.63.7Gaussian eliminationFactorizationTriangular matricesPivotingMore readingExercisesSolutionsChapter 4. Direct Solvers4.14.24.34.44.54.6Direct factorizationCaution about factorizationBanded matricesMore 0353638424447475051515658606063
viiiCONTENTSChapter 5. Vector Spaces5.15.25.35.45.55.65.7Normed vector spacesProving the triangle inequalityRelations between normsInner-product spacesMore readingExercisesSolutionsChapter 6. torsSchur decompositionConvergent matricesPowers of matricesExercisesSolutions828489899295Chapter 7. Nonlinear Systems977.17.27.37.47.57.67.7Functional iteration for systemsNewton’s methodLimiting behavior of Newton’s methodMixing solversMore readingExercisesSolutionsChapter 8. Iterative Methods8.18.28.38.48.58.6Stationary iterative methodsGeneral splittingsNecessary conditions for convergenceMore readingExercisesSolutionsChapter 9. Conjugate Gradients9.19.29.39.49.59.69.7Minimization methodsConjugate Gradient iterationOptimal approximation of CGComparing iterative solversMore 6117123128128131133133137141147147148149
CONTENTSChapter 10. Polynomial Interpolation10.110.210.310.410.510.6Local approximation: Taylor’s theoremDistributed approximation: interpolationNorms in infinite-dimensional spacesMore readingExercisesSolutionsChapter 11. Chebyshev and Hermite 52157160160163167Error term ωChebyshev basis functionsLebesgue functionGeneralized interpolationMore ter 12. Approximation Theory18312.112.212.312.412.512.612.712.8Best approximation by polynomialsWeierstrass and BernsteinLeast squaresPiecewise polynomial approximationAdaptive approximationMore readingExercisesSolutionsChapter 13. Numerical y quadraturePeano kernel theoremGregorie-Euler-Maclaurin formulasOther quadrature rulesMore readingExercisesSolutionsChapter 14. Eigenvalue Problems14.114.214.314.414.514.614.714.8Eigenvalue examplesGershgorin’s theoremSolving separatelyHow not to eigenReduction to Hessenberg formMore 03203209212219221221224225225227232233234237238240
xCONTENTSChapter 15. Eigenvalue Algorithms15.115.215.315.415.515.615.7Power methodInverse iterationSingular value decompositionComparing factorizationsMore readingExercisesSolutionsChapter 16. Ordinary Differential Equations16.116.216.316.416.516.616.7Basic theory of ODEsExistence and uniqueness of solutionsBasic discretization methodsConvergence of discretization methodsMore readingExercisesSolutionsChapter 17. Higher-order ODE Discretization Methods17.117.217.317.417.517.6Higher-order discretizationConvergence conditionsBackward differentiation formulasMore readingExercisesSolutionsChapter 18. Floating Point18.118.218.318.418.5Floating-point arithmeticErrors in solving systemsMore 301305305308Chapter 19. Notation309Bibliography311Index323
Preface“.by faith and faith alone, embrace, believing where wecannot prove,” from In Memoriam by Alfred Lord Tennyson, a memorial to Arthur Hallum.Numerical analysis provides the foundations for a major paradigm shiftin what we understand as an acceptable “answer” to a scientificor techni cal question. In classical calculus we look for answers like sin x, that is,answers composed of combinations of names of functions that are familiar.This 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. We will see that far more complex functions, defined,e.g., only implicitly, can be evaluated just as easily and with the same technology. This makes the search for answers in classical calculus obsolete inmany cases. This new paradigm comes at a cost: developing stable, convergent algorithms to evaluate functions is often more difficult than moreclassical analysis of these functions. For this reason, the subject is still being actively developed. However, it is possible to present many importantideas at an elementary level, as is done here.Today there are many good books on numerical analysis at the graduatelevel, including general texts [47, 134] as well as more specialized texts. Wereference many of the latter at the ends of chapters where we suggest further 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 mathematical subject. We hope to provide an alternative.Several books written some decades ago addressed specifically a mathematical audience, e.g., [80, 84, 86]. These books remain valuable references,but the subject has changed substantially in the meantime.We have intentionally introduced concepts from various parts of mathematics as they arise naturally. In this sense, this book is an invitation 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 that is accessible toadvanced undergraduates, an introduction to many of the advanced conceptsof modern analysis.We have assumed that the general style of a course using this book willbe to prove theorems. Indeed, we have attempted to facilitate a “Moore2method” style of learning by providing a sequence of steps to be 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 list of topics coveredas short as possible. Completeness is left to graduate level courses using thetexts we mention at the end of many chapters.The prerequisites for the course are not demanding. We assume a sophisticated understanding of real numbers, including compactness arguments.We also assume some familiarity with concepts of linear algebra, but we include derivations of most results as a review. We have attempted to makethe book self-contained. Solutions of many of the exercises are provided.About the name: the term “numerical” analysis is fairly recent. A classic 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 names.There are many areas of analysis in addition to numerical, including complex, convex, functional, harmonic, and real. Some areas, which might havebeen given such a name, have their own names (such as probability, insteadof random analysis). There is not a line of demarcation between the different areas of analysis. For example, much of harmonic analysis might becharacterized as real or complex analysis, with functional analysis playing arole in modern theories. The same is true of numerical analysis, and it canbe viewed in part as providing motivation for further study in all areas ofanalysis.The subject of numerical analysis has ancient roots, and it has had periodsof intense development followed by long periods of consolidation. In manycases, the new developments have coincided with the introduction of newforms of computing machines. For example, many of the basic theoremsabout computing solutions of ordinary differential equations were provedsoon after desktop adding machines became common at the turn of the 20thcentury. The emergence of the digital computer in the mid-20th centuryspurred interest in solving partial differential equations and large systems oflinear equations, as well as many other topics. The advent of parallel com2 RobertLee Moore (1882–1974) was born in Dallas, Texas, and did undergraduatework at the University of Texas in Austin where he took courses from L. E. Dickson.He got his Ph.D. in 1905 at the University of Chicago, studying with E. H. Moore andOswald Veblen, and eventually returned to Austin where he continued to teach until his87th year.
PREFACExiiiputers similarly stimulated research on new classes of algorithms. However,many fundamental questions remain open, and the subject is an active areaof research today.All of analysis is about evaluating limits. In this sense, it is about infiniteobjects, unlike, say, some parts of algebra or discrete mathematics. Often akey step is to provide uniform bounds on infinite objects, such as operatorson vector spaces. In numerical analysis, the infinite objects are often setsof algorithms which are themselves finite in every instance. The objective isoften to show that the algorithms are well-behaved uniformly and provide,in some limit, predictable results.In numerical analysis there is sometimes a cultural divide between coursesthat emphasize theory and ones that emphasize computation. Ideally, bothshould be intertwined, as numerical analysis could well be called computational analysis because it is the analysis of computational algorithms involving real numbers. We present many computational algorithms and encouragecomputational exploration. However, we do not address the subject of software development (a.k.a., programming). Strictly speaking, programming isnot required to appreciate the material in the book. However, we encouragemathematics students to develop some experience in this direction, as writing a computer program is quite similar to proving a theorem. Computersystems are quite adept at finding flaws in one’s reasoning, and the organization required to make software readable provides a useful model to followin making complex mathematical arguments understandable to others.There are several important groups this text can serve. It is very commontoday for people in many fields to study mathematics through the beginningof real analysis, as might be characterized by the extremely popular “littleRudin” book [141]. Our book is intended to be at a comparable level ofdifficulty with little Rudin and can provide valuable reinforcement of theideas and techniques covered there by applying them in a new domain. Inthis way, it is easily accessible to advanced undergraduates. It provides anoption to study more analysis without raising the level of difficulty as occursin a graduate course on measure theory.People who go on to graduate work with a substantial computationalcomponent often need to progress further in analysis, including a study ofmeasure theory and the Lebesgue integral. This is often done in a course atthe “big Rudin” [142] level. Although the direct progression from little tobig Rudin is a natural one, this book provides a way to interpolate betweenthese levels while at the same time introducing ideas not found in [141] or[142] (or comparable texts [108, 121]). Thus the book is also appropriate asa course for graduate students interested in computational mathematics butwith a background in analysis only at the level of [141].We have included quotes at the beginning of each chapter and frequentfootnotes giving historical information. These are intended to be entertaining and perhaps provocative, but no attempt has been made to be historically complete. However, we give references to several works on the historyof mathematics that we recommend for a more complete picture. We indi-
xivPREFACEcate several connections among various mathematicians to give a sense of thepersonal interactions of the era. We use the terms “student” and “advisor”to describe general mentoring relationships which were sometimes differentfrom what the terms might connot
“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.
