The Bisection Method

<BODY LANG="EN"> <HR><center> <table border=1> <td><A NAME="tex2html20" HREF="uces-7.html"><img height=36 width=36 alt="PREVIOUS" src="http://www.cs.utah.edu/icons/latex2html/previous.gif"></A></td> <td><A NAME="tex2html26" HREF="uces-7.html"><img height=36 width=36 alt="UP" src="http://www.cs.utah.edu/icons/latex2html/up.gif"></A></td> <td><A NAME="tex2html28" HREF="node2.html"><img height=36 width=36 alt="NEXT" src="http://www.cs.utah.edu/icons/latex2html/next.gif"></A></td> <td><a href="contents-node1.html"><img height=36 width=36 alt="CONTENTS" src="http://www.cs.utah.edu/icons/latex2html/toc.gif"></a></td> <td><a href="reset.hamlet"><img height=36 width=36 alt="RESET" src="http://www.cs.utah.edu/icons/latex2html/stop.gif"></a></td> <td><a href="copyright.html"><img height=36 width=36 alt="COPYRIGHT" src="http://www.cs.utah.edu/icons/latex2html/copyright.gif"></a></td> <td><a href="mailto:hamlet@cs.utah.edu"><img height=36 width=36 alt="FEEDBACK" src="http://www.cs.utah.edu/icons/latex2html/feedback.gif"></a></td> <td><a href="http://www.cs.utah.edu/%7Ehamlet/icons.html"><img height=36 width=36 alt="ABOUT" src="http://www.cs.utah.edu/icons/latex2html/about.gif"></a></td> </table> </center> <HR><H1><A NAME="SECTION00010000000000000000">The Bisection Method</A></H1> <P> <A NAME="bisection"> </A> Suppose that we have a function <I>f</I> of one argument and we want to find a real number <I>x</I> such that <I>f</I>(<I>x</I>) = 0. As you know, there can be zero or more solutions to an equation of this form. We are interested in finding one of them. <P> The bisection method works by assuming that we know of two values <I>h</I> and <I>l</I> such that <I>f</I>(<I>h</I>) > 0 and <I>f</I>(<I>l</I>) < 0. If this is the case (and the function <I>f</I> is continuous), then there must be at least one value <I>v</I> that falls between <I>h</I> and <I>l</I> such that <I>f</I>(<I>v</I>) = 0. <P> This fact is best appreciated graphically. Suppose that we want to find a root of the function <P> <table><td valign=top><a href="send2.hamlet"><img height=24 width=24 alt="EXECUTE" src="http://www.cs.utah.edu/icons/latex2html/execute.gif"></a></td><td valign=top><code>f := x -> cos(x) - x;</code></td></table> <P> It is easy to verify that <I>f</I>(0) is positive whereas <I>f</I>(1) is negative. If we plot <I>f</I> between these two points <P> <table><td valign=top><a href="send3.hamlet"><img height=24 width=24 alt="EXECUTE" src="http://www.cs.utah.edu/icons/latex2html/execute.gif"></a></td><td valign=top><code>plot(f(x), x=0..1);</code></td></table> <P> we see that since the plot crosses the x-axis, there <EM>must</EM> be a root between 0 and 1. <P> The bisection method works by repeatedly narrowing the gap between <I>h</I> and <I>l</I> until it closes in on the correct answer. It narrows the gap by taking the average <I>v</I> of <I>h</I> and <I>l</I>. If <I>f</I>(<I>v</I>) is positive, then <I>v</I> becomes the new value of <I>h</I>. If <I>f</I>(<I>v</I>) is negative, then <I>v</I> becomes the new value of <I>l</I>. In either event, we still have the root bracketed by <I>h</I> and <I>l</I>. If we repeat this process long enough, we'll eventually converge down to a good approximation to that root. <P> Let's look at a couple of repetitions through this algorithm. The average of 0 and 1 is 0.5, and <I>f</I>(0.5) is positive. Thus, our new value for <I>h</I> is 0.5, and our value for <I>l</I> remains 1.0. Let's plot this: <P> <table><td valign=top><a href="send4.hamlet"><img height=24 width=24 alt="EXECUTE" src="http://www.cs.utah.edu/icons/latex2html/execute.gif"></a></td><td valign=top><code>plot(f(x), x=0.5..1);</code></td></table> <P> Notice that the scale of the x-axis is half what it was before. We're narrowing in on an answer. <P> The average of 0.5 and 1 is 0.75, and <I>f</I>(0.75) is negative. Thus, our new value for <I>l</I> is 0.75 and our value for <I>h</I> remains 0.5. Let's plot this: <P> <table><td valign=top><a href="send5.hamlet"><img height=24 width=24 alt="EXECUTE" src="http://www.cs.utah.edu/icons/latex2html/execute.gif"></a></td><td valign=top><code>plot(f(x), x=0.5..0.75);</code></td></table> <P> We can continue this process until our root is close enough. <P> <HR><center> <table border=1> <td><A NAME="tex2html20" HREF="uces-7.html"><img height=36 width=36 alt="PREVIOUS" src="http://www.cs.utah.edu/icons/latex2html/previous.gif"></A></td> <td><A NAME="tex2html26" HREF="uces-7.html"><img height=36 width=36 alt="UP" src="http://www.cs.utah.edu/icons/latex2html/up.gif"></A></td> <td><A NAME="tex2html28" HREF="node2.html"><img height=36 width=36 alt="NEXT" src="http://www.cs.utah.edu/icons/latex2html/next.gif"></A></td> <td><a href="contents-node1.html"><img height=36 width=36 alt="CONTENTS" src="http://www.cs.utah.edu/icons/latex2html/toc.gif"></a></td> <td><a href="reset.hamlet"><img height=36 width=36 alt="RESET" src="http://www.cs.utah.edu/icons/latex2html/stop.gif"></a></td> <td><a href="copyright.html"><img height=36 width=36 alt="COPYRIGHT" src="http://www.cs.utah.edu/icons/latex2html/copyright.gif"></a></td> <td><a href="mailto:hamlet@cs.utah.edu"><img height=36 width=36 alt="FEEDBACK" src="http://www.cs.utah.edu/icons/latex2html/feedback.gif"></a></td> <td><a href="http://www.cs.utah.edu/%7Ehamlet/icons.html"><img height=36 width=36 alt="ABOUT" src="http://www.cs.utah.edu/icons/latex2html/about.gif"></a></td> </table> </center> <HR><P><ADDRESS> <I><A NAME="tex2html1" HREF="http://www.cs.utah.edu/~zachary">Joseph L. Zachary</A> <BR> <A NAME="tex2html2" HREF="http://www.cs.utah.edu/~hamlet">Hamlet Project</A> <BR> <A NAME="tex2html3" HREF="http://www.cs.utah.edu/">Department of Computer Science</A> <BR> <A NAME="tex2html4" HREF="http://www.utah.edu/ HTML_Docs/UofUHome.html">University of Utah</A></I> </ADDRESS> </BODY>