### Paper Menu >>

### Journal Menu >>

Applied Mathematics, 2010, 1, 520-528 doi:10.4236/am.2010.16069 Published Online December 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. AM Scanning and Selection Methods Using Solution Boxes of Inequality Ferenc Kálovics Analysis Department, University of Miskolc, Miskolc, Hungary E-mail: matkf@uni-miskolc.hu 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 xxis 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 Copyright © 2010 SciRes. AM 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)( 2xf 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 ,1nob ,0 exb ,0vol ),(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 BIand :(,,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 0nob, then go to (c). If ,0nob 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 Copyright © 2010 SciRes. AM 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)( 1xf and 2,,0Bfc is a solution box to the inequality ,0)( 2xf then the box 12 ,,0,,0BfcBf cis 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 ILet ,1nob ,0 exb ,0avi ),(Ivolepswhere ,,,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 ,0nob 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 Copyright © 2010 SciRes. AM 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 0exb , 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)( 1xf and 0,, 2cfB is a solution box to the inequality ,0)( 2xf then the box F. KÁLOVICS Copyright © 2010 SciRes. AM 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 ,0exb , 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 .1exbexb 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 ,0nob then go to (c). If ,0nob 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)( 1xf and 0,, 2cfB is a solu- Figures 2-3. Feasible point set A and graph of f over D. F. KÁLOVICS Copyright © 2010 SciRes. AM 525 tion box to the inequality ,0)( 2xf 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 ILet ,1nob 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 thiand 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 ,100rsb 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 Copyright © 2010 SciRes. AM 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 Copyright © 2010 SciRes. AM 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 Copyright © 2010 SciRes. AM 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. |