WIXLIB

iiixinterval2008/11/18page xiPrefacemethod, the interval Newton method can be used in an algorithm that is mathematicallyguaranteed to find all roots within a given starting interval.Interval analysis permits us to compute interval enclosures for the exact values ofintegrals. Interval methods can bound the solutions of linear systems with inexact data.There are rigorous interval branch-and-bound methods for global optimization, constraintsatisfaction, and parameter estimation problems.The book opens with a brief chapter intended to get the reader into a proper mindsetfor learning interval analysis. Hence its main purpose is to provide a bit of motivation andperspective. Chapter 2 introduces the interval number system and defines the set operations(intersection and union) and arithmetic operations (addition, subtraction, multiplication,and division) needed to work within this system.The first applications of interval arithmetic appear in Chapter 3. Here we introduceoutward rounding and demonstrate how interval computation can automatically handlethe propagation of uncertainties all the way through a lengthy numerical calculation. Wealso introduce INTLAB, a powerful and flexible MATLAB toolbox capable of performinginterval calculations.In Chapter 4, some further properties of interval arithmetic are covered. Here thereader becomes aware that not all the familiar algebraic properties of real arithmetic carryover to interval arithmetic. Interval functions—residing at the heart of interval analysis—areintroduced in Chapter 5. Chapter 6 deals with sequences of intervals and interval functions,material needed as preparation for the iterative methods to be treated in Chapter 7 (onmatrices) and Chapter 8 (on root finding). Chapter 9 is devoted to integration of intervalfunctions, with an introduction to automatic differentiation, an important tool in its ownright. Chapter 10 treats integral and differential equations. Finally, Chapter 11 introducesan array of applications including several of those (optimization, etc.) mentioned above.Various appendices serve to round out the book. Appendix A offers a brief reviewof set and function terminology that may prove useful for students of engineering and thesciences. Appendix B, the quick-reference Formulary, provides a convenient handbookstyle listing of major definitions, formulas, and results covered in the text. In Appendix Cwe include hints and answers for most of the exercises that appear throughout the book.Appendix D discusses Internet resources (such as additional reading material and softwarepackages—most of them freely available for download) relevant to interval computation.Finally, Appendix E offers a list of INTLAB commands.Research, development, and application of interval methods is now taking place inmany countries around the world, especially in Germany, but also in Austria, Belgium,Brazil, Bulgaria, Canada, China, Denmark, Finland, France, Hungary, India, Japan, Mexico,Norway, Poland, Spain, Sweden, Russia, the UK, and the USA. There are published worksin many languages. However, our references are largely to those in English and German,with which the authors are most familiar. We cannot provide a comprehensive bibliographyof publications, but we have attempted to include at least a sampling of works in a broadrange of topics.The assumed background for the first 10 chapters is basic calculus plus some familiarity with the elements of scientific computing. The application topics of Chapter 11 mayrequire a bit more background, but an attempt has been made to keep much of the presentationaccessible to the nonspecialist, including senior undergraduates or beginning graduate students in engineering, the sciences (physical, biological, economic, etc.), and mathematics.iiii

iiiPrefaceinterval2008/11/18page xiixiOf the various interval-based software packages that are available, we chose INTLABfor several reasons. It is fully integrated into the interactive, programmable, and highlypopular MATLAB system. It is carefully written, with all basic interval computationsrepresented. Finally, both MATLAB and INTLAB code can be written in a fashion that isclear and easy to debug.We wish to cordially thank George Corliss, Andreas Frommer, and Siegfried Rump,as well as the anonymous reviewers, for their many constructive comments. We oweSiegfried Rump additional thanks for developing INTLAB and granting us permission touse it in this book. Edward Rothwell and Mark Thompson provided useful feedback onthe manuscript. We are deeply grateful to the staff of SIAM, including Senior AcquisitionsEditor Elizabeth Greenspan, Developmental Editor Sara J. Murphy, Managing Editor KellyThomas, Production Manager Donna Witzleben, Production Editor Ann Manning Allen,Copy Editor Susan Fleshman, and Graphic Designer Lois Sellers.The book is dedicated to our wives: Adena, Ruth, and Beth.Ramon E. MooreR. Baker KearfottMichael J. Cloudiiii

iinterval2008/11/18page xiiiiiiiii

iiiinterval2008/11/18page 1iChapter 1Introduction1.1Enclosing a SolutionIn elementary mathematics, a problem is “solved” when we write down an exact solution.We solve the equationx2 x 6 0by factoring and obtaining the roots x1 3 and x2 2. Few high school algebrateachers would be satisfied with an answer of the formOne root lies between 4 and 2, while the other lies between 1 and 3.We need not look far, however, to find even elementary problems where answers of preciselythis form are appropriate. The quadratic equationx2 2 0 has the positive solution 2. We understand that there is more to this symbol than meetsthe eye; the number it designates cannot be represented exactly with a finite number ofdigits. Indeed, the notion of irrational number entails some process of approximation fromabove and below. Archimedes (287–212 BCE) was able to bracket π by taking a circle andconsidering inscribed and circumscribed polygons. Increasing the numbers of polygonalsides, he obtained both an increasing sequence of lower bounds and a decreasing sequenceof upper bounds for this irrational number.Exercise 1.1. Carry out the details of Archimedes’ method for a square and a hexagon.(Note: Hints and answers to many of the exercises can be found in Appendix C.)Aside from irrational numbers, many situations involve quantities that are not exactlyrepresentable. In machine computation, representable lower and upper bounds are requiredto describe a solution rigorously. This statement deserves much elaboration; we shall returnto it later on.The need to enclose a number also arises in the physical sciences. Since an experimentally measured quantity will be known with only limited accuracy, any calculation1iiii

iii2interval2008/11/18page 2iChapter 1. Introductioninvolving this quantity must begin with inexact initial data. Newton’s lawF ma(1.1)permits us to solve for the acceleration a of a body exactly only when the force F and massm are known exactly (i.e., to unlimited decimal precision). If the latter quantities are knownonly to lie in certain ranges, say,F0 F F F0 Fandm0 m m m0 m,then a can only be bounded above and below:al a au .(1.2)For a relation as simple as (1.1), it is easy to determine how al and au depend on F0 , m0 , F , and m.Exercise 1.2. Carry out this derivation to find explicit bounds on a.For more complicated relations, however, ordinary algebra can be cumbersome. Thetechniques of interval analysis will render the computation of bounds routine. In fact,interval computation was designed for machine implementation! Examples involving handcomputation will appear throughout the book, but the reader should bear in mind that thisis only for learning purposes.In interval analysis, we phrase inequality statements in terms of closed intervals onthe real line. We think of an interval as a set of numbers, which we commonly1 representas an ordered pair. Instead of (1.2), for instance, we writea [al , au ] .(1.3)We call the interval [al , au ] an enclosure of a. The use of simple set notation will repay usmany times over in the book; the reader can find a review and summary of this notation inAppendix A. Henceforth, we will prefer notation of the form (1.3) to that of (1.2). However,it is important to keep in mind that placing a number within a closed interval is the same asbounding it above and below.Let us return to our discussion of scientific calculations. We noted above that measurement error can give rise to uncertainty in “initial data” such as F and m in (1.1). Thegeneral sense is that we would like to know F and m exactly so that we can get a exactly.In other circumstances, however, we might wish to treat F and m as parameters and intentionally vary them to see how a varies. Mathematically, this problem is still treated as inExercise 1.2, but the shift in viewpoint is evident.We have one more comment before we end this section. The act of merely enclosinga solution might seem rather weak. After all, it fails to yield the solution itself. While thisis true, the degree of satisfaction involved in enclosing a solution can depend strongly onthe tightness of the enclosure obtained. The hypothetical math teacher of the first paragraphmight be much happier with answers of the formx1 [ 3.001, 2.999],1 Otherx2 [1.999, 2.001].representations are discussed in Chapter 3.iiii

iii1.2. Bounding Roundoff Errorinterval2008/11/18page 3i3In fact, it is worth noting that if we obtain something likex [0.66666, 0.66667],then we do know x to four places. Moreover, there are times when we can and should besatisfied with rather loose bounds on a solution. It might be better to know that y [59, 62]rigorously than to have an “answer” of the form y 60 with no idea of how much errormight be present. If we can compute an interval [a, b] containing an exact solution x to someproblem, then we can take the midpoint m (a b)/2 of the interval as an approximationto x and have x m w/2, where w b a is the width of the interval. Hence weobtain both an approximate solution and error bounds on the approximation.Exercise 1.3. A computation shows that the mass M of a certain body lies in theinterval [3.7, 3.8] kg. State an approximation for M along with error bounds on thisapproximation.1.2Bounding Roundoff ErrorThe effects of finite number representation are familiar to anyone who has done scientificcomputing. Rounding error, if it manages to accumulate sufficiently, can destroy a numericalsolution.The folklore surrounding this subject can be misleading. Here we will provide oneexample of a computation—involving only a small number of arithmetic operations—thatalready foils a scheme often thought to be adequate for estimating roundoff error. The ideais to perform the same computation twice, using higher-precision arithmetic the secondtime. The number of figures to which the two results agree is supposed to be the number ofcorrect figures in the first result.Example 1.1. Consider the recursion formulaxn 1 xn2(n 0, 1, 2, . . .),(1.4)and suppose that x0 1 10 21 . We seek x75 . Performing the computation with 10-placearithmetic, we obtain the approximate valuesx0 1,x1 1,.,x75 1.Using 20-place arithmetic, we obtain the same sequence of values; hence the two values ofx75 agree to all 10 places carried in the first computation. However, the exact value satisfiesx75 10 10 .Exercise 1.4. Verify this.Example 1.1 illustrates that repeating a calculation with higher-precision arithmeticand obtaining the same answer does not show that the answer is correct. The reasonwas simply that x1 is not representable exactly in either 10- or 20-place arithmetic. Thenext example, first given by Rump in [220], shows that the problem can occur in a moresubtle way.iiii

iii4interval2008/11/18page 4iChapter 1. IntroductionExample 1.2. Consider evaluation of f defined byf 333.75 b6 a 2 (11 a 2 b2 b6 121 b4 2) 5.5 b8 a/(2b)with a 77617.0 and b 33096.0.Computing powers by successive multiplications on an IBM 370 system using single, double, and extended precision (approximately 7, 16, and 33 decimal digits, respectively),Rump obtained the following results:single precisionfdouble precisionfextended precision f 1.17260361 . . . 1.17260394005317847 . . . 1.17260394005317863185 . . . .The underlining indicates agreement in digits from one computation to the next. We mightbe tempted to conclude that f is close to 1.172603. However, the exact result is f 0.827396 . . . .Exercise 1.5. How many digits of precision are required to find the value of f in Example 1.2 correct to six decimal digits? Can we know when we have these six digits correct?Preliminary hint: We will discuss INTLAB in Chapter 3, after explaining machine implementations of interval arithmetic. Example 3.6 gives an INTLAB program that can computerigorous bounds for f to a specified accuracy.These examples make it clear that repeating a calculation with more precision doesnot necessarily provide a basis for determining the accuracy of the results. In many cases2it is true that by carrying enough places a result of arbitrarily high accuracy can be found inany computation involving only a finite number of real arithmetic operations beginning withexactly known real numbers. However, it is often prohibitively difficult to tell in advance ofa computation how many places must be carried to guarantee results of required accuracy.If instead of simply computing a numerical approximation using limited-precisionarithmetic and then worrying later about the accuracy of the results, we proceed in the spiritof the method of Archimedes to construct intervals known in advance to contain the desiredexact result, then our main concerns will be the narrowness of the intervals we obtain andthe amount of computation required to get them. The methods treated in this book willyield for Example 1.1, for instance, an interval close to [0, 1] using only 10-place intervalarithmetic. However, they will yield an interval of arbitrarily small width containing theexact result by carrying enough places. In this case, obviously, more than 20 places areneeded to avoid getting 1 for the value of x0 .We have chosen just two examples for illustration. There are many others in whichthe results of single, double, and quadruple precision arithmetic all agree to the number ofplaces carried but are all wrong—even in the first digit.2 There are cases in which no amount of precision can rectify a problem, such as when a final result depends ontesting exact equality between the result of a floating point computation and another floating point number. Thecode “IF sin(2 · arccos(0)) 0 THEN f 0 ELSE f 1” should return f 0, but it may always returnf 1 regardless of the precision used.iiii

iii1.3. Number Pair Extensions1.3interval2008/11/18page 5i5Number Pair ExtensionsFrom time to time, mathematicians have found it necessary to produce a new number systemby extending an old one. Extensions of number systems involving ordered pairs of numbersfrom a given system are commonplace. The rational numbers are essentially ordered pairsof integers m/n. The complex numbers are ordered pairs of real numbers (x, y). In eachcase, arithmetic operations are defined with rules for computing the components of a pairresulting from an arithmetic operation on a pair of pairs. For example, we use the rule(x1 , y1 ) (x2 , y2 ) (x1 x2 , y1 y2 )to add complex numbers. Pairs of special form are equivalent to numbers of the originaltype: for example, each complex number of the form (x, 0) is equivalent to a real number x.In Chapter 2 we will consider another such extension of the real numbers—this time,to the system of closed intervals.iiii

iinterval2008/11/18page 6iiiiiii

iiiinterval2008/11/18page 7iChapter 2The Interval NumberSystem2.1Basic Terms and ConceptsRecall that the closed interval denoted by [a, b] is the set of real numbers given by[a, b] {x R : a x b}.Although various other types of intervals (open, half-open) appear throughout mathematics,our work will center primarily on closed intervals. In this book, the term interval will meanclosed interval.Endpoint Notation, Interval EqualityWe will adopt the convention of denoting intervals and their endpoints by capital letters.The left and right endpoints of an interval X will be denoted by X and X, respectively.Thus, (2.1)X X,X .Two intervals X and Y are said to be equal if they are the same sets. Operationally, thishappens if their corresponding endpoints are equal:X YifX Y and X Y .(2.2)Degenerate IntervalsWe say that X is degenerate if X X. Such an interval contains a single real number x.By convention, we agree to identify a degenerate interval [x, x] with the real number x. Inthis sense, we may write such equations as0 [0, 0].(2.3)7iiii

iii8interval2008/11/18page 8iChapter 2. The Interval Number SystemIntersection, Union, and Interval HullThe intersection of two intervals X and Y is empty if either Y X or X Y . In this casewe let denote the empty set and writeX Y ,indicating that X and Y have no points in common. Otherwise, we may define the intersection X Y as the intervalX Y {z : z X and z Y } max{X, Y } , min{X, Y } .(2.4)In this latter case, the union of X and Y is also an interval:X Y {z : z X or z Y } min{X, Y } , max{X, Y } .(2.5)In general, the union of two intervals is not an interval. However, the interval hull of twointervals, defined by (2.6)X Y min{X, Y } , max{X, Y } ,is always an interval and can be used in interval computations. We haveX Y X Y(2.7)for any two intervals X and Y .Example 2.1. If X [ 1, 0] and Y [1, 2], then X Y [ 1, 2]. Although X Yis a disconnected set that cannot be expressed as an interval, relation (2.7) still holds.Information is lost when we replace X Y with X Y , but X Y is easier to work with,and the lost information is sometimes not critical.On occasion we wish to save both parts of an interval that gets split into two disjointintervals. This occurs with the use of the interval Newton method discussed in Chapter 8.Importance of IntersectionIntersection plays a key role in interval analysis. If we have two intervals containing aresult of interest—regardless of how they were obtained—then the intersection, which maybe narrower, also contains the result.Example 2.2. Suppose two people make independent measurements of the same physicalquantity q. One finds that q 10.3 with a measurement error less than 0.2. The otherfinds that q 10.4 with an error less than 0.2. We can represent these measurements as theintervals X [10.1, 10.5] and Y [10.2, 10.6], respectively. Since q lies in both, it alsolies in X Y [10.2, 10.5]. An empty intersection wo

Introduction to - nsc.ru . interval