Interval Arithmetic, Part II - psholtz/MIT-SICP GitHub Wiki

Eva Lu Ator, another user, has also noticed the different intervals computed by different but algebraically equivalent expressions. She says that a formula to compute with intervals using Alyssa's system will produce tighter error bounds if it can be written in such a form that no variable that represents an uncertain number is repeated. Thus, she says, "par2" is a better program for parallel resistances than "par1". Is she right? Why?

Solution

We observed in the last exercise that the "par2" procedure seemed to produce tighter error bounds than the "par1" procedure. Let's go back and look more closely at this:

First look at the sample with the extremely wide intervals:

(define x (make-center-percent 10 0.3))
(define y (make-center-percent 10 0.4))

(/ (percent (par1 x y)) (percent (par2 x y)))
;; ==> 2.2727

And let's look next at the example with the tighter intervals:

(define x (make-center-percent 40000 0.005))
(define y (make-center-percent 65000 0.0125))

(/ (percent (par1 x y)) (percent (par2 x y)))
;; ==> 3.453721

So in both cases, the bounds produced by "par1" are about 2-3 times as wide as those produced by "par2".

Let's take a closer look at the two procedures:

(define (par1 r1 r2)
 (div-interval (mul-interval r1 r2)
               (mul-interval r1 r2)))

(define (par2 r1 r2)
 (let ((one (make-interval 1 1)))
  (div-interval one
                (add-interval (div-interval one r1)
                              (div-interval one r2)))))

One difference between the two procedures is that "par2" employs an interval in its computations, "one", which has no uncertainty. On the other hand, all the combinations created by "par1" involve intervals with some finite measure of uncertainity.

Combining two intervals can never DECREASE the uncertainty in the resulting measurement, although it could possibly INCREASE that uncertainty.

For instance, suppose we have two intervals, both of width "a" (i.e., b=a), and we add them together:

http://farm9.staticflickr.com/8066/8268659464_3ddb547ed3.jpg

The resulting interval has a width of "2a".

On the other hand, suppose we combine one interval of width "a" with a second interval having zero uncertainty:

http://farm9.staticflickr.com/8360/8268659440_d24a889746.jpg

The resulting interval has a width of only "a" this time.

In this sense, using intervals that combine objects like "one" -- that have no uncertainty -- will produce a result that has "tighter" error bounds.

Eva Lu Ator further suggested writing the code in such a way that no variable that represents an uncertain number is repeated. One issue with repeating such uncertain numbers is that once a number has been specified, its value is no longer "uncertain" (so to speak). That is, "r1" has a concrete and "certain" value, it's just that we are not able to narrow this number down any further than by saying that it must occur in the range specified by the interval.

But the way "par1" is written, it treats the intervals "r1" and "r2" as being "equally" uncertain in both the "add-interval" and "mul-interval" procedures. Or said differently, the "r1" used in "add-interval" and "mul-interval" refers to the SAME resistor with the SAME DISTINCT uncertainty, not to TWO resistors whose values are known only to the same, EQUAL uncertainty. The way "par1" is written it models this latter case, although that will produce an overly pessimistic estimation of the uncertainty of the resulting interval.

It's not necessarily clear or obvious how to write "par1" so that it models the first case, which would produce tighter error bounds, or if this is even possible.

For the sake of interest, we can walk through a more quantitative analysis as well.

Recall the definition of "div-interval":

(define (div-interval x y)
 (mul-interval x 
               (make-interval (/ 1.0 (upper-bound y))
                              (/ 1.0 (lower-bound y)))))

PAR1

First let's step through the calculation for "par1".

We are interested here in taking two intervals, r1 and r2, both modeled as having the same percentage error "p", and understanding what the expected uncertainty in the resulting value given by "par1" should be.

Suppose we have two intervals with the same percentage error:

http://farm9.staticflickr.com/8340/8267616469_bacee6111b_m.jpg

where a = xp and b = yp, where p is the same in both equations.

We could then write:

http://farm9.staticflickr.com/8064/8267681103_5dc25a130d_o.jpg

for the two intervals, and adding them obtain:

http://farm9.staticflickr.com/8341/8267616453_2e1b7d13b7_o.jpg

Suppose now that we multiply the two intervals together. This calculation was already carried out Exercise 2.13 but we repeat it (in essence) here:

http://farm9.staticflickr.com/8057/8267616425_dd8aa603cd_o.jpg

Ignoring the second order terms, and writing p = b/y = a/x, we have:

http://farm9.staticflickr.com/8494/8267616407_ee4fc89803_o.jpg

In other words, if we take two intervals, each with percentage uncertainty "p", and multiply them together, the resulting interval will have percentage uncertainty "2p".

(div-interval x y)
(mul-interval x (make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y))))

Consider first the second argument to "mul-interval".. the term "y" in this expression is the interval:

http://farm9.staticflickr.com/8490/8268686908_b3efce7ce4_o.jpg

Allowing z = x + y, we can write:

http://farm9.staticflickr.com/8219/8267616365_feb74bd822_o.jpg

hence

(make-interval (/ 1.0 (upper-bound y)) (/ 1.0 (lower-bound y)))

becomes

http://farm9.staticflickr.com/8353/8267616349_f67fcbb963_o.jpg

Recalling the Taylor expansion for f(z) = 1/z, we have:

http://farm9.staticflickr.com/8079/8268686850_fa659b1b88_o.jpg

and since a = zp, we can write:

http://farm9.staticflickr.com/8363/8268750950_08a35a7df5_o.jpg

Keeping only the first-order terms, our expansion for the argument interval becomes:

http://farm9.staticflickr.com/8361/8267616321_fc9422e0a4_o.jpg

Where z = x + y.

Returning now to our definition of "par1", it reduces to:

(div-interval x y)

Where the uncertainty in x is known to be (roughly) 2p, and the uncertainty in y is known to be (roughly) p. So the question is, if we multiply two intervals, one w/ uncertainty "2p" and the other with uncertainty "p", what is the uncertainty of the resulting interval?

The answer is straightforward:

http://farm9.staticflickr.com/8058/8268686822_e1d4229acc_o.jpg

Ignoring the second-order p^2 terms, the answer reduces to:

http://farm9.staticflickr.com/8208/8268686800_259d097124_o.jpg

Or in other words, the resulting answer will have an uncertainty of "3p".

We would thus expect, that it we supply "par1" with two intervals, each with the same percentage uncertainty "p", that the resulting answer produced by "par1" will have an uncertainty of (roughly) "3p".

PAR2

Now let's step through the calculation for "par2".

As before, we are interested in taking two intervals, r1 and r2, both modeled as having the same percentage uncertainty "p", and understanding what the expected uncertainty in the resulting value given by "par2" should be.

First let's work through the expansion for (div-interval one r1), supposing that r1 is defined as the interval (x-a,x+a), and that p, the percentage uncertainty, is given by a = xp.

As before, we have:

(div-interval one r1)
(mul-interval one (make-interval (/ 1.0 (upper-bound r1)) (/ 1.0 (lower-bound r1))))

The interval which represents the second argument to "mul-interval" can be represented as:

http://farm9.staticflickr.com/8481/8268933304_9b8a62d77b_o.jpg

A Taylor expansion of f(x) = 1/x, given:

http://farm9.staticflickr.com/8338/8268933288_27749db9b0_o.jpg

and since a = px, we can write:

http://farm9.staticflickr.com/8199/8267864149_6b35a1c07a_o.jpg

So to a first order approximation, we can write the interval as:

http://farm9.staticflickr.com/8224/8268933252_8ff9c23db1_o.jpg

In other words, the resulting interval has a percentage uncertainty of "p" (just as the initial argument interval, r1, had).

Similarly, the computation (div-interval one r2) will give (supposing that r2 is defined as the interval (y-b,y+b) where b=yp, and p is the same percentage uncertainty as in r1):

http://farm9.staticflickr.com/8060/8268933234_2ccf84b2c4_o.jpg

Next we must combine these two intervals by adding. If we add two intervals, each with percentage uncertainty of "p", the resulting interval will still have percentage uncertainty "p":

http://farm9.staticflickr.com/8212/8268933204_4ab20fa1b6_o.jpg

Finally, we must divide this interval into "one" (the interval with no uncertainty), but as we have already shown, dividing an interval with uncertainty "p" into "one" will produce a resulting interval of uncertainty "p". Hence, we expect the final answer produced by "par2" to have an uncertainty of "p".

We can test this by considering two resistors, each with the same percentage error in uncertainty, and seeing whether the results generated by "par1" and "par2" conform to the expectations we derived above:

(define x (make-center-percent 10000 0.1))
(define y (make-center-percent 12500 0.1))

Note that the interval above as uncertainty 0.1 (10%):

(percent (par1 x y))
;; ==> 0.292233
(percent (par2 x y))
;; ==> 0.1

Which is what we expect.

So clearly, "par2" produces tighter error bounds than "par1". Whether this makes it a "better" program for parallel resistances depends on the nature of the project requirements.

Home