next up previous notation contents
Next: 1.7 Outline Up: 1 Motivation Previous: 1.5 Computability

1.6 Perseverance

Disregarding all of these difficulties, we shall carry on. It is clear that we will be able to find an algorithm that can correctly graph many common equations. In fact; for any finite set of equations, we know that there exists a program that will generate the correct graph for every equation in that set.

We start by defining a novel set of numbers, along with an arithmetic over these numbers, so that we may compute without worrying excessively about numerical round-off. This arithmetic is a generalization of interval arithmetic, so we will refer to it as ``generalized interval arithmetic''. With interval arithmetic, lower and upper bounds on computed result are kept. With our previous example, of graphing y = n(x),

figure5397

the sampling computation, for x = 1, would proceed as follows:

figure5403

where in each tex2html_wrap_inline32017 pair, the first element, a, is a lower bound, while the second element, b, is an upper bound. We have limited ourselves to three digits of precision, as before. Similarly computing samples for x = -1,0,2,3 allows us to create a reliable subgraph of y = n(x).

figure5424

As our interval arithmetic was correctly carried out, we may place complete confidence in our produced subgraph: the actual samples for x=-1,0,1,2,3 lie within our computed samples.

The true strength of interval arithmetic is revealed by sampling with intervals, rather than points. Consider graphing y=m(x),

figure5677

using interval arithmetic. We may sample the interval tex2html_wrap_inline32111 by computing tex2html_wrap_inline32113 , as follows:

figure5687

Similarly computing samples for tex2html_wrap_inline32115 allows us to create a reliable graph of y = m(x).

figure5714

Again, we have complete confidence in our computed graph: the true graph lies within our computed graph.

A detailed explanation of these techniques form the bulk of this thesis. The techniques are general and may be expanded to grapple other difficult problems.


next up previous notation contents
Next: 1.7 Outline Up: 1 Motivation Previous: 1.5 Computability
Jeff TupperMarch 1996