11.6 Case Study 2: Bisection Root Finder

There are many problems in which you need to find the root of an equation. For example, you need to find x such that f(x)=0 when x is in some interval (say, [a,b] where f(a)<0<f(b) or f(a)>0>f(b). The following example solves √3 by finding the root of f(x)=x-√3. (This example is used by my colleague, Bob Noble, to illustrate SAS/IML coding in his class. It is included in this section.) The lower limit lo and upper limit hi are specified to be 0 and 3, respectively. The bisection method finds the midpoint of the current interval, mid=(lo+hi)/2, and checks to determine whether mid-√3>0, or, equivalently, whether mid²>3. If it is, then the guess for the solution, mid, is too high. Thus, hi is set to mid, and the process begins again. If it is not, then lo is set to mid, and the process begins again. (Admitted, this is a lot of work to find a value that is one keystroke on a calculator. However, this gives you the flavor of the example and demonstrates the flexibility of SAS/IML.) This code saves a matrix with the history of (lo, hi) intervals checked. The code executes until the interval is sufficiently narrow. A convergence criterion of hi-lo<10-⁷ is set. The SAS/IML code in Display 11.10 generates a data set process containing the (lo, hi) pairs (the iteration history), which is then printed and plotted.

Display 11.10. Using the method of bisection to estimate √3