Validated Numerics: A Short Introduction to Rigorous Computations

Warwick Tucker
Publisher:
Princeton University Press
Publication Date:
2011
Number of Pages:
135
Format:
Hardcover
Price:
45.00
ISBN:
9780691147819
Category:
Textbook
[Reviewed by
John D. Cook
, on
07/27/2011
]

Validated Numerics by Warwick Tucker is more narrow than its title may imply. The subtitle is a bit more specific: A Short Introduction to Rigorous Computations. Even more specifically, this is a book about interval analysis.

As one might expect, interval analysis works with intervals rather than simply with numbers. For example, if you know the side of a square is somewhere between 2 and 3, then you know that the area of the square is somewhere between 4 and 9. Real applications are much more complicated but follow the same basic principle.

One justification for interval analysis is the ability to represent uncertain quantities without a loss of information. For example, if a measured quantity is believed to be between 3.5 and 4.5 centimeters, one could carry out calculations with the interval [3.5, 4.5] rather than the single point 4 in the middle. Another justification, one emphasized in Validated Numerics, is to work around the limitations of computer arithmetic. For example, π is an irrational number and so cannot be represented exactly in computer arithmetic. (Neither can most rational numbers be represented exactly. See Anatomy of a floating point number for an explanation of the limits of computer arithmetic.) To avoid using an approximation for π, one could work with an interval [a, b] containing π, where a is the largest number less than π that can be exactly represented in a computer. Likewise b would be the smallest machine-representable number greater than π.

Given the promise of interval analysis, why is it not more widely used? Here are three reasons.

1. Interval bounds on computed quantities can be so large as to be impractical. Because interval estimates are based on what is possible rather than what is probable, the bounds can become extremely conservative after a long sequence of calculations.
2. Floating point error is often orders of magnitude smaller than other sources of error in application. If you are estimating the weight of a cow by modeling her as a sphere filled with water, it hardly matters that your value of π is only good to 15 decimal places.
3. Interval arithmetic is tedious, as Validated Numerics illustrates.

Regarding the first reason, imagine estimating some physical quantity by averaging a large number of measurements. The possible error grows with each measurement, while the expected value of the error decreases. This observation may not seem profound, but brilliant mathematicians saw things differently in the 18th century. Because they thought in terms of logic rather than probability, they thought that using more data would decrease the accuracy of predictions. The statistical mindset of modeling errors as random variables did not develop until the 19th century.

Despite the objections to interval analysis listed above, there are instances where interval analysis is quite valuable. For example, suppose you believe you found a point z where Re ζ(z) is slightly more than 0.5. It’s no good to say that the real part is 0.50000000001 as far as your program computes it. But if you could demonstrate that the real part lies in an interval with lower bound 0.500000000005, you would be famous because you would have disproved the Riemann hypothesis.

Validated Numerics gives a thorough introduction to interval analysis and its applications in a small space, about 90 pages devoted to interval analysis plus around 50 pages of introduction and appendices. The book covers the basic theory of interval analysis and its application to automatic differentiation, root-finding, optimization, quadrature, and ordinary differential equations.

While Validated Numerics goes into theoretical detail, it also includes a computational perspective. The book sprinkles in examples of Matlab code and includes four computer labs. Although interval analysis can be complicated, the book discusses software libraries that hide much of the complication.

John D. Cook is a research statistician at M. D. Anderson Cancer Center and blogs daily at The Endeavour.

Preface ix
Introduction xi
What Is Validated Numerics? xi
The Scope and Aim of This Book xi
Acknowledgments xii

Chapter 1. Computer Arithmetic 1
1.1 Positional Systems 1
1.2 Floating Point Numbers 2
1.3 Rounding 5
1.4 Floating Point Arithmetic 12
1.5 The IEEE Standard 14
1.6 Examples of Floating Point Computations 19
1.7 Computer Lab I 23

Chapter 2. Interval Arithmetic 24
2.1 Real Intervals 24
2.2 Real Interval Arithmetic 27
2.3 Extended Interval Arithmetic 30
2.4 Floating Point Interval Arithmetic 37

Chapter 3. Interval Analysis 46
3.1 Interval Functions 46
3.2 Centered Forms 55
3.3 Monotonicity 58
3.4 Computer Lab II 59

Chapter 4. Automatic Differentiation 60
4.1 First-Order Derivatives 60
4.2 Higher-Order Derivatives 64
4.3 Higher-Order Enclosures 71
4.4 Computer Lab III 72

Chapter 5. Interval Analysis in Action 73
5.1 Zero-Finding Methods 73
5.2 Optimization 87
5.4 Computer Lab IV 105

Chapter 6. Ordinary Differential Equations 106
6.1 A Gentle Mathematical Introduction 106
6.2 Simple Enclosure Methods 107
6.3 High-Order Methods 111
6.4 Rigorous High-Order Examples 112

Appendix A. Mathematical Foundations 118
A.1 The Rational Numbers 118
A.2 What Is a Real Number? 120
A.3 Completeness 122
A.4 Fixed-Point Theorems 124

Appendix B. Program Codes 126
B.1 IEEE Constants 126
B.2 Changing Rounding Modes 127
B.3 A Sample Code in C++ 128
Bibliography 131
Index 137