Applied Mathematics, 2010, 1, 520-528
doi:10.4236/am.2010.16069 Published Online December 2010 (http://www.SciRP.org/journal/am)
Scanning and Selection Methods Using Solution Boxes of
Inequality
Ferenc Kálovics
Analysis Department, University of Miskolc, Miskolc, Hungary
Received September 10, 2010; revised October 18, 2010; accepted October 22, 2010
Abstract
Numerical methods often reduce solving a complicated problem to a set of elementary problems. In some
previous papers, the author reduced the finding of solution boxes of a system of inequalities, the computation
of integral value with error bound, the approximation of global maxima to computing solution boxes of one
inequality. This paper contains new and improved methods for application of solution boxes of an inequality,
furthermore the computational aspects are discussed in detail.
Keywords: Inequality, Solution Box, Scanning of Set
1. Introduction
The paper [1] gives a complete description and code of a
process which is able to compute solution boxes of an
inequality automatically (using only the structure of the
appropriate expression). This means the following. Let
:m
g
DR R be a continuous multivariate real func-
tion, where
 


12 12
,,,,, ,
m m
Dxxxx xxis an open
box. Define the box


,, ,Bgc D  where ,,cD R


as an open box around c, in which the relation is the same
as between ()
g
c and α (it is supposed that ()gc


).
Thus, if () ,gc

then ()gx


for all1 (, ,)
m
x
xx


,, ,Bgc

if () ,gc

then ()gx

 for all


1
(, ,),,
m
x
xxBgc

. The C++ function segment
void solbox (double D[][3], double G[][4], double c[],
double alp, int m, int nt) of [1] can compute a box


,,Bgc

if the continuous multivariate real fun-
ction :m
g
DR R
is built of the well-known (univa-
riate real) elementary functions by the ordinary function
operations, and the expression ()
g
x is given in so-
called triple form ()G. This numerically coded form G
is easy to learn, but also [1] gives a Maple code for its
preparation. The parameter list of the segment is
D[][3] D, G[][4] G, c[]c, alpα, m

m,
nt number of triples in G and the output parameter is


,,Bgc

. The five numerical methods defined in the
following four sections are based on automatic compu-
tation of


,,Bgc

. Here, let us emphasize two facts
about solution boxes. 1) If() ,gc

then (,,)xBgc


implies () .gx

 Consequently, the box (,,)Bgc

of domain D is assigned to the interval (,)


 of
function values. Similarly, if ()gc

, then the box
(,,)Bgc

of domainDis assigned to the interval
(, )


of function values. The so-called interval exten-
sion functions used in interval methods (see e.g. in [2])
are inverse type functions, they assign intervals of fun-
ction values to boxes of domain. The handling and appli-
cation of these two tools require a highly different ma-
thematical and computational background. 2) The box
(,,)Bgc

is not a symmetrical box around c. Often it
has a large volume, although ()gc

 or ()gc

 is
only just satisfied. At the end of this section, some pro-
perties of our methods are mentioned. The notations,
names, definitions and discussions (similarly to [1]) are
simpler and clearer than they were in the former papers
of the author. Each of our five methods has both scan-
ning and selection features, with the names showing the
more characteristic feature. The methods for computation
of area and volume, for computation of integral values
and for finding global maxima can give an error bound to
the solution. The author is not aware of tools aside from
solution boxes of inequality for such a demanding han-
dling of these problems. The methods for finding a so-
lution of a system of equations and for finding of global
minima cannot give error bounds, they are only reliable
methods (which can be an important feature in case of
practical problems). The computational aspects of our
methods are discussed in detail in an appendix (the last
section).

F. KÁLOVICS
521
2. A Scanning Method for Area and Volume
Let a section set S be given by the system of inequalities
12
(,,,)0, 1,2,,,2,1,
im
fxxxinmn 
where the multivariate real functions 12 ,,,
n
ff f are
continuous on the closed box I and are built from the
well-known univariate real elementary functions. Our
aim is to give a good approximation value with gua-
ranted error bound for the area (the volume) of the set S.
The method is based on the following four principles. 1)
If the box I contains the set S, then the scanning of S
gives an approximation of the volume of S and the
scanning of the complementary set
I
S also facili-
tates the computation of an error bound. 2) If


1,,0Bfc
is a solution box to the inequality 1()0fx and


2,,0Bfc is a solution box to the inequality ,0)(
2xf
then the box

0,,0,,21 cfBcfB  is a solution box to
the system of the two inequalities. 3) If U and T are
m-dimensional boxes, then the set TU  can be
divided into (at most) 2m boxes easily. 4) The too small
boxes (the volume is too small) are filtered by the simple
condition .)(

Bvol Naturally, the value

has a
strong influence on the available error bound. The
algorithmic description of the method is as follows.
(a) Call (b)-(d). Let 2/,2/ epsepsepsvolvol

 .
Print , and volepsexb . Stop.
(b) Define the first element of an interval (box)
sequence

k
I by II 
1. Let ,1nob ,0

exb
,0vol ),(Ivoleps where ,,,volexbnob eps
denote the number of boxes in the sequence, the
number of the boxes examined, the approximating
value of )(Svol , and the error bound, respectively.
(c) Let .1 exbexb Compute the first 
i where
)(min)( cfcf i
i
 if ni

1 and c is the centre
of nob
I.
(c1) If 0)( 
cfi, then compute the box
(,,0) .
i
BBfcS IS

(The ‘worst ine-
quality’ is used here.) Let ).(Bvolepseps


(c2) If 0)( 
cfi, then
:nob BIand :(,,0),
i
BBBfc .,,1ni
Let vol = vol + vol (B), ).(Bvolepseps 
(d) Divide the set BInob  into nb boxes (if the set
is empty, then :0nb ). Filter the ‘unimportant’
(too small) boxes by the condition vol (box) ,


where  is a (small) given value. Place the
nbnb 
 new boxes into the box sequence


k
I as
nob th, )1( nob th,…,)1( 
nbnob th elements
and let 1  nbnobnob . If 0nob, then go to
(c). If ,0nob then go to the calling point.
The C++ program uses the above ‘reminding names’
and   .,,kapIcecIseI kk 

This algorithm
does not appear in other papers of the author. Now solve
the problem described by





22 22
12 12
1640,40,5,5,5,5xx xxI 
and illustrated in the Figure 1.
The exact area of ‘the double moon’ is
2
42π2π4π12.5664.  For ,10 4   ,105  
6
10   the area, the error bound, the real error, the
number of boxes examined and the running time (with
our Visual C++ version 6.0 code on a PC of two 2.2 GHz
processors) are
sec;03.0,4131,0015.0,0902.0,5679.12
sec;1.0,13051,0007.0,0283.0,5671.12
sec,3.0,41359,0000.0,0089.0,5664.12
respectively. The program scans ‘the double moon’ S
by solution boxes of an inequality system and it scans the
complementary set SI

by solution boxes of ‘wrong
inequalities’.
3. A scanning method for integrals
Let the definite integral


121 121
,,,
mm
V
f
xxxdxdxdx
 
 
be given, where the 1

m dimensional point set V is
described by the system of inequalities


12 1
,,,0,1, 2,,1,2,1,
im
fxxxin mn
  
the multivariate real functions ,f,
1
f12 ,,n ff are
continuous on the closed box VD and are built from
the well-known univariate real elementary functions. Let
us assume that we know (rough) lower and upper bounds
,0

m
x 0
m
x so that


12 112 1
,,,, ,,,.
mm m m
x
fxx xx xx xD


 
Our aim is to give a good approximation value with gua-
ranted error bound for the integral value. The method is
based on the following five principles. 1) The computa-
tion of the integral value is equivalent to the computation
of the volumes of the solution sets of the two systems of
inequalities (consider the geometrical meaning of simple
and double integrals, furthermore the definition of defi-
nite integrals)
Figure 1. Section set S.

F. KÁLOVICS
522


12 1
12 1
,,,0, 1,2,, 1
,
,,, 0,
im
mm
fxx xin
fxx xx


  


 



where












111 11
,,0,, ,,,,0,,
mm mm m
xxID xxxxxx
 
 
and


12 1
12 1
,,,0,1,2,, 1
,
,,, 0,
im
mm
fxx xin
fxx xx


 







where












11111
,,0,, ,,,,0,.
mmmmm
xxIDxxxxxx

 
The integral value is the difference of the first and
second volumes. 2) The scanning of the complementary
sets also facilitates the computation of an error bound. 3)
If


1,,0Bfc is a solution box to the inequality 0)(
1xf
and


2,,0Bfc is a solution box to the inequality
,0)(
2xf then the box




12
,,0,,0BfcBf cis a
solution box to the system of the two inequalities. 4) If
U and T are m-dimensional boxes, then the set
TU can be divided into (at most) 2m boxes easily. 5)
The too small boxes (the volume is too small) are filtered
by the simple condition .)(

Bvol The algorithmic
description of the method is as follows.
(a) If ,0
m
x then call (c)-(e) with







11 11
,,, ,,0,
mm m
Ixxxxx
 

and () ()
nm
fxfx x.
Print avi=avi+eps/2, eps=eps/2, exb and stop.
(b) If ,0
m
x ,0
m
x then call (c)-(e) with








11 11
,,, ,,0,
mm m
Ixxxxx
 

and mn xxfxf  )()( .
Let .,2/,2/ exbexbbepsepssepsaviavii


Call (c)-(e) with








11 11
,,, , ,0,
m mm
Ixxxxx
 

and mn xxfxf  )()( .
Print avii = avi i− avi − eps / 2, eps s = eps s + eps / 2,
exbb = exbb + exb and stop.
(c) Define the first element of an interval (box)
sequence 
k
Iby 1.
I
ILet ,1nob ,0

exb
,0avi ),(Ivolepswhere ,,,nobexbavieps
denote the number of boxes in the sequence, the
number of the boxes examined, the approximating
value of the integral value, the error bound,
respectively.
(d) Let .1 exbexb Compute the first iwhere
)(min)( cfcf i
i
 if ni 1 and c is the centre
of nob I .
(d1) If 0)( 
cfi, then compute the box
(,,0) .
i
BBfcS IS

(The ‘worst ine-
quality’ is used here.) Let ).(Bvolepseps


(d2) If 0)( 
cfi, then :nob
BI and
:(,,0),1,2,,.
i
BBBfc in


Let ),(Bvolaviavi


).(Bvolepseps
(e) Divide the set BInob

into nb boxes (if the set is
empty, then :0nb

). Filter the ‘unimportant’ (too
small) boxes by the condition vol (box) ,

 where

is a (small) given value. Place the nbnb 
 new
boxes into the box sequence 
k
I as th,nob


1th, ,(1)thnobnob nb elements and let
.1 nbnobnob If ,0nob then go to (d). If
,0

nob then go to the calling point.
The C++ program uses the above ‘reminding names’ and




,,.
kk
I
Ise cIcekap   This algorithm is a
strongly improved version of a method in [3]. Here solve
the problem


22
23 123
,
V
x
xdxdxdx

where V is described by the inequality


222
3123
2440,0,2.xxxx
(A triple integral with a cone region—the radius of the
base circle is 1 unit, the altitude is 2 units—is given.)
The exact value (which can be obtained by using cylin-
der coordinates) is11π/ 301.1519.For4 10 , 


5
10 , 

 6 10 

 the integral value, the error bound,
the real error, the number of boxes examined and the
running time (with our Visual C++ version 6.0 code on a
PC of two 2.2 GHz processors) are
sec;08.0,9053,0361.0,3423.0,1880.1
sec;4.0,44191,0062.0,1684.0,1581.1
sec,2,217361,0004.0,0816.0,1523.1
respectively. Observe that the ratios for the running times
sec2sec,4.0sec,08.0 move together with the ratios for
numbers of boxes examined ,217361,44191,9053 i.e.
the running time increases linearly. The method of [3]
mentioned (which has not this property) can produce
similar results in sec,146sec,5.3sec,2.0 respectively.
4. A Selection Method for System of Equations
Let the nonlinear system of equations




12 12
,,, 0,,,,,
m
im m
f
xxxxxxxIR 
1, 2,,;in


or in short form


0,,where:mn
f
xxI fIRR 
be given. We assume that the multivariate real functions
i
f are continuous on the closed interval (box) I and
built from the well-known real elementary functions. The

F. KÁLOVICS
523
aim is to find one root, i.e. to find a point z for which
 

)(zf . The method is based on the following four
principles. 1) Select the ‘most promising box’ in every
step. 2) Exclude a box from further examination in every
step. 3) If U and T are m-dimensional boxes, then the set
TU  can be divided into (at most) 2m boxes easily. 4)
The too small boxes are filtered by the simple condition
.)(

Bvol The algorithmic description of the method
is as follows.
(a) Call (b)-(e). Print   )(, zffbestczplace
(the best norm value of f), exb and stop.
(b) Define the first element of an interval (box)
sequence

i
I by II

1. Let 1

nob and
0exb , where nob denotes the number of boxes
in the sequence and exb denotes the number of the
boxes examined.
(c) Choose the first element 
i
I of the box sequence

i
I for which  )(cf is the smallest value (we
always use the ‘most promising box’). Interchange
the 
ith and nob th elements in the sequence.
(d) If ,)(  

cf where c is the centre of the interval
,
nob
I then:
(d1) Choose the first 
j
f from among
12
,,,
n
f
ff which gives the largest value at c
in absolute value (we may exclude the largest
box from further examination by this 
j
f).
(d2) Exclude the box )0,,(cfBB j
 around
centre c. Divide the set BInob  into nb
boxes (if the set is empty, then :0nb

).
Filter the ‘unimportant’ (too small) boxes by
the condition vol (box) ,

 where

is a
(small) given value. Place the nbnb
 new
boxes into the box sequence

i
I as th,nob

1th,,(1)thnobnob nb elements and
let .1 nbnobnob Go to (c).
(e) If ,)(
 

cf where c is the centre of the
interval ,
nob
I then go to the calling point.
The C++ program uses the above ‘reminding names’ and
 
,,
ii
I
Ise cIcekap   , eps

. This algo-
rithm is a simplified and improved version of a method
in [4]. Now solve the problem
 
2
13132
ln125 0,5 0,xxxxx

312 3
160,xxxx

34 4
exp2arctan710xx x.
It has one solution which will be searched in different
starting intervals .I The exact root is )7,5,3,1(z

.
For fixed 312 10,10    three different starting
intervals are used. The interval
I
, the error  zz

,
the number of examined boxes and the running time
(with our Visual C++ version 6.0 code on a PC of two
2.2 GHz processors) are






0,10 ,, 0,100.0010,179,0.0024sec;






10,10 ,,10,100.0018,284,0.0037sec;






0,100 ,, 0,1000.0011,370,0.0047sec,
respectively. Here the selection character is dominant,
because of very small

and small

. If the aim is to
produce a suitable starting vector for a fast (finishing)
method (e.g. a Newton-type method) in a more compli-
cated problem, then it is practical to utilize the scanning
character by greater

and

(e.g. 1,10 4 

).
5. A Scanning Method and a Selection
Method for Global Extremes
Consider the problem
maximize


12 1
,,,
m
fxx x


subject to


12 1
,,,0,1,2,, 1,2,1;
im
fxx xinmn
 








1
11 11 11
,,, ,,,,
m
mm m
xx DxxxxR

 
 
where the multivariate real functions i
f
, 1,,1in


and f are continuous on the box D and built from
the well-known elementary functions. Let us assume that
we know (rough) lower and upper bounds ,, m
mxx that


12 112 1
,,,, ,,,.
mm m m
x
fxx xxxx xD


 
Define the system of inequalities



12 1
12 1
,,,0,1,2,, 1
,,, 0,
im
mm
f
xx xin
fxx xx






where










121 1 11
,,,, ,,,,,,
mmm mm
xxxxIxxx xxx
 

or briefly


12 12
,,,0,1,2,,, ,,,,
im m
f
xxxinxxx I 
where




1212 1
,,,,,, .
nm mm
f
xx x fxx xx


The solution of our problem is a point of the solution set
S of this system of inequalities with the largest mth
coordinate. Our aim is to find a good approximation
obest of the maximum function value (belonging to the
objective function f and the set
A
of feasible points)
and to prove that the value epsobest  (where eps is
a supposed error bound) is an upper bound to the mth
coordinate of the solution. The method is based on the
following four principles. 1) If  0,,
1cfB is a solution
box to the inequality 0)(
1xf and

0,,
2cfB is a
solution box to the inequality ,0)(
2xf then the box

F. KÁLOVICS
524




12
,,0,,0BfcBf c is a solution box to the system
of the two inequalities. 2) If U and T are m-dimensional
boxes, then the set TU  can be divided into (at most)
2m boxes easily. 3) Here it is sufficient to do a fine scan-
ning only around the solution point, therefore a second
filter is used besides the simple one seen in the integral
algorithm.The too small boxes are filtered by the condi-
tion

)(Bvol and a second filter obestxm (where
m
x is the maximum value of the mth coordinate in the
box) saves much needless work. 4) To prove that the
value epsobest  is an upper bound to the maximum
value it is sufficient to see (because of the continuity of
f on D) that the ‘narrow stripe’








11 11
,,, ,,,2
m m
x xxxobestobest


 
has no common point with S. The algorithmic description
of the method is as follows.
(a) Call (b)-(d) with






1 1,,, , m m
Ixxxx
and 0.
  Print,place ,obest.exb Call (b)-(d) with







11 11
,,, ,,,2
m m
Ix xxxobestobest


 

and 0

. If m xobest , then print upper bound
.

obest Print exb and stop.
(b) Define the first element of an interval (box) sequence

k
I by II
1. Let ,1

nob ,0exb ,



obest
where obestexbnob ,, denote the number of boxes
in the sequence, the number of the boxes examined,
the approximating value of the global maximum, re-
spectively.
(c) Let .1exbexb Compute the first  i where
)(min)( cfcf i
i
 if ni

1 and c is the centre
of nob
I. If 0)( 
cfi and ,)()( obestccfcfmn 
then let ),,,(11 
m ccplace  ).(cfobest 
(c1) If 0)(
cfi, then compute the box
.)0,,( SIScfBB i 
(c2) If 0)( 
cfi, then :nob
BI and
:(,,0),
i
BBBfc 1,2,,.in
(d) Divide the set BInob  into nb boxes (if the set is
empty, then :0nb ). Filter the ‘unimportant’ boxes
by the conditions vol(box)

 and obestxm.
Place the nbnb 
 new boxes into the box se-
quence 
k
I as
th,nob

1th, ,(1)thnobnob nb elements and
let .1
nbnobnob If ,0nob then go to (c).
If ,0nob then go to the calling point.
The C++ program uses the above ‘reminding names’ and
 
,,.
kk
I
Ise cIcekap  
This algorithm does
not appear in other papers of the author referred to. Here
solve the problem described by




22
12 12
22
12 12
2cos3cos2164 0
max,
14 40
xx xx
xx xx
   


 


and illustrated, with



 ,5,5,5,5 


D in the Figures
2-3. The exact solution is )3/)2cos5cos2(,0,2(



).6273.0,0,2(

For 579 10,10,10, 

 be-
side fixed ,10 2   the solution vector, the number of
examined boxes (to the solution vector + to the supposed
error bound 2
10   ) and the running time (with our
Visual C++ version 6.0 code on a PC of two 2.2 GHz
processors) are
sec;045.0,3173160),6206.0,0063.0,0030.2( 

sec;21.0,27414431),6256.0,0007.0,0030.2( 

sec,71.0,26549407),6271.0,0002.0,0004.2( 


respectively.
Observe that the ‘linearity’ is excellent and the proof of
the supposed error bound requires insignificant work.
For a practical problem (with an uncertain error bound)
this work could increase considerably, therefore the se-
cond part of our examination is sometimes omitted.
Now consider the problem
minimize


12
,,,
m
f
xx x
subject to


12
,,,0, 1,2,,,1,1;
im
fxxxinm n

 





11 1
,,, ,,,,
m
mm m
x
xDxxxx R 
where the multivariate real functions ,
i
f1, ,in and
f are continuous on the box D and built from the well-
known elementary functions, furthermore the objective
function f is strictly increasing for every variable on D,
i.e. the best (the minimum) value of )(xf on a box
]),[,],,([11 mm




 appears at the ‘left lower vertex’
).,,( 1m





Our aim is to create a reliable method
for finding the minimum function value (belonging to the
objective function f and the set A of feasible points). The
method is based on the following four principles. 1)
Select the ‘most promising box’ (for which the box
centre best satisfies the inequalities describing the set A
of feasible points) at the beginning of the running,
hereby take advantage of the speciality of the objective
function in the filtering. 2) If  0,,
1cfB is a solution
box to the inequality0)(
1xf and
 0,,
2cfB is a solu-
Figures 2-3. Feasible point set A and graph of f over D.

F. KÁLOVICS
525
tion box to the inequality ,0)(
2xf then the box




12
,,0,,0BfcBf c is a solution box to the system
of the two inequalities. 3) If U and T are m-dimensional
boxes, then the set TU  can be divided into (at most)
2m boxes easily. 4) The ‘unimportant’ boxes are filtered
by the conditions vol(box)

 and obestf

)(

(

is the ‘left lower vertex’). The algorithmic descrip-
tion of the method is as follows.
(a) Call (b)-(e) with






1 1,,, , m m
I
Dxx xx  and
0

. Print .,,,nsbexbobestplace
(b) Define the first element of an interval (box)
sequence

i
Iby 1.
I
ILet ,1nob 0,exb

0,nsb ,obest where ,nob ,exb ,nsb obest
denote the number of boxes in the sequence, the
number of the boxes examined, the number of the
solution boxes in A, the best discovered value of the
objective function in A, respectively.
(c) If rsbnsb  (the partial selection works as long as
the number of solution boxes is less than the
required number), then choose the first element 
i
I
of the box sequence

i
I for which ),(mincf j
,1 nj  (c is the centre of )
i
I is the largest
value (we use the ‘most promising box’). Inter-
change the thiand thnob elements in the
sequence.
(d) Let .1 exbexb Take out the first  j where
)(min)( cfcf j
j
 if nj

1 and c is the centre
of nob I .
(d1) If 0)( 
cf j, then compute the box
.)0,,( SIScfBBj  (The ‘worst
inequality’ is used for exclusion.)
(d2) If 0)( 
cf j, then :1;:
nob
nsb nsbBI 
and :(,,0),
i
BBBfc 1, 2,,.in
If ,)()(1obestff n


where
1
(,, )
m

 is the ‘left lower vertex’ of
the box B of feasible points, then
).(,


fobestplace 
(e) Divide the set BInob  into nb boxes (if it is
empty, then :0nb ). Filter the ‘unimportant’ boxes
by the conditions vol (box)

 and obestf

)(

(

is the ‘left lower vertex’). Place the nbnb 

new boxes into the box sequence 
i
I as th,nob

1th,,(1)thnobnob nb elements and let
.1 nbnobnob If 0 nob , then go to (c).
Otherwise go to the calling point.
The C++ program uses the above ‘reminding names’ and
 
,,.
ii
I
Ise cIcekap   This algorithm shows
some similarity to a method in [5]. Here solve the
optimal design problem described by
2
13 245
741 minxxx xx
subject to
2
23 131
0.10.01 0,xxxxx


1
1/2
2
2
135 1
26732.25194.37 0,
xxx x











where 2
11
0.47 27.8013366.13,
x
x   

11/2
1/2 2
25
25
2
245 2
1
1
6684.7085.04 0,
x
x
xxx
x













where
 
1/2
222
52 52
0.4713.90 13342.35 1
x
xxx    ,
2
23
231 21
235
77.75
1.32921.250,0.350,xxx xx
xxx







1/2
2
125125
0, 1.50.110,xxxxx x

 
13314 2
150,350,3000 1000;xxxxx x

 














12 5
,,,100,120,80,100, 1,11 ,1,11 , 1,11,xxx D
which satisfies the above conditions. For1,


1
10 , 

2 10 , 

beside fixed ,100rsb the
objective function value belongs to the best discovered
place, the number of boxes examined, the number of
solution boxes in the set A of feasible points and the
running time (with our Visual C++ version 6.0 code on a
PC of two 2.2 GHz processors) are
sec;31.0,907,6168,71.4849
sec;1.2,2367,46607,46.4836
sec,17,7052,379336,09.4722
respectively. Similar results (obtained by much more
complicated methods) can be seen in [5]. The volume of
the starting box D is fairly large (5 104 units),
therefore the use of too small

(a too fine scanning of
D) could require a long time to run (on our PC).
6. Appendix: C++ Codes for the Five
Algorithms
Our Visual C++ version 6.0 programs have 5 segments
for each of the five algorithms. The first 3 segments are
the same in these codes. For computing the solution
boxes of an inequality the function segment solbox is
used, which handles the function


solbox:,,,,,( , ,),DGc mntBgc

 
where D is the domain box of the multivariate real
function g, G is a numerically coded form of g, ,Dc

,R


m is the number of the variables in g and nt is
the number of triples in G. The complete segment

F. KÁLOVICS
526
solbox (which is the base of all five methods) is
published in [1]. The function segment fval computes
the function values from the numerically coded form, i.e.
it handles the function

fval:,,,Gcntg c
where G is a numerically coded form of the multivariate
real function g, c is a point of the domain and nt is the
number of triples in G. To divide the difference of a
closed m-dimensional box U and an open m-dimensional
box T into closed boxes, 12 ,,,
nb
box boxbox which do
not contain common interior points, our function seg-
ment divi handles the function
  
12
divi:, ,,,,,
nb
U Tmboxboxboxnb
An algorithmic description and a two-dimensional illus-
tration of this simple process can be seen e.g. in [3]. The
functions of the fourth segments are


scanvol:,,,,(,,),
F
Imnvoleps exb  


scanint:, ,,,(,,),
F
Imnavi eps exb  


selecteqs:,,, ,,(,,),
F
Im nplacefbestexb  


scanmax:, ,,,(,,),
F
Imnplace obestexb  


selectmin:, ,,,,(,,,),
F
Irsb m nplace obestexb nsb  
where F contains all the multivariate functions needed in
triple form and the other parameters are the same as in
the algorithmic descriptions. The task of the fifth (main)
segments is given at the beginning of the algorithmic
descriptions. A complete code of the first method is as
follows.
#include <iostream.h>
#include <math.h>
double Ise[100000][10][3], Ice[100000][10];
/* THE OUTPUT PARAMETERS OF THE NEXT 4 FUNCTIONS */
double B[10][3];
double gc;
double boxes[20][10][3]; int nb;
double vol,eps; int exb;
/* FUNCTION: SOLUTION BOXES OF INEQUALITY */
void solbox(double D[][3],double G[][4],double c[],double alp,int m,int nt)
{see in [1]}
/* FUNCTION: FUNCTION VALUE g(c)*/
void fval(double G[][4],double c[],int nt)
{double fv[100],x,y,w; int i,j,k,l; const double Pi=3.14159265;
for (i=1; i<=nt; i++)
{j=(int)G[i][1]; k=(int)G[i][2]; l=(int)G[i][3]; w=G[i][3];
if (k<0) x=c[-k]; else x=fv[k]; if (j>=3 && j<=5) y=fv[l];
switch (j)
{case 1:fv[i]=x+w;break; case 2:fv[i]=x*w;break; case 3:fv[i]=x+y;break;
case 4:fv[i]=x/y;break; case 5:fv[i]=x*y;break; case 6:fv[i]=pow(x,w);break;
case 7:fv[i]=exp(x);break; case 8:fv[i]=log(x);break; case 9:fv[i]=fabs(x);break;
case 10:fv[i]=sin(x);break; case 11:fv[i]=cos(x);break; case 12:fv[i]=tan(x);break;
case 13:fv[i]=1/tan(x);break; case 14:fv[i]=asin(x);break; case 15:fv[i]=acos(x);break;
case 16:fv[i]=atan(x);break; case 17:fv[i]=Pi/2-atan(x);break;}}
gc=fv[nt];}
/* FUNCTION: DIFFERENCE OF TWO m-DIMENSIONAL BOXES */
void divi(double U[][3],double T[][3],int m)
{double ax[10][3],len[10],x; int ind[10],i,j,k;
nb=0; for (i=1; i<=m; i++) {ax[i][1]=U[i][1]; ax[i][2]=U[i][2]; len[i]=U[i][2]-U[i][1];}
/*Permutation of indexes by side lengths of the box U*/
for (i=1; i<=m; i++) {j=1; for (k=1; k<=m; k++)
{if (len[k]>len[i]) j=j+1; if (len[k]==len[i] && k<i) j=j+1;}; ind[j]=i;}
/*Dividing the set U-T*/
for (i=1; i<=m; i++) {j=ind[i]; x=ax[j][1];
if (ax[j][1]<T[j][1]) {ax[j][1]=T[j][1]; nb=nb+1;
for (k=1; k<=m; k++) {boxes[nb][k][1]=ax[k][1]; boxes[nb][k][2]=ax[k][2];}

F. KÁLOVICS
527
boxes[nb][j][1]=x; boxes[nb][j][2]=T[j][1];}
x=ax[j][2];
if (ax[j][2]>T[j][2]) {ax[j][2]=T[j][2]; nb=nb+1;
for (k=1; k<=m; k++) {boxes[nb][k][1]=ax[k][1]; boxes[nb][k][2]=ax[k][2];}
boxes[nb][j][1]=T[j][2]; boxes[nb][j][2]=x;}}}
/* FUNCTION: COMPUTING AREA AND VOLUME */
void scanvol(double F[][100][4],double I[][3],double kap,int m,int n)
{double ce[10],ax[100][4],xx[10][3],res[10][3],minf,vo; int nob,i,j,k,iast,N;
for (i=1; i<=m; i++) {Ise[1][i][1]=I[i][1]; Ise[1][i][2]=I[i][2]; Ice[1][i]=(I[i][1]+I[i][2])/2;}
vo=1; for (i=1; i<=m; i++) vo=vo*(I[i][2]-I[i][1]);
nob=1; exb=0; vol=0.; eps=vo;
/*Using solution boxes of inequality*/
while (nob>0)
{exb=exb+1; for (i=1; i<=m; i++) ce[i]=Ice[nob][i]; minf=1.e10;
for (i=1; i<=n; i++) {N=(int)F[i][0][0];
for (j=1; j<=N; j++) for (k=1; k<=3; k++) ax[j][k]=F[i][j][k];
fval(ax,ce,N); if (gc<minf) {minf=gc; iast=i;}}
if (minf<0)
{N=(int)F[iast][0][0]; for (i=1; i<=N; i++) for (j=1; j<=3; j++) ax[i][j]=F[iast][i][j];
solbox(I,ax,ce,0.,m,N); vo=1.;
for (i=1; i<=m; i++) {res[i][1]=B[i][1]; res[i][2]=B[i][2];
if (Ise[nob][i][1] > B[i][1]) B[i][1]=Ise[nob][i][1];
if (Ise[nob][i][2] < B[i][2]) B[i][2]=Ise[nob][i][2]; vo=vo*(B[i][2]-B[i][1]);}
eps=eps-vo;}
if (minf>=0)
{for (i=1; i<=m; i++) {res[i][1]=Ise[nob][i][1]; res[i][2]=Ise[nob][i][2];}
for (i=1; i<=n; i++)
{N=(int)F[i][0][0]; for (j=1; j<=N; j++) for (k=1; k<=3; k++) ax[j][k]=F[i][j][k];
solbox(I,ax,ce,0.,m,N);
for (j=1; j<=m; j++)
{if (B[j][1]>res[j][1]) res[j][1]=B[j][1]; if (B[j][2]<res[j][2]) res[j][2]=B[j][2];}}; vo=1;
for (i=1; i<=m; i++) vo=vo*(res[i][2]-res[i][1]); vol=vol+vo; eps=eps-vo;}
for (i=1; i<=m; i++) {xx[i][1]=Ise[nob][i][1]; xx[i][2]=Ise[nob][i][2];}
nob=nob-1;
/*Dividing the actual box*/
divi(xx,res,m);
for (i=1; i<=nb; i++)
{vo=1.; for (j=1; j<=m; j++) vo=vo*(boxes[i][j][2]-boxes[i][j][1]);
if (vo>kap) {nob=nob+1;
for (j=1; j<=m; j++)
{Ise[nob][j][1]=boxes[i][j][1]; Ise[nob][j][2]=boxes[i][j][2];
Ice[nob][j]=(boxes[i][j][1]+boxes[i][j][2])/2;}}}}}
/* THE CALLING SEGMENT, example 1 */
void main()
{double F[10][100][4],I[10][3],kap; int m,n,i,j;
double f1[6][3]= {{6,-1,2},{6,-2,2},{2,1,-1},{2,2,-4},{3,3,4},{1,5,16.}};
double f2[4][3]= {{6,-1,2},{6,-2,2},{3,1,2},{1,3,-4}};
m=2; n=2;
F[1][0][0]=6; for (i=1; i<=6; i++) for (j=1; j<=3; j++) F[1][i][j]=f1[i-1][j-1];
F[2][0][0]=4; for (i=1; i<=4; i++) for (j=1; j<=3; j++) F[2][i][j]=f2[i-1][j-1];
I[1][1]=-5.; I[1][2]=5.; I[2][1]=-5.; I[2][2]=5.;
kap=1.e-6; scanvol(F,I,kap,m,n); vol=vol+eps/2; eps=eps/2;
cout <<"Volume, error bound: "<< vol <<" "<< eps << endl;
cout <<"Examined boxes: "<< exb << endl;}

F. KÁLOVICS 528
To avoid the dimension trouble, the two large arrays
Ise and Ice (which could contain thousands of box
data) are declared at the beginning of the program. The
calling (main) segment uses a simple trick (push down of
indexes) for the easy handling of triple forms. The codes
of the further four methods are very similar to this code;
the author would gladly send them to interested readers
in e-mail as attached files. Finally two remarks: 1) The
computation efforts (the evaluation times) belonging to
),,(

cgB and )(cg can be characterized well enough
by the formula: effort   10),,(

cgB effort).(cg 2)
We always used floating point arithmetic for computing
solution boxes. Since these boxes are computed by lower
estimates, we have never happened to obtain a faulty
result because of the effect of rounding errors.
7. References
[1] F. Kálovics, “A New Tool: Solution Boxes of Inequality,”
Journal of Software Engineering and Applications, Vol. 3,
No. 8, 2010, pp. 737-745.
[2] R. Hammer, M. Hocks, U. Kulisch and D. Ratz, “Numer-
ical Toolbox for Verified Computing”, Springer-Verlag,
Berlin, 1993.
[3] F. Kálovics, “Zones and Integrals,” Journal of Computa-
tional and Applied Mathematics, Vol. 182, No. 2, 2005,
pp. 243-251.
[4] F. Kálovics and G. Mészáros, “Box Valued Functions in
Solving Systems of Equations and Inequalities,” Numeri-
cal Algorithms, Vol. 36, No. 1, 2004, pp. 1-12.
[5] F. Kálovics, “Solving Nonlinear Constrained Minimiza-
tion Problems with a New Interval Valued Function,” Re-
liable Computing, Vol. 5, No. 4, 1999, pp. 395-406.