- Hello people,

I found a copy of the SICP book in a used book store a few month ago,

and after realising how good it was I started working on the

exercises. I'm now at ex 2.43. I discovered this group yesterday and

this is a nice surprise. Please excuse me in advance if I'm not always

using the correct technical terms as I never had any math course in

english.

For this first post I would like to discuss ex 2.16. I hope it doesn't

bother you that I come back to an already discussed exercise. John

Berthels has made good points about this exercise. From a software

engineering point of view, I think "interval arithmetic" is an

inprecise description of the problem we are trying to solve. "Error

calculation" might be a better term.

To build a better system, my first idea was to use symbolic

manipulation to transform the expression to an algebraically

equivalent form which minimize the interval. But what is this form ?

It should probably minimize the repetition of a single variable, but

is it enough ? And how to select the right transformation rules ?

These problems are a bit over my head...

My second idea was more mathematical, and seems more practical too.

I'll explain through an example: When asked to find the bounds of an

expression such as (R1*R2)/(R1+R2), where R1 and R2 are intervals,

find the extremas of the (mathematical) function f(x,y) = (x*y)/(x+y),

where x and y are real values, over the domain formed by the

intervals: R1xR2. The extremas (global minimum and maximum over the of

the resuldomain) are the bounds ting interval. Well, finding the

extremas of arbitrary functions is not that easy (maybe numerical

methods would help?) but at least the solution is well defined. It

wouldn't depend on the algebraic form of the expression, and give the

smaller acceptable interval in all cases.Thinking about it, it may be

the only correct way to do it in the general case.

I would be interested to know if you agree or disagree. Is this the

"right" way to perform error calculation ? If not, where is the fault

in my reasonning ?

regards,

Ioura - On 7/2/05, Ioura Batugowski <ibatugow@...> wrote:

> To build a better system, my first idea was to use symbolic

Yes, this was my thought too. I also thought it was over my head :-)

> manipulation to transform the expression to an algebraically

> equivalent form which minimize the interval. But what is this form ?

> It should probably minimize the repetition of a single variable, but

> is it enough ? And how to select the right transformation rules ?

> These problems are a bit over my head...

Although, pleasingly, SICP seems to come closer to this sort of

symbolic manipulation a bit further on, so it looks more reasonable. I

don't have sufficient motivation to try and work on a real solution to

this, however.

For example, the constraint modelling, as refined in exercise 3.37 is

a system which maintains the algrebraic structure of a calculation, in

order to be able to calculate the value of whichever term lacks one.

It doesn't seem beyond the bounds of possibility that rules for

algrebraic simplification could be built into this. Also, the symbolic

differentiation from chapter 2.3 is also fairly close to this problem

area.

> My second idea was more mathematical, and seems more practical too.

This is interesting. As your discussion with Pascal highlights, such

> I'll explain through an example: When asked to find the bounds of an

> expression such as (R1*R2)/(R1+R2), where R1 and R2 are intervals,

> find the extremas of the (mathematical) function f(x,y) = (x*y)/(x+y),

> where x and y are real values, over the domain formed by the

> intervals: R1xR2. The extremas (global minimum and maximum over the of

> the resuldomain) are the bounds ting interval. Well, finding the

> extremas of arbitrary functions is not that easy (maybe numerical

> methods would help?) but at least the solution is well defined. It

> wouldn't depend on the algebraic form of the expression, and give the

> smaller acceptable interval in all cases.Thinking about it, it may be

> the only correct way to do it in the general case.

an analysis should also need to track the identity of various

quantites, to differentiate (mul-interval x y) from (mul-interval x x)

Note, however, that you can't re-establish identity from noting within

the mul-interval function that the two arguments have the same value

and error, since they may still be independent variables/measurements

which happen to have the exact same value and error.

So I guess you need a rule/restriction which states that when

analysing (f x y ... z), all the arguments must be independent

measurements/variables. Which is fine, since if they aren't you can in

theory define a function of fewer variables and analyse that instead.

As you suggest, a numerical approach (where you put a mesh or grid

over the function domain, and evaluate at all points in the grid)

sounds feasible, but has the drawback that it will always tend to

underestimate the error, perhaps badly, depending on the resolution of

the mesh and the shape of the function.

> I would be interested to know if you agree or disagree. Is this the

It is an interesting approach. I guess the 'right' way depends on the

> "right" way to perform error calculation ? If not, where is the fault

> in my reasonning ?

intended usage, as always. The numeric approach may be quite

practical, if you have some domain knowledge which allows you to

choose appropriate shaped/sized meshes and sufficient horsepower to

evaluate functions on a sufficiently dense mesh. (since even a

10-interval mesh has just raised the cost of evaluating a function of

two numbers by a factor of 100...).

I guess the 'right' answer is whatever people selling software in this

area have researched and implemented :-)

jb