UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Sequentially localizable functionals. Booth, Raymond Sydney 1965

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-UBC_1966_A1 B6.pdf [ 6.41MB ]
Metadata
JSON: 831-1.0080573.json
JSON-LD: 831-1.0080573-ld.json
RDF/XML (Pretty): 831-1.0080573-rdf.xml
RDF/JSON: 831-1.0080573-rdf.json
Turtle: 831-1.0080573-turtle.txt
N-Triples: 831-1.0080573-rdf-ntriples.txt
Original Record: 831-1.0080573-source.json
Full Text
831-1.0080573-fulltext.txt
Citation
831-1.0080573.ris

Full Text

SEQUENTIALLY LOCALIZABLE FUNCTIONALS by RAYMOND S. BOOTH B„Sc. T J n i v e r s i t y of Otago, Nev Zealand, 1961 M.Sc U n i v e r s i t y of Otago, Nev Zealand, 1962 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY i n the Department of MATHEMATICS ¥e a c c e p t t h i s t h e s i s as conforming t o the r e q u i r e d s t a n d a r d U n i v e r s i t y of B r i t i s h Columbia December, 1965 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of Bri t ish Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that per-mission for extensive copying of this thesis for scholarly purposes may be granted by the Head of my Department or by his representatives,, It is understood that copying or p u b l i -cation of this thesis for financial gain shall not be allowed without my written permission. Department of kg i^^-f-/'c ^  .  The University of Bri t ish Columbia Vancouver 8, Canada Date 2 O -t-U . r P ^ c r c o ^ t g e ^ f ^ ^ ^ The U n i v e r s i t y of B r i t i s h Columbia FACULTY OF GRADUATE STUDIES PROGRAMME OF THE FINAL ORAL EXAMINATION FOR THE DEGREE OF DOCTOR OF PHILOSOPHY RAYMOND SIDNEY: BOOTH B.A. 3 U n i v e r s i t y of Otago, 1961 M . S c U n i v e r s i t y of Otago, 1962 THURSDAY, DECEMBER 16th, 1965, AT 3:30 P„M„ IN ROOM 225, MATHEMATICS BUILDING COMMITTEE IN CHARGE Research Supervisor: : Z. A. Melzak E x t e r n a l Examiner: J . E. L. Peck of Chairman: I. McT. Cowan P. B u l l e n C. Froese E. E. G r a n i r e r I. Hacking Z. A. Melzak B. N. Moyls U n i v e r s i t y of A l b e r t a , Calgary SEQUENTIALLY LOCALIZABLE FUNCTIGNALS ABSTRACT A standard way of f i n d i n g the unique zero on (0, 1 ) of a continuous decreasing functions w i t h f(0) f ( l ) < 0, i s to t e s t the s i g n of f ( l / 2 ) , then the sign of f ( l / 4 ) ( i f f ( l / 2 ) < 0) or the s i g n of f(3/4) ( i f f ( l / 2 ) >-€)), e t c . In t h i s way, the zero of f i s l o c a l i z e d i n n steps to an i n t e r v a l of length 2~ n. The unique maximum of a unimodal f u n c t i o n on £ o , 1~J can be s i m i l a r l y l o c a l i z e d , but the unique maximum of a unimodal f u n c t i o n on the u n i t square cannot. We s t a r t by g e n e r a l i z i n g these problems: l e t A be'a compact subset of E n , l e t F be a set of r e a l - v a l u e d f u n c t i o n s on A, and f o r each f i n F l e t S ( f ) be a point i n the Ca r t e s i a n product A^; S ( f ) i s c a l l e d a f u n c t i o n a l on F. Examples of such f u n c t i o n a l s are zeros, extrema, i n f l e x i o n p o i n t s , saddle p o i n t s , etc.,-as w e l l as sets of these. A t e s t f u n c t i o n T i s a f u n c t i o n of m r e a l v a r i a b l e s , which takes up only a f i n i t e number (^.2) of d i s t i n c t values. An a b s c i s s a set X-^  i s an ordered m-tuple ( X ] _ i , . . . X J J ^ ) ,, w i t h each X j ^ i n A. A s e q u e n t i a l s t r a t e g y i s a way of s e l e c t i n g a b s c i s s a sets Xj_, X£,..., where the knowledge of T ( f (x-^) , „ . , , f ( x ^ ) ) i s used to determine X i + i . The N-th set of indeterminacy f o r S ( f ) i s the l a r g e s t subset of i n which S ( f ) can l i e s c o n s i s t e n t w i t h the r e s u l t s of the f i r s t N - l t e s t s . A functional;. S ( f ) i s s e q u e n t i a l l y l o c a l i z a b l e i f a t e s t f u n c t i o n T.and a s e q u e n t i a l s t r a t e g y e x i s t , such that f o r every f i n F the sets of.indeterminacy s h r i n k to a point (which must then be S ( f ) i t s e l f ) . F i r s t , , s e v e r a l c o n d i t i o n s are given to ensure the se q u e n t i a l l o c a l i z a b i l i t y of a f u n c t i o n a l , these are presented i n terms of c e r t a i n topologies induced on Ak and.in terms of c o n t r a c t i o n maps. I t i s then shown that i f a f u n c t i o n a l i s l o c a l i z a b l e , there e x i s t s an optimal s t r a t e g y under which the sets of indeterminacy converge f a s t e s t ; f u r t h e r , the speed of l o c a l i z a t i o n i s always exponential. Next, the concept o f a. random strategy, and of random l o c a l i z a b i l i t y i s introduced, and i t i s shown that i n many cases random l o c a l i z a b i l i t y and s e q u e n t i a l l o c a l i z a b i l i t y are eq u i v a l e n t . A l s o , the speed.of the former i s not too much worse than.the speed.of the l a t t e r . F i n a l l y , optimal and near-optimal s t r a t e g i e s are worked out f o r some f u n c t i o n a l s of i n t e r e s t . GRADUATE STUDIES D i f f e r e n t i a l Equations F u n c t i o n a l A n a l y s i s Complex V a r i a b l e Convexity D i f f e r e n t i a l Geometry C. Clark. D, Bures R, Cleveland Z. A, Melzak E. L u f t ABSTRACT Supervisor: Dr. Z.A. Melzak A standard way of finding the unique zero of a continuous decreasing function f(x) defined on the closed i n t e r v a l [ 0 , l ] , where f(0) > 0 > f ( l ) , i s the bisection method. One tests the X 3 sign of f ( ^ ) f "this i s positive, then one tests the sign of f(j)> and i f negative, one tests f ( ^ ) , etc. In t h i s way, the zero i s lo c a l i z e d i n n steps to an int e r v a l of length 2~n. The unique maximum point of a unimodal function defined on [0,l] can be loca-l i z e d i n a similar manner; however, the maximum point of a unimodal function defined on a square cannot be so lo c a l i z e d . We generalize these problems. Let D be a compact subset of Euclidean q-dimensional space, and l e t P be a family of r e a l -valued functions defined on D. To each f(-F, associate a unique poin.t S(f) i n D x D x D Xoo. x D (m times). The mapping S i s called a functional. An abscissa set .-J i s an ordered k-tuple X = (x^,X2> . <. ., x^) where x^€ D„ A .:^ .'at?^ ;,y i s a rule for selecting a sequence of abscissa sets 7. 9 X,, X^, o „ o, X , .... where each X depends on X., and the o i 2 n n I values of a function f€F at the elements of X., i = 0, 1, «, 0(n-l)o The functional i s said to be lo c a l i z a b l e i f there i s a strategy such that the diameter of the largest set K n which may contain S ( f ) , consistent with the observations of the values of f at the abscissa sets X., i ss 0, 1, 0 . . , n - l , decreases to zero as n -» independently o f t h e f u n c t i o n f € F . A t e s t f u n c t i o n i s a map T, w i t h f i n i t e r a n g e V, w h i c h a s s o c i a t e s w i t h e a c h a b s c i s s a s e t X and t h e v a l u e s o f a f u n c t i o n f a t t h e e l e m e n t s o f X, an e l e m e n t o f V. I t i s shown i n c h a p t e r 2 t h a t many f u n c t i o n a l s c a n be l o c a l i z e d w i t h t h e a i d o f a s u i t a b l e t e s t f u n c t i o n . S e v e r a l n e c e s s a r y and s u f f i c i e n t c o n d i t i o n s f o r a f u n c t i o n a l t o be l o c a l i z a b l e a r e g i v e n . I n p a r t i c u l a r , l o c a l i -z a t i o n i s c h a r a c t e r i z e d i n t e r m s o f t h e s t r e n g t h o f a c e r t a i n t o p o l o g y i n d u c e d on D m by t h e s t r a t e g y o r t e s t f u n c t i o n . I n c h a p t e r 3, t h e s p e e d o f l o c a l i z a t i o n i s c o n s i d e r e d , and i t i s shown t h a t i n most c a s e s t h e s p e e d i s e x p o n e n t i a l . A measure o f t h e s p e e d i s d e f i n e d , and s u f f i c i e n t c o n d i t i o n s a r e g i v e n f o r t h e e x i s t e n c e o f an o p t i m a l s t r a t e g y . C h a p t e r 4 i s c o n c e r n e d w i t h random s t r a t e g i e s and random l o c a l i z a b i l i t y , and i t i s shown t h a t l o c a . l i z a b i l i t y o f t e n i m p l i e s random l o c a l i z a b i l i t y . The p a r t i c u l a r p r o b l e m o f l o c a t i n g t h e z e r o o f a c o n t i n u o u s monotone f u n c t i o n d e f i n e d on an i n t e r v a l b y random l o c a l i z a t i o n i s c o n s i d e r e d i n d e t a i l , and compared w i t h t h e c l a s s i c b i s e c t i o n method. F i n a l l y , o p t i m a l and n e a r - o p t i m a l s t r a t e g i e s a r e w o r k e d o u t f o r a number o f f u n c t i o n a l s o f s p e c i a l i n t e r e s t . TABLE OF CONTENTS CHAPTER 1 INTRODUCTION 1 - 1 The bisection problem 1 - 2 Outline of the general problem 1 - 3 The unimodal problem 1 - 4 An example of n o n - l o c a l i z a b i l i t y 1 - 5 A two-dimensional problem 1 - 6 Remarks CHAPTER 2 LOCALIZABILITY 2 - 1 Basic d e f i n i t i o n s 2 - 2 Test functions 2 - 3 Examples 2 - 4 L-topology 2 - 5 A simultaneous search problem CHAPTER 3 RATE OF LOCALIZATION 3 - 1 Speed 3 - 2 Speed with Lipschitz Conditions 3 - 3 Exponents 3 - 4 Optimal Strategies page CHAPTER 4 RANDOM LOCALIZABILITY 68 4 - 1 D e f i n i t i o n s 68 4 - 2 " General theorems and examples 72 4 - 3 Random search f o r a zero 76 4 - 4 J o i n t p r o b a b i l i t y d i s t r i b u t i o n 79 4 - 5 Expected values 91 4 - 6 The behaviour of e (a) 99 n 4 - 7 Rectangular d e n s i t y f u n c t i o n 118 CHAPTER 5 LOCALIZATION OF ZEROES OF DERIVATIVES 121 5 - 1 General r e s u l t s 121 5 - 2 D e r i v a t i v e s of odd order 127 BIBLIOGRAPHY 130 i ACKNOWLEDGEMENTS I w i s h t o thank my s u p e r v i s o r , Dr. Z.A. Melzak, f o r s u g g e s t i n g the t o p i c f o r t h i s t h e s i s , and f o r p r o -v i d i n g much v a l u a b l e guidance throughout my graduate s t u d i e s and d u r i n g the p r e p a r a t i o n and w r i t i n g of t h i s t h e s i s . The f i n a n c i a l a s s i s t a n c e of the Canadian U n i v e r s i t i e s ' F o u n d a t i o n v i a a s c h o l a r s h i p which made i t p o s s i b l e f o r me t o study i n Canada i s g r a t e f u l l y acknow-l e d g e d . 1 CHAPTER 1 INTRODUCTION 1 - 1 The b i s e c t i o n problem One of the o l d e s t methods of approximating the zero of a f u n c t i o n i s the b i s e c t i o n method. Suppose f i s any continuous r e a l - v a l u e d f u n c t i o n d e f i n e d on the c l o s e d i n t e r v a l [ 0 , 1 ] of the r e a l l i n e such that f ( 0 ) > 0 > f ( l ) , f posse s s i n g a unique zero a i n t h i s i n t e r v a l . By computing the s i g n of f ( ^ ) ) i t can be deter-mined whether 0 < a < ^ , a = 77, or ^  < a < 1; the f i r s t of these holds i f f{ ^ ) < 0, the second i f f ( ^ ) = 0, and the t h i r d i f f (-•) > 0„ Ignoring the p o s s i b i l i t y t h a t f (^) = 0, when c l e a r l y no f u r t h e r computation i s needed, the p o s s i b l e p o s i t i o n of a i s r e s -t r i c t e d to an i n t e r v a l of len g t h at most 7j . By c o n s i d e r i n g the sign of f at the mid-point of the new i n t e r v a l , one can i n the same way, r e s t r i c t the p o s s i b l e p o s i t i o n of a to an i n t e r v a l of l e n g t h at most ^. By s u c c e s s i v e l y com-pu t i n g the s i g n of f at the mid-point of the l a r g e s t i n t e r v a l to which a can belong, on the b a s i s of previous e v a l u a t i o n s of f; one can, a f t e r n steps i n v o l v i n g the e v a l u a t i o n of f at n p o i n t s , r e s t r i c t a to an i n t e r v a l of length at most 2 n . Thus by t a k i n g n s u f f i c i e n t l y l a r g e , a can be approximated as a c c u r a t e l y as de-s i r e d . 1 - 2 O u t l i n e of the general problem More g e n e r a l l y , l e t P be a f a m i l y of r e a l - v a l u e d func-t i o n s d e f i n e d on a given domain D. Suppose that the values of 2 f ( x ) , x€D, f€F, are a l l unknown, but can always be computed for any given x£D 0 It i s desired to locate a pa r t i c u l a r point associ-ated with the function f (e.g., a zero, a maximum-point, a point of inflexion) as accurately as possible by finding the values of f(x) for a suitable sequence of properly selected points x€D. The mapping which assigns to each member f of P a point, w i l l be called a functional; the image of the mapping w i l l be written S(f)„ S(f) can be regarded as a point i n the Cartesian product D x D x D o o „ x D ( m times), where m i s a positive integer. This would allow consideration of the problem of approximating m zeros of a suitable function simultaneously. The problem of finding methods for approximating such a point has been considered for special cases since before the time of Newton, especially i f severe r e s t r i c t i o n s are placed on F„ For example, there are a very large number of ways in which one may approximate a solution to the equation f(x),= 0 i f f i s a polynomial i n x of small degree. Ve are concerned here with problems which can be solved by generalizing the bisection method, and, with this i n mind, make the following general assumtpions. (i) The domain D i s a compact convex subset of f i n i t e -dimensional Euclidean space. The class of functions F i s usually taken to be the largest possible class for which the problem i s well-defined, provided n o n - t r i v i a l results may be obtained. The class P for the bisection problem, i.e„, the class of a l l real continuous functions f defined on D = [0,l] such that f(0) > 0 > f ( l ) , possessing a unique zero a, 0 < a < 1; i s typic a l of the type of class P to be considered. ( i i ) If x€D i s given, and f€F, then no errors are made i n computing the numerical value of f ( x ) . This property means that some care i s needed i n practice when using the subsequent results to be obtained. The case of errors can be handled i n some i n -stances by stochastic approximation methods as shown by Robbins and Monro [8], but we shall not be concerned with this subject here, ( i i i ) The choice of points x i n D for which f(x) i s computed i s to be determined on a sequential basis. That i s , suppose n i s a positive integer, and already n points x^,X2» x n€ D have been selected, and f(x^),f(xg)>••• ^ ( x n ) have been evaluated, for some f?P. The choice of the next point x n + ^ ^ ^  m a v depend on the points x^,X2? x n, and the numerical values f(x^), f ( x 2 ) , . 0 0 f ( x n ) . For example, in the bisection problem, we choose x^ = ijj and evaluate f ^ ) . We "then choose X2= ^  i f f(~ ) < 0; x 2 = | i f f(§) > 0. (iv) A rule for determining the selection of the successive elements x i n D at which a function f€F i s to be evaluated shall n be given before any computations are made. Such a rule w i l l be called a strategy. The strategy for the bisection problem i s simple; find the largest i n t e r v a l to which the zero of the function f can belong on the basis of previous evaluations ( i f any), and select the mid-point of the i n t e r v a l . There are, of course, many alternative strategies which could be used to approximate the zero of f. One of the points of t r i s e c t i o n would s u f f i c e . (v) Before any computations are made, i t must be known that a l l points 3(f), f£F, belong to some set K q of (bounded) diameter d Q. K q i s a subset of a Cartesian product of D with i t s e l f a f i n i t e number of times. The diameter d i s that defined by the o J usual Euclidean metric. For the bisection problem we may take K Q as the int e r v a l D, with d =1. o 4 (vi) For a given strategy M, a function f€F and any posi-tive integer n, ve can define a set K n(f,M) which i s known to contain S(f), after f has been evaluated at n sets of points i n D determined successively by the strategy M. K n(f,M) i s a (possibly improper) subset of K q . As a measure of the worth of the str a -tegy, and of the speed of the determination of the functional, we set d'(M) = sup d[K (f,M)] n f 6 p n where d[K n(f,M)] i s the diameter of the set K Q(f,M). Ve shall say that the functional i s l o c a l i z a b l e with respect to the strategy M i f lim d' (M) = 0 ; _ n ' n — CO t h i s means that S(f) can be successively r e s t r i c t e d to sets K n(f,M) whose diameters decrease to zero. For example, in the bisection problem, ve have d^ (M) < 2 - n for a l l positive integers n. So, for this example, the functional i s l o c a l i z a b l e by the b i -section strategy. It i s sometimes convenient to say that S(f) i s l o c a l i -zable. No confusion arises, since f i s a typi c a l member of F, and the set of a l l points S(f) for f€F, i s just the range of the functional. Ve can nov raise some questions of a general nature con-cerning l o c a l i z a b i l i t y . (i) For given D and F, i s there a strategy M v i t h respect to vhich the functional i s l o c a l i z a b l e ? ( i i ) If there does not exist such an M, can F be r e s t r i c t e d 5 to a reasonably large subclass F' of F, vhere l o c a l i z a t i o n i s nov possible? ( i i i ) If l o c a l i z a t i o n i s possible, can one determine a best strategy in some sense? If, by best we mean one for vhich the diameters d^(M) decrease fastest, then for the bisection problem, the best strategy i s eas i l y seen to be the one described in sec-tion 1-1. It i s possible to take other factors into consideration i n deciding vhat i s to be regarded as optimal. For example, the cost of evaluating f(x) for some f€F, x€D, computer time involved, or the calculations used to determine the successive points at vhich f i s to be evaluated, could a l l be taken into account. Even i f we ask for a minimal d^(M), there are two d i s t i n c t cases to be considered: (i) strategies for which an a p r i o r i upper bound N i s given on the number of points i n D at which a function may be evaluated, ( i i ) strategies which are allowed to continue i n d e f i n i t e l y . Should WR 'ask for a strategy M ( i f there i s one) which minimizes djJj(M), where N i s decided i n advance of any computations; the strategy M may not be so effective i f , after evaluating a function f at N points in D, we then decide to l o c a l i z e more exactly by further computation. Kiefe'r,[6], defines optimality for the case where N i s given i n advance, using the term minimax, or €-minimax, and considers optimal strategies for some of the problems we discuss l a t e r . His treatment of the problem however, d i f f e r s from ours. In general, we are concerned with strategies for which the number of observations 'is allowed to increase i n d e f i n i t e l y , Ve can also ask for optimal strategies under the con-d i t i o n that computations cease as soon as the point being l o c a l i z e d i s known t o b e l o n g t o a s e t w i t h d i a m e t e r a t most €, where 6 i s g i v e n . A s t r a t e g y o f a d i f f e r e n t t y p e w i l l c o n c e r n us i n c h a p t e r 4. R a t h e r t h a n s e l e c t i n g t h e p o i n t s X p X ^ , . . . , x n i n D by a f i x e d r u l e , we c o n s i d e r t h e p o s s i b i l i t y o f s e l e c t i o n 'by c h a n c e ' . As an i l l u s t r a t i o n , we t a k e t h e b i s e c t i o n p r o b l e m , w i t h D = [ 0 , l ] , and d e f i n e a d e n s i t y f u n c t i o n f j ) ( t ) , 0 < t < 1. I n -s t e a d o f s e l e c t i n g x^= ^ , and e v a l u a t i n g fC^O* where f € F , s u p p o s e we s e l e c t x^ a r b i t r a r i l y i n D, i n s u c h a way t h a t f o r a l l r e a l numbers a,b w i t h 0 < a < b < 1, t h e p r o b a b i l i t y t h a t a < x, < b i s v 1 J J <!>(t)dt. ' a As b e f o r e , we have X ; L < S ( f ) < 1 i f f ( X ; L ) > 0 0 < S ( f ) < xx i f f ( x x ) < 0 . So, S ( f ) c a n be r e s t r i c t e d t o one o f t h e two i n t e r v a l s [0,x^] o r [ x ^ , l ] . W i t h t h e d e n s i t y f u n c t i o n r e d e f i n e d on t h e new i n t e r v a l , we c a n s i m i l a r l y s e l e c t a p o i n t X £ > and c o n t i n u e t h i s p r o c e d u r e i n d e f i n i t e l y . Ve t h e n a s k , what i s t h e e x p e c t e d v a l u e o f t h e l e n g t h o f i n t e r v a l t o w h i c h S ( f ) i s c o n f i n e d a f t e r f i s e v a l u a t e d a t n p o i n t s i n D? One o f o u r aims i s t o compare t h i s w i t h t h e b i s e c t i o n s t r a t e g y . R.S. P i n k h a m [7] has c o n s i d e r e d t h i s p r o b l e m w i t h t h e r e s t r i c t i o n t h a t one s t o p s c o m p u t a t i o n as s o o n as S ( f ) i s l o c a l i z e d t o an i n t e r v a l o f l e n g t h b , where h i s g i v e n . Ve p o s t p o n e d e f i n i t i o n s a nd t h e o r e m s u n t i l c h a p t e r s 2 and 3. The r e m a i n d e r o f t h i s c h a p t e r g i v e s some e x a m p l e s t o i l l u s t r a t e t h e p r e v i o u s r e m a r k s . 7 1 - 3 Unimodal problem For completeness and fu t u r e reference, ve i n s e r t the problem of l o c a l i z i n g the maximum (or minimum) p o i n t of a unimodal f u n c t i o n . This vas f i r s t solved by K i e f e r [5] i n 1953, and i s d e a l t v i t h i n d e t a i l by Bellman and Dreyfus [ l ] . Let D = [a,b] be a compact i n t e r v a l on the r e a l l i n e . L et F be the c l a s s of a l l continuous unimodal r e a l - v a l u e d func-t i o n s d e f i n e d on D v h i c h possess a (unique) maximum p o i n t . That i s , i f f€F, then f i s s t r i c t l y i n c r e a s i n g on [ a , S ( f ) ] f i s s t r i c t l y decreasing on [ s ( f ) , b ] f o r some p o i n t S(f) i n D. Ve a l l o v the improper case S ( f ) = a or S ( f ) = b. The problem i s to l o c a l i z e the maximum p o i n t at S ( f ) . The s t r a t e g y uses the f a c t t h a t i f f€F, and x,y are any tvo p o i n t s i n D, v i t h x < y, then a < S ( f ) < y i f f (x) > f (y) x < S(f) < b i f f ( x ) < f ( y ) x < S ( f ) < y i f f ( x ) = f ( y ) . I f these c o n d i t i o n s do not hold, then there vould be more than one maximum p o i n t , c o n t r a r y to hypothesis. Thus ve can alvays l o c a l i z e S ( f ) to a s u b i n t e r v a l of D of l e n g t h < Max {y-a, b-x}, and t h i s i s a proper s u b i n t e r v a l of D of len g t h < c(b-a), vhere c i s a f i x e d constant l e s s than 1 P independent of a and b, provided x and y are p r o p e r l y chosen. By i t e r a t i o n , ve can s u c c e s s i v e l y r e s t r i c t S ( f ) to a sequence of i n t e r v a l s whose lengths decrease to zero. So the f u n c t i o n a l i s l o c a l i zable o In order to f i n d the best s t r a t e g y , that i s , the s t r a t e g y M which minimizes d w(M), N being the number of p o i n t s i n D at 8 vhich f may be evaluated; i t i s convenient to ask the following •question. If D i s the interval [0, Lj^], what i s the largest possible value of LJJ, so that S(f) can be r e s t r i c t e d to a unit i n t e r v a l by computing f at most N points i n D ? The answer i s given by the following theorem. Theorem 1.1 If the sequence P n i s defined by the equations F = F = 1 o 1 x F = F , + F „ for a l l integers n > 2, n n-1 n-2 6 — ' then L F L < F n for a l l positive integers n. Moreover, i f € > 0 i s arbitrary, there exists a strategy v i t h respect to vhich S(f) can be l o c a l i z e d to an interval of unit length, i f F L = — n > 2 n l+€ L = L, = 1 . o 1 F i s the nth Fibonaccian number, n We omit the proof of this theorem since an excellent account of i t i s given by Bellman and Dreyfus [ l ] . However, we wish t o give an outline of the proof since the proofs of some lat e r theorems are based on similar arguments. That L Q = = 1 i s obvious, because evaluating f at just one point i n D yields no information about S(f)„ Suppose n i s an integer > 2 , and two points x^,x^ are selected so that 0 < x 0 < x, < L . ~ 2. I — n One can by evaluating f at x^ and X£, r e s t r i c t S(f) to either [0,x^] or [x2,L n]" Since, to r e s t r i c t S(f) further, a t h i r d point must be chosen, the ine q u a l i t i e s (1.1) x l ^ L n - l (1.2) L n - x 2 * L n - l ' must hold i f S(f) can be l o c a l i z e d to a unit i n t e r v a l , by 9 evaluating f at at most n points i n D. No matter where a t h i r d point i s chosen, the inequalities (1.3) *2*\-2 ( 1 . 4 ) V l S L - 2 must also hold, otherwise again more than n points would be required. So, by addition of (1.2) and (1.3) <X'5> L n ^ L n - l + x 2 L < L , + L _ n — n-1 n-2 for a l l integers n > 2, which gives L < P n — n for a l l non-negative integers n. The second part of the theorem follows from the fact that i f f i s defined on [0,L n], n > 2, we can by choosing x^= L n - 1 and ^2 = l J n_2 a n c^ evaluating f at these points, r e s t r i c t S(f) to an i n t e r v a l of length Ln_^« Ve need choose only one new point x^, to r e s t r i c t S(f) to an interval of length L n ^ since the points X2>x^ are i n t e r i o r respectively to [0,x^] or fx2>L n]« By iteration, we can repeat u n t i l S(f) i s r e s t r i c t e d to an i n t e r v a l of length 2, where the value of f i s known at the mid-point of t h i s i n t e r v a l , and one f i n a l selection x^ may be made. Since we cannot choose x n at the mid-point, we choose x n at an arb i t r a r y distance £ from the mid-point, allowing one to r e s t r i c t S(f) to an i n t e r v a l of length l+€ . By a change of scale by the factor l + €, the result follows. Corollary 1.2 If P i s i n i t i a l l y defined on the interval D = [ o , l ] , i f € > 0 and an integer n > 2 are given, then for any f€F, S(f) can be l o c a l i z e d to an interval of length (l+e)/P by 10 e v a l u a t i n g f a t a s e q u e n c e o f n s u i t a b l e p o i n t s i n D„ Remark 1.3 The i n t e g e r n must be g i v e n a p r i o r i , s i n c e t h e s e l e c t i o n o f t h e f i r s t two p o i n t s and x^ depend on n. I n d e e d , i f D = [ 0 , 1 ] , = P ,/ F and x„ = F J P 1 n-1' n 2 n-2' n x, However, a n o t h e r s t r a t e g y f o r l o c a l i z i n g S ( f ) s u g g e s t s i t s e l f , w h i c h does n o t r e q u i r e t h a t n be d e c i d e d i n a d v a n c e . I t i s w e l l known t h a t n+1 ( i i ) l i m F / F , = « 1.618 . n' n-1 „ n -• eo 2 T h i s l e a d s t o what we w i l l r e f e r t o as t h e g o l d e n -mean s t r a t e g y . S t a r t i n g w i t h domain D = [ 0 , l ] , we s e l e c t t h e two p o i n t s _ _ x _ 75 - 1 _ , ,/5 - 1 1 ~ 2 2 ~ 2 w h i c h d i v i d e D i n t h e g o l d e n r a t i o , and f o r some f € F , e v a l u a t e f ( x ^ ) and f ( x 2 ) . We t h a n have e i t h e r S ( f ) 6 [ O j X ^ w i t h f ( x 2 ) known o r S ( f ) e [ x 2 , l ] w i t h f U - ^ known. /~5 — 1 B o t h t h e s e i n t e r v a l s have l e n g t h Y- ^ — , and i n e i t h e r case;, one new p o i n t x-j c a n be c h o s e n so t h a t a g a i n we have two p o i n t s w h i c h d i v i d e t h e a p p r o p r i a t e i n t e r v a l i n t h e g o l d e n r a t i o . By i t e r a t i n g t h i s i n d e f i n i t e l y , we c a n r e s t r i c t S ( f ) t o an i n t e r v a l 11 ( 1•= _ 1 \ n-1 o f l e n g t h a t most I ^ — ^ — y , e v a l u a t i n g f a t n > 2 s u i t a b l e p o i n t s i n D. 1 - 4 An example o f n o n - l o c a l i z a b i l i t y We show t h a t i f D and F a r e g i v e n , F b e i n g a u n i o n o f two c l a s s e s P' and F", t h e n t h e f u n c t i o n a l d e f i n e d by F i s n o t n e c e s s a r i l y l o c a l i z a b l e , e ven i f l o c a l i z a t i o n i s p o s s i b l e when P i s i n t e r s e c t e d w i t h e i t h e r F' o r P". I n e s s e n c e , t h i s c a n h appen b e c a u s e f o r e v e r y s t r a t e g y w h i c h one m i g h t u s e t o l o c a l i z e t h e f u n c t i o n a l , t h e r e e x i s t f u n c t i o n s f f P f o r w h i c h t h e r e i s no way o f d e c i d i n g w h e t h e r f p P ' o r f ? P " . L e t D be t h e c l o s e d u n i t i n t e r v a l [ 0 , l ] . D e f i n e F' t o be t h e c l a s s o f a l l c o n t i n u o u s r e a l - v a l u e d u n i m o d a l f u n c t i o n s f w i t h domain D, w h i c h p o s s e s s a u n i q u e maximum a t a p o i n t S ( f ) , 0 < S ( f ) < 1. D e f i n e F" t o be t h e c l a s s o f a l l c o n t i n u o u s r e a l -v a l u e d u n i m o d a l f u n c t i o n s f w i t h d o m a i n -D, w h i c h p o s s e s s a u n i q u e minimum a t a p o i n t S ( f ) , 0 < S ( f ) < 1. D e f i n e P t o be t h e u n i o n o f P' and F". E a c h member o f P has a u n i q u e e x t r e m e p o i n t i n t h e i n t e r i o r o f D. I n c o n t r a s t t o t h e f u n c t i o n s o f t h e o r e m 1.1, we do n o t a l l o w t h e c a s e s S ( f ) = 0 o r S ( f ) = 1; h e n c e t h e two c l a s s e s P' and P" a r e d i s j o i n t . Now, by t h e r e s u l t s o f s e c t i o n 1-3, i f f € F , ve c a n l o c a l i z e S ( f ) by t h e g o l d e n - m e a n s t r a t e g y i f i t i s k n o v n t h a t f € F ' . We c a n a l s o l o c a l i z e S ( f ) i f i t i s known t h a t feP". Thus t o show t h a t t h e f u n c t i o n a l i s n o t l o c a l i z a b l e ^ we must d e m o n s t r a t e t h a t , f o r e v e r y s t r a t e g y , t h e r e i s a f u n c t i o n f£F f o r w h i c h t h e r e i s i n s u f f i c i e n t i n f o r m a t i o n t o d e c i d e w h e t h e r f ^ F ' o r f € F " . T h i s i s a c o n s e q u e n c e o f t h e f o l l o v i n g lemma. 12 Lemma 1.4 Let G > 0 be given, and l e t k be an a r b i t r a r y p o s i t i v e i n t e g e r . For any set of k d i s t i n c t p o i n t s , x.^ f x3» • • • x k "*-n ^ •such that 0 < x^ < < x^ < . . . < x^ < 1 there e x i s t two f u n c t i o n s f and g s a t i s f y i n g ( i ) f€F' g€P" ( i i ) f ( x ± ) = i = 1, 2, ... k ( i i i ) |s(f) - S(g)| > Proof Let u = min {x^,€} i f x^ > 0 u = min {x^jC} i f x^ = 0 v = max {x^,l-€} i f x^ < 1 v = max t x ^ - ^ j l - f } i f x^ = 1 Define f and g by the equations i f 0 < x < v , 1+v v < x S T ~ f ( x ) = V 4x - 3v i f i f ^ < x < l •2x i f 0 < x < ~ g(x) = i 4x - 3u i f | < x < u V x i f u < x < 1 I t i s easy to check t h a t f and.g s a t i s f y the requirements of the 1emma. C o r o l l a r y 1.5 The f u n c t i o n a l d e f i n e d by the set of a l l extreme p o i n t s of the members of F i s not l o c a l i z a b l e . For, since € and k are a r b i t r a r y , we cannot guarantee to reduce the diameter of the s m a l l e s t set which may con t a i n S(f) to any number l e s s than 1, If ve exclude the p o s s i b i l i t y t h a t f o r f€F, S(f) may be a r b i t r a r i l y near e i t h e r end of D, then l o c a l i z a t i o n i s p o s s i b l e . 13 For i t i s then easy to determine whether f?F' or f€F" by evaluating f at two points of a subinterval of D which contains an end-point of D, but cannot contain S ( f ) . This argument gives the following lemma whose proof we omit. Lemma 1.6 Let 6, 0 < 6 < 1 be given. Let F^ be the subclass of F for vhich 0 < 6 < S(f) for a l l f € F 6 . Then the functional determined by the extreme points of members of F^ i s l o c a l i z a b l e . If such a 6 i s not knovn, ve can alvays attempt to lo c a l i z e S(f), under the two separate assumptions f€?' and f f F " , by the golden-mean strategy. After evaluating f at (n+l) points of D under each assumption, ve get tvo closed intervals K^(f), K£(f) i n D, each of length < ~ 1 j , such that S(f) € K'(f) i f f6F' n S(f) f K"(f) i f f€P" o n If one of these intervals does not contain an end-point of D? ve can apply lemma 1.6, and determine vhether f€F' or f€F,,„ If not, the most that ve can say i s that S(f) € IP(f) U K«(f), vhere K'(f) contains one end-point of D, and K"(f) contains the n n other. 1 - 5 A two-dimensional problem We wish nov to consider the problem of l o c a l i z i n g the maximum points of a suitable class of functions defined on a square i n the Euclidean plane. Nev d i f f i c u l t i e s arise i n problems vhere the dimension of the domain D i s greater than 1, not a l l of vhich are due to the lack of ordering of points i n D. Generally speaking, the obvious analogues of the one-dimensional case do not put 14 s u f f i c i e n t r e s t r i c t i o n s on the class P i n order to get l o e a l i z a -b i l i t y . We take three different classes of functions for the present problem, to show what situations may arise under the d i f f e r e n t assumptions. Let D be the unit square D = {(x,y) I 0 < x < 1, 0 < y < 1} in the Euclidean plane. The three classes of functions to be considered are defined as follows: (i) i s the class of a l l real continuous functions defined on D which possess a unique (relative) maximum point i n the i n t e r i o r of D, ( i i ) F£ i s the subclass of F^ such that for every real number 6, and a l l f ^ ^ > the set [x€D | f(x) > (3 J i s a s t r i c t l y convex figure. Alternatively, we may say that for every real number 6, the l e v e l curve {x£D | f(x) = B) i s a convex curve containing no l i n e segments. ( i i i ) F^ i s the subclass of F^ such that for some fixed con-stant a > 0, every real number B, and a l l f€F^, {x€D| f ( X ) > 6} has diameter d, implies that {x€D| f(x) > 8} contains a disc of radius ad. This requirement can be rephrased by the statements a l l l e v e l curves are of 'bounded eccentricity'. It i s understood that the terms distance, diameter, etc., are referred to the usual Euclidean metric. In a l l three cases, S(f) i s to be the point in D where f attains i t s maximum value. The conditions on F^ are quite weak, and i t i s almost obvious that l o c a l i z a t i o n i s not possible. Indeed, we show below that i f f€F^, then no matter how many points in D are chosen for evaluating f, S(f) may s t i l l be anywhere i n D except on a f i n i t e 15 number of l i n e segments. The c o n d i t i o n s on F 2 are the d i r e c t analogue of" those i n theorem 1.1. The assumption that the l e v e l curves do not c o n t a i n l i n e segments i s simply to ensure t h a t i f three p o i n t s x^,x 2,x.j i n D l i e on a l i n e , v i t h x 2 betveen x^ and x 3, and i f f U ^ = f ( x 3 ) , then f ( x 2 ) > f (x±) = f {x^) . Ve s h a l l shov t h a t i f f€P 2» then S(f) can, a f t e r e v a l u a t i n g f at a s u i t a b l e f i n i t e number of p o i n t s , always be r e s t r i c t e d to a convex set of a r b i t r a r i l y small area. Ve cannot however, prove that the f u n c t i o n a l i s l o c a l i z a b l e , f o r the f u n c t i o n s f£f 2« A convex set of small area and l a r g e diameter i s neces-s a r i l y long and t h i n ; i . e . the r a t i o of diameter to width must be l a r g e . The assumptions f o r the c l a s s F^ guarantee t h a t i f f€F^ and S ( f ) can be r e s t r i c t e d to a set of small area, then t h a t set must n e c e s s a r i l y have small diameter. I t turns out t h a t ve get l o c a l i z a b i l i t y f o r the c l a s s F^, even v i t h o u t the convexity c o n d i t i o n as i n F^o The proof of t h i s was obtained by A.M. Gleason [ 2 ] , i n 1961. Our r e s u l t f o r the c l a s s F^ i s summarized by the f o l -i o v i n g lemma. Lemma 1.7 Let k be an a r b i t r a r y p o s i t i v e i n t e g e r , and l e t x^,x 2,...x^j be a set of k d i s t i n c t p o i n t s i n D. Let f i n F^ be such t h a t S(f) ^ x^, i - l,2,...k. Let H be the set of a l l p o i n t s z i n D such that the c l o s e d l i n e segment from z to S(f) contains an x. . 1 Then, i f y belongs to both the i n t e r i o r of D and the complement of H, there i s a f€F^ such t h a t ( i ) gix.^) = f ( x i ) i = 1,2,...k, ( i i ) S(g) = y . 16 Proof Let L denote the closed l i n e segment joining y and S ( f ) . Since H i s closed r e l a t i v e to D, and L does not meet H, there exists an open rectangle U containing L, and contained i n the intersection of the complement of H with the i n t e r i o r of D. Let L' be the l i n e through S(f) perpenducular to L, and l e t V be that open half space bounded by L 1 which contains y. Now, every point x in the closure of U fl V can be written uniquely i n the form x = 6y + (1 - £)x' where 0 < •© < 1 and x' l i e s on the boundary of U fl V . Define the function g by the equations g(x) = f(x) i f x belongs to both D and the complement of UTW g(y) = f ( S ( f ) ) + 1 g(x) = e g(y) + ( l - e ) f ( x ' ) i f x i s i n UHV and ' x = Oy + ( l - e ) x ' . It i s easy to check that g€F^, S(g)=y and g(x^) = f(x^) i=l , 2,...k. Thus i f f€P^> and f i s evaluated at any f i n i t e number of points i n D, S(f) may s t i l l be anywhere i n D except perhaps on a f i n i t e number of l i n e segments. Before considering the class ~&2> v e state a theorem on plane convex sets which w i l l be needed l a t e r . The theorem was o r i g i n a l l y proved by A. Vinternitz. An account of i t i s to be found i n the book by Yaglom and Boltyanskii [lO] on page 36. Theorem 1.8 Let K be a plane convex figure with area A. Then any li n e L which passes through the centroid of K divides K into two convex subsets, of areas A^ and k^i where f A < A x < | A. • 17 Ve w i s h t o show t h a t i f f £ F 2 , "then t h e p o s s i b l e p o s i t i o n o f S ( f ) c a n be r e s t r i c t e d to a c o n v e x s e t o f a r b i t r a r i l y s m a l l a r e a b y e v a l u a t i n g f a t a s u i t a b l e f i n i t e s e q u e n c e o f p o i n t s i n D. I t i s enough t o show t h e e x i s t e n c e o f a c o n s t a n t c < 1, s u c h t h a t i f A i s any c o n v e x s u b s e t o f D, and, f o r some f € F 2 ^ s known t h a t S ( f ) € A, t h e n , b y e v a l u a t i n g f a t s u i t a b l e p o i n t s i n A, one c a n r e s t r i c t S ( f ) t o a c e r t a i n h a l f - s p a c e and t h e n c e t o a c o n v e x s e t B, where t h e a r e a o f B i s l e s s t h a n c t i m e s t h e a r e a o f A. Ve u s e t h e f o l l o w i n g n o t a t i o n : A w i l l d e n o t e an a r b i t r a r y c o n v e x s u b s e t o f D w i t h p o s i t i v e a r e a . I f x a , X p a r e two p o i n t s o f A, t h e n [ x a , X p ] w i l l d e n o t e t h e l i n e segment j o i n i n g x and x R , i n c l u d i n g i t s end p o i n t s . I f x , x n , and x , a r e t h r e e d i s t i n c t n o n - c o l l i n e a r p o i n t s a' 8 y i n t h e i n t e r i o r o f A, we c a n c o m p l e t e t h e t r i a n g l e w i t h v e r t i c e s a t x a , X p , and x^ , and e x t e n d a l l s i d e s t o meet t h e b o u n d a r y o f A. Of t h e s i x open r e g i o n s ( o p e n r e l a t i v e t o A) e x t e r i o r t o t h e t r i a n g l e so f o r m e d , ^ a f i y d e n o t e t h e one whose c l o s u r e has t h e v e r t e x x ^, and o n l y t h e v e r t e x x^. i n common w i t h t h e t r i a n g l e . Ve p r o v e f i r s t a lemma t o d e s c r i b e how, by e v a l u a t i n g a f u n c t i o n f € F 2 a ^ t h r e e p o i n t s , t h e p o s i t i o n o f S ( f ) may be r e s t r i c t e d . T h e r e f o l l o w s a lemma t o show how S ( f ) c a n t h e n be r e s t r i c t e d t o a s u i t a b l e h a l f - s p a c e . Lemma 1.9 I f f £ F 2 , A i s g i v e n , S ( f ) ? A , x a , X p , x^ , a r e any x h r e e d i s t i n c t n o n - c o l l i n e a r p o i n t s i n A, and i f f ( x a ) < M i n { f ( x ) , f ( x y ) } 18 t h e n P r o o f I f S ( f ) € I""1 o , t h e n t h e r e i s a p o i n t z i n [x„,x ] • apy P Y s u c h t h a t x ^ l i e s i n t h e l i n e segment [ z , S ( f ) ] . B u t t h i s i m p l i e s t h a t f ( z ) < f ( x a ) < M i n { f ( x p ) , f ( x y ) } w h i c h c o n t r a d i c t s t h e a s s u m p t i o n s c o n c e r n i n g F£ • Lemma 1.10 Suppose A i s g i v e n , f ? ^ ' a n ( ^ ^ ( f ) € A. L e t 5 be t h e c e n t r o i d o f A, and l e t £ > 0 be g i v e n , € l e s s t h a n h a l f t h e s h o r t e s t d i s t a n c e f r o m ? t o t h e b o u n d a r y o f A. Then t h e r e i s a s t r a t e g y w i t h r e s p e c t t o w h i c h S ( f ) c a n be r e s t r i c t e d t o a h a l f -p l a n e w i t h b o u n d a r y t a n g e n t t o t h e c i r c l e , w i t h c e n t r e a t § and r a d i u s 2(F . P r o o f S e l e c t p o i n t s x ^ , X 2 » x ^ , i n A t o f o r m t h e v e r t i c e s o f an e q u i l a t e r a l t r i a n g l e w i t h c e n t r e a t § and edge l e n g t h l e s s t h a n €. E v a l u a t e f ( x ^ ) , i = 1, 2, 3. By r e l a b e l l i n g t h e t h r e e p o i n t s i f n e c e s s a r y , i t may be assumed t h a t f ( x - j ) < M i n [ f (x^) , f ( x ^ ) } B y lemma 1.9, S ( f ) £ P 321 S e l e c t p o i n t s x^, x,_, i n A, s u c h t h a t t h e p o i n t s x - ^ , X 2>x^,x^ f o r m t h e v e r t i c e s o f a r e c t a n g l e w i t h x^ as t h e m i d -p o i n t o f [ x ^ , x ^ ] . By c o n v e x i t y , a t l e a s t one o f t h e numbers f ( x ^ ) , f ( x j - ) i s l e s s t h a n f ( x ^ ) . By r e l a b e l l i n g x ^ and x,_ i f n e c e s s a r y , i t may be assumed t h a t f ( x ^ ) < f ( x ^ ) and b y r e l a b e l l i n g x-^  and X 2 i f n e c e s s a r y , [ x ^ , x ^ ] i s a s i d e o f t h e r e c t a n g l e . One now has S ( f ) P , by lemma 1.9, s i n c e 413 f ( x 4 ) < f ( x 3 ) < f ( x x ) . 1 19 There are two p o s s i b i l i t i e s (i) f ( x 5 ) < f ( x 3 ) . Then S(f) £ P 5 2 3 , and the two regions ^4^3 s> ^ 523 "together define a half-space not containing S(f) vhich s a t i s f i e s the requirements of the lemma. In this case the proof i s finished. ( i i ) f ( x 5 ) > f ( x 3 ) . Then S(f) £ ^325 > a n d s i n c e a l s 0 S(f) £ ^2,21 ' ^ ^315 ' v^L-'-c'1 a r e g l o n with a vertex angle of 120° at x 3. Proceeding from case ( i i ) , select tvo points x^ and X j so that the three points x^,x 3, and Xj, are co l l i n e a r , and per-pendicular to [ x 2 , x 3 ] , and such that the t r i p l e s at points x-^,x^,x^ and x2,x^,x^. are c o l l i n e a r . Evaluate f(x^) and f ( x ^ ) , and vithout loss of generality, assume that f U 6 ) < f ( x 3 ) . Then S(f) £ P 6 1 7 by lemma 1.9. Again there are two p o s s i b i l i t i e s (i) f ( x 7 ) < f ( x 3 ) , from which i t follows that S(f)^nj 2 3, and as i n case (i) above the theorem i s proved. ( i i ) f(x^)> f ( x 3 ) , whence S(f) £ ^ 317' v n i c n i s a region v i t h a vertex angle of 150° at x 3 > Clearly, the vhole processes can be continued for as long as desired. At each stage, two new points are selected, ly i n g on a li n e through x 3, which i s perpendicular to the bisector of the vertex angle at x 3 of the largest region which i s known not to contain S ( f ) . Either we f i n i s h at some stage when case (i) applies, or, for some two points x^ and x^, we have, after n stages involving the evaluation of f at 2n+l points i n A, S(f) ft > which i s a region with vertex angle at x 3 equal to 1 n 0 180° - (—) 240 , n > 1. M o r e o v e r , e v e r y p o i n t a t w h i c h f i s e v a l u a t e d i s w i t h i n d i s t a n c e 2€ o f % and so b e l o n g s t o A. The l i n e segments [ x ^ x ^ ] and [ x ^ j X ^ ] c a n be e x t e n d e d b e y o n d x^ t o meet t h e b o u n d a r y o f A a t two p o i n t s y ^ and y^ r e s p e c t i v e l y . An e a s y c a l c u l a t i o n shows t h a t t h e l i n e segment [y a>y"p] p a s s e s w i t h i n 2£ o f ? , p r o v i d e d n i s c h o s e n so t h a t 2 - n < 3€/ (4 T" d) , where d i s t h e d i a m e t e r o f A. T h i s c o m p l e t e s t h e p r o o f o f t h e lemma. Theorem 1.11 I f A i s an a r b i t r a r y c o n v e x s u b s e t o f D, and i f f g F ^ , S ( f ) € A , t h e n by e v a l u a t i n g f a t a s u i t a b l e s e q u e n c e o f p o i n t s i n A, S ( f ) c a n be r e s t r i c t e d t o a c o n v e x s e t B, B z> A, where t h e ( a r e a o f B) < | ( a r e a o f A ) . P r o o f L e t A d e n o t e t h e a r e a o f A, and d t h e d i a m e t e r o f A. L e t § be t h e c e n t r o i d o f A, and w t h e s h o r t e s t d i s t a n c e f r o m % t o t h e b o u n d a r y o f A. I f w = 0, t h e n A = 0 and t h e r e i s n o t h i n g t o p r o v e , so w i t h o u t l o s s o f g e n e r a l i t y , w > 0 , A > 0 , d > 0 . Choose € > 0, so t h a t € < M i n { ^ , } , and c h o o s e a p o s i t i v e i n t e g e r n so t h a t 2 " n < 36 / (4TT d) . A p p l y t h e s t r a t e g y d e f i n e d by lemma 1.10. S i n c e £ < ^ > a l l p o i n t s a t w h i c h f i s e v a l u a t e d b e l o n g t o A. Hence S ( f ) c a n be r e s t r i c t e d t o a h a l f - s p a c e c o n t a i n i n g ? w h i c h i s b o u n d e d by a l i n e t a n g e n t t o t h e c i r c l e w i t h c e n t r e a t § and r a d i u s l e s s t h a n 2£, by e v a l u a t i n g f a t 2n+l s u i t a b l e p o i n t s i n A I f B i s t h e i n t e r s e c t i o n o f A w i t h t h i s h a l f - s p a c e , t h e n B i s c o n v e x , and by t h e o r e m 1.8, t h e a r e a o f B i s b ounded above by 5 A ^ A + 2£d„ S i n c e € < YhTd ' ^ e ^ ^ e o r e m ^ s P r o v e d , 21 C o r o l l a r y 1.12 I f f ? ^ ' "there e x i s t s a s t r a t e g y s u c h t h a t S ( f ) c a n be s u c c e s s i v e l y l o c a l i z e d t o a s e q u e n c e A = D 3 A, 3 A« 3 , o o => A, =5 , „ „ o 1 2 k o f c o n v e x s u b s e t s o f D, where f o r e a c h p o s i t i v e i n t e g e r k, t h e 2 \k a r e a o f A^ i s l e s s t h a n o r e q u a l t o (^O . Remark The c h o i c e o f t h e i n t e g e r n i n lemma 1.10 i s d e t e r m i n e d by t h e i n e q u a l i t i e s 2 ~ n < 3€ / (4TT d) < A / ( 2 4 n ~ d 2 ) . T h i s means t h a t n c a n n o t n e c e s s a r i l y be a f i x e d i n t e g e r , s i n c e t h e l o n g e r and t h i n n e r A i s , t h e l a r g e r n h a s t o be. K i e f e r [ 6 ] has shown t h a t c o n t a i n s a s u b c l a s s f o r w h i c h , i f f C P ^ * t h e n S ( f ) c a n n o t be r e s t r i c t e d t o a c o n v e x s e t o f d i a m e t e r l e s s t h a n 1. Hence, i f f€?2> w e c a n n o t e x p e c t t o do b e t t e r t h a n t o r e s t r i c t S ( f ) t o a c o n v e x s e t o f a r b i t r a r i l y s m a l l a r e a . We s h a l l n o t d i s c u s s a l l t h e d e t a i l s o f t h e p r o o f t h a t t h e f u n c t i o n a l i s l o c a l i z a b l e f o r f u n c t i o n s i n P^, s i n c e t h i s p r o b l e m i s c o n s i d e r e d i n f u l l b y A.M. G l e a s o n [ 2 ] , f o r t h e c a s e where D i s t h e n - d i m e n s i o n a l u n i t c u b e . C-leason p r o v e s t h e f o l l o w i n g t h e o r e m : Theorem 1.13 I f D i s t h e u n i t cube i n E u c l i d e a n n - s p a c e , and i f f€F-j> t h e n t h e r e i s a s t r a t e g y s u c h t h a t f o r a n y g i v e n p o s i t i v e €, S ( f ) c a n be r e s t r i c t e d t o a b a l l o f r a d i u s €, by c o m p u t i n g t h e v a l u e s o f f a t , a t most, L-K L o g € p o i n t s i n D. L and K a r e c o n s t a n t s d e p e n d i n g o n l y on a and on t h e d i m e n s i o n n. We g i v e a b r i e f d e s c r i p t i o n o f t h e s t r a t e g y u s e d b y G l e a s o n . L e t p, 0 < p < 1, be a r b i t r a r y . Suppose i t i s known 22 t h a t f o r some p o i n t y£D, { X£D | f ( x ) > f ( y ) } c B ( y , \ ) , where B ( y , \ ) i s t h e c l o s e d b a l l w i t h c e n t r e y and r a d i u s X. Choose p o i n t s Z q = y, z^,Z£>•••z^, q < «, so t h a t q D n B ( y , \ ) c U B ( z . , p a \ ) . i = 0 1 Compute f ( z ^ ) , i = 0 , l , 2 , . . . q , and l e t s be t h e l e a s t i n d e x f o r w h i c h f ( z ) = sup [ f ( z . ) } , i = 0 , l , 2 , . . . q . G l e a s o n p r o v e s t h a t t h e n [x6D | f ( x ) > f ( x )} c B ( z , p \ ) . s s Thus, k n o w i n g t h a t S ( f ) b e l o n g s t o a b a l l o f r a d i u s A, we c a n r e s t r i c t S ( f ) t o one o f r a d i u s p\, and t h i s p r o c e d u r e can be i t e r a t e d . S i n c e i n i t i a l l y S ( f ) € D c ^ ( y ^ , ^/2) where y Q i s t h e c e n t r e o f D, we c a n a f t e r n s t a g e s r e s t r i c t S ( f ) t o a b a l l o f r a d i u s p n ^/2 . S i n c e p< 1, l i m p n ^v/2 = 0. So t h e maximum n -• oe p o i n t i s l o c a l i z a b l e . 1 - 6 Remarks ' S e v e r a l q u e s t i o n s and p o s s i b l e t h e o r e m s a r e s u g g e s t e d by t h e p r o c e d i n g e x a m p l e s . I n t h e f i r s t p l a c e , i t w o u l d seem d e s i r a b l e t o f i n d s u f f i c i e n t c o n d i t i o n s on D and F t o g i v e l o c a l i z a b i l i t y . One p o s s i b i l i t y f o r t h i s i s g i v e n b y t h e t h r e e e x a m p l e s g i v e n i n s e c t i o n 1-1, t h e o r e m 1.1, and t h e o r e m 1.13. I n a l l t h r e e c a s e s , i f i t i s assumed t h a t S ( f ) b e l o n g s t o an i n t e r -v a l o r b a l l o f d i a m e t e r d s a y , we c a n "by e v a l u a t i n g f a t a f i x e d number o f p o i n t s i n D r e s t r i c t S ( f ) t o a n o t h e r i n t e r v a l o r b a l l o f d i a m e t e r d' s a y , where t h e r a t i o d'/d. i s l e s s t h a n 1 and i s i n d e -p e n d e n t o f t h e v a l u e o f d. T h i s n o t o n l y g i v e s l o c a l i z a b i l i t y b y i t e r a t i o n , b u t a l s o t h e f a c t t h a t t h e d i a m e t e r s o f t h e s u c c e s s i v e s e t s t o w h i c h S ( f ) i s c o n f i n e d d e c r e a s e a t l e a s t as f a s t as a 23 g e o m e t r i c s e q u e n c e o f p o s i t i v e numbers c o n v e r g i n g t o z e r o . S e c o n d l y , i n t h e c a s e s where t h e f u n c t i o n a l i s n o t l o c a l i z a b l e , as i n s e c t i o n 1-4 and t h e o r e m 1.11, i t i s by e x a m i n i n g t h e way i n w h i c h l o c a l i z a t i o n f a i l s t h a t s u g g e s t s t h e e x t r a r e s t r i c t i o n s t o be p l a c e d on F i n o r d e r t o g i v e l o c a l i z a b i l i t y . T h i s s u g g e s t s t h a t i n o r d e r t o d e c i d e w h e t h e r o r n o t a f u n c t i o n a l i s l o c a l i z a b l e , i t m i g h t be p o s s i b l e t o examine t h e s e q u e n c e o f s e t s t o w h i c h S ( f ) , f € F , may be r e s t r i c t e d , r a t h e r t h a n t h e c l a s s F i t s e l f . F o r , i f f € F , and S ( f ) i s s u c c e s s i v e l y r e s t r i c t e d t o t h e s e t s K Q 3 K ^ ( f , M ) r> K^(ffK),», 3 K n(f,M).». where M i s some s t r a t e g y , t h e r e a r e j u s t two p o s s i b i l i t i e s ; ( i ) The d i a m e t e r s d n ( f , M ) o f t h e s e t s K n ( f , M ) d e c r e a s e t o a p o s i t i v e l i m i t as n - » . ( i i ) The d i a m e t e r s d n ( f , M ) d e c r e a s e t o z e r o . I f we have l o c a l i z a b i l i t y w i t h r e s p e c t t o M, t h e n c a s e ( i i ) must h o l d f o r a l l f u n c t i o n s f € F , Hence t o a s k f o r l o c a l i z a b i l i t y , i s t h e same t h i n g as t o a s k i f t h e s e q u e n c e o f s e t s { K n ( f ) } c o n v e r g e t o S ( f ) i n t h e s e n s e o f f i l t e r s on a t o p o -l o g i c a l s p a c e . I n c h a p t e r 2, we d e f i n e a weak t o p o l o g y on t h e s e t K q , a n d c h a r a c t e r i z e l o c a l i z a b i l i t y i n t e r m s o f t h e r e l a t i o n b e t w e e n t h i s weak t o p o l o g y and t h e s t a n d a r d m e t r i c t o p o l o g y on K QO F i n a l l y , t h e b i s e c t i o n p r o b l e m p r o v i d e s an example where -, f o r f£F and xgD, t h e f u l l i n f o r m a t i o n p r o v i d e d b y t h e n u m e r i c a l v a l u e o f f ( x ) i s n o t u s e d . I t i s o n l y n e c e s s a r y t o know w h e t h e r f ( x ) i s p o s i t i v e , n e g a t i v e o r z e r o . S i m i l a r l y , i n t h e u n i m o d a l p r o b l e m o f t h e o r e m 1.1, o n l y t h e s i g n o f f ( x ^ ) - ^ ( x ^ ) * s u s e ( l t o r e s t r i c t t h e p o s i t i o n o f S ( f ) . I n g e n e r a l , i t c a n be a s k e d i f 24 a n y t h i n g i s t o be g a i n e d by u s i n g t h e f u l l i n f o r m a t i o n a v a i l a b l e , n a m e l y , t h e n u m e r i c a l v a l u e o f f ( x ) , as o p p o s e d t o t h e p a r t i a l i n f o r m a t i o n p r o v i d e d by t h e s i g n o f f ( x ) . T h i s q u e s t i o n i s c o n -s i d e r e d i n c h a p t e r 2, when t h e c o n c e p t o f t e s t - f u n c t i o n i s i n t r o -d u c e d . F i r s t , m o t i v a t e d by t h e e x a m p l e s o f t h i s c h a p t e r , g e n e r a l d e f i n i t i o n s and n o t a t i o n a r e s e t up f o r t h e p r o b l e m o f l o c a l i z a -b i l i t y . 25 CHAPTER 2 L O C A L I Z A B I L I T Y 2 - 1 B a s i c d e f i n i t i o n s D e f i n i t i o n 2.1 L e t P be a g i v e n f a m i l y o f r e a l - v a l u e d f u n c t i o n s d e f i n e d on a compact c o n v e x s e t D, where D i s c o n t a i n e d i n a E u c l i d e a n q - d i m e n s i o n a l s p a c e E^-, q < ». F o r a p o s i t i v e i n t e g e r m, and any s e t A c E^, d e f i n e A t o be t h e C a r t e s i a n p r o d u c t s p a c e A m = AxAxAx...xA (m t i m e s ) , A r a c E™^, w i t h t h e u s u a l E u c l i d e a n m e t r i c i n I t i s assumed t h a t f o r e a c h f u n c t i o n f € F , and some f i x e d p o s i t i v e i n t e g e r m, t h e r e i s a u n i q u e v e c t o r S(f)eD m„ The m a p p i n g S; F -• D m w h i c h t a k e s f t o i t s image S ( f ) i s c a l l e d a f u n c t i o n a l . D e f i n e t h e s e t H q as t h e r a n g e o f S; t h u s H = {x € D m | x = S ( f ) f o r some f € F } . I t i s assumed t h a t i f f € P and x€D, t h e n f ( x ) c a n be computed n u m e r i c a l l y w i t h o u t e r r o r . D e f i n i t i o n 2.2 I f H i s any s u b s e t o f D, a k - a b s c i s s a s e t i n H ( o r , i f t h e r e i s no a m b i g u i t y , an a b s c i s s a s e t ) i s an o r d e r e d k - t u p l e { x ^ , X 2 , ..», x^) where x^€ H, i = l , 2 , . . . k . I t i s c o n -v e n i e n t t o d e n o t e s u c h an a b s c i s s a s e t b y X. D e f i n i t i o n 2.3 I f X i s t h e a b s c i s s a s e t [ x ^ , X 2 ? ... x^} where x^€D, and i f f € F , t h e n f ( X ) d e n o t e s t h e s e t o f k r e a l numbers { f ( x 1 ) , f ( x 2 ) , . . . , f ( x k ) 3 . D e f i n i t i o n 2.4 Suppose f f F . A s e a r c h p r o c e d u r e f o r S ( f ) i s d e f i n e d b y t h e f o l l o w i n g s e q u e n c e o f s t e p s : 26 ( i ) S e l e c t a bounded set K c E m < l , which contains H . o o (The reason f o r not n e c e s s a r i l y s e l e c t i n g H q i t s e l f , i s t h a t i t may be more convenient to use a l a r g e r s e t . For example, may be open, but i t may be simpler to use c l o s e d s e t s , i . e . , K q might be chosen as the c l o s u r e of H q. In general, K q w i l l be the smal-l e s t convenient set c o n t a i n i n g H q . S i m i l a r l y f o r the sets K ^ ( f , X Q ) , K„(f,X ,X..), e t c . below. 2 ' o' 1 ' ( i i ) S e l e c t a k Q - a b s c i s s a set X q i n D, and evaluate f ( x o ) . ( i i i ) Put K 1(f,X Q) = {x€K o | x = S(g) f o r some g€F such t h a t f ( X Q ) = g ( X Q ) } . ( i ) » S e l e c t a set K ^ ^ X ) such that E± (f , X q ) C K^f , X Q ) ( i i ) ' S e l e c t a k ^ - a b s c i s s a set X^ i n D,and evaluate f ( ) . ( i i i ) ' Put H 2 ( f , X o , X 1 ) = [ x e K 1 ( f , X )|x = S(g) f o r some g€F such that f(X±) = g ( X ] [ ) } . In g e n e r a l , having s e l e c t e d k ^ - a b s c i s s a sets X^, i = 0,1,2,... n-1, and d e f i n e d H . ( f , X , X N , ... X. ,) f o r i = 1,2,...n, l ' o 1' 1-1 K . ( f , X ,X_, ... X. .) f o r i = 1,2,... ( n - l ) l ' o' 1 7 l - l ' ' the procedure continues: ( i ) S e l e c t a set K ( f , X , X 1 F ... X ,) such t h a t n ' o 1 n - l H ( f , X ,..,X ,) c K ( f , X ,X, ,...X ,) c K . ( f , X ,...X N ) . n ' o' n - l n ' o 1 n - l n - l ' o' n-2 ( i i ) S e l e c t a k n - a b s c i s s a set X N i n D and evaluate f ( X N ) . ( i i i ) Put II J_1 (f ,X ,X, , .. .X ) v ' n+1 ' o' 1' n = {x6K ( f ,X , . . .X x ) | x = S(g) f o r some g f F such t h a t f (X n)=g(X N) ) . This procedure i s to continue f o r a l l p o s i t i v e i n t e g e r s n, 27 D e f i n i t i o n 2.5 A strategy for l o c a l i z i n g the functional, usually denoted by M, i s a rule for successively determining the selection of the positive integers k , the k -abscissa sets X , the set K , * 6 n' n n o and the sets K ( f . X ,'X, , . . ,X , ) , n > 1. The strategy M i s to be n o 1 n-1 —• °^ stated before any computations are carried out. Given M, the set K Q ( f , X Q , , . 0 X N ^) must be uniquely defined i n terms of H n ( f , X Q , . . . X N _ ^ ) alone, and furthermore, given M and a set K ( f , X ,X. , . . 0 X , ) , the k -abscissa set X must be uniquely n o I n-1 n n -± ^ defined i n terms of K (f,X ,...X , ) , the abscissa sets X., and n ' o' n-1 ' I ' numbers f(X^), i = 0,1,2,...,(n-1). Remarks If M i s a given strategy, and f€F, we can nov v r i t e K (f,M) i n place of K (f,X ,...X If there i s no ambiguity, n A n o n—1 ve can abbreviate this further to K n ( f ) or even to K n. It i s obvious that i f f€?, then S(f)€K n(f,M) for a l l positive integers n. Ve say that n stages have been completed i f ve knov that S ( f ) € K n ( f ) . D e f i n i t i o n 2.6 Let M be a strategy for l o c a l i z i n g the functional. The functional i s l o c a l i z a b l e v i t h respect to M i f lim sup d[K (f,M)] = 0 n f€P n vhere d[K n(f,M)] i s the diameter of the set K n(f,M) i n the Euclidean space 2 - 2 Test functions For many problems, the search procedure as defined i n d e f i n i t i o n 2,4, may be replaced by something more r e s t r i c t i v e but 28 s i m p l e r . One p o s s i b i l i t y i s p r o v i d e d b y t h e b i s e c t i o n p r o b l e m . Suppose i t i s a l r e a d y d e t e r m i n e d t h a t , f o r some f € F , S ( f ) € K n S where K i s a c l o s e d i n t e r v a l [ a ,b ] , I f , f o r t h e a b s c i s s a s e t n n' n J ' a + b X , t h e p o i n t __S Jl i s s e l e c t e d , one n eeds t o c o n s i d e r n 2 ( e s s e n t i a l l y ) o n l y two p o s s i b l e s e t s f o r & n +^> n a m e l y ! a n + b n K ,, = [ a , ^ ] n+1 n' 2 a„ + b w h i c h i s t o be u s e d i f f \ n 2 — ~ i **• ® a + b /a + b \ w h i c h i s t o be u s e d i f f \ 2 J > 0« Ve t h e r e f o r e a s k i f we c a n f i n d a f u n c t i o n T o f X a n d f ( X ) n n a l o n e , w i t h f i n i t e r a n g e , so t h a t , g i v e n S ( f ) € K n , t h e p o s i t i o n o f S ( f ) c a n be s u i t a b l y r e s t r i c t e d t o a s e t K + ^ ( f ) w h i c h i s c o m p l e t e l y d e t e r m i n e d by t h e s e t K n and t h e v a l u e o f T ( X n ; f ( X n ) ) < D e f i n i t i o n 2.7 L e t k be a p o s i t i v e i n t e g e r . A t e s t f u n c t i o n o f o r d e r k i s a m a p p i n g T ; ^ x Rk—>V, o f t h e f o r m T ( X ; f ( X ) ) > where X i s a k - a b s c i s s a s e t i n D, f £ F , and V i s a s e t w i t h a f i n i t e number o f e l e m e n t s . D e f i n i t i o n 2.8 L e t D and F be g i v e n . L e t T be a k - t h o r d e r t e s t f u n c t i o n w i t h r a n g e [ \ , . . . \ }. A k - t h o r d e r s e a r c h p r o c e d u r e w i t h t h e t e s t f u n c t i o n T i s d e f i n e d by t h e f o l l o w i n g s e q u e n c e o f s t e p s : ( i ) S e l e c t a b ounded s e t K , so t h a t H c K c D m, o o o ( i i ) S e l e c t a k - a b s c i s s a s e t X i n D. o ( i i i ) D e f i n e w s u b s e t s , 1 < i < w, o f K q , d e p e n d i n g o n l y on X q and K q , s u c h t h a t f o r e v e r y f € F , S ( f ) € K 1 ; L i f 29 T ( X q ; f ( X Q ) ) = \ i , i = 1,2,3,...v. ( i v ) F o r e a c h s e t K - ^ i ' s e l e c t a k - a b s c i s s a s e t X ^ i n D. ( v ) F o r e a c h s e t , d e f i n e v s u b s e t s _. , ( i - l ) w < j < i v , d e p e n d i n g o n l y on X ^ and K^^, so t h a t f o r e v e r y f € F s a t i s f y i n g S t f ) ^ . , S(f)eK 2 ;. i f T ( X ] _ i ; f ^ . ) ) = \. . I n g e n e r a l , h a v i n g d e f i n e d s e t s K ^, 1 < i < v 1 1 f o r some p o s i t i v e i n t e g e r n, t h e p r o c e d u r e i s c o n t i n u e d by ( i ) s e l e c t i n g f o r e a c h s e t , a k - a b s c i s s a s e t X n ^ , ( i i ) d e f i n i n g , f o r e a c h s e t K ^, v s u b s e t s K-n+± > J o f K ^, ( i - l ) v < j < i v , d e p e n d i n g o n l y on K ^ and X ^ , so t h a t f o r e v e r y f?F s a t i s f y i n g S ( f ) € K n i , S ( f ) f K n + 1 ^ i f T ( x n i ; f ( X n ± ) . T h i s p r o c e d u r e i s t o be c o n t i n u e d f o r a l l p o s i t i v e i n t e g e r s n. D e f i n i t i o n 2.9 I f D,F and a k t h - o r d e r t e s t f u n c t i o n T a r e g i v e n , a s t r a t e g y , d e n o t e d b y M, i s a r u l e by v h i c h e a c h k - a b s c i s s a s e t X . i s d e t e r m i n e d when K . i s k n o v n , and by v h i c h e a c h K , , . i s n i m ' J n+1, j d e t e r m i n e d v h e n K . and X . a r e k n o v n , ( k - l ) v < j < i v . The n i n i s t r a t e g y M i s t o be s t a t e d b e f o r e any c o m p u t a t i o n s a r e c a r r i e d o u t . D e f i n i t i o n 2.10 I f D and F a r e g i v e n ; i f T i s a k t h - o r d e r t e s t f u n c t i o n , and M i s a s t r a t e g y , t h e n t h e f u n c t i o n a l i s l o c a l i z a b l e v i t h r e s p e c t t o T and M i f l i r a sup d [ K ] = 0 _ i ^ . 5. n n i n -• « 1 < I < v v h e r e d [ K .] i s t h e d i a m e t e r o f t h e s e t K . i n t h e E u c l i d e a n n i n i s p a c e E m q . I t i s e v i d e n t t h a t i f f o r some T and M, t h e f u n c t i o n a l i s l o c a l i z a b l e v i t h r e s p e c t t o T and M, t h e n t h e f u n c t i o n a l i s 30 l o c a l i z a b l e with respect to some strategy i n the sense of d e f i n i t i o n 2.6. There are two main questions to consider; (i) If the functional i s l o c a l i z a b l e with respect to some strategy, does there exist a test function T, and another strategy M so that the functional i s l o c a l i z a b l e with respect to T and M? ( i i ) If the answer to (i) i s yes, how do the two methods compare? In chapters 3 and 5 i t i s shown that for many problems, question (i) can be answered i n the affirmative. For the present, we prove below a theorem which gives a necessary condition that, for suitable strategies M, the closure of every set H (f,X ,..,X .) 0 7 ' ' n o n—i as in d e f i n i t i o n 2.4 i s equal to the closure of some K . as i n H ni d e f i n i t i o n 2.8. To do t h i s , we must decide f i r s t when for two functions f and g i n F, and some abscissa set X, we have T(X;f(X)) = T(X;g(X)). This i s done by p a r t i t i o n i n g the class F into suitable equivalence classes as i n the following d e f i n i t i o n . D e f i n i t i o n 2.11 Suppose D and F are given, and a suitable set K q i s selected. If f£F, g€F, and X i s any k-abscissa set i n D, the r e l a t i o n ^ i s defined by f ^ g i f and only i f H (f,X) = H^gjX). It i s easy to see that i s an equivalence r e l a t i o n on F. Hence F i s partitioned into a number of equivalence classes 'at X'. Moreover, the set H^(f,X) depends only on the set X and the equivalence class at X to which f belongs. Lemma 2.12 Suppose D and F are given. Let M be a strategy for l o c a l i z i n g the functional so that each set K (f,X ) i s chosen as 31 the closure of H,(f,X ), where f€-F, and X i s an abscissa set i n 1 ' o ' ' o D. Then there i s a test function T such that every set K ^ ( f , X O ) i s a as i n d e f i n i t i o n 2.8 i f and only i f the r e l a t i o n ^ o p a r t i t i o n s F at X q into a f i n i t e number of equivalence classes. Then T must be defined so that for a l l f£F, g€F f r£ g i f and only i f T(X : f ( X J ) = T ( X :g(X ) ) . A . O O O O 0 Proof The finiteness of the number of equivalence classes i s evidently necessary since a test function has f i n i t e range. Conversely, i f p a r t i t i o n s F into a f i n i t e number of equivalence o classes, the number of d i s t i n c t sets H, ( f , X ) for fixed X i s ' 1 ' o o f i n i t e , and so the number of d i s t i n c t sets K, ( f , X ) for fixed X l o o i s also f i n i t e . F i n a l l y , f and g both belong to the same equivalence class at X q i f and only i f H ^ ( f , X Q ) = H^(g,X Q), and, by d e f i n i t i o n of T, this i s i f and only i f T(X : ±{X)) = T ( X ; g(X ) ) . It i s worth noting that to find the set K^(f,X Q), for some f£F, one need only compute T ( X o ; f ( X Q ) ) , and that this need not en t a i l evaluating a l l the numerical values of f(X ). Of ° o course, i t does not necessarily follow that with T defined as i n lemma 2.12, the functional i s l o c a l i z a b l e with respect to T and M. 2 - 3 Examples Example 2.13 We take the bisection problem as defined i n section 1-1, with domain D = [ 0 , l ] . Choose for the strategy M, the one defined by the following rules: 32 o f K . n ( i ) E v e r y s e t K n i s t h e c l o s u r e o f t h e c o r r e s p o n d i n g E ^ . ( i i ) G i v e n K n, t h e a b s c i s s a s e t X r i s t h e m i d - p o i n t I t f o l l o w s t h a t t h e f i r s t a b s c i s s a s e t X_ i s x_ = 77 , 2 and t h a t K 1 ( f , x o ) = [ x , l ] i f and o n l y i f f ( x Q ) > 0 K 1 ( f , x Q ) = [ 0 , x ] i f and o n l y i f f (x ) < 0 K, ( f , x ) = x i f and o n l y i f f ( x ) = 0. 1 7 0 0 J 0 Hence, i f f € F , g€F, f g i f and o n l y i f sgn f ( x ) = sgn g ( x ). x 0 The t e s t f u n c t i o n T c a n be w r i t t e n i n t h e f o r m T ( x , f ( x ) ) = sgn f ( x ) ; t h e t h r e e v a l u e s o f w h i c h a t X=X q d e t e r m i n e u n i q u e l y t h e t h r e e s e t s K ^ ( f , x Q ) 0 S i n c e u s i n g t h e t e s t f u n c t i o n T g i v e s t h e same r e s u l t s as i n s e c t i o n 1-1, n o t h i n g i s t o be g a i n e d b y c o m p u t i n g t h e n u m e r i c a l v a l u e o f f ( x ) , a t any p o i n t x i n D. Example 2.14 F o r t h e u n i m o d a l p r o b l e m , as i n s e c t i o n 1-3, an a b s c i s s a s e t must c o n s i s t o f a t l e a s t two p o i n t s i n D. I f X Q i s t h e p a i r o f p o i n t s {x^,x 23 w i t h x^ < x 2 , and i f f and g a r e two f u n c t i o n s i n P, t h e n f ^ g i f and o n l y i f s g n [ f {x^)-f ( x 2 ) ]= s g n [ g ( x 1 ) - g ( x 2 ) ] -0 So t h e t e s t f u n c t i o n T c a n be w r i t t e n T ( x ; f ( x ) = T ( X l , x 2 ; f ( X ; L) , f ( x 2 ) ) = s g n [ f ( x ^ - f ( x 2 ) ] . Example 2.15 C o n s i d e r t h e p r o b l e m i n t h e o r e m 1.13; t o l o c a l i z e t h e maximum p o i n t o f a f u n c t i o n f € P ^ , d e f i n e d on t h e u n i t s q u a r e D. F o r c e r t a i n c o n s t a n t s p, a, and X, one t a k e s as an a b s c i s s a s e t X q i n D a s e t o f q+1 d i s t i n c t p o i n t s Z Q,Z^,...,Z , so t h a t t h e u n i o n o f t h e open b a l l s w i t h c e n t r e z^ and r a d i u s paX c o n t a i n s 33 i D. The c l a s s P-j h a s t h e p r o p e r t y t h a t i f f € P ^ , and f ( z ^ ) a r e a l l c omputed, t h e n S ( f ) b e l o n g s t o a c e r t a i n b a l l v i t h c e n t r e a t z , v h e r e s i s t h e l e a s t i n d e x s u c h t h a t f ( z ) = sup { f ( z . ) , i = 0,1,2,...q}. S 1 Thus, f o r g i v e n X q , and any t v o f u n c t i o n s f and g i n P^, f ^ g i f and o n l y i f b o t h f ( z ) > f ( z . ) 0 < i < q o g ( z ) > g ( z . ) 0 < i < q v h e r e s i s m i n i m a l i n b o t h c a s e s . The t e s t f u n c t i o n T must have a r a n g e c o n s i s t i n g o f q+1 e l e m e n t s , one f o r e a c h p o i n t z^. F i n a l l y , v e g i v e an example v h e r e a t e s t f u n c t i o n c a n be u s e d , b u t o n l y b y f a i l i n g t o u s e a l l t h e a v a i l a b l e i n f o r m a t i o n . E x a m p l e 2.16 L e t D = [ 0 , l ] and F t h e c l a s s o f a l l c o n v e x mono-t o n e f u n c t i o n s f d e f i n e d on D f o r v h i c h f ( 0 ) = 1 and f ( l ) = - 1 . By c o n v e x i t y , i t i s meant t h a t i f f € F , and 0 < x^ < x 2 < x-j < 1, t h e n f ( * 2 ) < h, v h e r e t h e p o i n t s ( x ^ , f ( x ^ ) ) , ( x 2 , h ) and ( x - j , f ( x ^ ) ) a r e c o l l i n e a r . I f f € F , l e t S ( f ) be t h e ( u n i q u e ) z e r o o f f . I t i s o b v i o u s t h a t l o c a l i z a t i o n i s p o s s i b l e b y t h e b i s e c t i o n s t r a t e g y . H o v e v e r , as d e s c r i b e d b y G r o s s and J o h n s o n [ 3 ] o r B e l l m a n and D r e y f u s [ l ] , one c a n do much b e t t e r . F o r , H q = {y<=D | y = S ( g ) f o r some g€F} = {y€D I 0 < y < — ^ ) f ( 0 ) - f ( l ) = {y€D | 0 < y < \ } . I f one t a k e s f o r K t h e c l o s u r e o f H , and s e l e c t s a s i n g l e o o' to p o i n t x i n K as t h e f i r s t a b s c i s s a s e t , t h e n t h e c l o s u r e o f 34 H ^ f j x ) i s [?,•>/] i f f ( x ) > 0 x i f f ( x ) = 0 [ M a x { 0 , ^ }, §] i f f ( x ) < 0 w h ere § = x / ( l - f ( x ) ) and -7 = ( f ( x ) + x ) / ( f ( x ) + l ) . Hence f o r g i v e n x, t h e l e n g t h o f t h e i n t e r v a l H ^ ( f , x ) v a r i e s c o n t i n u o u s l y w i t h t h e n u m e r i c a l v a l u e o f f ( x ) . So no t e s t f u n c t i o n c a n be u s e d w i t h r a n g e e l e m e n t s w h i c h d e s c r i b e e a c h s e t H ^ f . x ) . 2 - 4 L - t o p o l o g y We t u r n now t o t h e q u e s t i o n o f d e f i n i n g t h e t o p o l o g y as i n d i c a t e d a t t h e end o f c h a p t e r 1. L e t us s u p p o s e t h a t t h e d o m a in D and t h e c l a s s P a r e g i v e n , a l o n g w i t h t h e s e t H^ c D m f o r some known p o s i t i v e i n t e g e r m. L e t M be a s t r a t e g y f o r w h i c h K i s t h e c l o s u r e o f H . Whether t h e f u n c t i o n a l i s l o c a l i z a b l e o o w i t h r e s p e c t t o M o r n o t , t h e r e i s a l w a y s d e f i n e d f o r e a c h f € F , a d e c r e a s i n g s e q u e n c e o f s e t s K q , ( f , M ) , ( f , M ) . . . ( f , M ) . . . , s u c h t h a t ' f o r a l l p o s i t i v e i n t e g e r s n, S ( f ) f K ( f , M ) and so n S ( f ) e O I C ^ ( f , M ) . The q u e s t i o n o f l o c a l i z a b i l i t y d epends m o s t l y k = l n on t h e b e h a v i o u r o f O K, ( f , M ) as n i n c r e a s e s , and t h i s i s . k = l K s u g g e s t i v e o f t h e t h e o r y o f f i l t e r s on a t o p o l o g i c a l s p a c e . I n what f o l l o w s , we mean by t h e m e t r i c t o p o l o g y on t h e r e l a t i v e t o p o l o g y on K q i n d u c e d by t h e E u c l i d e a n m e t r i c o f t h e s m a l l e s t E u c l i d e a n s p a c e c o n t a i n i n g K q . The t e r m s 'open' a n d ' c l o s e d ' e t c . , a r e r e l a t i v e t o t h i s t o p o l o g y . I t i s c o n v e n i e n t t o r e s t a t e t h e d e f i n i t i o n o f l o c a l i z a b i l i t y i n a n o t h e r f p r m . 35 Lemma 2 . 1 7 Let M be a strategy such that i s the closure of H . Then the functional i s lo c a l i z a b l e with respect to M i f and o only i f for every € > 0 , there i s an integer n Q such that for a l l x i n K , o' K (f,M) c K q H B(x,€) i f n > n Q , f € F , and S(f) €B(x,|)', where B(x,€) i s the open b a l l with centre x and radius €. The proof i s omitted, since i t follows d i r e c t l y from d e f i n i t i o n 2 . 6 . Ve can now define a topology on the set i n terms of the class P and the strategy M. Defi n i t i o n 2 . 1 8 Suppose M i s given. A subset V of K q w i l l be called L-open (with respect to M) i f and only i f V i s open (metric), and for every x€V, there exists an € q > 0 and a positive integer n Q such that K n(f,M) c V i f n > n Q,f€F, and S(f) €B(x, 6 Q )cV. Lemma 2 . 1 9 The class of a l l subsets of K which are L-open 0 are the open sets of a topology for K q . This topology i s called the L-topology with respect to M for K Q . Proof Ve have to show that the class of a l l L-open sets i s closed under ar b i t r a r y unions and f i n i t e intersections. Por this purpose, l e t I be an indexing set, and t^ a3 a^j °e a c o l l e c t i o n of L-open subsets of K q . If x € ^ V^, then x€V y for some y f l . So there i s an € > 0 and an integer n , such that K (f,M)c V o 6 o' n ' Y i f n > n Q, feP, and S(f)6B(x,€ Q) <= V, since i s L-open. But then K (f,M) c U V and so U V i s L -open. n ael a a€l a If and are L-open subsets of K q , and x€V^ 11 Y^, then there i s a 6 such that B(x,6) c fl . Since x€V^, there i s an > 0 and an integer n^ such that K n(f,M) c i f n > 36 and S(f)eB(x,€-^) c . S i n c e x € V 2 , t h e r e i s an ^ > 0 a n d - a n i n t e g e r n 2 s u c h t h a t K n ( f , M ) c V 2 i f n > n 2 and S(f)€B(x,£ 2)c V 2 . I f € Q = M i n {6, € 2 } and n Q = Max [ n ^ n ] , t h e n K n ( f j M j c V ^ n ^ i f n > n , f € F , and S ( f ) € B ( x , € ) c V 2« By i n d u c t i o n , t h e i n t e r s e c t i o n o f f i n i t e l y many L-ope n s e t s i s a g a i n L-open. F i n a l l y , t h e s e t K q i t s e l f i s L - o p e n . T h i s c o m p l e t e s t h e p r o o f . We c a n now c h a r a c t e r i z e l o c a l i z a b i l i t y i n t e r m s o f t h e L - t o p o l o g y . Theorem 2.20 L e t D,P and a s t r a t e g y M be g i v e n s u c h t h a t K Q i s t h e c l o s u r e o f H . Then t h e f u n c t i o n a l i s l o c a l i z a b l e w i t h o r e s p e c t t o M i f and o n l y i f t h e L - t o p o l o g y w i t h r e s p e c t t o M i s s t r o n g e r t h a n t h e m e t r i c t o p o l o g y f o r K q . A l t e r n a t i v e l y t h i s i s i f and o n l y i f e v e r y open s e t ( m e t r i c ) i n K q i s L - o p e n . P r o o f Suppose V i s open ( m e t r i c ) i n K q , x€V, and t h e f u n c t i o n a l i s l o c a l i z a b l e w i t h r e s p e c t t o M. Then t h e r e i s an € > 0 s u c h t h a t B ( x , 2 € q ) cz V. B u t t h e n b y lemma 2.17, t h e r e i s an i n t e g e r n s u c h t h a t K ( f , M ) c K fl B(x,2€ ) c V i f n > n , f g P , and 0 n ' o ' 0 — 0 ' ' S ( f ) € B ( x , € ) c V. So V i s L - o p e n . C o n v e r s e l y , l e t € > 0 be a r b i t r a r y , and s u p p o s e t h a t e v e r y open s e t i s L - o p e n . I t must be shown t h a t t h e r e i s an i n t e g e r n Q , s u c h t h a t f o r e v e r y X € K Q , K n ( f , M ) c K q fl B ( x , € ) i f n > n , f € F , and S ( f ) e B ( x , | ) . By h y p o t h e s i s , K Q n B ( x , |) i s L - o p e n f o r e v e r y X € K q . So i f x i s g i v e n , t h e r e i s a number € Q ( x ) < -| , and an i n t e g e r n Q ( x ) s u c h t h a t K n ( f , M ) c K Q n B ( x , ^ ) . Now t h e u n i o n o f a l l open b a l l s B ( X , € Q ( X ) ) c o v e r s K q , and s i n c e K q i s c o m p a c t , a f i n i t e s u b c o v e r B ( y ^ , € Q ( y ^ ) ) where y ^ € K , i = l , 2 , . . . p , f o r K c a n be s e l e c t e d , s u c h t h a t 37 K o C B ^ i ^ o ( y i ) ) . L e t n Q = Max { n ^ y . , ) , n Q ( y 2 ) , ... n Q ( y p ) } . L e t X € K q , and s u p p o s e t h a t f€F, S ( f ) € B ( x , | ) . Then S ( f ) € B ( y i , e Q ( y i ) ) f o r some i , and so K n ( f , M ) c K Q n B(y., |) i f n > n Q , v h i c h g i v e s K (f,M)cK QnB(x,€) i f n > n ,.f€F, and S ( f ) € B ( x , | ) . Remark M i n o r m o d i f i c a t i o n s must be made i n t h e above d e f i n i t i o n s a n d r e s u l t s i f one c o n s i d e r s ' n o n - u n i f o r m ' l o c a l i z a b i l i t y , m e a n i n g t h a t d e f i n i t i o n 2.6 i s r e p l a c e d by t h e r e q u i r e m e n t t h a t t h e f u n c t i o n a l i s l o c a l i z a b l e v i t h r e s p e c t t o M i s and o n l y i f f o r e v e r y feF, l i m d [ K ( f , M ) ] = 0. The s t a t e m e n t o f t h e o r e m 2.20 n -• oo r e m a i n s v a l i d i f t h e L - t o p o l o g y i s d e f i n e d on t h e s e t H q ( r a t h e r t h a n K q ) . H e r e , a s u b s e t V o f H q i s L - o p e n i f and o n l y i f f o r e v e r y x€V, t h e r e i s an i n t e g e r n Q s u c h t h a t i f S ( f ) = x, and n > n Q , t h e n K n ( f , M ) c V. U n d e r t h i s d e f i n i t i o n s , t h e r e may be L - o p e n s e t s v h i c h a r e n o t ( m e t r i c ) o p en, as i n t h e b i s e c t i o n s t r a t e g y v i t h x as t h e m i d - p o i n t o f D. The p o i n t x i s L - o p e n , b u t n o t open. E x a m p l e 2.21 As an a p p l i c a t i o n , ve c o n s i d e r t h e p r o b l e m d e f i n e d i n s e c t i o n 1-4. T h e r e , i t was shown t h a t t h e f u n c t i o n a l i s l o c a l i z a b l e i f f o r a l l f€F, S ( f ) i s bounded a v a y f r o m an end o f t h e i n t e r v a l D, b u t n o t i f S ( f ) may be a r b i t r a r i l y c l o s e t o e i t h e r end o f t h e i n t e r v a l . S i n c e a l l L-open s e t s a r e ( m e t r i c ) open by d e f i n i t i on, i t f o l l o v s t h a t f o r t h e s t r a t e g y d e f i n e d a t t h e end o f 1-4, t h e L - t o p o l o g y f o r K q = [ 0 , l ] , i s t h a t vvith t h e f o l l o v i n g s e t s as a b a s i s : 38 ( i ) I n t e r v a l s o f t h e f o r m {x|a < x < b } , where 0 < a < b < 1. ( i i ) U n i o n s o f d i s j o i n t i n t e r v a l s o f t h e f o r m {x|o < x < a ) U [ x | b < x < l ) . F o r no s t r a t e g y M, can a l l s e t s o f t h e f o r m {x|0 < x < a} be L - o p e n . • E xample 2.22 The L - t o p o l o g y f o r t h e c l a s s F^ d e f i n e d i n s e c t i o n 1- 5 i s t h e i n d i s c r e t e t o p o l o g y f o r t h e u n i t s q u a r e . T h a t i s , o n l y t h e u n i t s q u a r e and t h e empty s e t a r e L - o p e n . 2 - 5 A s i m u l t a n e o u s s e a r c h p r o b l e m As a f u r t h e r example t o i l l u s t r a t e how t h e L - t o p o l o g y d e s c r i b e s how l o c a l i z a t i o n may f a i l , we c o n s i d e r a p r o b l e m where two p o i n t s i n D a r e t o be s i m u l t a n e o u s l y a p p r o x i m a t e d by l o c a l i -z a t i o n . A s i d e f r o m t h e t o p o l o g y , t h i s p r o b l e m i s o f some i n t e r e s t i n i t s own r i g h t . L e t D be t h e c l o s e d i n t e r v a l [ 0 , l ] . L e t F be t h e c l a s s o f r e a l - v a l u e d c o n t i n u o u s f u n c t i o n s f d e f i n e d on D s u c h t h a t f o r two d i s t i n c t p o i n t s a-^(f) and a 2 ( f ) i n D, 0 < a1(f) < a 2 ( f ) < 1, f i s s t r i c t l y i n c r e a s i n g on [ 0 , a ^ ( f ) ] , f i s s t r i c t l y d e c r e a s i n g on [a-^ ( f ) , a 2 ( f ) ] , f i s s t r i c t l y i n c r e a s i n g on [ a 2 ( f ) , l ] . L e t S ( f ) be t h e v e c t o r ( a - ^ f ) , a 2 ( f ) ) i n t h e p l a n e E . We t a k e as K q , t h e s e t K q = { ( x , y ) JO < x < y < 1} c E 2 . We show f i r s t t h a t t h e f u n c t i o n a l i s n o t l o c a l i z a b l e . I n t u i t i v e l y , t h i s i s b e c a u s e F c o n t a i n s f u n c t i o n s f w h i c h c a n be r e g a r d e d as i n c r e a s i n g on D e x c e p t f o r a s m a l l ' w i g g l e ' , w h i c h may be c o n t a i n e d i n an i n t e r v a l so s m a l l t h a t one c a n n o t be s u r e o f f i n d i n g i t f o r a n y g i v e n s t r a t e g y . 39 Lemma 2.23 Let k be an a r b i t r a r y p o s i t i v e i n t e g e r , and l e t x^,x 2, ... xk_,_i he any set of (k+l) d i s t i n c t p o i n t s i n D such t h a t 0 < x, < x» < x- . . . < x, ,, < 1. — 1 2. i k+l ~~ Then f o r each t, t = 1,2,... k, and every p a i r of r e a l numbers ? = ? ( t ) , yj = 77 (t) such that x t < 5 < x^ .+ ~^  < x ^ + 1 , there i s a f u n c t i o n f. _ ^ € F, such t h a t t , s > y ( i ) f, (x.) = x. i = 1,2,... k+l T> > 51 7 1 1 ( i i ) s ( f t > 5 ) = ( ? ( t ) , >/(t)). Proof Define f. _ (x) such that. > = » ( f+ . - y , (x) = x i f 0 < x < t or x. ., < x < 1 * t l 8 , ^ (?) - s + l f ^ g, i s l i n e a r on the i n t e r v a l s [x^, ? ] , [ ?,*^ ] and ["7 , x t + 1 ] . Since d[H (f , X ) ] =^2 = d[K ], where X i s the (k+l) 1 X y ^ y / O 0 0 a b s c i s s a set [x^,x 2 ... x^ +^3> the f u n c t i o n a l i s not l o c a l i z a b l e . One suspects from the above lemma that l o c a l i z a t i o n i s p o s s i b l e i f the two p o i n t s a ^ ( f ) , ^ ( f ) are u n i f o r m l y bounded away from each other. This i s indeed the case. Suppose f o r the moment, that f o r given f€F, a p o i n t R ( f ) , such that a ^ ( f ) < R(f) < a 2 ( f ) , can be found. Then the f u n c t i o n f, r e s t r i c t e d to the i n t e r v a l [ 0 , R ( f ) ] i s unimodal, with a unique maximum p o i n t at a-^(f), and so a ^ ( f ) can be l o c a l i z e d as de s c r i b e d i n s e c t i o n 1-3. S i m i l a r l y , one can l o c a l i z e a 2 ( f ) , and hence S ( f ) . 40 Two r e s t r i c t i o n s on the c l a s s P are considered which guarantee that f o r each f, a p o i n t R ( f ) , oc^f) < R(f) < a 2 ( f ) can be found. The f i r s t i s to take, f o r some p o s i t i v e number 6 the c l a s s Fg which c o n s i s t s of a l l f u n c t i o n s f f F f o r which « 2 ( f ) - a i ( f ) ^  ^ o r each 6 > 0, the f u n c t i o n a l d e f i n e d by Fg i s l o c a l i z a b l e . This i s e a s i l y seen: choose as a b s c i s s a set X Q = {x^,x 2, ... ] so that ( 2 . l ) 0 = x^ < x 2 < x-j .. . < Xj^+i = 1> where k 6 sup ( x . + 1 - x ) < j . i=l Then, since f i s s t r i c t l y d e creasing over an i n t e r v a l of l e n g t h 6, i f f€Fg, there i s an index t , 2 < t < k, such that f ( x t _ 1 ) > f ( x t ) > f ( x t + 1 ) . But then, ct-^f) < x t < a 2 ( f ) , and so, by the above remarks, the f u n c t i o n a l i s l o c a l i z a b l e f o r f u n c t i o n s f € F 6 . As a c o r o l l a r y , i f we put K q ( 6 ) equal to the c l o s u r e of H f o r the f u n c t i o n s f € F E , then K (6) i s the i n t e r s e c t i o n of 0 0 0 {(x,y) |o < x < y < 1} with {(x,y) |y > x + 6], and there i s a s t r a t e g y M f o r which the L-topology f o r K q ( 6 ) i s exactly, the r e l a t i v e metric topology f o r K (6). Suppose such a 6 i s not known. Then one can attempt' to l o c a l i z e S ( f ) f o r f£F, by assuming f€Fg , f o r some 6 q. I f o S(f) cannot be r e s t r i c t e d , by s e l e c t i n g the a b s c i s s a set ( 2 . l ) a p p r o p r i a t e f o r 6 = 6 q, the process can be repeated f o r 6-^ = 2 ^ 0 ' and i f necessary, f o r 6 2,6^... where 6 n= O^)*1 6 q. This s t r a t e g y , i t - being understood t h a t as soon as a s u i t a b l e 6 r i s found, one l o c a l i z e s a ^ ( f ) and a 2 ( f ) , has as L-topology that d e f i n e d by the b a s i s c o n s i s t i n g of 4 1 ( i ) K q i n t e r s e c t e d v i t h open b a l l s vhose c l o s u r e does not c o n t a i n a p o i n t of the l i n e y=x, ( i i ) s t r i p s of the form K^H { ( x , y ) | x < y < x+6]. E v e r y L-neighbourhood of a p o i n t on the l i n e y=x c o n t a i n s every o t h e r p o i n t on t h a t l i n e i n K Q . An a l t e r n a t i v e r e s t r i c t i o n on the c l a s s P to g i v e l o c a l i z a b i l i t y l i e s i n the p o s s i b i l i t y t h a t one can approximate an i n f l e x i o n p o i n t R ( f ) , a-^(f) < R ( f ) < a 2 ( f ) . The r e s t r i c t i o n s p l a c e d on F so t h a t t h i s can be done are analogous to those i n the unimodal problem, except t h a t c o n v e x i t y c o n d i t i o n s r e p l a c e m o n o t o n i c i t y ones, and the second-order d i f f e r e n c e q u o t i e n t f ( x 3 ) - f ( x 2 ) f ( x 2 ) - f ( x x ) x 3 ~ X 2 X 2 ~ X l / i s used, r a t h e r than the f i r s t o r d e r d i f f e r e n c e q u o t i e n t f ( x 2 ) - f ( x x ) x 2 ~ x l The e xact c o n d i t i o n s on P to g i v e l o c a l i z a b i l i t y of the' f u n c t i o n -a l d e f i n e d by 3 ( f ) are g i v e n i n theorem 2.25 b e l o v ; f i r s t ve d e f i n e the term ' s t r i c t l y convex'. D e f i n i t i o n 2.24 Suppose f i s a r e a l - v a l u e d f u n c t i o n d e f i n e d on xhe c l o s a d i n t e r v a l [ a , b ] . Then f i s s t r i c t l y convex up on [a„b] i f , f o r a l l p o i n t s x ^ , x 2 , x 3 such t h a t a < x^ < x 2 < x-^  < b, ( x 3 - x , ) f ( x 2 ) < ( x 2 - x 1 ) f ( x 3 ) + ( x 3 - x 2 ) f ( x 1 ) . f i d s t r i c t l y convex dovn i f , under the same c o n d i t i o n s , (x- s- x ] ) f ( x 2 ) > ( x 2 - x x ) f ( x 3 ) + ( x 3 - x 2 ) f ( x x ) . Theorem 2.25 L e t D be the c l o s e d i n t e r v a l [ 0 , l ] , and F the c l a s s of a l l r e a l c o n t i n u o u s f u n c t i o n s f d e f i n e d on D f o r v h i c h t h e r e are t h r e e numbers a - ^ ( f ) , R ( f ) , ^ ( f ) s u c n t h a t 42 0 < a x ( f ) < R ( f ) < a 2 ( f ) < 1, and f i s s t r i c t l y i n c r e a s i n g on [ 0 , a ^ ( f ) ] f i s s t r i c t l y d e c r e a s i n g on [ a ^ ( f ) , a 2 ( f ) ] f i s s t r i c t l y i n c r e a s i n g on [ a 2 ( f ) , l ] f i s s t r i c t l y c o n v e x up on [ 0 , R ( f ) ] f i s s t r i c t l y c o n v e x down on [ R ( f ) , l ] . L e t S ( f ) be t h e p o i n t ( c ^ C f ) , a 2 ( f ) ) € E 2„ Then t h e f u n c t i o n a l d e f i n e d by S ( f ) i s l o c a l i z a b l e . P r o o f F i r s t , t h e f u n c t i o n a l d e f i n e d b y R ( f ) i s l o c a l i z a b l e w i t h r e s p e c t t o t h e t e s t f u n c t i o n T g i v e n b y T = T ( X ] L , X 2 , X 3 J f ( X l ) , f ( x 2 ) , f ( x 3 ) ) = ( x ^ - x - L ) f ( x 2 ) - ( x 2 - x 1 ) f ( x 3 ) - ( x ^ - x 2 ) f ( x 1 ) where 0 < x-^  < x 2 < x^ < 1. F o r , i t f o l l o w s f r o m d e f i n i t i o n 2.23, t h a t i f 0 < x^ < x 2 < x^ < 1, t h e n R ( f ) > x± i f T > 0 R ( f ) < x 3 i f T < 0 x x < R ( f ) < x 3 i f T = 0 . Thus,, i f f € F , R(f) c a n , by e v a l u a t i n g f a t 3 p o i n t s o f D, be r e s t r i c t e d to one o f t h e two i n t e r v a l s [ 0 , x 3 ] o r [ x ^ , l ] , and b y s u i t a b l e choice o f x ^ , x 2 , x 3 b o t h t h e s e i n t e r v a l s c a n be c h o s e n 2 to have length not gre a t e r t h a n TJ t h a t o f D. Hence by i t e r a t i o n , one c a n by e v a l u a t i n g f a t a ;inU-,i:>it sequence o f 3n p o i n t s i n D, r e s t r i c t R ( f ) t o an i n t e r v a l of length . A more e f f i c i e n t s t r a t e g y f o r l o c a l i z i n g R(f) i s g i v e n i n c h a p t e r 5. S e c o n d l y , t h e f u n c t i o n a l d e f i n e d b y S ( f ) i s l o c a l i z a b l e , , The s t r a t e g y commences by r e s t r i c t i n g R ( f ) t o a s u b i n t e r v a l o f D of l e n g t h 2c and m i d - p o i n t %, where 0 < c < M i n { ? , ! - ? } , f o r 43 f € F , and c a r b i t r a r y , A c h o i c e o f c i s made l a t e r , b u t assume t h a t c < j . Thus 0 < Z - c < R ( f ) < ? + c < 1 . T h e r e a r e two p o s s i b i l i t i e s : (a) ? > 2 ° Then c < g } so two p o i n t s y^ and y 2 c a n be s e l e c t e d s u c h t h a t 0 < S - 2 c < y i < y 2 < 5 ~ c < R ( f ) . E v a l u a t e f ( y ^ ) and f ( y 2 ) . A g a i n , t h e r e a r e two p o s s i b i l i t i e s : ( i ) f ( y 1 ) > f ( y 2 ) « Then a ^ f ) < y 2 < R ( f ) . T h i s means that a p o i n t s u c h t h a t a ^ ( f ) < y^ < a2^^ ^ s known. S i n c e f r e s t r i c t e d t o [ 0 ^ 2 ] i s a u n i m o d a l f u n c t i o n w i t h a u n i q u e maximum p o i n t a t a ^ ( f ) j a ^ ( f ) and s i m i l a r l y ( ^ ( f ) c a n be l o c a l i z e d ( s e p a r a t e l y ) by t h e g o l d e n - m e a n s t r a t e g y , and so i n t h i s c a s e S(f') c a n be l o c a l i z e d , ( i i ) f ( y x ) < f ( y 2 ) . Then §~2c < y± < a^f) < R ( f ) < a 2 ( f ) < l , A t w o r s t , t h e w h o l e p r o c e d u r e c a n be s t a r t e d a g a i n on t h e i n t e r -v a l [ y - j _ . l L 1 1 (b) § < ~2 ° Then c < -^(l - ? ) , and two p o i n t s z^ and Z 2 c a n be s e l e c t e d 3 0 that R ( f ) < § + c < z1 < z 2 < ? + 2c < 1. By e v a l u a t i n g f ( z ^ ) and f{z^)f t h e r e a r e t h e two p o s s i b i l i t i e s ? ( i ) f ( z 1 ) > f ( z 2 ) , f r o m w h i c h one g e t s a ('-,.' < R(f) < z, < a 0 ( f ) s and l o c a l i z a t i o n p r o c e e d s as i n c a s e ( i ) above. ( i i ) ^ ^ z ] ) f ( x 2 ^ ' w h i c h g i v e s 0 < a x ( f ) < R ( f ) < a 2 ( f ) < z 2 < ? + 2 c , V i t h t h e c h o i c e c = \x o f t h e l e n g t h o f De t h e p r o b l e m yan be recommenced on an i n t e r v a l o f l e n g t h a t most •jr t h a t o f Dj, 44 s h o u l d c a s e ( i i ) a r i s e . T h i s can be i t e r a t e d as o f t e n as n e c e s -s a r y u n t i l e v e n t u a l l y e i t h e r c a s e ( i ) a r i s e s , o r i t i s known t h a t a - ^ ( f ) j R ( f ) , and c t 2 ( f ) a l l l i e i n an i n t e r v a l o f l e n g t h a t most 3 m ( f ) m f o r some s u f f i c i e n t l y l a r g e i n t e g e r m. T h i s c o m p l e t e s t h e p r o o f . T h e r e a r e many p r o b l e m s s i m i l a r t o t h e one j u s t d i s -c u s s e d w h i c h c a n be h a n d l e d i n t h e same way. One o f i m p o r t a n c e i s where D = [ 0 , l ] , and P i s t h e c l a s s o f a l l c o n t i n u o u s r e a l -v a l u e d f u n c t i o n s f d e f i n e d on D f o r w h i c h f ( 0 ) > 0, f ( l ) > 0, f v a n i s h e s a t e x a c t l y two p o i n t s a-^(f) and a 2 ( f ) s 0 < a x ( f ) < a 2 ( f ) < 1, and f ( x ) i s n e g a t i v e i f a 1 ( f ) < x < a 2 ( f ) . As i n t h e p r e v i o u s e x a m p l e , r e s t r i c t i o n s on P a r e r e q u i r e d b e f o r e l o c a l i z a t i o n i s p o s s i b l e . 45 CHAPTER 3 R A T E O P L O C A L I Z A T I O N 3 - 1 Speed This chapter i s concerned with the rate of decrease of the sets K Q , K ^ ( f ) , ^ ( f ) i . e . , with the speed at which the diameters d [ K n ( f ) ] converge. In general terms, suppose that the domain D and the class of functions P are given. Let M be a s t r a t -egy. Then for each ffF, S(f) i s successively r e s t r i c t e d to the sets K => K. (f,M) a K„(f,M) => ... => K (f,M) ... where K i s deter-o l 2 n o mined by M and each set K (f,M) i s uniquely determined by f and M. Define d = d[K ] to be the diameter of K , which i s o o o' f i n i t e since K q i s bounded, and put d [ K (f,M)] equal to the diameter of the set K. (f,M), for each p o s i t i v e integer n. In c h a p t e r one, the sequence d'(M) = sup d[K (f,M)] n f f p n vr-.s d e f i n e d . The significance of this number, for g i v e n n, i s that by using the s t r a t e g y M, i t i s guaranteed, t h n t f o r any f i n F, 3(f) can be r e s t r i c t e d t o a s e t w i t h diameter a t most d^(M) after the s e l e c t i o n of a sequence of n s u i t a b l e abscissa s e t s . However, i t seem more a p p r o p r i a t e to c o n s i d e r the number of p o i n t s i n D at which a function f€P i s evaluated, rather than the number of abscissa sots. This i s because d i f f e r e n t strategies may involve d i f f e r e n t numbers of points i n D for each abscissa set. Hence we adopt the following definitions 46 D e f i n i t i o n 3.1 Let N be a positive integer, and M a given strategy. . For each f f F , l e t n be the largest positive integer such that i f the strategy M i s used to search for S(f), then f i s evaluated at no more than N d i s t i n c t points i n D. Define dM(M) = sup d[K (f,M)] N > 1 « f 6 P n and d N = i n f dN(M) N > 1 . M It i s evident from d e f i n i t i o n 3.1 that d^(M) > d-^+^ (M), and djj > djj +^ for a l l integers N > 0. Moreover, n < N, since each time a new abscissa set X i s selected, the function f€F i s n 7 evaluated at at least one new point i n the domain D. From this fact, and from d e f i n i t i o n 2=6, i t follows that i f the functional i s loc a l i z a b l e with respect to M, then lim ^(M) = 0. Conversely, N -» » i f M i s a strategy such that the number of elements i n each abscissa set i s uniformly bounded, and i f lim d^ -(M) = 0, then N -• 0 0 lim sup d[K (f,M)] = 0, i.e., the functional i s l o c a l i z a b l e n -» oo fgF n with respect to M. Ve are concerned with the behaviour of the ratios d^(M)/d Q and d^/d Q as N » , For many problems these sequences are bounded both from above and below by geometric sequences of positive numbers which converge to zero. In terms of numerical analysis, we might say that in these cases, l o c a l i z a t i o n i s a f i r s t -order process. That this i s normally to be expected i s demonstra-ted by some of the examples given i n chapters one and two. For instance, in the bisection problem.of section 1-15 the domain D = [0,l] may equally well be replaced by any other compact interval [a,b]. One can s t i l l r e s t r i c t the possible 47 p o s i t i o n of S ( f ) to a s u b i n t e r v a l of l e n g t h ^ t h a t o f [ a , b ] 0 S i n c e the f a c t o r -jj ^ s independent of a and h v the procedure can be i t e r a t e d i n such a way t h a t d N(M)/d < (p „ S i m i l a r l y f o r the unimodal problem, i f D = [a,b] i s any compact i n t e r v a l on the l i n e , S ( f ) can be r e s t r i c t e d to a s u b i n t e r v a l of D of l e n g t h 3 a t most ^ t h a t of D, by e v a l u a t i n g f a t a t most 2 p o i n t s i n D„ 3 A g a i n , the f a c t o r ^ i s independent of a and b, so t h a t by 3 N i t e r a t i o n , t h e r e i s a s t r a t e g y M f o r v h i c h d o-^(M)/d 0 < (—) f o r a l l p o s i t i v e i n t e g e r s N„ These c o n s i d e r a t i o n s l e a d i m m e d i a t e l y t o the f o l l o w i n g lemmao Lemma 3.2 L e t the domain D and c l a s s of f u n c t i o n s F be g i v e n , w i t h D c f o r some q„ Suppose c D m f o r some p o s i t i v e i n t e g e r m„ A s u f f i c i e n t c o n d i t i o n t h a t the f u n c t i o n a l be l o c a l i z a b l e is that t h e r e e x i s t s a p o s i t i v e i n t e g e r k, a r e a l number c, 0 < c < 1, and a c l a s s B of bounded subsets of such that ( i ) K f B o ( i i ) For every s e t K6B, t h e r e e x i s t k p o i n t s x^ ;X2> =.» x^., such t h a t i f f € F and 3 ( f ) gK, then K D [y 6 K q ! y = S(g) f o r gCF such that -- f(x..) i = 1, 2. ... k } c' K • , where K'€ B and d[K'] < ed[K]„ Moreover, t h e r e i s a s t r a t e g y M such t h a t d^(M) < (v /c)^d Q/c , f o r a l l p o s i t i v e i n t e g e r s N. P r o o f I t i s e v i d e n t t h a t i f M denotes the s t r a t e g y v h i c h d e f i n e s the g i v e n k p o i n t s terms of' K, and r e s t r i c t s S ( f ) t o the c o r r e s p o n d i n g s e t K', then d j c(M) < c ^ 0 > ^ o r 48 p o s i t i v e i n t e g e r s p. I f N i s any p o s i t i v e i n t e g e r , then there i s an i n t e g e r p such t h a t pk < N < pk + k; so d N(M) < d p k(M) < e*d ~~ o = feQ*k+k d Q / c < fcfc)N d o/c . In p a r t i c u l a r , the f u n c t i o n a l i s l o c a l i z a b l e with r e s p e c t to M. The c l a s s B of lemma 3 ,2 i s more or l e s s a r b i t r a r y , though there i s u s u a l l y a simple and convenient choice f o r any given problem. I t i s o f t e n p o s s i b l e to take f o r B the c l a s s of a l l homothetic images of K q ; thus, i f K q i s a compact i n t e r v a l , so are a l l the members of B . O c c a s i o n a l l y , i t may be d e s i r a b l e , e s p e c i a l l y i f the dimension of D or K Q i s g r e a t e r than 1, to choose B as the c l a s s of a l l compact convex subsets of K Q . We are i n t e r e s t e d i n p r o v i n g a converse r e s u l t to lemma 3 . 2 ; namely t h a t i f a f u n c t i o n a l i s l o c a l i z a b l e , then i t i s l o c a l i z a b l e at at l e a s t a geometric r a t e . This r e q u i r e s a r e s t r i c t i o n which i s perhaps best s t a t e d as a separate hypothesis. D e f i n i t i o n 3 .3 Suppose the domain D and c l a s s F are given, where D i s a compact cube i n E^, and K Q= D. Consider any compact cuhe H contained i n D. The coordinates of H can be i d e n t i f i e d with those of D by a mapping ^ of H onto D c o n s i s t i n g of a proper E u c l i d e a n motion followed by a change of s c a l e . The c l a s s F i s c a l l e d homogeneous with respect to the f u n c t i o n a l S, i f , given any f€F, and a compact subset H of D, c o n t a i n i n g S ( f ) , 4 9 A the f u n c t i o n f r e s t r i c t e d to H becomes a nev f u n c t i o n i d e f i n e d on D a f t e r a p p l y i n g the map where r5 s a t i s f i e s ( i ) s ( f ) = e ( s ( f ) ) ( i i ) ? <= P . Theorem 3.4 I f P and D are g i v e n , D = K b e i n g a compact cube i n E q , and i f P i s homogeneous w i t h r e s p e c t to the f u n c t i o n a l S, then a l l the hypotheses of lemma 3.2 h o l d . I n p a r t i c u l a r , t h e r e i s a c o n s t a n t c < 1, and a s t r a t e g y M, such t h a t d^(M)<(k«/c ) ^ d o / c , f o r some k. P r o o f L e t B be the c l a s s of a l l compact subcubes of D. L e t c, 0 < c < 1 be a r b i t r a r y . S i n c e the f u n c t i o n a l i s l o c a l i z a b l e , t h e r e i s an i n t e g e r k, and an a b s c i s s a s e t X , such t h a t f o r a l l f € P d[H 1(f,x o)] < c d [ K o ] . But then, H..(f,X ) can be c o n t a i n e d i n u cube R, (l')€B where i o .1 d[K-^(f)] < cd[KQ]» The hypotheses guarantee th»t t h i s can be i t e r a t e d i n d e f i n i t e l y by s u i t a b l e changes of s c a l e . Theorem 3.4 can be extended to the general cp.se where f o r a l l f € F , S ( f ) € K = BM f o r some i n t e g e r IT: > 1, D b e i n g a compact cube i n E q„ F i r s t , d e f i n i t i o n 3.3 i s adopted;, re pi r. c:mw t h ? pc Lnt S(f)eH by i t s c o r r e s p o n d i n g m-tuple [d^ ( f ) , a 0 ( f ) , . . . a m ( f ) 1 where a ^ ( f ) € D . Theorem 3.4 then c a r r i e s over f o r some c o n s t a n t c^ Tor at l e a s t a f i n i t e number of stn g e s . (K , and I L t f ^ X ) must be ,J o 1 o r e p l a c e d by D and a subcube of i) r e s p e c t i v e l y ) , The procedure c o n t i n u e s i n d e f i n i t e l y s h o u l d a . , ( f ) , . . . ( f ) happen to c o i n c i d e , o t h e r w i s e i t ceases, f o r some cube 1! "~ D, when a t l e a s t two p o i n t s are near o p p o s i t e ends of a 50 d i a m e t e r o f H. I f nov, H c a n be s p l i t i n t o a f i n i t e number o f s u b c u b e s , e a c h c o n t a i n i n g a k n o v n s u b s e t of the p o i n t s a - ^ ( f ) , ... a m ( f ) > a n ^ i f e a c h o f t h o s e define l o c a l i z a t i o n p r o b l e m s v i t h s i m i l a r h o m o g e n e i t y c o n d i t i o n s as i n d e f i n i t i o n 3.4, l o c a l i -z a t i o n may p r o c e e d , v i t h n e v c o n s t a n t s c f o r e a c h s u b s e t . By c o n t i n u i n g i n t h i s v a y , one e v e n t u a l l y a r r i v e s a t t h e s i t u a t i o n v h e r e e a c h a ^ ( f ) i s k n o v n t o 1 Le i n a cube H_.(f) ? t h e I L ( f ) b e i n g d i s j o i n t . I f e a c h a ^ ( f ) c a n be l o c a l i z e d as a p o i n t i n i t s c o r r e s p o n d i n g cube R \ ( f ) , i n t h e c l a s s o f f u n c t i o n s o f t h e t y p e f r e s t r i c t e d t o H ^ ( f ) , and i f a g a i n t h e h o m o g e n e i t y r e q u i r e m e n t i s met, e a c h a ^ ( f ) c a n be l o c a l i z e d a t a g e o m e t r i c r a t e . I f c i s n o v t a k e n as t h e supremum o f a l l t h e c o n s t a n t s c-^, ... u s e d i n t h e above p r o b l e m s , t h e n c < 1, and d j j ( M ) , f o r some M, i s bounded above by a g e o m e t r i c s e q u e n c e c o n v e r g i n g t o z e r o . An example v h e r e t h e above argument v o r k s i s p r o v i d e d by t h a t i n s e c t i o n 2-5. Q u i t e o f t e n , t h e r e q u i r e m e n t that D be a cube c a n be d r o p p e d . The o n l y r e a s o n f o r c h o o s i n g D as a cube i s t h e f a c t t h a t any s u f f i c i e n t l y s m a l l s u b s e t o f a cube ca n be c o n t a i n e d i n a p r o p e r s u b c u b e o f a cube. This p r o p e r t y i s n o t enjoyed by, f o r e x a m p l e , d i s c s i n a p l a n e . However, f o r some problems, as i n t h e o r e m 1.13, t h i s r e q u i r e m e n t i s i r r e l e v a n t . The e x i s t e n c e o f a g e o m e t r i c sequence of p o s i t i v e terms v h i c h p r o v i d e s a l o v e r bound f o r the sequence d^ i s l e s s obvious even on i n t u i t i v e g r o u n d s t h a n t h e corresponding r e s u l t f o r u p p e r b o u n d s . T h i s i s so b e c a u s e , f o r g i v e n f'CF, the i n f o r m a t i o n knosm 51 a b o u t f n e c e s s a r i l y i n c r e a s e s as t h e s t r a t e g y c h o s e n p r o c e e d s , and c o n c e i v a b l y , t h i s c o u l d r e s u l t i n a q u i c k e r d e c r e a s e o f djj f o r l a r g e N compared t o t h e d e c r e a s e f o r s m a l l N„ Ve have s e e n e a r l i e r i n t h i s c h a p t e r t h a t i f d k ( M ) < cd f o r some k, some s t r a t e g y M^and some c < 1, t h e n q u i t e o f t e n d ,.(M) < c P d f o r a l l p o s i t i v e i n t e g e r s p, The c o r r e s p o n d i n g s t a t e m e n t w i t h t h e i n e q u a l i t y s i g n s r e v e r s e d i s n o t t r u e . F o r e x a m p l e , i n t h e u n i m o d a l p r o b l e m o f t h e o r e m 1.1, where D = [ 0 , l ] , d 2 ( M ) > i | f o r a l l s t r a t e g i e s M. B u t d ^ ( M ) , by a s u i t a b l e c h o i c e o f M, c a n be made a r b i t r a r i l y c l o s e o f ^ . The m a i n r e a s o n f o r t h i s i s t h a t t h e v a l u e o f f ( x ) , f € F , x€D, c a n be u s e d f o r x b e l o n g i n g t o two o r more a b s c i s s a s e t s . The f o l l o w i n g t h e o r e m h o l d s i n a l l t h e e x a m p l e s c o n s i -d e r e d where D c o n t a i n s a l l p o i n t s S ( f ) , and t h e a s s u m p t i o n s o f d e f i n i t i o n 3,3 h o l d . I t s p r o o f i s d e r i v e d i n a manner s i m i l a r t o t h e p r o o f o f t h e i n e q u a l i t y L n < L n ^ + L n ^ ^ n t h e o r e m 1.1. Theorem 3.5 Suppose t h e domain D and c l a s s o f f u n c t i o n s F a r e g i v e n , where D = K q i s a compact cube c o n t a i n e d i n t h e E u c l i d e a n s p a c e Assume t h a t t h e r e e x i s t s an i n t e g e r k and a c o n s t a n t c, 0 < c < 1 s u c h t h a t f o r a l l c l o s e d s u b c u b e s H o f D, t h e f o l l o w i n g c o n d i t i o n s h o l d : ( i ) T h e r e e x i s t k d i s t i n c t p o i n t s , x ^ , x 9 ? X j _ , b e l o n g i n g t o t h e i n t e r i o r o f H s u c h t h a t i f f € F and S ( f ) c H , t h e n [y€H | y = S ( g ) f o r some g i n F s u c h t h a t f ( x i ) = g ( x i ) , i = l , 2 , . . , k 3 i s c o n t a i n e d i n a su b c u b e a t H w h i c h does n o t c o n t a i n a t l e a s t one o f t h e p o i n t s x. i n i t s i n t e r i o r . 52 ( i i ) I f f f P a n d S(f)<=H, t h e n H i s i d e n t i c a l v i t h {y€H|y=S(g) f o r some g^F s u c h t h a t g ( x ) = f ( x ) f o r a l l x i n D b u t n o t i n H ] , ( i i i ) I f X = {x-p x^, • .» x^} i s any s e t o f k d i s t i n c t p o i n t s i n H, t h e n t h e r e i s a f u n c t i o n f € F s u c h t h a t S ( f ) € H and t h e s e t {y€H| y = S ( g ) f o r some g6F s u c h t h a t f ( X ) = g ( X ) } c o n t a i n s a cube H 1, v h e r e d [ H ' ] > c d [ H ] . Then, t h e r e i s a p o s i t i v e c o n s t a n t K s u c h t h a t N djg > f o r a l l p o s i t i v e i n t e g e r s N a Remark C o n d i t i o n ( i i ) g u a r a n t e e s t h a t once i t i s k n o v n t h a t S ( f ) € H , no f u r t h e r r e s t r i c t i o n on S ( f ) may be o b t a i n e d by e v a l u -a t i n g f a t p o i n t s e x t e r i o r t o H. C o n d i t i o n ( i i i ) means t h a t t h e c l a s s P c o n t a i n s 'too many' f u n c t i o n s f o r l o c a l i z a t i o n t o be 'to o f a s t ' . P r o o f o f Theorem 3,5 As i n t h e p r o o f o f t h e o r e m 1.1, a p o s i t i v e i n t e g e r n i s s e l e c t e d , n > k, and t h e c o o r d i n a t e s o f D a r e c h a n g e d by a p r o p e r E u c l i d e a n m o t i o n and s c a l a r m u l t i p l i c a t i o n so t h a t D i s a cube o f d i a m e t e r L . L i s d e f i n e d t o be t h e l a r g e s t r e a l n n number, s u c h t h a t , f o r a l l f e F , S ( f ) c a n be r e s t r i c t e d t o a cube o f d i a m e t e r 1 b y t h e e v a l u a t i o n o f f a t a t most n p o i n t s . I t i s s u f f i c i e n t t o show t h a t L .. > cL f o r a l l p o s i t i v e i n t e g e r s n > k. S e l e c t k d i s t i n c t p o i n t s {x^, x 2« x^} i n t h e domain D v i t h d i a m e t e r L n , and e v a l u a t e f ( x ^ ) , i = 1, 2, ,,. k, f o r some f£F. C o n s i d e r t h e s e t D' = {y€~D\ y = S ( g ) f o r some g€P s u c h t h a t g ( x ^ ) = f ( x ^ ) , i = 1, 2, ... k.}. I t f o l l o v s f r o m c o n d i t i o n s ( i ) and ( i i ) t h a t , g i v e n S ( f ) f D ' , one c a n r e s t r i c t S ( f ) t o a cube o f 53 diameter 1 , for at least one suitable choice of the abscissa set {xj^ , ...x^3> by evaluating f at (n-l) points i n D'„ By condition ( i i i ) D" contains, for some f£_F, a cube of diameter at least cL>n. Hence, L , > cL , and this i s true for a l l n > k. ' n - l _ n' Since L^ . must be f i n i t e , the result follows. / Remark Like theorem 3.4, this result can be extended under suitable conditions to the case where S(f)gK = IT for some o m > 1 . 3 - 2 Speed with Lipschitz Conditions An important question, which i s here l e f t unanswered, arises out of theorem 3.5. If, for given F and D, the sequence djj can be bounded from below by a geometric sequence of positive terms converging to zero, what r e s t r i c t i o n s on F are necessary so that djj cannot be bounded from below in this way ? In other words, what conditions on F give a sequence &^  which converges to zero faster than any geometric sequence ? Consider for example the problem of l o c a l i z i n g the (unique) zero of a real-valued function f defined on an i n t e r v a l . If a l l that i s known about f i s the fact that f i s continuous and s t r i c t l y monotonic, vanishing at a single point i n the i n t e r v a l , then as i n section 1 - 1 , d-^ > ( • 2 ^ ' On "the other ha.nd, i f f i s also known to possess a derivative which i s bounded away from zero, and a bounded second-derivative, then the cla s s i c regula-f a l s i sequence 54 w i t h X q and g i v e n , and v h i c h c a n he f o r m u l a t e d i n t e r n s of d e f i n i t i o n 2.4, g i v e s a s e q u e n c e f o r v h i c h t h e r a t i o d j ^ + ^ / d-^ a p p r o a c h e s z e r o as N -The one r e s u l t ve have i n t h i s d i r e c t i o n i s t h a t i t i s n o t s u f f i c i e n t f o r f a s t e r t h a n g e o m e t r i c c o n v e r g e n c e t o know t h a t f i s c o n t i n u o u s l y d i f f e r e n t i a b l e w i t h k n o v n u p p e r and l o w e r bounds on t h e d e r i v a t i v e s . More p r e c i s e l y : Theorem 3 . 6 L e t D be t h e u n i t i n t e r v a l [ o , l ] , and l e t P be t h e c l a s s o f r e a l - v a l u e d c o n t i n u o u s l y d i f f e r e n t i r b l e f u n c t i o n s f d e f i n e d on D, f o r v h i c h f ( 0 ) < 0 < f ( l ) , 0 < P < f ( x ) < Q < », v h e r e P and Q a r e two f i x e d c o n s t a n t s , and f ' ( x ) i s t h e d e r i v a t i v e o f f a t any p o i n t x€D. L e t a = S ( f ) be t h e z e r o o f f . Then t h e r e e x i s t s a s t r a t e g y M f o r v h i c h dN(M) = [ | U - | ]» and m o r e o v e r t h i s s t r a t e g y i s b e s t p o s s i b l e i n t h e s e n s e tha,t d N > [ 2' (1 " QJ f o r a l l p o s i t i v e i n t e g e r s N. P r o o f L e t [ a , b ] be any c l o s e d s u b - i n t e r v a l of D, and s u p p o s e f o r some f € P , i t i s k n o v n t h a t a = S ( f ) € [a,b]>, SeJ e c t a p o i n t x ^ [ a , b ] , and e v a l u a t e f ( x ) 0 T h e r e a r e f o u r p o s s i b i l i t i e s f o r a, g i v e n b y Q(b-x) < f ( x ) < - P ( b - x ) P ( b - x ) < f (x) < 0 0 < f ( x ) < P ( x - a ) P ( x - a ) < f ( x ) < Q(x-a) . ( i ) x ( i i ) x ( i i i ) x ( i v ) a f(x) Q ftxi < a < b P a < x -< a S x < a < x f ( x ) HA p Q i f i f i f i f 55 A l l o f t h e s e i n e u q a l i t i e s a r e b e s t p o s s i b l e i n t h e s e n s e t h a t f o r g i v e n f ( x ) , {y| a < y < b, y = S ( g ) where g € ? and g ( x ) = f ( x ) } c o n t a i n s t h e i n t e r i o r o f t h e a p p r o p r i a t e i n t e r v a l f o r a. The l e n g t h s o f t h e two i n t e r v a l s i n ( i ) and ( i i ) a r e bounded above b y ( b - x ) ( l - j^ ) , w i t h e q u a l i t y i f f ( x ) = - P ( b - x ) . S i m i l a r l y , t h e l e n g t h s o f t h e two i n t e r v a l s i n ( i i i ) and ( i v ) a r e bounded above by ( x - a ) ( l - ^) w i t h e q u a l i t y i f f ( x ) = P ( x - a ) . I t f o l l o w s , t h a t i n o r d e r t o m i n i m i z e t h e maximum o f a+b t h e l e n g t h s o f t h e f o u r i n t e r v a l s , one must c h o o s e x = "^J"? & n ( l t h e n , by e v a l u a t i n g f ( x ) , a c a n be r e s t r i c t e d t o an i n t e r v a l o f l e n g t h ^ ( b - a ) ( l - Q) , Hence, by r e p e a t e d b i s e c t i o n , S ( f ) c a n • 1 / , E M N engxn L " f a t a s e q u e n c e o f N p o i n t s i n D . be r e s t r i c t e d t o an i n t e r v a l o f l e n g t h [ ^ ( l - g ) ] by e v a l u a t i n g To c o m p l e t e t h e p r o o f , i t must be shown t h a t d-N > L^(x - Q)]^» T h i s i s done by i n d u c t i o n on N. I f N = 1 , a = 0 , and b = 1 , t h e n t h e maximum l e n g t h o f t h e f o u r i n t e r v a l s 1 P i s g r e a t e r t h a n o r e q u a l t o 7 j ( l - jj) , w i t h e q u a l i t y o n l y i f x = ^ - a n d f ( x ) = - ^ P . So d^ > ^ ( l - ~)< L e t F_^  be t h e s u b c l a s s o f F f o r w h i c h f£F^ i f and o n l y , i f f o r some € > 0 , 0 < S ( f ) < €, and f ( x ) = P x i f € < x < 1 . Suppose f o r some f € F ^ , and any p o s i t i v e i n t e g e r N, i t i s known on o n l y t h a t 0 < S ( f ) < [ ^ ( l - Q)]^> f h a v i n g been e v a l u a t e d a t N p o i n t s i n D . Then, i f € i s s m a l l enough, f ^ ^ [ ^ ( l - Q)1^ ^ ^ [ ^ ( l - ^ ) ] ^ and S ( f ) c a n n o t be r e s t r i c t e d t o a s u b - i n t e r v a l o f t h e open i n t e r v a l ( 0 , [ ^ ( l - )^]^ ~t*"'')« T h i s c o m p l e t e s t h e 56 i n d u c t i o n , and p r o v e s t h a t d^ > L ^ d - JJ) J f o r a l l p o s i t i v e i n t e g e r s N. Remark U n l i k e t h e b i s e c t i o n p r o b l e m o f s e c t i o n 1-1, t h e s t r a t e g y M o f t h e o r e m 3.6 u s e s t h e f u l l i n f o r m a t i o n p r o v i d e d by t h e n u m e r i -c a l v a l u e o f f ( x ) w h e n e v e r t h i s i s computed. F u r t h e r , i f P=0,or Q i s i n f i n i t e , t h e n d M = ( T T ) ^ e x a c t l y as i n s e c t i o n 1-1, 3-3 E x p o n e n t s G i v e n a s e q u e n c e [x n3 w h i c h c o n v e r g e s t o t h e z e r o a o f a f u n c t i o n , one d e f i n e s i n n u m e r i c a l a n a l y s i s , an i n d e x as a m e a sure o f t h e s p e e d a t w h i c h X q a p p r o a c h e s a., I t i s c o n v e n i e n t t o i n t r o d u c e h e r e a s i m i l a r i n d e x f o r c o m p a r i n g d i f f e r e n t s t r a t e -g i e s . We c a l l i t an e x p o n e n t . As i n d i c a t e d i n c h a p t e r 1, t h e e x p o n e n t c o u l d r e f l e c t many t h i n g s a s s o c i a t e d w i t h t h e p r o b l e m . We s h a l l , h o w e v e r , a l l o w d ependence o n l y on t h e s t r a t e g y , t h e d i a m e t e r o f s e t s w h i c h a r e known t o c o n t a i n t h e p o i n t S ( f ) , and t h e number o f p o i n t s i n t h e domain D a t w h i c h a f u n c t i o n f i s e v a l u a t e d . Of t h e many p o s s i b l e i n d i c e s w h i c h may be m e a n i n g f u l l y d e f i n e d , we s e l e c t t h e f o l l o w i n g : D e f i n i t i o n 3.7 L e t N be a. p o s i t i v e i n t e g e r . Suppose t h e domain D, and t h e c l a s s o f f u n c t i o n s F a r e g i v e n . F o r any s t r a t e g y M / 1 N u s e d t o s e a r c h f o r t h e f u n c t i o n a l , p u t pjj(M) = f-^ o y'^jj^^-5 > where d-^(M) i s as d e f i n e d i n d e f i n i t i o n 3.1, and d o i s t h e d i a m e t e r o f K . o 57 D e f i n e p N = sup p N ( M ) = [ d Q / d N ] ^ p = l i m p N p(M) = l i m p N ( M ) N -» eo p = sup P (M). M l i m PJ^ J d e n o t e s t h e l o v e r l i m i t o f p^ as N -* oo. T$ 0 0 D e f i n i t i o n 3.8 The number p i s c a l l e d t h e e x p o n e n t o f t h e l o c a l i -z a t i o n p r o b l e m . A s t r a t e g y M f o r v h i c h p(M) = p i s c a l l e d an o p t i m a l s t r a t e g y . D e f i n i t i o n 3.9 I f and M 2 a r e t v o s t r a t e g i e s f o r l o c a l i z i n g a f u n c t i o n a l , i s a t l e a s t as good as i f p(M^) > p (M^). Remark The t e r m i n o l o g y o f d e f i n i t i o n s 3.8 and 3.9 c a n e q u a l l y be a p p l i e d t o PJJ(M) and P j j , f o r a n y p o s i t i v e i n t e g e r N. T h i s i s a p p r o p r i a t e f o r t h e c a s e v h e r e i t i s d e c i d e d a p r i o r i t h a t no f u r t h e r c o m p u t a t i o n i s c a r r i e d o u t a f t e r t h e f u n c t i o n f 6 P has been e v a l u a t e d a t N p o i n t s i n t h e domain D. F o r g i v e n N, a s t r a -t e g y M f o r v h i c h Pj^(M) = p i s a l s o c a l l e d o p t i m a l . Lemma 3 . 1 0 F o r any s t r a t e g y M, t h e r e e x i s t c o n s t a n t s c^ and c^ s u c h t h a t 1 < c 2 < p N ( M ) < C ; I < CD f o r a l l s u f f i c i e n t l y l a r g e N, i f and o n l y i f -N d o C l < d„(M) < d c . " N f o r a l l s u f f i c i e n t l y l a r g e N. 58 Thus the quantity p(M) i s useful only for f i r s t order processes. Lemma 3.11 p = p Proof If M i s any strategy for l o c a l i z i n g the functional then P N (M) < sup p N (M) = p . M Since this inequality holds for a l l positive integers N, p (M) = lim_ p N (M) < lim_ P N = P . N -* oo N -• 00 But this i s true for a l l strategies M, and hence p < p . On the other hand, the inequality lim p N (M) = p (M) < p N -• 00 holds for a l l strategies M, and so lim P N < p . N -+ OS Therefore p < p Corollary 3.12 In order to estimate p, i t i s enough to estimate Pjj , and allow N to increase i n d e f i n i t e l y . One reason for our choice of exponent, i s that i t gives i n general a good estimate of the ratio (M) / djj(M) , i . e . , the average decrease i n diameter per evaluation of the function. More precisely: Lemma 3.13 p(M) = lim d-^ (M) / d N ,(M) N -* 00 provided the right hand side exists. 59 Proof By a standard result of c l a s s i c a l analysis, that for any sequence dM(M) of positive numbers lim % + 1 ( M ) / dN(M) < lira [ d N ( M ) ] N < lim" [ d N ( M ) ] N N -• oo N -* oo < ITS d N ,(M)/dN(M) N -» oo vhere lim and lim denote lover l i m i t and upper l i m i t respectively, i t f o l l o v s that 1 lim d N ,(M) / dN(M) = lim [ d N ( M ) ] N N -» oo N -• <o = M l i r a do / PN<M) N -» os = 1 / lim pN(M) N -» oo = 1 / p(M) Sxample 3.14 ¥e consider and compare the tvo strategies given in section 1-3 for l o c a l i z i n g the maximum point of a unimodal function. Take D = [0,l] = K so that d =1. ' o o If N i s any given integer, then d N = i n f x M So p = p = lim ( P N ) N = (1 + S)/2 . It should be N -• oo noted that there i s no strategy M for vhich PJJ(M) = PJJ , although for every € > 0, there i s a strategy M for vhich P N - € < PN(M) < p N . If Mf denotes the golden-mean strategy, then d = d,(M1) = 1 and o 1 dN(M') = [L/5- l ) / 2 f ~ 1 i f N > 2 60 1 " I So P N(M«) = [(V5 + 1)/ 2] i f N > 2 and p (M') = C/5 + l ) / 2 = p = p . M' i s an o p t i m a l s t r a t e g y a c c o r d i n g t o d e f i n i t i o n 3.8, I n o r d e r t o compare t h e t w o s t r a t e g i e s , l e t us s u p p o s e t h a t N i s g i v e n , and t h a t f u n c t i o n s f € F may be e v a l u a t e d a t j u s t N p o i n t s i n D, T h e r e i s t h e c h o i c e o f e i t h e r u s i n g t h e a p p r o p r i a t e F i b o n n a c c i numbers, o r u s i n g t h e gol d e n - m e a n s t r a t e g y . One c a n compute t h e r a t i o djj(M')/ djj o r p^(M')/p^ , t o g i v e some i d e a o f h o v much s l o v e r t h e golden-mean s t r a t e g y i s , when e m p l o y e d f o r t h e c a s e where N i s g i v e n . I n d e e d , s i n c e i , . /=• N+l , , i= N+l F N = h ( 1 X ^  ) - i ( 1 ; > / 5 ) , f o r N > 0 N V 5 2 7 5 2 a N ( M ' ) / d N = [ P N / P N ( M ' ) ] N N - l = V V-^-Y1) i f N > 2 = (3 + fi)/{2fi) + [U/5 - 3 ) / 2 ] N / S F o r l a r g e N, d^(M') ~ d N ( l . l 7 . . . ) and P N ~ P N(M') ^ ( l . l ? . . . ) One c a n a s k , i n g e n e r a l , t h e f o l l o w i n g q u e s t i o n . Suppose M i s a s t r a t e g v f o r w h i c h p(M) = p = l i m p N • N - • F o r any g i v e n p o s i t i v e i n t e g e r N, how does P^(M) compare w i t h p^ ? I n o t h e r w o r d s , i f M i s an o p t i m a l s t r a t e g y , and M i s u s e d o n l y u n t i l t h e f u n c t i o n f f F i s e v a l u a t e d a t N p o i n t s i n D, how does t h i s p r o c e d u r e compare w i t h t h e b e s t p r o c e d u r e p o s s i b l e when N i s g i v e n ? T h i s a p p e a r s t o be a d i f f i c u l t q u e s t i o n t o 6 1 answer, though we present below a solution for a special case. F i r s t , a lemma i s established which gives information on,the behaviour of p-^  . Lemma 3 . 1 5 Suppose the domain D , and class F are given, such that (i) D = K q i s a compact interval on the real l i n e with length d Q. ( i i ) If K i s any compact sub-interval of D , i f f€F,- S ( f ) £ K , and X i s any abscissa-set i n K , and i f K ' = [x 6 K| x = s(g) for some g€F such that f(x) = g(x) ] then K ' i s a sub-interval of K , and the ratio of diameters d [ K ' ] / d [ K ] i s invariant under a l l changes of coordinates of D which take the form of translation followed by a change of scale. Then (a) < p for a l l positive integers N. (b) Pjj < P m ^ for any N and a l l positive integers m. Proof It i s immediate from condition ( i i ) that i f , for some strategy M, and any k, d^(M) < d Q, then for a l l positive inte-gers m, d k / d Q < [ d k ( M ) / d o ] m , It follows that pK(M> - td o / d k ] k < [ d o / d m k r k = P n k and hence p k < p m k for a l l positive integers m and k. This proves (b). To prove (a), assume that p k > p for some fixed k. Then by (b), p f f l k > p k > p for a l l positive integers m. If N i s any s u f f i c i e n t l y large positive intever, then there i s an m such that mk < N < mk + k, Since the sequence d w i s 62 non-increasing in N, ^ ^ P N - [*„/ d / s [ d 0 / d ^ f * mk N-k > P k N . But this l a s t inequality i s impossible, since i t implies that p = lim p.T „ ^_ N — » > P k > P • D e f i n i t i o n 3.16 A strategy M i s called periodic i f for two fixed integers p and k, and some constant \, for a l l positive integers m. Periodic strategies often arise i n cases where given the domain D, and an abscissa set X i n D, one gets a new domain D' and an abscissa set X' related to the former by a translation and change of scale, by evaluating any function f£F at exactly k points i n D dif f e r e n t from X. An example i s the golden-mean strategy M, with p = 1, k = 1, d^ (M) = 1 and X = . Here, one always has an in t e r v a l , with an abscissa set which consists of the two points which divide the interval i n the golden r a t i o . Lemma 3.17 Suppose the conditions of lemma 3.14 are s a t i s f i e d , and there i s an optimal periodic strategy M (which implies that X = p). Then 1 S P p + m k / P p + m k<M) < o = 63 f o r a l l p o s i t i v e i n t e g e r s m where c i s a f i x e d c o n s t a n t c > 1 I n o t h e r w o r d s , t h e d i f f e r e n c e p . , — p , , (M) = 0 (—) . ' rp+mk p+mk %m P r o o f [p ^ . ( M ) ] p + k r a = [ d / d , (M)] = [ d 0 / d p ( M ) ] P m k = [p ( M ) P p m k Hence P p + k m ( M ) / p = [ p P ( M ) / P ] P + ^ and t h e r e f o r e P Fp+km Kp+km P i f c = [ p / P p ( M ) ] k . 3 - 4 O p t i m a l S t r a t e g i e s F o r t h e f i n a l p a r t o f t h i s c h a p t e r , we c o n s i d e r t h e q u e s t i o n o f t h e e x i s t e n c e o f o p t i m a l s t r a t e g i e s . Ve have s e e n a l r e a d y t h a t i f t h e number N o f o b s e r v a t i o n s a l l o w e d i s g i v e n a p r i o r i (N f i n i t e ) , t h e n t h e r e may n o t e x i s t an o p t i m a l s t r a t e g y . F o r e x a m p l e , c o n s i d e r N = 2 i n t h e u n i m o d a l p r o b l e m as i n t h e o r e m 1.1, where i f d = 1, t h e n d 2 = ^ » v e ^ d 2 ( M ) > ^ f o r e v e r y s t r a t e g y M.' N e v e r t h e l e s s , t h e r e do e x i s t two numbers x^ and x 2 i n a m e l y x^ = x 2 = s u c h t h a t t h e b e s t a t t a i n a b l e r e s u l t s may be o b t a i n e d b y c h o o s i n g an a b s c i s s a s e t , e a c h e l e m e n t o f w h i c h i s a r b i t r a r i l y c l o s e t o x-( and x 9 r e s p e c t i v e l y . 64 It i s the purpose of this section to show that under certain conditions, there exists a point X i n a Euclidean space, such'that the best possible results may be obtained by selecting a point Y either equal to X or a r b i t r a r i l y close to i t . This point Y e f f e c t i v e l y defines the strategy M. Defini t i o n 3.18 Let D be a given domain. For two positive integers k, and N, l e t X = l x ^ i X21' * ° *' x2k' x31' '' ° ' x3k^ ' x4]^ , . . . , X4k"^ ' x51 0 ° * ' ° * * ' x N l ' ° ° ° xNk^ ""^ " ^  be an ordered set of points i n D. X can be regarded as a vector in the Cartesian pro-duct set D = D x D x D x . . o X D Define a re l a t i o n on the elements x^^ , 1 < j < k^~\ of X by x.j -< x i + 1 ^ .,, i f and only i f ( j - l ) k < j 1 < jk for a l l i = 1, 2, 3, ... (N-l), D e f i n i t i o n 3.19 Let X be as i n d e f i n i t i o n 3.18 . A chain at X i s an ordered sequence x, •, x„ . , . . . x>T . of elements of U i 2 j 2 N , j N X, vhere x• • ^ x. for i = 1, 2, 3, ... (N-l), Thus, for each X, there are k^-"^ chains, each consisting of N elements of X. Defi n i t i o n 3.20 Suppose D and a class of functions F v i t h domain D are given. Suppose X i s as i n d e f i n i t i o n 3,18, such 65 that the re l a t i o n (see d e f i n i t i o n 2.1l) partitions F at X into a f i n i t e number p of equivalence classes F 1(X), P 2(X), ... F (X). Put d M[F.(X)] = i n f diam.{x€H |x = S(g) for some g€P such that JN X y 0 f(Y) = g(T), where feF.(X), g€F (X), and I i s a chain at X) , and put d N(X) = sup d N[P.(X)] . i=l Roughly, this means that given X, d^(X) i s computed by selecting for each equivalence class at X, the 'best' chain at X, and then the 'worst' case taken over a l l equivalence classes. Theorem 3.21 Suppose the class P, and the domain D are given, D being a convex compact subset i n the Euclidean space Assume that for every abscissa set X consisting of a f i n i t e number p of points i n D, the rel a t i o n '"^ partitions P at X into at most kP equivalence classes, where k i s a fixed positive integer. If the function <|>(X), defined by (a) <!>(X) = d^(X), i f every chain at X consists of N d i s t i n c t points i n D, (b) <!>(X) = lim <|>(Y), i f some chain at X consists of N-l or Y - X fewer d i s t i n c t points i n D, i s a continuous real-valued function on D (D with metric defined by the appropriate Euclidean space), then either (i) there i s a strategy M for which = P^(M) or ( i i ) there i s a strategy M for every € > 0, such that 66 p^(M) > p-j^  — where i s defined by points i n a neighbour-hood of a fixed point i n D . Proof It follows from the hypotheses of the theorem, and the preceeding d e f i n i t i o n s , that i f M is a strategy for which K Q = H Q, every i s chosen as the corresponding H^, and which involves the evaluation of functions f£F at N points of D, can be i d e n t i -f i e d with a point X i n D. For, one can select f i r s t a point x-|^ € D, evaluate f ( x ^ ) , select the appropriate equivalence class determined by f(x-j^), then the appropriate e t c . Moreover, under this i d e n t i f i c a t i o n , the two numbers d^(M) of d e f i n i t i o n 3.1, and d^(X) of d e f i n i t i o n 3.20, are i d e n t i c a l . Since D i s compact, so i s D by Tychonoff's theorem on the product of compact sets. So, since <j> i s continuous on D, <t> attains i t s minimum value at some point X i n 1) . There are two p o s s i b i l i t i e s . (i) Every chain at X consists of N d i s t i n c t points in D. Then X defines a strategy M for which PN(M) i s minimal, i . e . , pN(M) = p N . ( i i ) Some chain at X consists of less than N d i s t i n c t points of D. In this case, for € > 0 and arbitrary, there i s a point Y with distance € of X such that every chain at Y consists of N d i s t i n c t points of D. By continuity of the function (|>(X), the point Y defines a strategy M for which pjj(M) i s a r b i t r a r i l y close to p M. 67 Remark F o r t h e b i s e c t i o n and u n i m o d a l p r o b l e m s , and f o r t h o s e p r e -s e n t e d l a t e r i n c h a p t e r 5, t h e f u n c t i o n (j) i n t h e o r e m 3.21 i s t h e supremum o f f i n i t e l y many c o n t i n u o u s f u n c t i o n s , and so i s c o n t i n u o u s . Thus t h e o r e m 3,21 can be a p p l i e d t o t h e s e p r o b l e m s . 68 CHAPTER 4 RANDOM L O C A L I Z A B I L I T Y 4 - 1 D e f i n i t i o n s So f a r , we have c o n s i d e r e d ways o f l o c a l i z i n g a f u n c -t i o n a l by means o f an e x p l i c i t l y g i v e n s t r a t e g y . T h a t i s , a s e t K n , and p o s s i b l y some a b s c i s s a s e t s X^ and r e a l numbers f ( X ^ ) , f € P, i = 0, 1,-2. ... ( n - l ) u n i q u e l y d e t e r m i n e t h e n e x t a b s c i s s a s e t X N . Sometimes t h e u n i q u e n e s s r e q u i r e m e n t c a n be r e l a x e d , as i n t h e s t r a t e g y u s e d by G l e a s o n i n t h e o r e m 1.13, where t h e f i r s t a b s c i s s a s e t X q n e e d be c h o s e n o n l y so t h a t d i s c s o f a c e r t a i n r a d i u s w i t h c e n t r e s a t t h e p o i n t s o f X Q c o v e r t h e u n i t s q u a r e . One a s k s i f i t i s p o s s i b l e t o l o c a l i z e a f u n c t i o n a l b y c h o o s i n g a b s c i s s a s e t s a t random i n some s e n s e . T h i s q u e s t i o n i s i m p o r t a n t , s i n c e o p t i m a l s t r a t e g i e s may be t o o d i f f i c u l t t o d e t e r m i n e , o r t o o c o s t l y t o u s e . The more i n e f f i c i e n t p r o c e d u r e o f l e a v i n g t h e c h o i c e o f a b s c i s s a s e t s t o c h a n c e may be s u f f i -c i e n t l y s a t i s f a c t o r y . F i r s t , we d e f i n e random l o c a l i z a b i l i t y , p r e s e r v i n g t h e t e r m i n o l o g y and n o t a t i o n o f t h e p r e v i o u s c h a p t e r s as f a r as p o s s i b l e . Our d e f i n i t i o n i s e s s e n t i a l l y a g e n e r a l i z a t i o n o f t h e i d e a s g i v e n a t t h e end o f s e c t i o n 1-2. Ve assume that D i s a compact convex body i n Euclidean q-dimensional space E q. Let F be a given family of real-valued functions defined on D , such that to each function f€F, there corresponds a unique point S(f) i n D . Let <l>(x) be a density function defined on D. That i s , <!>(x) i s a non-negative Lebesgue integrable function which vanishes outside of D, such that / <Kx)dx = 1 . D In the following, the terms k-abscissa set X = {x^, x 2, ... x ^ l j and the notation f(X), D k etc., have the same meaning as i n chapter 2. Defini t i o n 4.1 x i s a random variable in D distributed with o density function <1» i f for each measurable subset E of D, the proba b i l i t y that the value of x belongs to E i s f (j>(x)dx. ° E Defi n i t i o n 4.2 Suppose f€F. A kth order random search for S(f) i s defined by the following procedure: (i) Let X = {x , , x _, ..., x , 1 be a k-abscissa set i n D, 0 ol o2 7 ok 7 the elements X q ^ of which are independently distributed random variables, each distributed with density function <|>. ( i i ) Put H (f,X ) = {x€D | x = S(g) for some g€F such that f ( x o ) = g ( x o ) 3 ( i i i ) Let K n(f,X ) be a subset of D such that 1 o H 1(f,X Q) c K 1(f,X Q) . (iv) Let (^(x) be a density function defined on K, ( f , X ) . In general, given the set K n(f,X , ... X J ^), and a density function ^.(x) defined on K ^ ^ X ,X, , ... X^ -j ) , the procedure is continued for a l l positive integers n, by 70 (i) l e t t i n g X n = ( x ^ , x n k ^ be a k-abscissa set in K n ( f , X o , ^n_]_-) > the elements of vhich are independent random variables on K (f, X , X,, ... X , ) , each distributed v i t h n ' o' 1' n-1 ' density (j>n; ( i i ) putting H n + 1(f,X o,X 1,...X a) = {x€K n(f,X o,X 1,..,X n_ 1|x=S(g) for some g£F such that f(X n).= g(X n)}; ( i i i ) l e t t i n g K n +^(f,X Q,X^,...X R) be a subset of K (f.X .X,....X , ) such that n ' o' 1' n-1 H ,,(f,X ,X, , ... X ) c K ,,(f,X , X-, . . . .X ) ; n+1 ' o' 1' n n+1 ' o' 1' n ' (iv) l e t t i n g ^n+^x) be a density function on K n + l ( f ' X o ' X l ' X n ) ' Definition 4.3 A random strategy (usually denoted by M), i s a rule, given i n advance of any computations, vhich determines the density function <|>, the integer k, the set K n in terms of H^, and the density function <fc (x) i n terms of both K and the density n n function q>(x). K , or K (f,MK i s an abbreviation for • n' n ' ' ' K n ( f ' X o , X l , , , , X n - l ) -If X i s the abscissa set X ={x , ,x „,... x , } and n n n l ' n2' nk q> i s the density function on K , ve write n u n' <|> (X ) = q > ( x - , ) < p ( x - ) . . . d ) ( x 1 ) n n T n nl n n2 n nk and dX = dx ,dx 0dx ^ ... dx , n nl n2 n3 nk Vith this notation, we can write an expression for the expected value of the diameter of the set'K M(f,M): n E[K(f,M)].= A X ), , d[K (f,X ,X,, ...X ,)] n D k K k K k K k , n 0 1 1 2 n-1 * n - l ( X n - l > ^ ( X l ^ ( X o ) d X n - l d X n - 2 - - d X n ' 71 where d [ K ( f , X ,X,.... X , ) ] i s t h e d i a m e t e r o f t h e s e t n ' o x n — i n ' o' 1' n - l D e f i n i t i o n 4.4 The f u n c t i o n a l i s r a n d o m l y l o c a l i z a b l e w i t h r e s -p e c t t o t h e random s t r a t e g y M i f l i m sup E [ K ( f , M ) ] = 0. n - » f € P n Remark Some l i m i t a t i o n s on t h e s c o p e o f t h e p r e v i o u s d e f i n i t i o n s a r i s e b e c a u s e t h e random s t r a t e g y must be s t a t e d a p r i o r i . P e r h a p s t h e most n a t u r a l random s t r a t e g y , i s t h a t w h i c h r e q u i r e s e a c h s e t K t o be t h e s m a l l e s t s u p e r s e t o f t h e c o r r e s p o n d i n g s e t H n, w h i c h i s s i m i l a r t o D. Then t h e d e n s i t y f u n c t i o n <l>n(x) on K n may be o b t a i n e d b y a d j u s t i n g t h e f u n c t i o n <|>(x) by a t r a n s l a -t i o n and change o f s c a l e o f i t s c o o r d i n a t e s , w i t h t h e r e s t r i c t i o n t h a t n W i t h t h e above random s t r a t e g y , i t i s p o s s i b l e t h a t some o f t h e s e t s K q may n o t be s u b s e t s o f domain D , i f D has d i m e n s i o n g r e a t e r t h a n 1. O c c a s i o n a l l y , we c a n remove t h i s d i f f i c u l t y b y e x t e n d i n g t h e domain D o f t h e c l a s s o f f u n c t i o n s P, t o D ' e n s u r i n g t h a t a l l p o i n t s S ( f ) , f € P , a r e i n D , and r e q u i r i n g o n l y t h a t K ^ c D 1 . Or, i f D i s a cube, we c a n r e q u i r e n o t o n l y t h a t K Q i s s i m i l a r t o D , b u t a l s o t h a t K i s a s u b s e t o f D . ' n A n o t h e r p o s s i b l e random s t r a t e g y i s one v h i c h demands t h a t e v e r y d e n s i t y f u n c t i o n <l>n(x) be c o n s t a n t . We c a n t h e n c h o o s e K = H f o r a l l n. n n We c a n m o d i f y t h e random s e a r c h p r o c e d u r e as d e s c r i b e d i 72 i n d e f i n i t i o n 4.2 by a l l o w i n g o n l y 1 p o i n t s o f an a b s c i s s a s e t X n t o be c h o s e n a t random, where L <k, f o r n > 1. The r e m a i n i n g (k-L) p o i n t s r e q u i r e d f o r X r c a n be s u p p l i e d b y known r e s u l t s f r o m p r e v i o u s s t a g e s . F o r e x a m p l e , i f D = [ 0 , l ] , and i f we a r e s e a r c h i n g f o r t h e maximum p o i n t o f a u n i m o d a l f u n c t i o n f , t h e n a f t e r s e l e c t i n g two p o i n t s x-^  and x 2 i n D f o r X q , t h e a b s c i s s a s e t X ^ may c o n s i s t o f one o f t h e s e p o i n t s , t o g e t h e r w i t h j u s t one t h i r d p o i n t x,. 4 - 2 G e n e r a l t h e o r e m s and e x a m p l e s I n t h i s s e c t i o n , v e c o n s i d e r t h e r e l a t i o n s h i p b e t w e e n l o c a l i z a b i l i t y and random l o c a l i z a b i l i t y , and some a n a l o g u e s o f t h e o r e m s o b t a i n e d i n c h a p t e r 3. I n t u i t i v e l y , we e x p e c t t h a t u n d e r s u f f i c i e n t r e s t r i c t i o n s , a f u n c t i o n a l i s l o c a l i z a - b l e i f and o n l y i f i t i s r a n d o m l y l o c a l i z a b l e , and t h a t random l o c a l i z a t i o n i s l e s s e f f i c i e n t t h a n l o c a l i z a t i o n . To i l l u s t r a t e some o f t h e d i f f i c u l t i e s w h i c h may a r i s e , l e t u s c o n s i d e r b r i e f l y t h e f o l l o w i n g p r o b l e m . L e t D = [ 0 , 1 ] be t h e u n i t i n t e r v a l , and F t h e c l a s s o f c o n t i n u o u s f u n c t i o n s f , d e f i n e d on D, v h i c h a r e n e g a t i v e e v e r y w h e r e e x c e p t f o r a s m a l l s u b i n t e r v a l o f D on w h i c h t h e y a r e p o s i t i v e and c o n c a v e w i t h a u n i q u e a b s o l u t e maximum p o i n t a t S ( f ) € H ^ . I t i s e a s i l y s e e n t h a t t h e f u n c t i o n a l S ( f ) i s n o t l o c a l i z a b l e , f o r t h e same r e a s o n as i n t h e p r o b l e m c o n s i d e r e d i n s e c t i o n 2-5. The s u b i n t e r v a l o v e r w h i c h a f u n c t i o n f£F i s p o s i t i v e may be t o o s m a l l . A c c o r d i n g t o d e f i n i t i o n 4.4, 73 t h e f u n c t i o n a l i s n o t r a n d o m l y l o c a l i z a b l e e i t h e r . On t h e o t h e r h a n d , l o c a l i z a t i o n o f any p o i n t S ( f ) i s p o s s i b l e a f t e r one p o i n t z a t w h i c h f ( z ) > 0 i s f o u n d . I f i s a l w a y s o f l e n g t h g r e a t e r t h a n z e r o , t h e n t h e r e i s a p o s i t i v e p r o b a b i l i t y o f f i n d i n g s u c h a p o i n t z, i f t h e d e n s i t y f u n c t i o n on D does n o t v a n i s h a n y w h e r e . We w i s h t o p r o v e now t h a t u n d e r s u f f i c i e n t r e s t r i c t i o n s , l o c a l i z a b i l i t y i m p l i e s random l o c a l i z a b i l i t y . L e t us assume t h a t a l l t h e c o n d i t i o n s o f t h e o r e m 3.3 a r e s a t i s f i e d . Then i n p a r t i c -u l a r , i f S ( f ) € K = D, and D i s a compact cube w i t h d i a m e t e r d , t h e n t h e r e i s an i n t e g e r k, a c o n s t a n t c, 0 < c < 1, and a k-a b s c i s s a s e t X , s u c h t h a t H, ( f , X ) c a n be c o n t a i n e d i n a cube o 1 o K, ( f , X ) o f d i a m e t e r a t most cd . T h i s c o n d i t i o n i s n o t 1 o o r s u f f i c i e n t t o Drove t h a t sup E [ K . ( f , M ) ] = J , d [ K ( f ,M) "H (x)dx < d . f € F D 0 Two more a r e r e q u i r e d . F i r s t , i f X q i s r e p l a c e d by any a b s c i s s a s e t Y s u f f i c i e n t l y c l o s e t o X q , t h e n Y i s e q u a l l y a c c e p t a b l e f o r l o c a l i z a t i o n . S e c o n d l y , t h e d e n s i t y f u n c t i o n c|> must be bounded away f r o m z e r o n e a r X q . W i t h t h e s e r e s t r i c t i o n s , we p r o v e Theorem 4.5 L e t D and F be g i v e n j s a t i s f y i n g a l l t h e above c o n d i -k t i o n s . L e t p be t h e E u c l i d e a n m e t r i c on D and s u p p o s e t h e r e i s a k - a b s c i s s a s e t X i n D , and an G > 0 s u c h tha.t o ' ( i ) t h e r e i s a c o n s t a n t c < 1, s u c h t h a t i f Y i s any k - a b s c i s s a s e t i n = { Y g D k | p ( X q , Y ) < € } ? t h e n f o r a l l f f F , H ^ ( f , Y ) c a n be c o n t a i n e d i n a cube K 2 ( f , Y ) where d L K ^ ^ Y ) ] < c d o ( i i ) f o r some 6 > 0, 6 < ( l - c ) J <t(Y)dY . Then sup E [ K ( f , M ) ] < ( l - 6 ) d f 6F 1 c 74 Proof If f€P, then E[K 1(f,M)] = / d L K ^ f ^ l ^ X j d X D k = / d[Kx(f,X)]<j.(X)dX + X d[K x(f,X)]<tdX Dk-B 1 < d Q J <t(X)dX + cd Q J <l(X)dX D k-B € B^ Hence d n [ l - (1-c) J <J»(X)dX] < (1 - 6)d Q sup E[K.(f,M)] < (1 - 6)d Corollary 4.6 If, under the conditions of theorem 4.5, "the den-s i t y functions <|> (x) are defined as indicated in the remark f o l -n lowing d e f i n i t i o n 4.4, then sup E[K (f,M)] < ( l - 6) nd„ f€F n 0 for a l l positive integers n. Example 4.7 Ve show that i f D = [0,l] and P i s the class of unimodal functions defined i n section 1-3, then the functional defined by S(f), f?P, i s randomly l o c a l i z a b l e . Suppose 0 < x < y < 1, and f€F. Then f y i f f(x) > f(y) d t K ^ f , (x,y))] = | l - x i f f(x) < f(y) (y-x i f f(x) = f(y) . 75 I f (j)(x) is a density function defined on D, then E t K ^ f . M ) ] = J | d[K1(f,(x,y)))]<Kx)<Ky) dx dy ^ R where R is the square {(x,y) | 0 < x,y < 1 }, and so sup E[K. (f ,M)] < sup d[K.(f,(xfy))](Kx)<Ky) dx dy f€P - K f g P 1 i y < \ \ [sup{l - x, y] <|>(x)<j.(y) dx dy 0 o 1 x n [ s u p { l - y , x } ] c|>(x)<!>(y) dy dx l / 2 1-x = 2 C \ (l-x)«Kx)«Ky) dy dx 0 X 1 y + 2 J f y «Kx) «t(y) dx dy 1/ , V 2 1-y I n p a r t i c u l a r , i f <|>(x) = 1 f o r 0 < x < 1, t h e n sup fi[K (f,M) ] < ~~ , f £F and, i f t h e a s s u m p t i o n s o f t h e o r e m 4.5 and c o r o l l a r y 4.6 a r e made 5 n sup E [ K , ( f , M ) ] < ( f ) . f <EF F o r c o m p a r i n g t h e e f f i c i e n c y o f random l o c a l i z a t i o n w i t h l o c a l i z a t i o n , we c a n d e f i n e a random e x p o n e n t , a n a l o g o u s t o t h e e x p o n e n t d e f i n e d i n d e f i n i t i o n 3 . 8 . Suppose t h e domain D, and c l a s s F a r e g i v e n , a l o n g w i t h a random s t r a t e g y M. F o r e a c h p o s i t i v e i n t e g e r n, p u t , <>kn<M> = C V ^ E [ K n ( f > M > l 1 k n 76 Vhere d 0 i s the diameter of D, and k i s the number of points i n D belonging to each abscissa set. Define the random exponent with respect to M, to be the number p(M) = l i m p k n (M) . n » There seems to be no point i n defining the number p = sup p(M), since usually one i s concerned with a pa r t i c u l a r M density function <J>. Indeed, i t i s shown l a t e r than the more e f f i c i e n t random strategies for the bisection problem are those for which <j> has a large and thin peak about the mid-point of D. The l i m i t i n g case arises when i i s the Dirac 6-distribution, which yiel d s the bisection method described i n section 1-1. 4 - 3 Random search for a zero By far the simplest problem i n considering random l o c a l i z a b i l i t y i s that of searching for the unique zero of a suitable function defined i n a compact i n t e r v a l . We shall be concerned with this p a r t i c u l a r problem for the remainder of the chapter. Three main results are obtained. F i r s t , three formulas are derived for the jo i n t d i s t r i b u t i o n of the end points of the intervals to vhich the zero of the function i s successively confined, Secondly, the expected values of the lengths of these interval s , and other associated quantities are computed. F i n a l l y , the behaviour of these expected values for large n i s i n v e s t i -gated, and some special cases are considered. It i s assumed throughout that the domain D i s the closed 77 i n t e r v a l [ 0 , l ] , and t h a t t h e c l a s s P d e f i n e d on D c o n s i s t s o f a l l r e a l - v a l u e d c o n t i n u o u s f u n c t i o n s f f o r w h i c h f ( 0 ) > 0 > f ( l ) , a n d w h i c h p o s s e s s a u n i q u e z e r o a = S ( f ) i n D, I t i s a l s o assumed t h a t <|>(x) i s a g i v e n c o n t i n u o u s d e n s i t v f u n c t i o n d e f i n e d on D. I n p a r t i c u l a r , | ( x ) > 0 i f 0 < x < 1, and f i ( x ) d x = 1. o By t h e d e n s i t y f u n c t i o n on t h e i n t e r v a l [ a , b ] , where 0 < a < b < 1, i s meant t h e f u n c t i o n r * <j» (—r ) , d e f i n e d D ~- £i D-—£l f o r a < x < b. T h i s f u n c t i o n i s j u s t <t(x) s u i t a b l y a d j u s t e d b y a t r a n s l a t i o n and change o f s c a l e . Suppose f£F. The random s e a r c h p r o c e d u r e a = S ( f ) commences b y l e t t i n g x be a p o i n t ( a b s c i s s a s e t ) i n D, c h o s e n a t random w i t h d e n s i t y f u n c t i o n d>. I t c a n a l w a y s be d e c i d e d w h e t h e r a < x^, a = x^, o r a > x^, by c o n s i d e r i n g t h e s i g n o f f ( x ) . So one c a n p u t 1^ = l ^ ( a , x ^ ) = 0 and r ^ = r ^ ( a , x ^ ) = x, i f x^ > a 1^ = l ^ ( a , x ^ ) = x^ and r^= r ^ ( a , x ^ ) = 1, i f x-^  < a 1^ = l ^ ( a , x ^ ) = x ^ and r^= r ^ ( a , x ^ ) = x^, i f = a , I n a n y o f t h e s e c a s e s , a f_ [ ] ^ , r ^ ] . L e t x 2 be a p o i n t i n t h i s i n t e r v a l , c h o s e n a t random w i t h r e s p e c t t o t h e d e n s i t y f u n c t i o n ij^on [ l - ^ r ^ ] , a nd d e f i n e and r 2 s i m i l a r l y . S u c c e s s i v e l y , l e t x^, x^, , , , x n , be a s e q u e n c e o f p o i n t s w h e r e , f o r a l l p o s i t i v e i n t e g e r s n, x n + - ^ i s d i s t r i b u t e d a t random w i t h r e s p e c t t o t h e d e n s i t y f u n c t i o n on i l n J r n ^ ? a n c ^ 78 L = L , r ,, = x,, , i f x ,, > a = n+1 n ' n+1 n+1 ' n+1 = x , r ,, = r , i f x J , < a n+1 n' n+1 n ' n+1 L = r = x ,, , i f x ,. = a. n+1 n+1 n+1 ' . n+1 For completeness, put L Q = 0, r = 1. It i s obvious that for a l l positive integers n, 0 < I < i < a < r _,, < r < 1. — n — n+1 — — n+1 — n — Both 1^ and r n are functions of a, and the sequence x ^ , X 2 ? . ..,x . It i s convenient at this stage to define the function F(?, s, t, >j ) for 0 < 5 < s < t < 7 ^ < l , by the equations s-g 1 F ( 5 , s, t, ?j ) = ( 1 ^ d,(x) dx + j J>(:0 dx , i f Z< ^  • F(§, s, t, yj ) = 1 ,. i f § = rj The usefulness of this function i s evident from the following lemma. Lemma 4.8 If ? = I < = r n for some n, bhen the probabj l i t y that either ? < x n + i < s or t < x f l + 1 < i s F(§, s, t,vj ). Proof The stated p r o b a b i l i t y i s n , . ) dx r s - i - 4 ( * 4 ) d x + P-L- i. (x_-g y 4 (l>(u) du + J i (u) du - p ( 5 , S j t,-^ ) t - 5 79 4 - 4 Joint probability d i s t r i b u t i o n Of basic importance i s the j o i n t p r o b a b i l i t y d i s t r i b u -tion of the end points 1 and r of the interval [ l ,r ]- which y n n n' n contains the zero a. This i s given i n terms of the function G n(s,t) below. Defin i t i o n 4.9 Let f€F, and suppose a i s the zero of f. Let s and t be any two numbers such that 0 < s < a < t < l . For each integer n > 0, define G (s,t) to be the probability that both « 1 < s and t < r n n Remark G (0,t) = G (s,l) = 0 and G (a,a) = 1 for a l l n. n ' n 7 n Ve prove now the fundamental recurrence r e l a t i o n s a t i s f i e d by G n ( s , t ) . Theorem 4.10 G Q(s,t) = 1 i f both s ^ 0, t ^ 0, and G Q(0,t) = G Q(s,l) = 0 for any s,t. For each non-negative integer k, G k + 1 ( s , t ) = j X P ( S > s, t, ^  ) dG k(?, ) where the range of integration i s over the rectangle 0 < § < s, t < ~yj < 1. The sense i n which the Riemann-Stielt j es integral i s to be taken i s described i n the proof. Proof Since 1 q(a) = 0 and r 0 ( a ) - x> ^he statements concerning G (s,t) are obvious, o ' For arbitrary € > 0, take partitions o = y 0 < y x < y 2 < y 3 < . •. < y n - s t = z < z, < z 0 < z 0 < . . . < z =1 o 1 2 3 m 80 o f t h e i n t e r v a l s [ 0 , s ] and [ t , l ] r e s p e c t i v e l y , s u c h t h a t n sup | y. - y. , | < € i = l 1 m I I sup | z. - z , I < € . 3=1 By m u t u a l e x c l u s i o n , t h e p r o b a b i l i t y t h a t b o t h y. , < 1, < y. and z . , < r. < z . i s • ^ l - l — k Ji j - 1 k - j G, ( y . , z . i ) - G, ( y . , z .) - G. ( y . , , z . , ) + Or, ( y . , , z .) k Ji' 0-1 k J i ' j k j ~ l k J i-l' j v h e r e 1 < i < n, 1 < j < m. M o r e o v e r , i f i t i s g i v e n t h a t b o t h 1^ < s and t < r ^ , t h e n t h e p r o b a b i l i t y t h a t b o t h 1, ,, < s and t < r, , , k + l k + l i s j u s t t h e p r o b a b i l i t y t h a t e i t h e r 1, < x, ,, < s o r t < x, ,, < r, . k — k + l k + l — k By lemma 4.8, t h i s e q u a l s s> ^» ° I t f o l l o v s , by a d d i n g o v e r a l l p a i r s o f i n t e r v a l s i n t h e p a r t i t i o n s and l e t t i n g € -> 0, t h a t n m G k + 1 ( s , t ) = l i m £ £ * < 5 i , S> i = l j = l [G, ( y . , z . -. ) - G, ( y . , z .) - G, ( y . . , z . , + G ( y . , , z .) ] k J i' j - 1 k X J i » j ' k i ' i - l j - 1 k " j - 1 j v h e r e f o r e a c h i and j , ?. and ^ . a r e a r b i t r a r y p o i n t s s u c h t h a t y. _ < 5. < y. J l - l - l J l z . , < v? . < y. . 81 The l i m i t i s t a k e n o v e r a l l p o s s i b l e p a r t i t i o n s as € 0 . T h i s d e f i n e s t o d o u b l e i n t e g r a l i n t h e s t a t e m e n t o f t h e t h e o r e m . I t r e m a i n s t o show t h a t t h e above l i m i t e x i s t s , I t i i enough, by a s t a n d a r d t h e o r e m on R i e m a n n - S t i e l t j e s I n t e g r a l s on t h e p l a n e , see f o r example, H i l d e b r a n d t [ 4 ] , t o show t h a t P ( ? , s, t , ^  ) i s c o n t i n u o u s i n § and ^ and t h a t G ^ ( y , z ) i s o f bounded v a r i a t i o n on R. S i n c e <J>(x) i s c o n t i n u o u s , i t i s i m m e d i a t e t h a t P( s, t , ^  ) i s c o n t i n u o u s f o r f i x e d s , t . The v a r i a t i o n o f G k i s n m g 1 ™ o § l a 1 ^ k ^ i ^ j - ^ ' G k ( y i > z j ) - V y i - i ' ^ - i ) + V ^ i - i ' 2 ^ 1 n m i = l J=l + G. (y . , , z .) ] ; k J i - 1 ' j ' t h e n o n - n e g a t i v i t y r e s u l t i n g f r o m t h e f a c t t h a t t h e e x p r e s s i o n i n s q u a r e b r a c k e t s r e p r e s e n t s t h e p r o b a b i l i t y o f an e v e n t . So t h e v a r i a t i o n o f G. k = l i m [G, ( y , z ) - G ( y ,z ) - G ( v , z ) -t- G ( y „ z ) J ~ k Jn' o k Jn m k " o' o k J o' m c -* u = G k ( s , t ) - G k ( s , l ) - G k ( 0 , t ) + G k ( 0 , l ) = G k ( s , t ) < 1 . I t f o l l o w s t h a t G k i s o f bounded v a r i a t i o n , and he n c e t h e i n t e g r a l e x i s t s f o r e a c h k. The r e c u r r e n c e r e l a t i o n o f t h e o r e m 4.10 i s t o o d i f f i -c u l t t o u s e f o r d e v e l o p i n g p r o p e r t i e s o f G k ( s , t ) and o t h e r f u n c t i o n s 82 w h i c h w i l l c o n c e r n us l a t e r . Ve a i m t o p r o v e two o t h e r r e c u r r e n c e r e l a t i o n s f o r G - k ( s , t ) , t h e f i r s t o f w h i c h i s o b t a i n e d f r o m t h e o r e m 4.10 by an i n t e g r a t i o n by p a r t s . F i r s t we r e q u i r e a lemma. The p r o o f i s o m i t t e d . Lemma 4.11 5 F ( g , s, t , H ) , S F ( § > S , t , 7 ) and as a r e c o n t i n u o u s f u n c t i o n s o f § and i n t h e r e c t a n g l e 0 < § < s, t < rj < 1. I n p a r t i c u l a r & F ( s , s, t , n ) = ( t - s ) 1 / t - s \ a^ Tv~s")2 [>\-s ) 9 F ( g , s, t , t ) = _ ( t - s ) <|/s-?) a? (t"l?7 2 [ t - § J F o r b r e v i t y i n what f o l l o w s , we w r i t e F ( ? , ^ j ) i n p l a c e o f F ( ? , s, t , *-| ) and a F ( g , ^ ) i n p l a c e o f S F ( g , s, t , ^  ) a§ ag Theorem 4.12 I f k i s a n o n - n e g a t i v e i n t e g e r , t h e n o t ' + J j Gr R (g , *| ) dF ( g , |^ ) R where R i s t h e r e c t a n g l e 0 < g < s , t < ^ < 1. The d o u b l e i n t e g r a l i s d e f i n e d as t h e l i m i t o f t h e Riemarm sum as 6 - 0 o f n-1 ra-1 i = l j = l + P ( ? i , vh ere t = z < " > } , < Z . . < ">10 < , „ „ < - > ) < 2 o — /1 ~ 1 ~ 1 2 — — / m — m and n , m sup |y. - y. -. | < f , sup | z - z \ < f i = i 1 1 - 1 j-1 J Proof The approximating Riemann sum f o r Jj F(§ , s, t ,-•)) dGj_ ( § ? i n theorem 4»10 may be rearranged to give •1 m-1 i = l j=I ^.-1-1 | ,> ^ J m-1 + > ' [F(? , -n • , - , ) - F(? 5 -v, (y . z .) m-1 j " ^ ^ ? l > - ) j + l ' - p < 5 i > V ^ o ' V n + F(§. , -v, )[G.(y.,z ) - G. (y .,z )] £—i l jo k J i ' o k 17 l - l o i = l n ">\ F(§.,>, ) [ G k ( y . , z ) - G. (y. , ,z )] i ' |m k ^ i ' m ^ J I - I m i=l Using the f a c t s that y =0. y = s, z = t, y = 1, and & J 0 y J n ' o m G- k(0jt) = G k(s,l) = 0, the sum s i m p l i f i e s to 84 n - l m-1 2 Tl I X S i . v ^ ) - F ( ? i ? ^ . ) - P ( ? i + 1 , - > ] j + 1 ) i = l j = l + P ( ? i + l ^ j ^ G k ^ V ' V m-1 + > J t F ( ? n , > , j + 1 ) - F ^ ^ J l G ^ z . ) 3=1 ' n - l + E t F ( ? i , y/J - F ( ? i + 1 J 7 1 ) ] « k ( y i > t ) 1=1 + F ( § n , ^ 1 ) G k ( s , t ) . Nov l e t t h e mesh € o f t h i s sum a p p r o a c h z e r o . S i n c e F i s c o n t i n u o u s l i m F ( ? , T ; 1 ) G . ( s , t ) = F ( s , t ) G , ( s , t ) g - 0 ' = F ( s , s , t , t ) G k ( s , t ) = 0 , By t h e m e a n - v a l u e t h e o r e m o f d i f f e r e n t i a l c a l c u l u s ? m-1 Tl t F ( ? n , F ( ? n , 7 . ) ] G k ( s , z . ) j = l m-1 The d i f f e r e n c e b e t ween t h i s e x p r e s s i o n and m-1 w h i c h i s t h e a p p r o x i m a t i n g Riemann sum t o i s l e s s t h a n o r e q u a l t o 85 5 = i a p ( s,z.) aF(?„,<|>,) j = i w h i c h a p p r o a c h e s 0 as € -» 0 by lemma 4.13. So m-1 1 l i m J - 1 t / S i m i l a r l y n - l i i . [ P ( ? 1 > > J O ) - p ( ? I + 1 , 7 o ) ] G k ( y . , t ) i = l 0 F i n a l l y , t h e sum o f a l l t h e r e m a i n i n g t e r m s must a p p r o a c h a l i m i t , a nd t h i s sum i s what i s d e f i n e d t o be G k ( § , ^ ) d F ( ? , ^ 7 ) . ¥e c a n now d e r i v e a t h i r d r e c u r r e n c e r e l a t i o n f o r G k ( s , t ) . I t i s t h e s i m p l e s t one t o u s e i n t h i s c h a p t e r . We c l a i m t h a t f o r a l l i n t e g e r s k > 0, •W«'*> = / \< -Eh • & > U x ) a x 0 + f l Gk< f . I > I t does n o t seem p o s s i b l e t o p r o v e t h i s r e s u l t d i r e c t l y f r o m t h e o r e m 4.12, so we o b t a i n i t by i n d u c t i o n on k. I t i s c o n v e n i e n t t o i n t r o d u c e some new n o t a t i o n , and r e p h r a s e t h e r e s u l t o f t h e o r e m 4.12. F o r each i n t e g e r k > 0, we p u t 86 C k ( s , t ) = J7.Ok(5,->l )dP(?,"7 ) . R ' By lemma, 4.11, we c a n r e w r i t e t h e r e s u l t o f t h e o r e m 4,12 by t h e e q u a t i o n G k + 1 ( s , t ) = ( t - s ) [ A k ( s , t ) + B k ( s , t ) ] + C k ( s , t ) Theorem 4.13 I f t h e f u n c t i o n s H k ( s , t ) , k = 0, 1, 2, ... a r e d e f i n e d on t h e r e c t a n g l e 0 < s < a, a < t < 1 by t h e e q u a t i o n s H Q ( 0 , t ) = H o ( s , l ) = 0 H o ( s , t ) = 1, i f 0 < s < t < 1 s . .1 H, k+1 t h e n H k ( s , t ) = G k ( s , t ) , i f 0 < s < a and a < t < 1, f o r e a c h p o s i t i v e i n t e g e r . P r o o f The t h e o r e m h o l d s f o r k = 0, b y t h e d e f i n i t i o n s . I f k = 1, t h e n H l ( s , t ) = J i ( x ) d x + J d>(x)dx = P ( 0 , s , t , l ) . Prom t h e o r e m 4.10, 87 n m ) G i ( s , t ) = ^i'o S j5 p < s i , , ' t ' 7 j ) C o . ( l ' i , * j - i ) - G o ( 7 i ' z j = l i m o P d ^ s . t ^ J ^ t x j , ^ ^ ) a l l other terms of the sum being zero, since G (s,t) = 1 i f 0 < s < t < 1 . o ' — So G.(s,t) = lim P(? , s , t , ^ ) 1 € - 0 ' = P(0,s,t,l) = H-^s.t). Assume the induction hypothesis that for some integer k > 0, H k(s,t) = G k(s,t) and H k + l ( s ' t ) = G k + l ( s ' t ) ' Ve prove under this assumption f i r s t that o t and then that H K + 2 ( s , t ) = G k + 2 ( s , t ) . By d e f i n i t i o n of C k +^» a n < * "the induction hypothesis, C k + 1 ( s , t ) = ff\+1^^ )<"?(?, ^ ) R I s ? 7|=t §=0 0 + f1 H k (f» <l>(x)dxdF(?,^ ) s i s 0 ^ = t § = X + / 1 / S / X % (f » |) 4<x)dF(§,^)dx t ?=0 ^ = t by changing the order of integration. So s 1 s ~ x C k + 1 ( s , t ) = f f / 1 _ X H k(u,v)dP(u,v) d>(x)dx J t-x ^  n o v=t v=0 1-x 1 1 + f J f Hk(u,v)dP(u,v)<l>(x)dx t v=0 v=-x 0 + " t since R%k = G_k by hypothesis, To complete the proof, we have G k + 2 ( s , t ) - C k + 1<s,t) = ( t - s ) A k + 1 ( s , t ) + ( t - s ) B k + 1 ( s , t ) • (t-s) f H f c f l ( ? 1 t ) 7 - A - : 2 i a; 89 1 s t o 1 1 + (t-s) s 5 0 0 o t by using the assumption that H^ — , and ^ +-^ = • By a suitable change of variables in each of these four integrals, Ws»*> - W s ' + ) =(t-s) o t-s+u(l-t) 1-s . t 1 ^ H n : ) i ^ 3 L l T - u H 1 - s ) J dvdu s ut s 1 X (^.-(UjV) (v-u) 2 "u(t-s) s(v-u) dvdu t o %_ (u,v) (v-u) 2 vs-ut t(v-u) dudv t-s 0 1-s t + \ f 1 |/s-u\ . / (t-s)+ u ( l - t ) ) = ( T - S ) J T^ T "JprJ. K ( u> —fcT"* / du 90 j3 + (t-s) / - J i (J) V«. d u s 0 + (t-s) / i i(x) A k( J , | ) dx t • <t-.)/ i U x ) V g j ' f=x>d* 0 s - / *<*H<W fit . fit' - ck< fit • fit >J d* o + / »i')[» w« i > x ) - °k< i • t > i d * t s-x 1-X ' X fit» ^(x)d* + /«W !• f ) i W d * -O k + 1(s,t) 91 F i n a l l y , t h e f u n c t i o n s H ^ ( s , t ) = G ^ ( s , t ) a r e a l l n o n -n e g a t i v e and c o n t i n u o u s i n t h e r e c t a n g l e 0 < s < a , a < t < 1 by i n d u c t i o n on K, and so a l l t h e i n t e g r a n d s a r e a b s o l u t e l y i n t e g r a b l e . So t h e ch a n g e s o f o r d e r o f i n t e g r a t i o n a r e v a l i d . The m a p p i n g s t - x S - X r. U = ~ , V = 1 - X 1 - X ' and , s x u = — , v - — X 1 X w i t h x r e g a r d e d as a p a r a m e t e r , a r e a l l 1-1 w i t h n o n - n e g a t i v e J a c o b i a n s , and so t h e c h a n g e s o f v a r i a b l e s u s e d above a r e a l s o j u s t i f i e d . Thus w-.*> • J <w < e • T i t > + /ws - t>*w** o t as c l a i m e d . T h i s c o m p l e t e s t h e p r o o f o f t h e t h e o r e m . 4 - 5 E x p e c t e d v a l u e s We a r e now i n a p o s i t i o n t o compute t h e moments and e x p e c t e d v a l u e s o f v a r i o u s f u n c t i o n s o f 1 and r Q . -In p a r t i c u l a r , we f i n d f o r m u l a s f o r t h e e x p e c t e d v a l u e and v a r i a n c e o f r n _ i n > t h e k n o w l e d g e o f w h i c h a l l o w s a c o m p a r i s o n w i t h t h e b i s e c t i o n method o f l o c a l i z a t i o n . S i n c e b o t h 1 and r depend on a as w e l l n n as on t h e a b s c i s s a s e t s x X x , t h e e x p e c t e d v a l u e s a r e f u n c t i o n s o f a. We u s e t h e s y m b o l E f o r e x p e c t e d v a l u e . R d e n o t e s t h e r e c t a n g l e { ( x , y ) 0 < x < a, ct < y < 1 }. D e f i n i t i o n 4.14 F o r e a c h n o n - n e g a t i v e i n t e g e r n, 92 y n(a) = E ( l n ) = ffx dG n(x,y) J R z n ( a ) = E ( r n ) = J fy dG n(x,y) R e (a) = E(r -1 ) = z (a) - y (a) n n n n ''n v (a) = E(r +1 ) = y (a) + z ( a ) Ix XI Q p n(a) = E ( l n r n ) = ffxy d& n(x,y) R h n(a) = E ( l 2 ) = ff x 2dG n(x,y) R k n(a) = E ( r 2 ) = ff y 2 dG n(x,y) R f (a) = E(r -1 ) 2 = h (a) + k (a) - 2p (a) n n n n n *n v n(a) = f n ( a ) - [ e n ( a ) r v (a) i s of course the variance of r -1 n n n A l l the above S t i e l t j e s Integrals are to be taken i n the same sense as that in theorem 4.10. We derive recurrence relations for some of the above functions. These are l a t e r used to find asymptotic estimates for e (a) and v (a). n n 93 Theorem 4.15 v 0 ( a ) = °« F o r each i n t e g e r n > 0, a a yn+1(a) = J U(t)dt + j (l-t)yn( ff| ) i(t)dt o 0 1 + j tyn(|)«Kt)dt. a ) = J/xdG n(x,y) R a a J xdG n(x,a) - J x d G n ( x , l ) 0 0 a ) xdG ( x , a ) , s i n c e G ( x , l ) = 0. J n ' ' n ' o a So y n ( a ) = a - J " G Q ( x , a ) d x on i n t e g r a t i n g by p a r t s . Hence, from theorem 4.13, a a " y n + l ( a ) = / G n + 1 ( x , a ) d x o a x • / J \ < i 3 - f i t - > *<*> d t d* 0 o a 1 + Jf G n ( | , ^ ) d>(t)dt dx 0 a " / / °n< & • & d t 1 a + J f G n ( ^ , |) d.(t) dx d t a 0 = fl1-* ( l - t ) G ( u, ffi)<|,(t)du d t o 0 o t a a-t 1 a + tG n(u,|)d.(t) du dt a 0 \ 9 4 a o 1 + / t [ f - y n ( f ) ] J(t) d t . a So a y n + 1 ( a ) = a - f ( a - t ) d > ( t ) d t - f c4(t)dt o a a 1 + J ( l - t ) y n ( f f i ) 4 ( t ) d t + / t y n ( f U ( t ) d t , a a n d s i n c e d t = 1, t h e r e s u l t f o l l o w s , In e x a c t l y t h e s a m e w a y , w e c a n p r o v e 1 z ' x T. a s n(a) = a + J G - n ( a , y ) d y z ( a ) = 1 o a a (4.1) a n d z n + i ( a ' = J t d > ( t ) d t + J ( l - t ) z n ( f = i ) * ( t ) d t o o 1 + f t z ( J ) < K t ) d t J n t a It f o l l o w s i m m e d i a t e l y t h a t f o r a l l i n t e g e r s n > o , t h e f u n c t i o n s e n(ct) s a t i s f y t h e e q u a t i o n s e 0 ^ a ) = !• a 1 (4.2) e n + 1 ( a ) = J - ( l - t ) e n ( f f * U ( t ) d t + J t e n ( * ) d t o a a n d t h e f u n c t i o n s v n ( a ) s a t i s f y t h e e q u a t i o n s v Q ( a ) = 1. a a (4.3) w n + 1(a) = 2J" t « K t ) d t + J ( l - t ) w n ( f f i ) d . ( t ) d t + J t w n ( | ) < | ) ( t ) d t . a 95 Theorem 4.16 h Q ( a ) = 0. For a l l i n t e g e r s n > 0, a a h n + 1 ( a ) = J t 2 < t ( t ) d t + 2 j " t ( l - t ) y n ( f f | ) 4 ( t ) d t o 0 1 + J ( l - t ) 2 h n ( f ^ ) < l » ( t ) d t + J t 2 h n ( f ) J ) ( t ) dt, a P r o o f h^(a) - ff x dG n(x,y) R a . x^dG (x,a) = J* x ^ d G n l a = a 2 - 2 J x G n ( x , a ) d x on i n t e g r a t i o n by p a r t s , So by theorem 4.13, a 2 - b - n + 1 ( a ) = 2 J x G n + 1 ( x , a ) d x o ct x = 2j f x G n ( x f | , f=± H ( t ) d t dx o o a 1 o a By changing the order of integration, and then changing varia-bles, the right hand side can be written ct-t  a l^ t 2J J (l-t)[t + u(l-t)]Gn(u, f f | ) <Kt) du dt o o I f + 2Jj u t 2 G n ( u , J)(t) du dt a o a = 2 j f t ( i - t ) [ f f i - y n ( f l=i ) ] ,Kt) d t + 96 a + o / d--t)2r ( f ^ ) 2 - h n ( f f | ) ] K t ) at + y t 2 [(f) 2 - hn(f) ] i ( t ) dt, a The result follows on simplification. Similarly, one can prove that k (a) = 1, and for a l l integers n > 0 a a ( 4 . 4 ) k n + i ( a ) = J t 2d . ( t )d t + 2 J t ( l - t ) z n ( Y f | H ( t ) d t o a + / ( l - t ) 2 k n ( f f i ) d » ( t ) d t +j " t 2 k n ( f)<i> ( t ) dt, a In order to evaluate the product moment p n(oc), and hence f n ( a ) , we need to know the value of 1 a J fGn^x,y^ d x dy° a o Denoting this integral .by'q (a), we have 1 a < W l ( a ) = / / G n + l ( x ^ ) d x d y a o l a x a o o 1 a 1 + f f / G n ( f , ^H(t) dtdxdy a o y which,by changing order of integration, and changing variables, can be written a 1 .1-t 97 a-t j J j Gn(u,v)d)(t) (1-t)2 dudvdt 1 1 f + J fj Gn(u,vH(t)t2 dudvdt. o a - t o , , a 1-t r r A a a o t So a (4.5) qn+1(a) =J (l-t) 2qn(ff|H (t)dt + f t2qn(f )(j, (t)dt . a Theorem 4.17 P 0^ a) - 0 and for a l l integers k > 0 a a P k + 1 ( a ) = j t2<j>(t)dt + Jt(l-t ) V k ( f f | ) < J>(t)dt o a + j (l-t)2pk(f^)<|»(t)dt + J t2pk(|)d,(t)dt . a Proof We form the approximating Riemann-Sum for the double in t e -gral J J xydG, (x,y) and rearrange terms. R * If 0 = x < x , < x „ . . . < x = a o 1 2 n and a = ^ 0 < y l < y2 ' * ' < ym = 1 are partitions of the intervals [0,a] and [ct,l] respectively, and ^ i ' l i ' a r e a r b i " t r a r y points such that x. , < ?. < x. for i = 1, 2, ... n l - l — I I ' ' <^j- < y , for j = 1, 2, ... m then the approximating sum n m ^ X / I V\ X I — X I V 1 ' " I V\ X — X X — x t\ X — X i can be rearranged and simplified exactly as i n the proof of theorem 4.12, to give 9 8 n - l m-1 m+1 + ^ - W l ^ W a) 1=1 + , l Gk(a,a). As the mesh of the p a r t i t i o n approaches zero, these terms approach the value l a 1 a - f f G k ^ y ) d x d y + /" a G k(a,y)d.y -y"aG k(?,a)d5 + a 2 . « a 0 a o So Pfc(a) = -q^(oc) + atzj^la) - a] - a[a - y (a)] + a Pj^ (a) = awk (a) - q k (a) - a „ By using the recurrence relations (4,3) and (4,5) for ^ ( a ) and q k(a), i t i s now easy to derive the f i n a l r e s ult. We remark that the method used to evaluate f J J xy dG^(x,y) may be adapted to finding product moments of R higher order. F i n a l l y , by using the three recurrence relations for h n(a), k^(a), p n ( a ) , one can prove easily Theorem 4.18 fQ(a) = x° For a l l integers n > o f n + l ( a ) = / ( l - t ) 2 i n ( f f | H ( t ) d t + f t 2 f n ( f ) ^ ( t ) d t . a 9 9 4 - 6 The behaviour of e (a) We nov attempt to investigate the behaviour of en(ct) and v n ( a ) as n -• », and to shov hov this depends on the density-function <|>(x). While i t i s easy to compute e x p l i c i t l y the values 1 1 of J~ e n(a)da and Jfn(a)da, giving a global solution , i t i s o o much more d i f f i c u l t to consider the sequence e n(a) for each fixed a, Our main result i s that for each a, 0 < a < 1 e (a) ~ Xn e(a) n vhere X i s a constant depending on (j) alone, and e(a) i s a solution to a homogeneous linear integral equation, vhich under suitable r e s t r i c t i o n s , can be solved by an equivalent ordinary d i f f e r e n t i a l equation, We define tvo numbers X and p. by the equations 1 1 X = f (l-t) 2<l>(t)dt + J t 2d>(t) dt o o 1 1 u = J (l-t)3<l>(t)dt + f t3<Kt)dt. The importance of these numbers i s apparent by the f o l -loving result: Theorem 4.19 For a l l integers n > 0 1 J " e ( a ) d a = Xn n o J* fn(a) da = u.n 100 Proof Ve take the recurrence r e l a t i o n (4.2) for e (a), and integrate both sides of the equation with respect to a. This gives 1 l a f e n + 1 ( a ) d a = f f ( l - t ) e n ( f f i ) d>(t) dt da o o 1 1 1 + j'J t e Q(^) |(t) dt da o a 1 1 = j j (1-t) e n ( f f i ) d»(t) da dt o t 1 t J j t e n(|) 4(t) da dt o o 1 1 ( 1 - t ) 2 4(t) e (u ) du dt n o o 1 + o J" t 2 <t(t) e n(u) du dt 1 = X o e (u) du . n Since 1 1 da = 1-, o 1 j" e Q(a) da = J da = Xn 101 S i m i l a r l y , f r o m t h e r e c u r r e n c e e q u a t i o n f o r f^ioc) i n t h e o r e m 1 1 "n 4.18, 1 f n + l ( a ) d a = J J ( 1 " t ) 3 ^"fc) f n ^ u ) d u d t o o 1 1 + f I t 3 l ( t ) f (u) du d t n o o = | i J" f n ( u ) du , and s i n c e . L ) du = 1 o o t h e p r o o f i s c o m p l e t e . 1 Thus t h e s p e e d a t w h i c h j d a a P P r o a c n e s 0 o depends o n l y on X, t h a t i s , o n l y on t h e f i r s t two moments o f -<1>. Bounds f o r X a r e p r o v i d e d by t h e e s t i m a t e s X = f1 [ t 2 + ( 1 - t ) 2 ] i ( t ) d t < f x ( t ) d t = 1 o o and \ = / [ t 2 + ( 1 - t ) 2 ] 4 ( t ) d t > / | | ( t ) d t = | . o o M o r e o v e r , we c a n n o t have e q u a l i t y , f o r i f X = ^ , J ( 2 t - l ) 2 i ( t ) d t = 0, f r o m w h i c h <|>(t) = 0 f o r o a l l t , s i n c e <|> i s c o n t i n u o u s , and i f X = 1 / t ( l - t ) <j)(t) d t = 0 , w h i c h a g a i n g i v e s <j>(t) = 0 . 102 But \ can take on any value between ^ and 1 by suitable choice of |. The fact that X > ^ shows that we cannot expect to get a faster rate of, convergence to a than that provided by the bisection strategy. The symmetric B e t a - d i s t r i -bution t m ~ ^ ( l -Qm~^ B^ m,m) where m i s positive, gives m+1 2m+l which can be made a r b i t r a r i l y close to ~£ i f nr i s large enough, If (|>(t) i s symmetric about t = ^ > then 1 | t d>(t)dt = | o and \ = + 2 ^ , 1 , ~ where u 2 = ^ ( t - * < K t ) dx o i s the variance of <j> . Thus the smaller i s , the closer X i s to ^ , and the more l i k e l y i t i s that abscissa sets are selected near the mid-points of i n t e r v a l s . The previous theorem suggests t h a t for large n9 the sequence e n ( a ) should behave l i k e \ ne(a) where e(a) i s a fixed function a such that .1 f e(a ) da = 1 It i s convenient to normalize the functions e (a), by defining n a new sequence e n ( a ) such that i n ( a ) = ^n e n ( a ) A. 103 Then, e (a) = 1, a (4.6) X e n + 1 ( a ) = [ ( l - t ) i n ( f f± H ( t ) d t + [ te^ (f) d» (t)dt o a 1 and j° e n ^ a ^ da = 1 , for a l l integers n > 0, The question of the behaviour of e (a) for large n n can now be put i n another way. Does lim e (a) exist? If so, n - » n does the l i m i t , e(a) say, s a t i s f y the equation a 1 \e(a) = \ (1-t) e ( f f | ) d>(t)dt + [" t e (|)dt ? o a Regarding the right hand side of this equation as a l i n e a r operator, this amounts to asking i f the sequence © n ( a ) converges point-wise to an eigen-function of the l i n e a r operator. By choice of X, this i s not a contraction operator i n either the L^-norm or sup-norm sense, so we have to consider other methods of solution. Henceforth we impose two additional r e s t r i c t i o n s on (|> (t) . These are (4.7) (i) d>(t) < M for a l l t, 0 < t < 1 . (4.8) ( i i ) <(,(!,) i s symmetric about i, = — , so that <|>(t) = (j> (l-"b) for a l l t. 1 Ve note that M > 1 since f (|>(t)dt = 1, and that o 1 (4.9) [ t |(t) dt = \ o 1 1 (4.10) X = 2 t2d>(t) dt, |i = 2 [ t 3 <l>(t) dt. 104 The s e c o n d r e s t r i c t i o n s i m p l i f i e s most o f t h e s u b -s e q u e n t c a l c u l a t i o n s . I n p a r t i c u l a r , e n ( c t ) 1 S a l s o s y m m e t r i c a b o u t a = ^ f o r a l l n. The p r o o f t h a t l i m e (a) e x i s t s f o r e a c h a p r o c e e d s n -* oe by f o u r m a i n s t a g e s . F i r s t , we show t h a t e (a) i s u n i f o r m l y 1 n bounded f o r a l l n and a. N e x t , t h a t I t e ( t ) d t i s a ^o c a u c h y s e q u e n c e f o r e a c h p o s i t i v e i n t e g e r k. From t h i s i t w i l l f 1 f o l l o w t h a t J i|i(t) e" ( t ) d t i s a c a u c h y s e q u e n c e f o r a l l o u n i f o r m l y c o n t i n u o u s f u n c t i o n s \}r(t). F i n a l l y , we c a n a p p r o x i m a t e t h e r i g h t h a n d s i d e o f t h e e q u a t i o n ( 4 . 6 ) b y 7 i|j(t) e ( t ) d t , o where \|j depends on a. — 1 n Lemma 4.20 e n ( ^ ) - e n ^ = ^ 2"h) ^ o r Vosl^lve i n t e g e r s n. P r o o f P u t a = 0 i n ( 4 . 6 ) . 1 , Then X V n < ° ) = j t l n ^ ° ) ^ ( t ) d t = 2 ® n ( 0 ) " o Theorem 4.21 T h e r e e x i s t s a r e a l number 6, 0 < 8 < ^ s u c h t h a t f o r a l l a, 0 < a < 1, and a l l n o n - n e g a t i v e i n t e g e r s n. P r o o f We f i r s t d e f i n e 6., and t h e n c o n s i d e r s e p a r a t e l y t h e c a s e s ° < a < B , B < a < 1-6. .1 a The a o -f u n c t i o n \ u <Uu) du + J (1-u) <t( u) du i s u n i f o r m l y c o n t i n u o u s i n a, and has t h e v a l u e u <Ji(u)du= -| i f e i t h e r a = 0 o r a = 1. Thus, s i n c e A. > ^ , t h e r e i s a B , 0 < B < ^ s u c h t h a t i f e i t h e r 0 < a < B o r 1-8 < a < 1, t h e n 105 .1 - a (4.11) f u <Hu) du + f (l -uH(u) du < X . a o Suppose 6 < a < 1-8. Then, by a change of variable i n equation (4.6) and using the fact that i i s symmetric, X5 n + 1(a) = (1-a) 2 P ^ *(l=a)du + a 2 f' ^ d u 1-a u a u 0 r1 e (u) 0 J" e (u) < M [ ( l - a ) 2 J du + a 2 f - ^ 3 — du ] 1-a u a u ^ M [(T=o-) I i n ( u ) d u + a J i n ( u ) d u ] 1-a a So, i f 8 < a < 1-8 , 'n+l^"" - X L 6 ' 1-8 e_ . n (a) < jj C a" + YTg 3 f o r a l l integers n > 0 and hence ©n(a) S \ C g" + Y^ B" ^ ^ O R i n t e g e r s n > 0 B 1-8 since P 1-P We prove that ©n(c() s a t i s f i e s the same inequality for a l l a by induction on n. This i s t r i v i a l i f n = 0, since e o(a)=l, Suppose for some positive integer k, e k(a) < ~ ( I + YTp ' for a l l a . Then, i f 0 < a < 6, 106 a l X e k + 1 ( a ) = J (1-t) i k(fl£) <t(t)dt + [ t i k ( f ) 4>(t) dt a a x [| + T^F ]C f t1-*)^*) d t * ( t < W t ) d t ] a - X ^ (3 + T^|3 ^ ^  b y equation, (4.1l)« So W a ) * X C p + l=p ] 0 < a < 6 and, since ek+-^ i s symmetric, e k + 1 (a) < ~ [ ~ + ~rj^ ] for a l l a, , 0 < a < 1 . ¥e prove now that the sequence ^ t k e" n(t)dt is acauchy 0 sequence for each non-negative integer k. To do t h i s , i t i s desirable to introduce some new notation. D e f i n i t i o n 4.22 Let p be an arbitrary positive integer, and put & n( a) = en+p^a^ ~ en^ a^ ^ o r e a c n n o n - n e g a t i v e integer n. Let k be any non-negative integer, and put 1 n,k = [ d t ' B Theorem 4.23 Choose E, E fixed, E > sup |6 (a)| . This i s n, a possible by theorem 4.21. 1 3 Since 2J u d>(u)du H _ 0 X 2 f X u 2 4(u) du < 1 there i s a number y such that ^ < y < 1 . 1 0 7 Define a sequence A^ for each integer k > 0 by the equations A' = 1 o ( 4 . 1 2 ) A, = 2 E + T - * — S f k) A , /k\ kJ where rj _ r i ( k - r ) I Then |Bn ^| < A^ y11 for a l l k, n. In p a r t i c u l a r ; lim |B , I = 0 . 1 n.k n oo > Proof ¥e use induction on k. F i r s t , i f k = 0 , 1 B = f 6 (t) dt n, o J n o 1 e . (t) dt - \ e (t) dt n+px \ n = 1 - 1 = 0 . So the result i s t r i v i a l for k = 0 . Assume that the theorem i s proved for a l l integers r, 0 < r < k - 1 , where k > 1 . From equation 4 . 6 and d e f i n i t i o n 4 „ 2 2 , i t follows by l i n e a r i t y that a 1 X 6 n + l ( a ) = [ ( l " t ) 6 n ( l f | ) ^ ( t ) d t + f t 6 n ( f ) ^ t ) d t o a for a l l integers n > 0 , K Multiplying each side of t h i s equation by a and integrating, gives l a 1 1 K B n + l , k = / [ ct k(l-t)6 n ( f f | ) d.(t)dtda + J" [a kt6 n(|)4(t) dtda o o o a 108 vhich i n turn, by putting ct—t 1-u = j—£ , 1-v = t i n the f i r s t i n t e g r a l , a u = T , v = t i n the second integral gives n+l,k 1 1 1 1 1 [" j ( l - u v ) k u 2 6 n(v) |(u) du dv + J" v k u k + 2 6 n ( v ) <l>(u) dudv o o o o k 1 1 r^O r 1 1 u r + 2 v r 6 n ( v ) <|)(u)dudv + v k u k + 2 6 n ( v H ( u ) d u d v o o 0 0 k ( k ) ( - l ) r B n u r + 2 * ( u ) d u + B n r=0 ' n » k • uk+2<|> (u)du = [ l + ( - l ) k ] B. n,k u k+2 u) du + ItjK-DX r f u r + 2 i ( u ) d u r=0 n> r J Therefore 1 n+l,k , < 2|B k l T u k + 2 *( u)du + ^1 ( k ) | B n | f u r + 2 <j,(u)du » o r=0 ' J k-1 x < 2 | B n > k | J u 3 d.(u)du + X _ ( p ) l B n > p l f u 2 4 ( u ) d u Hence k-1 ' W S jf l B n i k l + | g O l B n > r l 109 By the induction hypothesis and equation (4.12), t h i s implies that k-1 n+l,k' - X 1 n,k' + 2 Y ^ 0 ( r ^ r i.e. l B n + 1 > J S j } l B n > k l + i Y n ( A k - 2 E ) ( Y . { f ) . By considering this inequality for a l l integer values of n from 0 upwards, i t follows that m=0 < Y n + 1 | B o > k l + | U k - 2 E ) [ Y n + 1 - ( ^ ) n + 1 ] < Y n + 1 E + | (\ - 2E) Y : n+l ^ * n+l < \ Y •where the inequality JB , | < E follows from the fact that O j K. l l | B o , k l = I [ t \ ( t ) d t | < E t k d t < E. o o n Hence IB^ ^| < A^v for a l l k and a l l n, and so the induction i s complete. Corollary 4.24 1 lim I n -* » ^ o p(t) 6 n(t) dt 1 = 0 , where p(t) i s any polynomial i n t, JL r Proof p(t) i s a sum of the form a t where the a are r=0 constants, 110 Theorem 4.25 If i|r(t) i s any real uniformly continuous function defined for 0 < t < 1, then 1 l i m | f i j i ( t ) 6 ( t ) d t | = 0 n -• » J Proof For any 6 > 0 , there exists, by the Weierstrass approxi-mation theorem, a polynomial p c ( t ) such that |p €(t) - * ( t ) l < € for 0 < t < 1. Hence ^ i r *(t) 6 n ( t ) d t i = i [ u ( t ) ~ p € ( t ) + P g ( t ) ] 6 n ( t ) d t i o o ' "1 1 < I [ [ * ( t ) - p € ( t ) ] 6 n ( t ) d t + | J p € ( t ) 6 n ( t ) d t | o o 1 1 < 0 g | | 6 n ( t ) | d t + | J p € ( t ) 6 n ( t ) d t < e E + | p € ( t ) 6 n ( t ) dtI Since € i s arbitrary, the result follows on l e t t i n g n -» », by corollary 4.24. Theorem 4.26 The sequence ^ n(a) converges uniformly to zero on the interval 0 < a < 1. Proof As i n theorem 4.21, we must consider f i r s t the case 0 < 8 < a < 1-8 < 1, for some suitable 8, and then extend the result to cover the case 0 < a < 8. The f i r s t part of the proof rests on the equation I l l \ 6 n + 1(a) = a' ^ 6 (t) n — <|>(f)dt + ( i _ a ) 2 6 (t) , a 1-a i n which —_ i (T) and —<t (^T^) are approximated by suitable continuous functions. Theorem 4 . 2 5 can then be applied. Let € be given, f > 0 . Choose €, € > 0, such that (i) € < \€ (Y * - | ) / 1 6 E ( i i ) € < 6 MeE ( i i i ) where y and B are chosen such that ~ - < Y < 1 , 0 < 6 < | , and P 2 B . . ( 4 . 1 3 ) 0 < f (l-t)d>(t)dt + J~ t<t(t)dt < | (y\ - J ). o o These ineq u a l i t i e s are possible, since A. > 2 > a n ^ ^ ne integral i s increasing i n B . For each a, 8 < a < 1 - 6 , define the two functions ty^(t,a) and %^ (t,a), by the equations ^ ( t j C t ) 0 , i f 0 < t < a-€ f t - ( a - g ) U ( l ) , i f a-€ < t < a €a" [j) , i f a < t < 1 . # 0(t,a) = j 0 » i f 0 < t < l-a-€ 1 f t - ( l-a - g ) U ( l ) f ( 1 - a ) , i f l - a - 6 < t < 1-a V K H±=Z) , i f 1-a < t < t J t 112 Both f^(t,a) and f 2 ( t , a ) are uniformly continuous on the rectangle 8 < a < 1-P, 0 < t < 1. So there i s 6 > 0, such that i f both a and a^ belong to the closed interval [ 8 , 1-8], and | oc-a^ | < 6, then | ^ ( t j a ) - i]) 1(t,a i) | < € and ; 2(t,a) - il) 2(t,a i) | < € for a l l t, 0 < t < 1. Choose a f i n i t e set of points , i = 1, 2, . ..q, such that i f 8 < a < 1-8, there i s an a^ such that |a - a^| < 6. If 6 < a < 1-p, then O r 1 o 1 X 6 n + 1 ( a ) = a f * 1 ( t , a ) 6 n ( t ) d t + ( l - a T J * 2 ( t , a ) 6 n ( t ) d t a 1-a 1 1 = a 2 | i|i 1(t,a)6 n(t)dt + ( l - a ) 2 j" t 2 ( t , a ) 6 n ( t ) dt o o a - a 2 f EMa-OI 1 ( 1 ) 6 ( t ) d t ]c € a 3 a-€ 1-a - ( 1 - a ) 2 f [ t - ( l - a - € ) ] 1 ( 1 ) 6 ( t ) d t . •J n l - a - 6 € ( l - a ) J So X | 6 n + 1 ( a ) | < | # 1(t,a)6 n(t)dt| + | [' # 2(t,a)6 n(t) dt 1 1 r o a EM + gj [ [t-(a - € ) l dt a-€ •CM 1-a EM r €(l-a) \ [ t - ( l - a - e ) ] dt l-a-€ 113 2 1 < S I f U-,(t,a) - * H ( t , a . ) + *.:(t,a. )] 6 (t) dt | J 0 , E M C / 1 1 \ . I I - c + ( - + YIQ" ' vhere | oc—oc± 1 < 6 1 1 < 2€ J |6 n(t)|dt + | J * 1 ( t , a.)6 n ( t ) dt | o 1 + | ( 5 n ( t ) dt I + 4 ^ ( 1 ^ ) o < 2 € E + ( YX -' \) 1 1 + I f * , ( t , a . ) 6 ( t ) dt 1 + | f * 9 ( t , a.)6 (t)dt|. By theorem 4.25, and the fact that there are only a f i n i t e number of ct^, there exists an integer mQ , such that i f n > m , then , .. — o' 1 1 I | * 1 ( t , a . ) 6 n ( t ) d t t +,| f • 2 ( t , a i ) 6 n ( t ) d t l o o ( Y ^ - \ ) for each i , i = 1, 2, 3,. < — g p — v A. ^ r n I  I i , z  J . . q. But then, l ;' n + 1v-,, - 2 c V T " ~ 2' ' J- U i cl- L X " - '"o |6„,n (o) | < 4 € (y\ - , for a l l n > m ¥e wish to show that there i s a positive integer p, such that n > mQ+ p, then |6n(ct) i < € for a l l a, 0 < a < 1. It remains to consider the case 0 < a < 8 . Define B = sup [6 (a)|, 0 < a < 8 , for a l l positive a -integers n. Ve claim that i f B > , n > m + 1, then the o pn 2 o sequence B n decreases u n t i l ^N+^ S "§ ^ o r s o m e P» 114 Assume that 0 < a < 6 , n > m +1, and B > — . Then — K ' — o ' n 2 since 6„(t) I n i/1-ai 6 n + i ( a ) = * { ~ £ L y <Kf) d t + (1-a) 2 j - a ^ 4 ( i = a ) d t > a 1-a 1 B 1-P I X | 6 n + 1 ( a ) 1 < a 2 | - f 4(f)dt + a 2 J 3 2 ) Kftdt 1-p * p 1 a a 2 ^ 3* dt + (1-a) 2 { 3} dt a 1-a .3 y x t a r P < B n J 1 _ P u < U u ) d t + § €(yX - | ) f u d > ( u ) d u a a 1-P 1 1 + B f u<j»(u)du + B P u<l>(u)du n n 1-a 2a 1 < B n J ud>(u)du + I € {y\ - |) J u ( K u ) d u a + B n [ u<t(u)du + B n j (l-u) 4 (u)du 2P < B n[ ^ ud>(u)du + \ ( YX - | ) + I + (l-u)d>(u)du] So by assumption and choice of p, X ! 6 n + 1 ( a ) j < B n [ ( Y X - \) + § ] < Y X B — n 115 It follows that B < yB , and hence i f B > \ ?, n+l — 1 n 7 m + 1 2 7 o the sequence B 0 , B , o , . .. decreases u n t i l B ^ < i 6 , 1 m +2' m +J 7 m +p — 2 ' o o o for some p. Fi n a l l y , the equation a • 1 X 6 n + l ( a ) = J ( l " t ) 6 n ( l = t ) * ( t ) d t + f t 6 n ( t ) * ( t ) d t o 1 - 6 implies that x S UP l ^ j . ! (cc) | < sup 16 (a) | , 0 < a < 1 N + I 0 < a < 1 N and so B , < h sup | 6 (a)| < 2 sup | 6 (a) | N + 1 0 < a < l n 0 < a < 1 N for a l l n. It follows that B < € for a l l n > m + p. n — — o Hence l 6 n ( a ) | < € for a l l n > mQ + p , and for a l l a, 0 < a < 1 . By lemma 4 . 1 8 , this holds also for a = 0 and a = 1 . This completes the proof. Corollary 4 . 2 7 Since 6 (a) = e , (a) - e (a) , where p i s an _ _ _ _ _ _ _ _ _ _ . n n+p n r nteger, the cauchy sequence. So arbitrary positive i r, the sequence e n(°0 for each a i s a e(oc) = lim e (a) exists, and moreover, the n - « convergence i s uniform. Lemma 4 . 2 8 If the sequence i s defined by D Q = 0 , D ,, = 7 (D + C M) n+l A. n for each integer n > 0, where C = sup e (a), then n, a le n(a) - e N ( B ) | < D n|a - B | for any a , B i n the interval [ 0 , l ] . Proof Ve use induction on n. The lemma i s true for n = 0, since e (a) = e (fi) = 1, n n If |e n(a) - e N ( B ) | < D j a - B | for some n, and a > B , then a \| 5 n + 1(o) - e n + 1 ( B ) | = | | (1-t) i n ( f f $ ) 4(t)dt o P 1 1 - [ ( i - t)5 n ( f f i )4 ( t ) d t + J t s n ( f U u ) d t - f tin(f)<l>(t)dt| o a p a p ^ I J ^-^n (ff$)*(t)dtl + ( ( l - t H ( t ) | ? n ( f f i ) - e n ( f f i ) | dt P o a 1 + I J t i n ( f H ( t ) d t | + / t i ( t ) | i n ( f ) - e n (f)| dt P a a ; p < C / ( l - t U ( t ) d t + D n l a - B | | «Kt) dt P o a 1 + C | t i ( t ) d t + D nla-p| / d.(t) dt p a < C M|a-p| + D | ct—p | n Corollary 4.29 ® n ( a ) i s uniformly continuous on 0 < a < 1 for each n. 117 Corollary 4.30 e(a) = lim e n(a) i s uniformly continuous. n -• » Proof e(a) i s the l i m i t of a uniformly convergent sequence of continuous functions. Corollary 4.31 e(ct) s a t i s f i e s the integral equation Xe(a) = y a (1-t) e(ff|) J(t)dt + f t i ( f ) <j>(t)dt, o a Proof \e(a) = \ lim e n + - i (a) n - » a = lim f (l-t)e' (f=J)<|>(t)dt + lim f te\ ( f ) i ( t ) d t , n - » J i - t n - co J n x o a and a change of order of l i m i t and integration i s permissible by uniform convergence. The next lemma shows that to compute e(a), one may d i f f e r e n t i a t e the integral equation and solve the resulting ordinary d i f f e r e n t i a l equation, so long as I i s d i f f e r e n t i a b l e a s u f f i c i e n t number of times. The proof i s omitted, since i t follows from the c l a s s i c a l methods for d i f f e r e n t i a t i o n under the integral sign. Lemma 4.32 If <|>(t) i s N times continuously d i f f e r e n t i a b l e on [ 0 , l ] , then e(a) i s N times d i f f e r e n t i a b l e i n the open interval ( 0 , l ) , 118 A - 7 The r e c t a n g u l a r d e n s i t y f u n c t i o n As an example, l e t us c o n s i d e r b r i e f l y the case i ( t ) s l . I t i s e a s i l y checked t h a t X = 2 J t 2 4<t) d t = j o and c o n s e q u e n t l y ^ ^ f 1(a) = a 2 | i i t ) d t + ( 1 - a ) 2 f dt, a t 3 1 -a ^ f o r 0 < a < 1. By d i f f e r e n t i a t i n g t v i c e , ve have 2 a ( l - a ) e " ( a ) + ( l - 2 a ) e ' ( a ) + 2e(a) = 0, and i f we put e(a) = J a ( l - a ) g(a) , then 2 a ( l - a ) g " ( a ) + 3 ( l - 2 a ) g ' ( a ) = 0. The d i f f e r e n t i a l e q u a t i o n f o r g has two l i n e a r l y independent s o l u -t i o n s o n l y , namely g(a) = c o n s t a n t , and g(a) = k Cot k where k i s a c o n s t a n t , and a = S i n 2 ^ . The second of these s o l u t i o n s y i e l d s a s o l u t i o n e(a) of the d i f -f e r e n t i a l e q u a t i o n which becomes unbounded i n a neighbourhood of a = 0, or a = 1. T h i s p o s s i b i l i t y must be r e j e c t e d . So g(a) = c say, and e(a) = c * / a(l - a ) „ 1 To s a t i s f y the requirement J" e(a)da = 1 , we must take 119 g c = — , and so f i n a l l y , lim e (a) = zz V a ( l - a ) for a l l . a , 0 < a < n « ' ft * ? n Hence e n ^ ^ ? ^ vMl-a) . This re s u l t was suggested by E.N. Gilbert of B e l l Telephone Laboratories. It i s of interest to compute the variance v (a) for t h i s n case. Putting (|>(t) = 1, and using theorem 4.18, one shows f i r s t < by induction on n that f (a) = a + b a(l-a) n n n where ao = 1 an+l = 3 an n = °» l f 2> bo = 0 bn+l = 2 bn + a n n = °> X> 2 ' Hence *n(a) = (^)n +. 6 [ ( | ) n - (^) n] a ( l - a ) . It follows that v n(o) = f n ( o ) - [ e n ( a ) ] 2 = ( ^ ) n + 6 [ ( | ) n - ( i ) n ] a(l-a) - [ e n ( a ) ] 2 ~ ( j ) n + 6 [ ( | ) n - ( i ) n ] a(l-a) - | § ( f ) n a ( l - a ) So v ( a ) ^ 6a(l -a) n 2 n Similarly, one can show by induction- on n that i f <!>= 1, w (a) = 2a + ^ ~ n = 0, 1, 2, ... 2 which suggests that the mean value of 1 and r could be used to estimate a i f n i s s u f f i c i e n t l y large. 120 However, the variance of w n(a) i s too large for an effective estimate, since the variance of v (a) i s V (a), vhere ' n n ' V n(a) = E ( l n + r n ) 2 - [ E ( l n + r n ) ] : = f n ( a ) + 4p n(a) - [ v n ( a ) ) ] ^ . One can shov easily that i f <|> = 1, then pn(cc) = a 2 [ l - | n ] . Combining th i s result v i t h the knovn values for f" n( a) and wn(ct) gives the variance of w (a), n v ( a) = 2a(l-a) + 1 - 6a(l-a) _ ( l - 2a) n _n 0 n ,n 2 3 4 2 l . e, V (a) ~ 2 a i l - a l n 2 n Hence ,/V (a) > e n ( a ) i f n i s large enough. 121 CHAPTER 5 LOCALIZATION OF ZEROES OP DERIVATIVES 5 - 1 General Results We consider the problem of l o c a l i z i n g the unique zero of the kth order derivative of a suitable function defined on an i n t e r v a l . It i s convenient to change some of the notation used i n previous chapter. Let D be the unit i n t e r v a l [ 0 , l ] , and l e t k be any positive integer. Let P^ be the class of a l l r e a l -valued functions f defined on D vhich possess continuous monotohic kth order derivatives f ^ k / ( x ) , such that f ^ k / ( 0 ) < 0 < f ^ k / ( l ) . (k) The functional i s defined by the unique zero of f> . In place of the exponents p, pjj and pjj(M), we use p(k), pjj(k), and Pjj(k;M) respectively. See section 3-3. Lemma 5.1 For each k, the functional i s l o c a l i z a b l e with respect to a (k+l)th order test function. Moreover, p(k) > 2 k + 1 Proof Let H = [a,b] be any closed sub-interval of D. Select k+l • points x-^ , X £ > ... x k + i *-n ^  such that a < x^ < < x^ . . . < x^ < x k + ^ b. Define the test function T on the set D k + 1 X E k + 1 by: T = T ( X l , x 2, x k + 1 , f ( x 1 ) , f ( x 2 ) , . . . , f ( x k + 1 ) ) i s the sign of the kth difference quotient of f at the points 122 x^, x 2» xk + x w n e r e ^ n e difference quotient may be defined as the co e f f i c i e n t of t k i n the unique polynomial <j>k(t) of degree < k which assumes the value f(x^) at t = x., i = 1, 2, 3, ... (k+l). See for example van der Waerden [9], on page 67. It follows immediately from the d e f i n i t i o n of that i f feF k and S(f)eH, then S(f) < x x implies T > 0, and S(f) > x f c + 1 implies T < 0. Hence S(f) < x k + 1 i f T > 0 and S(f) > x x i f T < 0 . Thus, no matter what value T assumes, S(f) can always be r e s t r i c t e d to a subinterval of H of length at most Max{ x k + i - A » D — X j } , and i f , for some € > 0, the distance from both x^ and x^ +^ to the midpoint of H i s ^  , the subinterval of H has length at most ( ^  + €)(b - a). It follows from lemma 3.2 that the functional i s l o c a l i z a b l e . Moreover, i f the length of D = d = 1, then there i s a strategy M, such that But this implies that P n ( k + l ) < k . M ) x [ < 2 + 6 ) " n ] ^ ) ' from which p(k) > 2 k + 1 We can include the case k = 0 i n the above, by agreeing that the derivative of order zero of a function at a point i s the value of the function at that point. This gives the bisection problem, for which p(0) = 2. 123 The case k = 1 i s done already, since i s a subclass of the unimodal functions considered i n section 1-3. The above inequality p(l) > A/2 = 1.414... i s a poor one, since p(l) = (S + 1)/ 2 = 1.618... . The cases k = 0, k = 1, and k = 2 are a l l discussed i n de t a i l by Kiefer [6], who gives a complete analysis of the optimal strategies for these three problems. In particu l a r , he shows that p(2) = J2 . We wish to obtain estimates for p(k), where k i s any positive integer. The methods employed are very similar to those used i n the proof of theorem 1.1. Theorem 5.2 Let N be a positive integer. Define L^(k) to be the largest real number such that i f the domain of P^ i s the closed interval D = [0, L^(k)], then there i s a strategy M for which i f f€P k, S(f) can be r e s t r i c t e d to an interval of unit length by evaluating f at at most N points i n D. Then L^(k) =1 i f 0 < N < k, and % ( k ) 5 LN-p^k^ + LN+ p_k-2^ k / i f P i s a n y i n t e S e r » 1 < P < (k+l). Proof Let X be an abscissa set in the interval [0, Ljj(k)]. If X contains fewer than k+l d i s t i n c t elements, then the values of f(X), where f^P^, provide no information about S ( f ) . So L N(k) = 1 i f N < k. On the other hand, S(f) can always be r e s t r i c t e d to a proper subinterval of D i f X contains (k+l) d i s t i n c t elements. So, suppose X consists of the points x, , x~, . . ., x, , , where 124 0 < X l < x 2 < x 3 . .. < x k + 1 < L N Let p be an integer, 1 < p < k+l. No matter how the strategy proceeds, there must always be a(k+])-abscissa set selected i n an interval known to contain S ( f ) , before further r e s t r i c t i o n of S(f) i s possible. So, a further (k+l)-(p-l) points must be selected i n the interval [0, x p ] , before r e s t r i c t i o n i s possible, after determining that S(f) € [0,x p]. Thus, i f S(f) i s to be r e s t r i c t e d to a unit interval i n the required number of steps, x must be chosen such that P Xp ^ L N - [ ( k + l ) - ( p - l ) ] ( k ) • (5.D i . e . x p < % + p _ k _ 2 (k). Similarly, a further p points must be selected i n the inte r v a l tXp> Ljj(k)] before r e s t r i c t i o n to a subinterval of this i s possible, after determining that S(f) f [x p,Ljj(k)]. So, x must be such that P (5.2) L N(k) - x p < L N _ p ( k ) . By addition of (5.l) and (5.2), (5.3) L N(k) < L N_ p(k) + L N + p _ k _ 2 ( k ) . Theorem 5.3 If k i s even, and p = then p(k) <%/2. If k i s odd, and p = , then p(k) < B , where B i s the largest * P P p+1 positive root of the equation x^ = x + 1. Proof I f k i s even, then by equation 5.3, LN<k> * 2 LN-p ( k ) ' It follows by induction on N, and by the fact that 125 L (k) =1, that o ^ ( k ) S ( «/2) for a l l positive integers N. 1 But then, p N(k) < [ ( P / 2 ) N j N = ?/2 and so p(k) < ^J2 , i f k i s even. k+l If k i s odd, and p = ^ t then by theorem 5.2, L N(k) < L N_ p(k) + L N _ p _ 1 ( k ) . The inequality L N(k) < 8 p i s true i f N = 0. If i t i s true for a l l integers < m, for some m, then L m + 1 ( k ) < ( P p ) m + 1 " P + ( P p ) m - P • P P m " P d + V - P p m + 1 • So, by induction, L^(k) < 6 p for a l l integers N > 0. Hence p N(k) < |3p p(k) < P p » i f k i s odd. The theorem below shows that i f k i s even, then the upper bound p(k) < ?/2 i s best possible. The strategy described i s due to C.L. Mallows of Bell Telephone Laboratories, who conjectured that p(k) = p»/2 i f k i s even. Theorem 5.4 If k > 2 and k i s even, then there i s a strategy M for which p(k,M) = VJ2 , where p = Proof Without loss of generality assume that the domain of P^ i s the closed interval [0, 2(k+2)]. Select as the f i r s t abscissa set the k+l points x^= 2 i , i = 1, 2, (k+l). If f€F, , and i f the appropriate test 126 function T as defined i n lemma 5.1 i s evaluated, S(f) can be r e s t r i c t e d to either [0, 2(k+l)] or [2, 2(k+2)]. By symmetry, there i s no loss of generality i n assuming that S(f) € [0, 2(k+l)]« Nov choose x = k+l, that iSj the midpoint of [0, 2(k+l)]. There i s nov a suitable abscissa set i n this i n t e r v a l , so, by evaluating the test function T, S(f) can be r e s t r i c t e d to either [0, 2k] or [2, 2(k+l)]. Again by symmetry, assume that S(f) € [0, 2k]. The evaluation of f at x = k-1, allovs the r e s t r i c t i o n of S(f) to an in t e r v a l of length (2k-2). One successively selects a (k+l)th point i n an interval i n such a vay as to preserve sym-metry, and reduces by 2 the length of interval to which S(f) may belong. After p stages, during which f i s evaluated at p points i n addition to the o r i g i n a l abscissa set, S(f) i s r e s t r i c t e d to an interval of length (k+2), with the values of f known at a l l points i n the in t e r v a l distant by an integer from the endpoints. Since this reproduces the o r i g i n a l configuration, scaled down by the factor 2, i t follows that the procedure may be iterated i n d e f i n i t e l y . Denoting this strategy by M, i t follows that i f n i s an integer of the form n = (k+l) + yp, where y i s a positive integer, then d(k,M) = ( i ) Y d o  n 2 ° n-k-1 P n(k,M) = (2 Y)n = 2 P . It i s now easy to deduce that 127 1 lim p. (k,M) = 2 P n -» oo 1 i . e . p(k,M) = 2 P . Remark In chapter 3, i t was shown that the golden mean strategy, though optimal, i s not the best procedure i f the number N of observations allowed i s given iri advance of computations. By contrast, the strategy given i n theorem 5.4 i s also optimal for some f i n i t e integers N. For example, take k = 2, p = 2, and N=7. Then, by equation 5.3, L^(2) < 4. The strategy M defined i n theorem 5.4, gives d^(2,M) = ^ d Q , and so M i s optimal for N=7. For a f u l l e r discussion, we refer to Kiefer [6], 5 - 2 Derivatives of odd order Known results for the case when k i s odd are much less satisfactory, with the one exception k = 1, where p(l) = 6-^ = 1 2 ^ • I conjecture that the upper bounds p(k) < (3 are best possible, i n view of the fact that inequali-P ti e s i n theorem 5.2 are good ones i f k i s even. A lower bound for p(k) may be obtained by noticing that one may always"employ a strategy appropriate for the case k+l. It follows that p(k+l) < p(k) for a l l integers k, and hence by theorem 5.4, p(k) > 2 + for a l l odd k. If k > 3, 2 2 , so this new lower bound i s better than that given i n lemma 5.1. Another lower bound may be obtained by using what might be call e d a multiple version of the golden-mean strategy. This 128 k+l means simply that for some € > 0, ^ d i s t i n c t points are selected within distance £ of each point indicated by the golden-mean strategy. The ideal case €= 0, would allow one to r e s t r i c t S ( f ) , for f^P^ from the unit interval D, to an interval of length ( «/5 - 1 ) ^ e v a X u a t i n g f at N = n ( ^ p ) points i n D, n being an arbitrary positive integer. This leads to the inequality p(k) > ( & t 1 ) k + 1 i f ' k i s odd. k+3 This inequality i s i n f e r i o r to the bound p(k) > 2 except when k = 1 or k = 3. In practice, € must be chosen before any computations are made, and since the ratio of € to the length of interval to which S(f) i s confined increases steadily, the procedure breaks down unless the number N of evaluations of f i s specified i n advance. If N i s given, € can be chosen small enough such that pw(k,M) i s a r b i t r a r i l y close to _ 2 (*/5 + 1) k+3 The big d i f f i c u l t y with k odd, k > 3 P l i e s i n finding a strategy such that only one new point i s selected at each stage after the f i r s t , and such that a certain amount of symmetry i s preserved. It i s of course possible that the best strategies are not symmetric, but this seems unlikel y in view of the results for k even. 129 Ve conclude -with a b r i e f table giving the best known numerical bounds for p(k), for 0 < k < 6. k lower bound for p(k) upper bound for p(k) 0 2 2 1 B 1 = ^ * 1 = 1.618 ^ + 1 = 1.618 2 ,fl = 1.414 »/2 = 1.414 3 ^ =1.272 p 2 = 1.325 4 ^2 = 1.260 3/2 = 1.260 .5 t/2 = 1.189 B 3 = 1.207 6 $2 = 1.189 1/2 = 1.189 130 BIBLIOGRAPHY 1. R. B e l l m a n and S. D r e y f u s , A p p l i e d Dynamic P r o g r a m m i n g , P r i n c e t o n U n i v e r s i t y P r e s s , P r i n c e t o n , N.Y., 1962. 2. A.M. G l e a s o n , F i n d i n g t h e Maximum o f a C o n t i n u o u s F u n c t i o n , P r o c e e d i n g s o f a H a r v a r d Symposium o f D i g i t a l C o m p u t e r s and t h e i r a p p l i c a t i o n s , 3-6 A p r i l 1 9 6 1, H a r v a r d U n i v e r s i t y P r e s s , C a m b r i d g e , M a s s a c h u s e t t s , 1962, pp. 198-202. 3. 0 G r o s s and-S. J o h n s o n , S e q u e n t i a l m i n i m a x s e a r c h f o r a z e r o o f a c o n v e x f u n c t i o n , M a t h e m a t i c a l T a b l e s and o t h e r A i d s t o C o m p u t a t i o n , Volume 13, 1959, pp. 4 4 - 5 1 . 4. T. H i l d e b r a n d t , I n t r o d u c t i o n t o t h e T h e o r y o f I n t e g r a t i o n , A c a d e m i c P r e s s , New Y o r k , 1963. 5. J . K i e f e r , S e q u e n t i a l M i n i m a x S e a r c h f o r a Maximum, P r o c e e d i n g s o f t h e A m e r i c a n M a t h e m a t i c a l S o c i e t y , Volume 4, 1953, pp. 502-506. O p t i m a l S e q u e n t i a l S e a r c h and A p p r o x i m a t i o n M e thods u n d e r Minimum R e g u l a r i t y A s s u m p t i o n s , J o u r n a l o f t h e S o c i e t y o f I n d u s t r i a l and A p p l i e d M a t h e m a t i c s , Volume 5, 1957, pp. 105-136. 7. R.S, P i n k h a m , Random R o o t L o c a t i o n , J o u r n a l o f t h e S o c i e t y f o r I n d u s t r i a l and A p p l i e d M a t h e m a t i c s , Volume 12, No. 4, December 1964, pp. 855-864. 8. H. R o b b i n s and S. Monro, A S t o c h a s t i c A p p r o x i m a t i o n M e t h o d , A n n a l s o f M a t h e m a t i c a l S t a t i s t i c s , Volume 22, 1951, pp. 400-407. . B. v a n d e r Waorden, Modern A l g e b r a , R e v i s e d E n g l i s h E d i t i o n , T r a n s l a t i o n by F. Blum, Volume 1, U n g a r , New Y o r k , 1953. 1 0 , I.M. Yafflo^n and V. B o l t y a n s k i i , Convex F i g u r e s , ' E n g l i s h T r a n s -l a t i o n by P . J . K e l l e y and L.F. W a l t o n , H o l t R i n e h a r t and W i n s t o n , New Y o r k , 1961. 

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080573/manifest

Comment

Related Items