Friday, October 10, 2008

Adventures in Interval Arithmetic

I realize that some people read this blog just for the math. Those people have been mighty bored for the past several months as I've prattled on about Vinny, the fact that I am really busy, my vacation, etc. I need to remedy this problem and get talking more about math, as this blog's title implies it is about. So, math fans, this post is for you!

When you take a measurement of something (such as the temperature of your sick child, the height of your house's ceiling, or the RPM level of your car's engine), this measurement is not exact. For example, the thermometer we use to measure Vinny's temperature is digital, and displays the following: xyz.t (where x, y, z, and t represent any of the digits 0-9). Assuming that its method of measuring temperature is completely accurate, there is still error inherent in reading this measurement, because the precision of the readout is limited to increments of one-tenth of a degree Fahrenheit.

For example, if Vinny's actual temperature were 101.138˚F, we would see only 101.1 on the readout, because the temperature would be rounded to the nearest tenth of a degree. Therefore we would be unable to distinguish the temperatures from 101.05 to 101.149999.... They would all show up as 101.1. If we say that a is the actual temperature and â is the measured temperature, then for a in the interval [101.05, 101.15), â = 101.1.

Rebecca, you might say. Your parentheses don't match. You are correct! I did that on purpose. In mathematics we use [ or ] to mean "closed interval" and ( or ) to mean "open interval." Any number between 101.05 and 101.15 is within the interval. The only questions are about the numbers at the end of the interval. If a = 101.05 exactly, then it falls within the interval. But if a = 101.15, then it does not fall within the interval. A number infinitesimally smaller than 101.15 falls within the interval, but 101.15 itself does not. This is because a temperature of 101.15 would be rounded up to 101.2.

This is what we have to work with in interval arithmetic: these ranges. So, for example, if we want to figure out what Vinny's temperature range is in Celsius when the thermometer reads 101.1˚F, then we can convert the interval to Celsius.

Recall that C = 5/9 (F-32), where C = the temperature in Celsius, and F = the temperature in Fahrenheit.

So, we could take the minimum part of the interval and convert it, and then convert the maximum too, to create the Celsius interval. This works because [a, b] + x = [a+x, b+x], and µ [a, b] = [µa, µb] for non-negative µ. Thinking about it in geometric terms, picture the number line, and place a and b arbitrarily along the line such that b is greater than a. If you add the same number to both a and b, all you're doing is translating the interval to a different place along the line, but not changing the ordering of a and b. If you multiply by a non-negative number, you're just stretching the interval to be µ times its original width (or shrinking it, in the case of a µ less than one). Multiplying by a negative factor simply reverses the ordering of the interval, i.e., -µ [a, b] = [-µb, -µa].

So, if we do the interval conversion we obtain [101.05, 101.15)˚F = 5/9 {[101.05, 101.15) -32}˚C = 5/9 [69.05, 69.15)˚C = [38.36111…, 38.41666…)˚C.

Multiplication of intervals creates an interesting situation. Suppose you've measured the height of your ceiling and the length of a wall and you want to calculate the area of the wall. If the wall is 2.50 meters tall and 4.63 meters wide, and your measurements are accurate to the nearest centimeter, then the intervals are [2.495, 2.505) and [4.625, 4.635), respectively.

So how would you figure out the range of the area of the wall? When multiplying two intervals [a, b] and [x, y], there are four possible numbers to consider as the maximum or minimum of the interval: ax, bx, ay, and by. In general, we can't just take [ax, by] as the interval; for example the range for [-3, 1] [-1, 2] is [-6, 3], not [3, 2] -- which doesn't even make sense as an interval. In the case of the wall, though, there are no negative numbers to worry about, so the wall area is anywhere from [11.539375, 11.610375) m2.

The examples I have given here may seem silly or unimportant, but there are actually some very important applications of interval arithmetic. A big one is computer arithmetic.

Computers have a limited capacity to express numbers. A number such as 1/3 cannot be expressed as a fraction on a computer; instead it is expressed in a form similar to a truncated decimal representation (i.e., like 0.3333). It's not actually a decimal representation because computers represent numbers in base two, but the concept is the same.

As a result of this, if you subtract two numbers that are pretty close to one another, you may end up with a grossly inaccurate result. This phenomenon is known as catastrophic cancellation. For example, if we had a computer that had four digits of accuracy, and we used it to take the difference of 13/12 and 14/13, we would get 1.083 - 1.077 = 0.006. The real answer, 1/156, is approximately 0.006410, so we are not far off. But if our computer had only three digits, we would have 1.08 - 1.08 = 0.00 as the answer!

We can use interval arithmetic to see that while our answer is far from accurate, the interval of uncertainty contains the correct answer. So, in the case of the three-digit accurate computer, we would have [1.075, 1.085) - [1.075, 1.085) = [1.075, 1.085) + (-1.085, -1.075] = (-0.01, 0.01). (Subtracting is like adding the negative of the interval. And when we have the sum of an open and closed bound, the result is open, because (a + almost b) = almost (a+b).) As you can see, the interval of uncertainty contains the true answer, so using interval analysis we can find an upper bound on the margin of error for our calculation.

There are other cases in which an analysis using interval arithmetic is also useful, and I hope to write another application up soon. In the meantime, I hope you have enjoyed learning about interval arithmetic and if you have any questions feel free to ask!

No comments: