Interval of uncertainty

Apply a sequential one-dimensional search technique to reduce the interval of uncertainty for the maximum of the function/ = 6.64 + 1.2 - x2 from [0,1] to less than 2 percent of its original size. Show all the iterations. 

While the number of independent variables is arbitrary in our definitions, it makes a tremendous difference in computations. Simultaneous solution of n equations and minimization in n dimensions are much more difficult than in one dimension. The main difference between one and several dimensions is that in one dimension it is possible to "bracket" a root or a local minimum point between some bracketing values, and then to tighten the interval of uncertainty. This gives rise to special algorithms, and hence the solution of a single equation and minimization in one variable will be discussed separately from the multidimensional methods. 

Thus the sequential dichotomous search is considerably more powerful than the preplanned uniform dichotomous search, the advantage growing exponentially with the number of experiments. To reduce the interval of uncertainty to 1% of the original would require 200 preplanned dichotomous experiments. The same job could be done with only 14 sequential dichotomous experiments. 

Consider the placement x-) and x2 of the first two experiments in the original interval 70. 70 may also be written as 7i because a single experiment cannot reduce the interval of uncertainty. Let the two ends of the interval be denoted by ai and hi. Define the distance A2 by... 

Since A2 is never more than half the length of the original interval, either (oi, ai + A2) or (61 — a2, hi) will be eliminated by examining the results y(xi) and y(x2). Hence I2, the interval of uncertainty after two trials, will be shorter than 7i by the amount A2. Thus... 

As before, the interval of uncertainty remaining after the third experiment is... 

The last cycle of the method will be a dichotomous search, which we know is minimax for two experiments. Keifer (Kl) and Johnson (J2) show that the Fibonacci search is in fact minimax among all sequential techniques. In order to reduce the interval of uncertainty to less than 1% it only takes 11 Fibonacci experiments, three less than for a sequential dichotomous search. The advantage increases with the number of experiments. 

Let aj < bj < Cj < dj, where [a, is the interval of uncertainty at iteration k and assume that [<3i, di] = [a, d. Since functional evaluations are the most expensive step in the process, the golden section method reduces the amount of overall work by intelligently choosing symmetric points bj and Cj so that they can be reused on successive iterations, as illustrated in Figure 8. This is achieved by using the relationships b = Xa + (1 - X)d and = (1 - A)% + Xdj where A = 0.618. Observe that b and are simply expressed as convex combinations of % and idj A summary of the golden section algorithm follows ... 

The interval [tA,ts], in which function continuity and opposite signs at the boundaries are both present, is called the interval of uncertainty. 

Neither the interval of uncertainty nor the function monotonicity is known. The function may have several solutions with the objective being to find all of them. Alternatively, it may have some discontinuities or may be zero in several points without changing the sign locally. 

When the interval of uncertainty [Ia, ts] for a function y t) is known or the function is monotone, special algorithms can be used to guarantee the following appealing features ... 

From (1.26), it is possible either to evaluate a priori the interval of uncertainty after a predetermined amount n of iterations or, given the final interval, to know a priori the number of iterations required to reach it. 

In the case of a single processor, Bolzano s method minimizes the maximum interval of uncertainty. 

If several processors are available simultaneously, Bolzano s method can be generalized the function should be simultaneously evaluated in an evenly spaced number of points equal to the number of available processors and within the interval of uncertainty. 

One can use an iterative procedure without controlling the interval of uncertainty. 

If the interval of uncertainty [t, ts], where the function assumes opposite signs at the boundaries, is known, the intervals that follow will retain this property. 

The first strategy is the only one of any use when the interval of uncertainty is unknown. If the function is monotone, it is always possible to find an interval of uncertainty and, consequently, to use ad hoc techniques to find its root Algorithms for function root-finding with a known interval of uncertainty are discussed below, whereas the other situation is considered in Section 1.6. 

Convergence is not guaranteed also if the function is monotone or if we know the interval of uncertainty (unless opportune modifications are adopted in the latter case). 

The regula falsi algorithm is very similar to the previous one. The difference is in the support points adopted to linearize the function the last two values at each iteration are used in the secant method, whereas the boundaries of the interval of uncertainty are adopted in the regula falsi method. 

The advantage this has over the previous criteria is that the new iteration falls within the interval of uncertainty and thus method convergence is ensured. 

This algorithm too is important only from an educational point of view, as it is the simplest algorithm in this family, ensuring convergence when the interval of uncertainty is known. 

The efficiency of the regula falsi method can be improved by using the two best values from the previous iterations rather than the boundary values for the linear approximation. This device is implemented by checking the interval of uncertainty. 

Use of a Multiprocessor Machine with a Known Interval of Uncertainty... 

If an interval of uncertainty is known and some processors are available to find the root, Bolzano s method can effectively be coupled with a function approximation method. 

Suppose we have np available processors. The first one is used to calculate the function in the point selected by the efficient method being used, whereas the remaining np — 1 processors evaluate the function in the points opportunely placed in the two new subintervals, created by the splitting of the interval of uncertainty. 

The search for an interval of uncertainty is very simple if it is known a priori that the function is monotone. Specific techniques for the most general case are explained in Chapter 6. 

When the interval of uncertainty is identified, a dedicated algorithm capable of exploiting it can be adopted. 

Suppose we have rip available processors it is useful to place np points at a distance that gradually increases up to the detection of a proper interval of uncertainty. 

This test must be used only in programs that do not guarantee the solution will be kept within the interval of uncertainty. However, other very reliable tests will be covered later. 

In the special case of a knovm interval of uncertainty, there is a test that provides a maximum guarantee of reliability. If the algorithm checks the interval of uncertainty [Ia, h] and the best point between (a and ts is selected as the solution, the error on the solution is... 

This is the criterion that ensures maximum reliability in deeming the accuracy of the solution achieved, when the interval of uncertainty is given. 

The BzzFunctionRoot class is designed to search for the root of a function when an interval of uncertainty is given and when the user wants to find one solution vfithin that interval. 

The first is the default one and no data are needed. The second requires the boundaries and ts of the interval of uncertainty. 

Value of t at the left boundary of the interval of uncertainty TLef t (). 

---