A summer program and resource for middle school students
showing high promise in mathematics

Useful Computational Methods

The Bisection Method
- Finding roots by binary search -

Unlike the guess-and-check method, we start with two initial values - one value a below √Q and another value b above √Q, where Q is a positive real number. Since a is a low value, let us denote it by L. Similarly, denote b by H. Let m = (L+H)/2.
If m2 < Q, let L = m.
If m2 > Q, let H = m.
Let us find √5. So Q = 5.
since 22 < 5 < 32, let L = 2, H = 3.

L H m m2
2 3 2.5 >5
2 2.5 2.25 >5
2 2.25 2.125 <5
2.125 2.25 2.1875 <5
2.1875 2.25 2.21875 <5
2.21875 2.25 2.234375 <5
2.234375 2.25 2.2421875 >5
2.234375 2.2421875 2.2382812 >5
2.234375 2.2382812 2.2363281 >5
2.234375 2.2363281 2.2353515 <5
2.2353515 2.2363281 ... ...

This binary search method can be used not only to find the square-root of a positive number, but also for finding the zeros of any "continuous" function f. You enounter the precise definition of a conitnuous function in introductory calculus courses. For our purpose, it is sufficient to say that if r is the root of a continuous function, there exists an interval [a,b] containing r so that the graph of the function crosses at r on the x-axis in this interval. Let L = a, H = b, and m = (L + H)/2.
If f(m).f(L) < 0, let H = m.
If f(m).f(H) < 0, let L = m.
The first case says that f(m) and f(L) have opposite signs. Since f(L) < 0, it should be that f(m) > 0. So the graph crosses the x-axis between L and m. So we choose H now to be m. The second case should now be clear. Notice that it is not possible for both f(m).f(L) and f(m).f(H) to have the same sign since the choice of L and H are such that f(L) < 0 whereas f(H) > 0.

What function should we use to find the square-root of 5? It is f(x) = x2 - 5. The positive root of the function is √5.

The proof that the binary search method works is provided by Bolzano's Bisection Theorem. Denote the n-th midpoint by mn. Then the n-th interval contains mn as well as r. By the Nested Interval Property of Real Numbers the sequence of Nested Intervals converge to a unique point, which should therefore be r. You can verify that the n-th interval satisfies êr - mn ê ≤ (b - a)/2n, with the first midpoint corresponding to n = 1. This also points out a merit of the method, as opposed to guess-and-check. That is, we can estimate the accuracy of the computed solution. For instance, the table above has obtained ten successive values for m. The inequality says that the tenth value must be such that ê√5 - m10 ê ≤ (3 - 2)/210 @ 10-3. That is, the error in the tenth iterate is atmost 10-3. While this is a merit, we also note that even after ten iterations, we are only guaranteed an accuracy of two decimal places - the error being in the third or later decimal places. You may wish to do the algebra to prove that the number N of bisections needed to guarantee that the N-th midpoint mN approximates r with an error less than a given positive value D is N = ë(ln(b-a) - lnD)/ln2û, where the brackets denote the Floor function.

Why the binary search method is efficient
We could instead obtain estimates of the roots of any function by a brute force method. That is to scan the entire domain of the function by small increments and observe the steps in which a change of sign in the function f(x) occurs. This signals that the function f crosses the x-axis within the particular step. But this is a time-consuming procedure for functions whose roots lie in a large region of search. The binary search method divides the interval of search by 2 and retains that half of the search interval in which the change of sign will occur. A second merit of the binary search is that When the range of search has been narrowed down sufficiently, a more accurate search technique could be applied within that step in order to refine the value of the root.

A more efficient method based on the tangential descent of the function (Newton-Raphson method) is described elsewhere.

The Speed of convergence
We found that the binary search method of finding square roots is an efficient method. But there are other efficient methods. To compare the relative efficiency of a method, we ask how fast the method gives us close enough approximations to the root. The criteria used are the speed of convergence, which we now discuss, and the computational efficiency. The speed of convergence is given by the size of the error at the (n+1)-th step as compared to that at the n-th step, for sufficiently large n. "Sufficiently large n" means that there there exists an integer N such that from N onwards the error behaves as specified. The error at the n-th step, denoted by en, is defined as ï√Q - mnï, where mn is the approximation to √Q, at the n-th step. Then the speed of convergence is defined in terms of a positive real number k so that en+1/(en)k = A, where A is a constant. In other words, en+1 is proportional to enk. Subsituting the value of mn+1 in terms of mn, we get en+1/(en) @ 1/2. So k = 1 and A = 1/2. Thus, the error of the approximation halves with each succeeding step.

>>  The Babylonian Algorithm




Send suggestions to webmaster@mathpath.org
Copyright © 2001-   MathPath
Last updated - February 20, 2004