Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: Sorry, my example in error Re: Tetrits and "stickiness"

Dan,
The Brouwer fixed point theorem is related to the contraction mapping theorem, but not exactly the 
same.  (Does someone want to argue equivalence?)
The hypothesis of the theorem that is violated by the domainOut condition is continuity.
Although one sometimes does iterate a process, and fixed point iteration on g would indeed catch the problem, one also sometimes uses such computational fixed point theory to simply prove existence and uniqueness within a large box, without iterating to convergence. (For example, we sometimes construct as large a box as possible in which the conditions hold, to be able to eliminate it from further search in a branch and bound process.) Thus, checking the domainOut condition after the final result giving the overall expression value would be necessary, and we cannot rely on subsequent 
iterations revealing a problem.
I don't view the DomainOut condition as a serious programming blunder in this context, but halfway between an operation exception and something like the "inexact" flag from 754. Tracing where it occurs could be useful, and the user could check its value after each operation, but 
checking a final sticky value might be more efficient.
By the way, for these fixed point questions, John had initially proposed a "continuous" flag. I think (and John, am I remembering correctly?) he decided these domain checks would 
fill the bill.

Baker

On 4/15/2010 10:15 AM, Dan Zuras Intervals wrote:

D

.
.
.

	Well, I'm not quite sure.

	The argument in the fixed point theorem of contractive
	maps in topology involves an iteration of plugging the
	new contracted set back into the function&  trying it
	again.

	If you plug x = [0,0.5] back into g() then on the very
	next step you would get:

	g([0,0.5]) = 0.5*sqrt([0,0.5] - 1) + 0.5*sqrt([0,0.5])
		= 0.5*sqrt([-1,-0.5]) + 0.5*[0,sqrt(0.5)]
		= 0.5*[empty] + [0,0.5*sqrt(0.5)]
		= [empty] + [0,0.5*sqrt(0.5)]
		= [empty]

	Which would seem to violate any fixed point theorem as
	I understand it.  No matter WHAT the decorations are.

	Does that make this NOT a counter example?

	Or does this mean that arithmetic that permits this to
	happen is bad for us?

	If its the latter, I don't know how you're going to
	avoid it.  I think the best we could do is provide
	enough diagnostic information in the decorations to
	let the user know something about what went wrong.

	Now that you have me thinking about it what about the
	map g(x) = x - 1 on the input set x = [-oo,5]?  The
	iteration will produce an ever contracting (in the
	sense of subset) series of intervals but there is no
	fixed point unless you consider -oo to be a element of
	our topology.

	Actually, come to think of it, g() will never contract
	beyond [-oo,-b^p] where b is the base&  p is the
	precision since at that point we will have
	roundUp(-b^p - 1) = -b^p.

	Even a truly contractive map that contracts slowly enough
	to run afowl of the working precision of our underlying
	floating-point system will be unable to locate the fixed
	point with any accuracy.

	Or, for example, g(x) = x - arctan(x).  If fed a starting
	interval of [-1,1] it will converge rather rapidly to [0,0].
	But if fed a starting interval of [-b^p,b^p] it will never
	get started at all.  Even a divide&  conquer which will
	easily find [0,0] will not be able to eliminate the large
	intervals as they will appear 'computationally' to also
	contain fixed points.

	OK, I think I am digressing from the issue here.

	Forget everything from the word 'thinking' on down.

	It was a foolish thing to do anyway. :-)

	Chalk it up to being unfamiliar with the ways of the
	intervaller.

	Yours,

				   Dan