Numerical Analysis - University Of Chicago
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 connote today. Although this may not be historically accurate in some cases, it would be tedious to use more precise termsto describe the relationships in each case in the various periods. We haveused the MacTutor History of Mathematics archive extensively as an initialsource of information but have also endeavored to refer to archival literaturewhenever possible.In practice, numerical computation remains as much an art as it is a science. We focus on the part of the subject that is a science. A continuingchallenge of current research is to transform numerical art into numericalanalysis, as well as extending the power and reach of the art of numericalcomputation. Recent decades have witnessed a dramatic improvement in ourunderstanding of many topics in numerical computation, and there is reasonto expect that this trend will continue. Techniques that are supported onlyby heuristics tend to lose favor over time to ones that are understood rigorously. One of the great joys of the subject is when a heuristic idea succumbsto a rigorous analysis that reveals its secrets and extends its influence. It ishoped that this book will attract some new participants in this process.AcknowledgmentsI have gotten suggestions from many people regarding topics in this book,and my memory is not to be trusted to remember all of them. However,above all, Todd Dupont provided the most input regarding the book, including draft material, suggestions for additional topics, exercises, and overallconceptual advice. He regularly attended the fall 2009 class at the University of Chicago in which the book was given a trial run. I also thank all thestudents from that class for their influence on the final version.Randy Bank, Carl de Boor and Nick Trefethen suggested novel approachesto particular topics. Although I cannot claim that I did exactly what theyintended, their suggestions did influence what was presented in a substantialway.
Numerical Analysis
Chapter OneNumerical AlgorithmsThe word “algorithm” derives from the name of the Persian mathematician (Abu Ja’far Muhammad ibn Musa) AlKhwarizmi who lived from about 790 CE to about 840 CE.He wrote a book, Hisab al-jabr w’al-muqabala, that alsonamed the subject “algebra.”Numerical analysis is the subject which studies algorithms for computing expressions defined with real numbers. The square-root y is an example ofsuch an expression; we evaluate this today on a calculator or in a computerprogram as if it were as simple as y 2 . It is numerical analysis that hasmade this possible, and we will study how this is done. But in doing so,we will see that the same approach applies broadly to include functions thatcannot be named, and it even changes the nature of fundamental questionsin mathematics, such as the impossibility of finding expressions for roots oforder higher than 4.There are two different phases to address in numerical analysis: the development of algorithms and the analysis of algorithms.These are in principle independent activities, but in reality the developmentof an algorithm is often guided by the analysis of the algorithm, or of asimpler algorithm that computes the same thing or something similar.There are three characteristics of algorithms using real numbers that arein conflict to some extent: the accuracy (or consistency) of the algorithm, the stability of the algorithm, and the effects of finite-precision arithmetic (a.k.a. round-off error).The first of these just means that the algorithm approximates the desiredquantity to any required accuracy under suitable restrictions. The secondmeans that the behavior of the algorithm is continuous with respect to theparameters of the algorithm. The third topic is still not well understoodat the most basic level, in the sense that there is not a well-establishedmathematical model for finite-precision arithmetic. Instead, we are forcedto use crude upper bounds for the behavior of finite-precision arithmetic
2CHAPTER 1that often lead to overly pessimistic predictions about its effects in actualcomputations.We will see that in trying to improve the accuracy or efficiency of a stable algorithm, one is often led to consider algorithms that turn out to beunstable and therefore of minimal (if any) value. These various aspects ofnumerical analysis are often intertwined, as ultimately we want an algorithmthat we can analyze rigorously to ensure it is effective when using computerarithmetic.The efficiency of an algorithm is a more complicated concept but is oftenthe bottom line in choosing one algorithm over another. It can be relatedto all of the above characteristics, as well as to the complexity of the algorithm in terms of computational work or memory references required in itsimplementation.Another central theme in numerical analysis is adaptivity. This meansthat the computational algorithm adapts itself to the data of the problembeing solved as a way to improve efficiency and/or stability. Some adaptive algorithms are quite remarkable in their ability to elicit informationautomatically about a problem that is required for more efficient solution.We begin with a problem from antiquity to illustrate each of these components of numerical analysis in an elementary context. We will not alwaysdisentangle the different issues, but we hope that the differing componentswill be evident.1.1 FINDING ROOTSPeople have been computing roots for millennia. Evidence exists [64] thatthe Babylonians, who used base-60 arithmetic, were able to approximate 511024 3(1.1)2 1 60 602601nearly 4000 years ago. By the time of Heron a method to compute squareroots was established [26] that we recognize now as the Newton-RaphsonSimpson method (see section 2.2.1) and takes the form of a repeated iterationx 12 (x y/x),(1.2)where the backwards arrow means assignment in algorithms. That is,once the computation of the expression on the right-hand side of the arrowhas been completed, a new value is assigned to the variable x. Once thata
“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.
CHICAGO BUILDING CODE. Title 14B of the Municipal Code of Chicago. CHICAGO CONSTRUCTION CODES. As defined in Chapter 14A-2. CHICAGO ELECTRICAL CODE. Title 14E of the Municipal Code of Chicago. CHICAGO ENERGY CONSERVATION CODE. Title 14N of the Municipal Code of Chicago. CHICAGO FIRE PREVENTION CODE. Title 14F of the Municipal Code of Chicago.
green, Chicago-style/verde de estilo Chicago 11.04.07 Center for Urban Ecology, University of Illinois@Chicago . 0 200000 400000 600000 800000 1000000 1200000 1400000 "Chicago-style" "New York style" "L A -style" infomal comparisons/ Chicago style "Chicago style" "New York style" "LA style"
How advances in neural recording affect data analysis Ian H Stevenson1 and Konrad P Kording1,2,3 1Department of Physical Medicine and Rehabilitation, Northwestern University and Rehabilitation Institute of Chicago, Chicago, Illinois, USA. 2Department of Physiology, Northwestern University, Chicago, Illinois, USA. 3Department of Applied Mathematics, Northwestern University, Chicago, Illinois, USA.
When You're Good To Mama Songs from Chicago All I Care About Songs from Chicago A Little Bit Of Good Songs from Chicago We Both Reached For The Gun Songs from Chicago Roxie Songs from Chicago My Own Best Friend Songs from Chicago Me And My Baby Songs from Chicago Mister Cellophane So
The Chicago City Council - Office of Financial Analysis review of the City of Chicago 2022 Budget Recommendation will primarily focus on how the City of Chicago "budget gap" was closed, and the Chicago Recovery Plan. On Monday, September 20, 2021, the City of Chicago rolled out its 2022 Budget Recommendation totaling 16.7 billion.
Timothy A. Lavery, Chicago Police Department Rachel M. Johnston, Chicago Police Department Dennis P. Rosenbaum, University of Illinois at Chicago March 23, 2011 This project was supported under award number 2006-JJ-CX-0023 to the Chicago Police Department and the University of Illinois-Chicago by the National Institute of Justice, Office of
the numerical solution of second-order optimization methods. Next step development of Numerical Multilinear Algebra for the statistical analysis of multi-way data, the numerical solution of partial di erential equations arising from tensor elds, the numerical solution of higher-order optimization methods.
Engineering Mathematics – I, Reena Garg, Khanna Book Publishing . AICTE Recommended Books for Undergraduate Degree Courses as per Model Curriculum 2018 AICTE Suggested Books in Engineering & Technology w.e.f. 2018-19 BSC103 – Mathematics – II 1. Advanced Engineering Mathematics, Chandrika Prasad & Reena Garg, Khanna Book Publishing 2. Higher Engineering Mathematics, Ramana B.V., Tata .
