Skip to the content of the web site.

8 Bracketing

The most simplistic numerical techniques are based on bracketing the problem. If we have a function of one variable, if we can determine that a solution to our problem lies on a particular interval [a, b], it seems reasonable that if we can select a point on that interval, say c, then if we can determine whether or not the solution lies in [a, c] or [c, b], then we have restricted the domain on which we know the solution lies. In that case, we can try again: shrink the new interval and get a tighter bound on the solution.

Example

Humans use bracketing quite often. Consider a search through a dictionary. It is known that the first page of the standard English dictionary contains words starting with A, and the last contains words starting with Z. Any word you are looking for is bounded by these two points. By opening the dictionary at a page, it is easy to determine whether or not the word you are looking for lies before, on, or after that page. In this case, you have shrunk the number of pages you are searching: assuming we have not found the page containing the word, we are assured that the word lies either before or after the page we are currently inspecting. Next, we repeat this process on that portion of the dictionary in which the word is known to lie.

This may seem to be a very fast algorithm (for those who have studies run-times, you will know that such an algorithm is O(log(n))), however, unfortunately, it is an exceptionally slow numerical technique, as we will see.

Problems

Bracketing does not work very well in higher dimensions. For example, a system of n equations and n unknowns requires 2n points. However, it is very useful, still, when it is known that the function is exceptionally wild, that is, it is a low-dimensional problem, but it is known that the derivative and second-derivatives are very large on the interval of interest. In this case, using either interpolation or Taylor series will almost certainly result in non-convergent iterations.

Question

What properties of a dictionary or phone book do you use to speed up a bracketing search?