SICP Exercise 2.15: Better Bounds

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?

Yes, Eva is right, and we can show this to be the case by substitution. Firstly, let's assume we have two intervals, x and y that have the lower and upper bounds [l_x, u_x] and [l_y, u_y] respectively. Also, let's assume that x and y are non-negative intervals as we defined in exercise 2.11. We then can greatly simplify mul-interval to:

(define (mul-interval x y)
  (make-interval (* (lower-bound x) (lower-bound y))
                 (* (upper-bound x) (upper-bound y))))

We can then work through the evaluation of each program in turn.

Let's start with par1:

  (par1 x y)
= (div-interval (mul-interval x y) (add-interval x y))
= (div-interval (make-interval (* (lower-bound x) (lower-bound y))
                               (* (upper-bound x) (upper-bound y)))
                (add-interval x y))
= (div-interval (make-interval (* lx ly) (* ux uy))
                (add-interval x y))
= (div-interval (cons (* lx ly) (* ux uy))
                (add-interval x y))
= (div-interval (cons (* lx ly) (* ux uy))
                (make-interval (+ (lower-bound x) (lower-bound y))
                               (+ (upper-bound x) (upper-bound y))))
= (div-interval (cons (* lx ly) (* ux uy)) (make-interval (+ lx ly) (+ ux uy)))
= (div-interval (cons (* lx ly) (* ux uy)) (cons (+ lx ly) (+ ux uy)))
= (mul-interval (cons (* lx ly) (* ux uy))
                (make-interval (/ 1.0 (upper-bound (cons (+ lx ly) (+ ux uy))))
                               (/ 1.0 (lower-bound (cons (+ lx ly) (+ ux uy))))))
= (mul-interval (cons (* lx ly) (* ux uy))
                (make-interval (/ 1.0 (+ ux uy)) (/ 1.0 (+ lx ly))))
= (mul-interval (cons (* lx ly) (* ux uy))
                (cons (/ 1.0 (+ ux uy)) (/ 1.0 (+ lx ly))))
= (make-interval (* (lower-bound (cons (* lx ly) (* ux uy)))
                    (lower-bound (cons (/ 1.0 (+ ux uy)) (/ 1.0 (+ lx ly)))))
                 (* (upper-bound (cons (* lx ly) (* ux uy)))
                    (upper-bound (cons (/ 1.0 (+ ux uy)) (/ 1.0 (+ lx ly)))))))
= (make-interval (* (* lx ly) (/ 1.0 (+ ux uy))) (* (* ux uy) (/ 1.0 (+ lx ly))))
= (cons (* (* lx ly) (/ 1.0 (+ ux uy))) (* (* ux uy) (/ 1.0 (+ lx ly))))
≡ (cons (/ (* lx ly) (+ ux uy)) (/ (* ux uy) (+ lx ly)))

We now have the bounds for intervals produced by par1, so let's move on to par2:

  (par2 x y)
= (let ((one (make-interval 1 1))) 
    (div-interval one
                  (add-interval (div-interval one x)
                                (div-interval one y))))
= (let ((one (cons 1 1))) 
    (div-interval one
                  (add-interval (div-interval one x)
                                (div-interval one y))))
= (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (div-interval (cons 1 1) y))))
= (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (mul-interval (cons 1 1) 
                                            (make-interval (/ 1.0 (upper-bound y))
                                                           (/ 1.0 (lower-bound y))))))
= (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (mul-interval (cons 1 1) 
                                            (make-interval (/ 1.0 uy) (/ 1.0 ly)))))
= (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (mul-interval (cons 1 1) 
                                            (cons (/ 1.0 uy) (/ 1.0 ly)))))
= (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (make-interval (* (lower-bound (cons 1 1))
                                                (lower-bound (cons (/ 1.0 uy)
                                                                   (/ 1.0 ly))))
                                             (* (upper-bound (cons 1 1))
                                                (upper-bound (cons (/ 1.0 uy)
                                                                   (/ 1.0 ly)))))))
= (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (make-interval (* 1 (/ 1.0 uy))
                                             (* 1 (/ 1.0 ly)))))
≡ (div-interval (cons 1 1)
                (add-interval (div-interval (cons 1 1) x)
                              (make-interval (/ 1.0 uy) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (add-interval (mul-interval (cons 1 1) 
                                            (make-interval (/ 1.0 ux) (/ 1.0 lx)))
                              (cons (/ 1.0 uy) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (add-interval (mul-interval (cons 1 1) 
                                            (cons (/ 1.0 ux) (/ 1.0 lx)))
                              (cons (/ 1.0 uy) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (add-interval (make-interval (* (lower-bound (cons 1 1))
                                                (lower-bound (cons (/ 1.0 ux)
                                                                   (/ 1.0 lx))))
                                             (* (upper-bound (cons 1 1))
                                                (upper-bound (cons (/ 1.0 ux)
                                                                   (/ 1.0 lx))))
                              (cons (/ 1.0 uy) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (add-interval (make-interval (* 1 (/ 1.0 ux))
                                             (* 1 (/ 1.0 lx)))
                              (cons (/ 1.0 uy) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (add-interval (cons (* 1 (/ 1.0 ux)) (* 1 (/ 1.0 lx)))
                              (cons (/ 1.0 uy) (/ 1.0 ly))))
≡ (div-interval (cons 1 1)
                (add-interval (cons (/ 1.0 ux) (/ 1.0 lx))
                              (cons (/ 1.0 uy) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (make-interval (+ (lower-bound (cons (/ 1.0 ux) (/ 1.0 lx)))
                                  (lower-bound (cons (/ 1.0 uy) (/ 1.0 ly))))
                               (+ (upper-bound (cons (/ 1.0 ux) (/ 1.0 lx)))
                                  (upper-bound (cons (/ 1.0 uy) (/ 1.0 ly))))))
= (div-interval (cons 1 1)
                (make-interval (+ (/ 1.0 ux) (/ 1.0 uy))
                               (+ (/ 1.0 lx) (/ 1.0 ly))))
= (div-interval (cons 1 1)
                (cons (+ (/ 1.0 ux) (/ 1.0 uy)) (+ (/ 1.0 lx) (/ 1.0 ly))))
= (mul-interval (cons 1 1)
                (make-interval (/ 1.0 (upper-bound (cons (+ (/ 1.0 ux) (/ 1.0 uy))
                                                         (+ (/ 1.0 lx) (/ 1.0 ly)))))
                               (/ 1.0 (lower-bound (cons (+ (/ 1.0 ux) (/ 1.0 uy))
                                                         (+ (/ 1.0 lx) (/ 1.0 ly))))))))
= (mul-interval (cons 1 1)
                (make-interval (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly)))
                               (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy)))))
= (mul-interval (cons 1 1)
                (cons (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly)))
                      (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy)))))
= (make-interval (* (lower-bound (cons 1 1))
                    (lower-bound (cons (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly)))
                                       (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy))))))
                 (* (upper-bound (cons 1 1))
                    (upper-bound (cons (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly)))
                                       (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy))))))))
= (make-interval (* 1 (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly))))
                 (* 1 (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy)))))
= (cons (* 1 (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly))))
        (* 1 (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy)))))
≡ (cons (/ 1.0 (+ (/ 1.0 lx) (/ 1.0 ly))) (/ 1.0 (+ (/ 1.0 ux) (/ 1.0 uy))))
≡ (cons (/ 1.0 (/ (+ lx ly) (* lx ly))) (/ 1.0 (/ (+ ux uy) (* ux uy))))
≡ (cons (/ (* lx ly) (+ lx ly)) (/ (* ux uy) (+ ux uy)))

And now we have the bounds for intervals produced by par2. Let's bring them together and have a look:

(par1 x y) = (cons (/ (* lx ly) (+ ux uy)) (/ (* ux uy) (+ lx ly)))
(par2 x y) = (cons (/ (* lx ly) (+ lx ly)) (/ (* ux uy) (+ ux uy)))

As you can see they differ only in the denominators of the bounds. (par1 x y) uses the sum of the upper bounds of x and y as the denominator for the lower bound, and the sum of the upper bounds of x and y as the denominator for the lower bound. (par2 x y) swaps these around. What effect does this have? Well, as we're dealing with non-negative intervals we know summing the upper bounds produces a larger non-negative value than summing the lower bounds. Therefore, dividing a non-negative value by the former will produce a smaller value than if we divide it by the latter. This means that par1 will produce a smaller lower bound than par2 and a larger upper bound than par2. Or, to put it in other words, par1 will produce a larger interval than par2, and so par2 will provide a more accurate calculation of parallel resistances.