Generalized Interval Arithmetic M.Sc. Thesis

Jeffrey Allen Tupper

A thesis submitted in conformity with the requirements
for the degree of Master of Science
Graduate Department of Computer Science
University of Toronto

Abstract

Floating-point is commonly used in numerical computations; this use has revealed its inherent inaccuracy and has spread uncertainty throughout the computer community. Interval techniques unite the precision provided by the modern computer with the accuracy accorded to traditional mathematics. As interval analysis matured, sophisticated optimization of interval techniques has occurred.
This thesis presents a framework which enables further optimization of interval routines, while shielding the numerical practitioner from the complexities that have recently surfaced in interval algorithms. This new framework is constructed by migrating variables from the problem domain into the interval arithmetic. Properties of functions within the problem domain may be tracked, so many common non-differentiable partial functions are handled naturally.
This new approach is briefly compared with the much earlier, independent approach offered by Eldon R. Hansen in 1975. The fundamental problem of reliably rendering graphs of implicit equations drives the comparison.

Acknowledgments

First, I acknowledge my parents: my father, who revealed the world of logic, and my mother, who revealed the world of life. That life has become ever more precious after my recent marriage: I thank my wife, Brenda, for all of her kind acts and continued support.
I was given a challenging standard by my supervisors, Eugene Fiume and Rudi Mathon: one cannot be given more.
Much of the clarity of this document is owed to my readers, namely: John Funge, Wayne Hayes, and Francois Pitt. The patience and diligence exhibited by each was exemplary. I thank Xiaoyuan for her warm words; I thank Mahdi for his true words. I express graditude to the others in the lab, for providing the needed distractions from writing.
Finally, I must thank Jim Little, as he introduced me to interval methods during my initial undergraduate year [2, pages 84-88].
Of course, I assume full responsibility for all errors and mistakes still present in this document. I hope that I have met the expectations of all who have helped me on my journey.