SICP exercise 2.16

From Drewiki
Jump to: navigation, search

Problem

Explain, in general, why equivalent algebraic expressions may lead to different answers. Can you devise an interval-arithmetic package that does not have this shortcoming, or is this task impossible? (Warning: This problem is very difficult.)

Solution

In the interval arithmetic system we've defined, some of the laws of algebra that we're accustomed to don't apply to certain operations, so algebraic expressions that are equivalent in a non-interval arithmetic system are not necessarily equivalent in an interval arithmetic system.

For example, consider the distributive law. The distributive law states that

<math> a(b+c) = ab+ac </math>

but this law does not universally apply in our interval arithmetic system. Here's an example:

(define (make-interval a b) (cons a b))
 
(define (lower-bound i) (car i))
 
(define (upper-bound i) (cdr i))
 
(define (add-interval x y)
  (make-interval (+ (lower-bound x) (lower-bound y))
                 (+ (upper-bound x) (upper-bound y))))
 
(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))
 
(define a (make-interval 2 4))
 
(define b (make-interval -2 0))
 
(define c (make-interval 3 8))
 
(define x (mul-interval a
                        (add-interval b c)))
 
(define y (add-interval (mul-interval a b)
                        (mul-interval a c)))
 
(lower-bound x)

Output:

2


(upper-bound x)

Output:

32


(lower-bound y)

Output:

-2


(upper-bound y)

Output:

32


So the expression <math>a(b+c)</math> evaluates to the interval [2,32] and the expression <math>ab+ac</math> evaluates to the interval [-2,32]. Which one is "correct"? Are both?

There are other algebraic laws that fail in our system as well: try squaring the interval [-2,2], for example.

There are many pitfalls in designing an interval arithmetic system. I'm not sure whether it's possible to devise an interval arithmetic system that overcomes these problems, but there is a lot of documentation and research about interval arithmetic here:

http://www.cs.utep.edu/interval-comp/main.html

Here is a fairly accessible paper that gives a high-level overview of interval arithmetic, including why it's important and what some of the problems are (including the ones we've discussed in some of these exercises):

http://www.americanscientist.org/content/AMSCI/AMSCI/ArticleAltFormat/2003101124223_307.pdf

And here is a technical paper which describes a constrained interval arithmetic in which the distributive law (and several other algebraic laws) applies:

http://citeseer.ist.psu.edu/140381.html

Personal tools