Solving one Real Equation via Bisection

Matlab provides many means with which to solve equations. The diary demonstrates the use of the polynomial root finder, roots, and the symbolic solver, solve. In response to your question, "Hey man, how do these solvers solve?" we shall devote the rest of the semester to writing Matlab solvers of increasing complexity and hence applicability.

For real scalar equations with real solutions there is a simple divide-and-conquer algorithm that is fun to visualize and easy to code. Let us take, for example, the function 

     f(x) = x5+x2-2

and attempt to solve f(x)=0. We start by judicious snooping and note that f(0)f(3/2) < 0 and so f(0) and f(3/2) have opposite sign and so the Intermediate Value Theorem permits us to conclude that a solution lies in between 0 and 3/2. To bisect now means to check the sign of f(0)f(3/4) and to restrict attention to the interval [0,3/4] if negative or to [3/4,3/2] if positive or to stop if f(3/4) is small enough. This process is repeated until the value of f is indeed small enough. Here are the main steps. We suppose we have a Matlab function that evaluates f(x) for a given x. We also suppose the user has provided us with an interval of interest, [a,b] and a tolerance tol. Our job is to find an x in [a,b] for which |f(x)|< tol. 

   1. If f(a)f(b)>0 inform the user that a solution may not exist
      in [a,b] and exit.

   2. Set x=(a+b)/2. While |f(x)|>tol do

   3. If f(a)f(x)<0 set b=x else set a=x. Go to step 2.

In order to code this you shall build a function that (i) accepts the arguments, a, b, and tol, then (ii) executes steps 1-3 above and finally (iii) returns the answer.

In order to get you off on the right foot let me provide the following skeleton and a diary of its use 

>> x=biskel(0,.5,1)
Sorry, but I can not be sure your fun changes sign on [a,b]

x = NaN

>> biskel(0,1.5,1)

x = 0.7500

I have left it for you to code steps 2 and 3. There are a number of ways to do it. I suggest a while loop that encloses an if clause.