Über die Autorin bzw. den Autor

Warwick Tucker is professor of mathematics and principal investigator for the Computer-Aided Proofs in Analysis (CAPA) Group at Uppsala University in Sweden. He has been honored with several awards, including the European Mathematical Society's Prize for Distinguished Contributions in Mathematics, the R. E. Moore Prize for Applications of Interval Analysis, and the Swedish Mathematical Society's Wallenberg Prize.

Von der hinteren Coverseite

"Validated Numerics contains introductory material on interval arithmetic and rigorous computations that is easily accessible to students with little background in mathematics and computer programming. I am not aware of any other book like it. The exercises and computer labs make it ideal for the classroom, and the references offer a good starting point for readers trying to gain deeper knowledge in this area."--Zbigniew Galias, AGH University of Science and Technology, Kraków

"A significant contribution, particularly since there are not many texts in this area.Validated Numerics will be read by those interested in interval arithmetic, numerical analysis, and ways to make computer simulations more robust and less susceptible to errors. It is well written and well organized."--A. J. Meir, Auburn University

Auszug. © Genehmigter Nachdruck. Alle Rechte vorbehalten.

Validated Numerics

PRINCETON UNIVERSITY PRESS

Contents

Preface........................................................ixIntroduction...................................................xiChapter 1. Computer Arithmetic.................................1Chapter 2. Interval Arithmetic.................................24Chapter 3. Interval Analysis...................................46Chapter 4. Automatic Differentiation...........................60Chapter 5. Interval Analysis in Action.........................73Chapter 6. Ordinary Differential Equations.....................106Appendix A. Mathematical Foundations...........................118Appendix B. Program Codes......................................126Bibliography...................................................131Index..........................................................137

Chapter One

In this chapter, we give an elementary overview of how (and what type of) numbers are represented, stored, and manipulated in a computer. This will provide insight as to why some computations produce grossly incorrect results. This topic is covered much more extensively in, for example, [Mu09], [Hi96], [Ov01], and [Wi63].

1.1 POSITIONAL SYSTEMS

Our everyday decimal number system is a positional system in base 10. Since computer arithmetic is often built on positional systems in other bases (e.g., 2 or 16), we will begin this section by recalling how real numbers are represented in a positional system with an arbitrary integer base β ≥ 2. Setting aside practical restrictions, such as the finite storage capabilities of a computer, any real number can be expressed as an infinite string

(-1)^σ (b_nb_n-1 ... b₀.b_-1b_-2 ...)_β, (1.1)

where b_n, b_n-1, ... are integers in the range [0, β - 1], and σ [member of] {0, 1} provides the sign of the number. The real number corresponding to (1.1) is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

If the number ends in an infinite number of consecutive zeros we omit them in the expression (1.1). Thus we write (12.25)₁₀ instead of (12.25000 ...)₁₀. Also, we omit any zeros preceding the integer part (-1)^σ (b_nb_n-1 ... b₀)_β. Thus we write (12.25)₁₀ instead of (0012.25)₁₀, and (0.0025)₁₀ instead of (000.0025)₁₀. Allowing for either leading or trailing extra zeros is called padding and is not common practice since it leads to redundancies in the representation.

Even without padding, the positional system is slightly flawed. No matter what base we choose, there are still real numbers that do not have a unique representation. For example, the decimal number (12.2549999 ...)₁₀ is equal to (12.255)₁₀, and the binary number (100.01101111 ...)₂ is equal to (100.0111)₂. This redundancy, however, can be avoided if we add the requirement that 0 ≤ b_i ≤ β -2 for infinitely many i.

Exercise 1.1. Prove that any real number x [not equal to] = 0 has a unique representation (1.1) in a positional system (allowing no padding) with integer base β ≥ 2 under the two conditions (a) 0 ≤ b_i ≤ β - 1 for all i, and (b) 0 ≤ b_i ≤ β - 2 for infinitely many i.

Exercise 1.2. What is the correct way to represent zero in a positional system allowing no padding?

1.2 FLOATING POINT NUMBERS

When expressing a real number on the form (1.1), the placement of the decimal point is crucial. The floating point number system provides a more convenient way to represent real numbers. A floating point number is a real number on the form

x = (-1)^σ m x β^e, (1.2)

where (-1)^σ is the sign of x, m is called the mantissa, and e is called the exponent of x. Writing numbers in floating point notation frees us from the burden of keeping track of the decimal point: it always follows the first digit of the mantissa. It is customary to write the mantissa as

m = (b₀.b₁b₂ ...)_β

where, compared to the previous section, the indexing of the b_i has the opposite sign. As this is the standard notation, we will adopt this practice in what follows. Thus we may define the set of floating point numbers in base β as:

F_β = {(-1)^σ m × β^e : m = (b₀.b₁b₂ ...)_β},

where, as before, we request that β is an integer no less than 2, and that 0 ≤ b_i ≤ β - 1 for all i, and that 0 ≤ b_i ≤ β - 2 for infinitely many i. The exponent e may be any integer.

Expressing real numbers in floating point form introduces a new type of redundancy. For example, the base 10 number 123 can be expressed as (1.23)₁₀ x 10², (0.123)₁₀ x 10³ , (0.0123)₁₀ x 10⁴, and so on. In order to have unique representations for non-zero real numbers, we demand that the leading digit b₀ be non-zero, except for the special case x = 0. Floating point numbers satisfying this additional requirement are said to be normal or normalized.

Exercise 1.3. Show that a non-zero floating point number is normal if and only if its associated exponent e is chosen minimal.

So far, we have simply toyed with different representations of the real numbers R. As this set is uncountably infinite, whereas a machine can only store a finite amount of information, more drastic means are called for: we must introduce a new, much smaller set of numbers designed to fit into a computer that at the same time approximate the real numbers in some well-defined sense.

As a first step toward this goal, we restrict the number of digits representing the mantissa. This yields the set

F_{β, p} = {x [member of] F_β : m = (b₀.b₁b₂ ... b_p-1)_β}.

The number p is called the precision of the floating point system. It is a nice exercise to show that although F_{β, p} is a much smaller set than F_β, it is countably infinite. This means that even F_{β, p} is too large for our needs. Note, however, that the restriction 0 ≤ b_i ≤ β - 2 for infinitely many i becomes void in finite precision.

A finite set of floating point numbers can be formed by imposing a fixed precision, as well as bounds on the admissible exponents. Such a set is specified by four integers: the base β, the precision p, and the minimal and maximal exponents [??] and [??], respectively. Given these quantities, we can define...