Re: A Decorations Challenge

[John Pryce <j.d.pryce@xxxxxxxxxxxx>]

Arnold, P1788

On 14 Oct 2010, at 15:23, Arnold Neumaier wrote:
> Here is my answer to your challenge... below is an improved version.

Below is Arnold's code with a few errors corrected, which now runs as expected in Gnu Octave. I don't have Matlab available just now. The most annoying defect is due to Octave's dispatching rules, which mean that it inside the overloaded "sqrt" it doesn't use the built-in "sqrt", and tries to recurse instead. Maybe Matlab knows better? I cured this by defining "Sqrt" which calls the built in function.

The code as written gives the output I expected:
> > AN_Solution1
> info =
> {
>   fail = 0
>   nf =  2
> }
> 
> x =
> {
>   inf =  2
>   sup =  2.7321
>   dec = 0
> }

When the "domain" function is altered to do nothing, the output is again as expected:
> > AN_Solution1
> info =
> {
>   fail =  1
>   nf =  50
> }
> 
> x =
> {
>   inf =  2.6180
>   sup =  2.6180
> }

Regards

John Pryce

## Copyright (C) 2010 Arnold Neumaier, John Pryce
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License.

## AN_solution1
## Author: John Pryce j.d.pryce@xxxxxxxxxxxx
## Created: 2010-10-14
%This file is Arnold's solution to the "JDP Challenge" with minor syntax 
%errors removed. It now runs in Gnu Octave and gives expected results in 
%the single test in the function "AN_Solution1" below. When the "domain" 
%function is altered to do nothing, it gives the expected wrong 
%results.

function AN_Solution1
[info,x]= ExFixedPoint(@sqrtPlus1,-1,4,50)

%============================Arnold's code============================
% Consider an interval datatype that has for an interval x the
% floating-point data x.inf,x.sup, and optionally the integer x.dec
% (which makes the interval decorated).
%
% It is assumed that the following properties are invariants:
% Exactly one of the following holds:
%   (i) x.inf and x.sup satisfy x.inf<=x.sup; then x.dec<=2 if present.
%  (ii) x.inf and x.sup are NaN; then x.dec>=3 if present.
% Decorations are defined as in my recent position paper.

function x=interval(l,u)
 % constructs a decorated interval x
 % from given floating-point bounds l and u
 if l<=u,
   x.inf=l;x.sup=u;x.dec=isinf(u-l);
 else
   x.inf=NaN;x.sup=NaN;x.dec=4;
 end;

function x=domain(x)
 % declares an interval x to be a domain for a range computation
 x.dec=0;

function b=isEmpty(x)
 % checks emptiness of the interval x
 b=isnan(x.inf);

function b=subset(y,x)
 % checks whether y is a subset of x
 b=( y.inf>=x.inf && y.sup<=x.sup ) || isEmpty(y);

function b=isSafe(x)
 % checks a sufficient condition that the function f whose result
 % x=f(y) is passed as an argument is everywhere defined,
 % continuous, and bounded in the nonempty interval y
 if isfield(x,'dec'),
   b=(x.dec<1);
 else
   b=0;
 end;

function z=intersect(x,y)
 % intersects two intervals x and y;
 % the result z is a bare interval
 z.inf=max(x.inf,y.inf);
 z.sup=min(x.sup,y.sup);
 if z.inf>z.sup,
   z.inf=NaN;z.sup=NaN;
 end;

function z=add(x,y)
 % add two intervals x and y
 z.inf=x.inf+y.inf;
 z.sup=x.sup+y.sup;
 if isfield(x,'dec') && isfield(y,'dec'),
   z.dec=max(x.dec,y.dec);
 end;

function x=add(r,x)
 % add real number r and interval x
 x.inf=r+x.inf;
 x.sup=r+x.sup;

function x=sqrt(x)
 % compute square root of interval x
 if x.inf>=0,
   x.inf=Sqrt(x.inf);x.sup=Sqrt(x.sup);
 elseif x.sup<0,
   x.inf=NaN;x.sup=NaN;
   if isfield(x,'dec'), x.dec=3; end;
 else
   x.inf=0;x.sup=Sqrt(x.sup);
   if isfield(x,'dec'), x.dec=2; end;
 end;

function ans=Sqrt(x)
builtin("sqrt",x);

function x=sqrtPlus1(x)
 % evaluates f(x):=1+sqrt(x) at an interval argument x
 x=add(1,sqrt(x));

function [info,x]=ExFixedPoint(f,l,u,nfmax);
 % given an input interval [l,u], and a function handle f,
 % an interval x is produced that lies in [l,u].
 % if info.fail=0, x contains a fixed point of the function f
 % if info.fail=-1, x is Empty and f has no fixed point in [l,u]
 % if info.fail=1, no conclusion can be drawn after nfmax evaluations
 %
 % info.nf counts the number of function evaluations,
 % and is bounded by nfmax
 %
 x=interval(l,u);
 info.fail=1;
 info.nf=0;
 while 1,
   y=domain(x);        % declares y to be a domain in which the
                       % fixed-point property is checked
   x=f(y);             % interval evaluation
   info.nf=info.nf+1;  % update count
   if subset(x,y) && isSafe(x),
     % Brouwer's fixed-point theorem guarantees the existence
     % of a fixed point in x
     info.fail=0;
     return;
   end;
   if info.nf>=nfmax, break; end
   x=intersect(x,y);
   if isempty(x),
     info.fail=-1;
     return;
   end;
 end;

% It is easy to see that calling
%  [info,x]=ExFixedPoint(@sqrtPlus1,-1,4,50)
% produces (in exact arithmetic)
%   info.fail=0
%   info.nf=3
%   x.inf=2
%   x.sup=1+sqrt(3)
%   x.dec=0
% as it should be.